Multiple Choice Fragen

1

Dijkstras Algorithmus folgt dem Entwurfsprinzip "Divide and Conquer".

1

Ein Fibunacci-Heap mit n Knoten hat maximale Höhe O(log n)?

1

Optimale Suchbäume lassen sich in quadratischer Zeit berechnen.

1

Der Median einer Menge ganzer Zahlen kann gleich ihrem
Maximum sein.

1

Bubblesort benötigt auf allen Eingaben mehr Vergleiche als
Heapsort.

1

Verwendet man Fibonacci-Heaps zur Implementierung von
Heapsort, so erreicht man eine Worst-Case-Laufzeit von
O(n log log n).

1

Der in der Vorlesung behandelte Algorithmus von Stoer und Wagner berechnet einen minimalen Schnitt eines Graphen.

1

Quickselect benötigt im Durchschnitt nicht mehr als 4n Vergleiche auf einem Feld mit n Elementen.

1

Ein Fibunacci-Heap mit n Knoten kann eine Höhe von n erreichen.

1

Verwendet man Fibunacci-Heaps zur Implementierung von Dijkstras Algorithmus zur Berechnung kürzester Wege, so ist die Laufzeit in O (|E|+|V|log|V|) für einen Graphen G = (V,E,Lamda)

1

Prims Algorithmus zur Berechnung eines minimalen Spannbaumes folgt dem Entwurfsprinzip "Union-Find"

1

Bubblesort benötigt auf allen Eingaben mehr Vergleiche als Heapsort.

1

Der Algorithmus von Schönhage und Strassen zur schnellen Multiplikation ganzer Zahlen verwendet die schnelle Fouriertransformation.

1

Quickselect benötigt im Mittel mehr als 15n Vergleiche.

1

Es ist kein Algorithmus zur Berechnung optimaler Suchbäume in subkubischer Zeit bekannt.

1

Mergesort benötigt durchschnittlich Theta von (n log n)

1

Wie lautet die Laufzeit von Kruskal?

1

Quickselect benötigt O(n²) wenn...

1

Die Formel, welche das Dynamische Programm zur Berechnung der optimalen Anzahl an Multiplikationen zur Multiplikation mehrerer Matrizen anwendet lautet:

1

Die zentrale Operation von Prim ist Union-Find?

1

Eine Hashfamilie heißt universell, wenn gilt:

1

Damit die Wahrscheinlichkeit , dass eine Hashfunktion h injektiv ist, größer gleich 1/2 ist, muss folgendes gegeben sein:

1

Warshalls Algorithmus berechnet im Gegensatz zu Floyds Algorithmus:

1

Bei welcher Operation werden bei Fibonacci-Heaps größere Bäume (ausgehend von deren Wurzel) unter die Wurzel des kleineren gehangen?

1

Dynamische Programme liegen in der Komplexitätsklasse

1

Bei Fibonacci-Heaps haben Merge, Insert, delete_min sowie decrease_key die Laufzeit:

1

Im Vergleich zur naiven Multiplikation von O(n³) benötigt die Matrizenmultiplikation von Volker Strassen:

1

Wie viele Übergangskanten hat der Endliche Automat des KMP Algorithmus

1

Die Grundform des Mastertheorem 1 ist:

1

Verwendet man Fibonacci-Heaps zur Implementierung von
Heapsort, so erreicht man eine Worst-Case-Laufzeit von
O(elog n+ nlog n).

1

Der in der Vorlesung behandelte Algorithmus von Stoer und Wagner
berechnet einen minimalen Schnitt eines Graphen.

1

Der CYK-Algorithmus läuft in:

1

Welcher dieser Kuchenschneidalgorithmen ist nicht neidfrei?

1

Welche dieser Aussagen über den Stör-Wagner-Algorithmus ist zutreffend?

1

Diese Frage bezieht sich auf Fibonacci Heaps:
Verliert ein Knoten mehr als ein Kind, dann...

1

Kruskal hat eine Laufzeit von:

1

Das Rucksackproblem lässt sich durch Branch and Bound in:

1

Valiants Algorithmus läuft in:

1

Warshalls Algorithmus läuft im Gegensatz zu Floyds Algorithmus in:

1

Was ist die Abbruchbedingung für den Äquivalenztest Endlicher Automaten?

1

Negative Kanten sind bei Dijkstra nicht erlaubt?

1

