Prüfungsprotokolle lesen
Protokolle (1 gefunden)
| Nr. | Prüfer | Fach |
| 1032 | Meyerhenke, Hennig, Prof. Dr. | Algorithmen und Datenstrukturen |
Protokoll
= Datum der Prüfung: 31.07.2024 = Benötigte Lernzeit als Empfehlung = Verwendete Materialien: Folien, Internet, Probeklausuren Aufgabe 1 O-Notation und Mastertheorem 1.1 4 Paare von Funktionen f und g. Es war anzukreuzen, ob f Omega(g) oder g Omega(f)? (Bin mir nicht sicher ob es Omega oder O war) 1.2 Zeige am Entscheidungsgraph, warum es keinen allgemeinen Sortieralgorithmus geben kann, der schneller als Omega(n!) ist 1.3 Irgendwas mit Beweise, dass log(n!) element Omega(n log n) 1.5? Wende das Mastertheorem an und gib jeweils eine Funktion g(n) an, so dass T(n) in Θ(g) ist. (Das Mastertheorem mit den drei Fällen war gegeben.): T(n) = 16T(n/4) + n^2 + 3n T(n) = 81T(n/3) + n^(7/2) Aufgabe 2 Sortieren k-MergeSort Algorithmus war als Pseudocode mit kurzer Erklärung gegeben: Im Prinzip teilen wir bei MergeSort solange, bis die Teile kleiner als k sind. Die Teile dann mit BubbleSort sortieren und dann wie bei MergeSort zusammenfügen. 2.1 Schreibtischtest für 4-MergeSort ausführen auf einer gegebenen Instanz von 13? Elementen. 2.2 Eine Best-Case und eine Worst-Case Instanz für 4-MergeSort angeben. 2.3 Wahr oder Falsch? Mit Begründung bzw. Sortierverfahren Lässt sich Array A der Länge 3n in O(n) sortieren, wenn man folgende Eigenschaft des Arrays kennt: Das Array besteht aus sortierten Tripeln. Z.B. [3, 9, 34, 5, 12, 19, 1, 4, 7] Das erste, mittlere und letzte Drittel des Arrays sind für sich sortiert, z. B. [5, 12, 30, 52, 2, 6, 13, 20, 1, 7, 15, 42] Aufgabe 3 Datenstruktur Es soll eine Datenstruktur gefunden werden, die kompakte Intervalle speichert. Jedes Intervall enthält dabei die 0. Die Operation query(x) soll alle Intervalle ausgeben, in denen x enthalten ist und zwar in O(k). k ist dabei die Anzahl an Intervallen, in denen x vorkommt. 3.1 Eine solche Datenstruktur beschreiben. (Vorprozessierung darf beliebig lang dauern) 3.2 Begründen warum bei der Datenstruktur aus 3.1 query() in O(k) läuft. Aufgabe 4 Heaps 4.1 Erstelle einen Heap mit dem Bottom-Up-Sift-Down Verfahren, bei dem alle Elemente gleichzeitig eingefügt werden. (Der Start in Heap-Form war gegeben und man sollte den „Heap“ nach jeder Swap-Operation aufschreiben. Die Grundstruktur war schon gegeben, man musste nur die Label eintragen.) 4.2 Schreibtischtest der deleteMin() Operation auf einem gegebenen Heap 4.4? Laufzeit von Dijkstra unter Verwendung eines Binären Heaps bzw. eines Fibonacci Heaps als Prioritätswarteschlange. Aufgabe 5 Graphen 5.1 Führe den Dijkstra-Algorithmus auf dem gegebenen Graphen aus. (Schreibtischtesttabelle wie in der Übung mit Angabe der Prioritätswarteschlange) 5.4? Finde einen Algorithmus der in O(|V| + |E|) Laufzeit und mit O(n) Speicher herausfindet, ob ein gegebener Graph bipartit werden kann. 5.6? a) Wie lautet die Schnitteigenschaft eines minimalen Spannbaums? b) Wie lautet die Kreiseigenschaft eines minimalen Spannbaums? Aufgabe 6? Hashing 6.1 Führe die folgenden insert() und delete() Operationen aus. Dabei soll lineares Sondieren benutzt werden. Eine Tabelle für die einzelnen Schritte und den Array Indizes war angegeben. Funktion war glaube einfach f(n) = n mod 13 und bei Kollisionen sollte f(n) - i mod 13 bentutzt werden 6.2 Nenne 2 Eigenschaften einer guten Hashfunktion