Arbeitsblatt Algorithmen & Komplexität mit Lösungen

Was bedeutet f(n) = Θ(g(n))?

1. Af wächst echt schneller als g
2. Bf ist für jedes n immer kleiner als g, also beschränkt g es nach oben, aber nie nach unten
3. Cf wächst gleich schnell wie g, nach oben und unten durch konstante Vielfache von g beschränkt
4. Df wächst echt langsamer als g

Welche Zeitkomplexität hat Mergesort im Worst Case?

1. AO(n)
2. BO(n²)
3. CO(log n)
4. DO(n log n)

Ein O(n²)-Algorithmus braucht für n = 1000 eine Sekunde. Wie lange braucht er etwa für n = 2000?

1. A8 Sekunden
2. B1 Sekunde
3. C2 Sekunden
4. D4 Sekunden

Welche Zeitkomplexität hat: for i = 1 to n: for j = 1 to i: O(1)-Arbeit?

1. AO(n log n)
2. BO(n³)
3. CO(n²)
4. DO(n)

Welche Greedy-Regel liefert beim Aktivitätsauswahlproblem immer eine maximale Anzahl sich nicht überschneidender Aktivitäten?

1. ADie Aktivität wählen, die am frühesten beginnt
2. BDie Aktivität wählen, die am frühesten endet, dann mit den verträglichen wiederholen
3. CZuerst die kürzeste Aktivität wählen
4. DZuerst die Aktivität mit den wenigsten Überschneidungen wählen, dann mit den verträglichen wiederholen

Wie viele Vergleiche braucht die binäre Suche im Worst Case ungefähr bei einem sortierten Array mit 1,000,000 Elementen?

1. AEtwa 500,000
2. BEtwa 1,000
3. CEtwa 20
4. DEtwa 100

Welches dieser Erfüllbarkeitsprobleme ist bekanntermaßen in polynomieller Zeit lösbar?

1. AAllgemeines SAT für Formeln in konjunktiver Normalform
2. BSchaltkreis-Erfüllbarkeit
3. C3-SAT, bei dem jede Klausel genau drei Literale hat
4. D2-SAT, bei dem jede Klausel höchstens zwei Literale hat

Welche Definition der Klasse NP ist richtig?

1. AProbleme, die kein Algorithmus lösen kann
2. BProbleme, die nicht polynomiell sind
3. CProbleme, die nicht in polynomieller Zeit gelöst werden können
4. DEntscheidungsprobleme, deren Ja-Antworten mithilfe eines Zertifikats in polynomieller Zeit überprüft werden können