Bottom-up Heapsort benötigt im Vergleich zu Standardheapsort nur:

1

Die Laufzeit des Äquivalenztests endlicher Automaten beträgt O(n2)

1

Sei M eine Menge reeler Zahlen mit 3 <=|M| < unendlich. Der Median von M kann gleich dem
Minimum von M sein.

1

Der Algorithmus von Matiyasevich, Knuth, Morris und Pratt testet endliche Automaten auf Aquivalenz.

1

Welche Laufzeit hat der Karger-Stein Algorithmus?

1

Bei Heapsort werden immer mehr als die Halfte der Vergleiche waehrend des Heapaufbaus ausgefuhrt.

1

Der in der Vorlesung behandelte Algorithmus von Karger und Stein zur Berechnung eines minimalen Schnitts liefert immer ein korrektes Ergebnis.

1

Bei Union-Find mit Pfadverkürzung sind die Kosten O(n*inverseAckermannfkt(n))?

1

Angenommen Alice beabsichtigt, an Bob über Oskar ein unterschriebenes Dokument
(x, h(x)) zu senden, der jedoch (y, s) mit x ungleich y weitergibt. Oskar wählt die
”Unterschrift” s ∈ Fp bzgl. irgendeiner selbstgewählten Strategie. Dann ist die Wahrscheinlichkeit= 1/p², dass Bob von der Sache Wind bekommt

Fragen eines Algorithmikmoduls auf Masterniveau

Multiple Choice Fragen

Dijkstras Algorithmus folgt dem Entwurfsprinzip "Divide and Conquer".

Ein Fibunacci-Heap mit n Knoten hat maximale Höhe O(log n)?

Optimale Suchbäume lassen sich in quadratischer Zeit berechnen.

Der Median einer Menge ganzer Zahlen kann gleich ihrem Maximum sein.

Bubblesort benötigt auf allen Eingaben mehr Vergleiche als Heapsort.

Verwendet man Fibonacci-Heaps zur Implementierung von Heapsort, so erreicht man eine Worst-Case-Laufzeit von O(n log log n).

Der in der Vorlesung behandelte Algorithmus von Stoer und Wagner berechnet einen minimalen Schnitt eines Graphen.

Quickselect benötigt im Durchschnitt nicht mehr als 4n Vergleiche auf einem Feld mit n Elementen.

Ein Fibunacci-Heap mit n Knoten kann eine Höhe von n erreichen.

Verwendet man Fibunacci-Heaps zur Implementierung von Dijkstras Algorithmus zur Berechnung kürzester Wege, so ist die Laufzeit in O (|E|+|V|log|V|) für einen Graphen G = (V,E,Lamda)

Prims Algorithmus zur Berechnung eines minimalen Spannbaumes folgt dem Entwurfsprinzip "Union-Find"

Bubblesort benötigt auf allen Eingaben mehr Vergleiche als Heapsort.

Der Algorithmus von Schönhage und Strassen zur schnellen Multiplikation ganzer Zahlen verwendet die schnelle Fouriertransformation.

Quickselect benötigt im Mittel mehr als 15n Vergleiche.

Es ist kein Algorithmus zur Berechnung optimaler Suchbäume in subkubischer Zeit bekannt.

Mergesort benötigt durchschnittlich Theta von (n log n)

Wie lautet die Laufzeit von Kruskal?

Quickselect benötigt O(n²) wenn...

Die Formel, welche das Dynamische Programm zur Berechnung der optimalen Anzahl an Multiplikationen zur Multiplikation mehrerer Matrizen anwendet lautet:

Die zentrale Operation von Prim ist Union-Find?

Der Median einer Menge ganzer Zahlen kann gleich ihrem
Maximum sein.

Bubblesort benötigt auf allen Eingaben mehr Vergleiche als
Heapsort.

Verwendet man Fibonacci-Heaps zur Implementierung von
Heapsort, so erreicht man eine Worst-Case-Laufzeit von
O(n log log n).

Verwendet man Fibonacci-Heaps zur Implementierung von
Heapsort, so erreicht man eine Worst-Case-Laufzeit von
O(elog n+ nlog n).

Der in der Vorlesung behandelte Algorithmus von Stoer und Wagner
berechnet einen minimalen Schnitt eines Graphen.

Diese Frage bezieht sich auf Fibonacci Heaps:
Verliert ein Knoten mehr als ein Kind, dann...