Bearbeiten von „Gedächtnisprotokoll AD08-1“

Die Klausur war zeitlich kaum zu schaffen. Die schwierigkeit der einzelnen Aufgaben wurde unterschiedlich zwischen angemessen und zu hoch bis viel zu hoch bewertet.

Man konnte eine handbeschriebene Din-A4-Seite mit beliebigem Inhalt mitbringen.


== Multiple-Choice Teil ==

* Hashing
* P/NP

== asymptotische Laufzeiten ==
Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)

Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)<br>
Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist.

Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)

Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).

== Suchen ==
Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit bekannten Sortieralgorithmen

Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?

Quicksort

Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben.

== Bäume ==
Gegeben: 5 Bäume. Entscheiden Sie jeweils ob ein korrekter Rot-Schwarz-Baum vorliegt. Begründen Sie ihre Antwort.

Geben Sie einen Algortithmus an, der ein Array mit n Zahlen in einem unbalancierten Binärbaum sortiert. Sie können dabei die aus der Vorlesung bekannten Operationen auf Binärbäumen verwenden. Geben Sie die asymptotischen Best- und Worst-Case-Laufzeiten an.

Algoritmus implementieren der berechnet wieviele Knoten k mit a <= k <= b es gibt. (in O(log n))

== Graphen ==
Dijkstras Algortitmus anwenden.

Problemstellung: Aus einem Rohstoff wird über Zwischenzustände ein Endprodukt erstellt. Ein DAG ist gegeben. Die Kantengewichte sind prozentuale Angaben darüber wieviel von der vorherigen Masse noch da ist (alle < 100%). Gesucht ist der Weg mit dem geringsten Verlust.
* Warum kann der optimale Pfad keine Zyklen enthalten?
* Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?
* Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.

== Dynamische Programmierung ==
Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen
* Randbedingungen formulieren
* Rekursionsgleichung formulieren
* Algorithmus implementieren
* Laufzeit?

[[Kategorie:Gedaechtnisprotokoll]]
@@ Zeile 12: / Zeile 12: @@
 Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen)
-Finden Sie die geschlossene Form für folgende Rekurenzgleichung: <math>T(\sqrt{(N)})+1</math> (oder so ähnlich)<br />
+Finden Sie die geschlossene Form für folgende Rekurenzgleichung: T(sqrt(N))+1 (oder so ähnlich)<br>
-Sie können annehmen dass <math>n \in 2^{2^i}</math> mit <math>i \in \mathbb{N}</math> ist.
+Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist.
 Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt)
-Zeigen Sie anhand der Definition des O-Kalküls: <math>f(n) = O(g(n))</math>. (Natürlich für konkrete f und g).
+Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g).
 == Suchen ==
-Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit dem bekannten Sortieralgorithmen Insertion-, Selection-, Bubble- und Quicksort.
+Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit bekannten Sortieralgorithmen
 Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?
@@ Zeile 26: / Zeile 26: @@
 Quicksort
-Annahme:Jedes Element steht maximal k Plätze von seinem richtigen entfernt
+Bubble-Sort an Zusatzbedingung anpassen: Jedes Element steht maximal k Plätze von seinem richtigen entfernt. Quicksort war gegeben.
-* Zeigen Sie, dass eine Vertauschung von <nowiki>A[j] und A[j+1] mit A[j] > A[j+1]</nowiki> diese Eigenschaft nicht zerstört.
-* Passen Sie Bubble-Sort an die Zusatzbedingung an. (Bubble-Sort gegeben)
-== Hashing ==
-Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion <math>h(k,i) = h_1(k) + i * h_2(k)</math> mit <math>h_1(k) = k \mod m</math> und <math>k_2 = 1 + k \mod (m-1)</math>. Geben Sie die Sondierungsfolge an.
 == Bäume ==
@@ Zeile 39: / Zeile 34: @@
 Algoritmus implementieren der berechnet wieviele Knoten k mit a <= k <= b es gibt. (in O(log n))
-Gegeben: Ein Heap. Entfernen Sie das grösste Element (Heap-Extract-Max) und geben Sie den Heap nach der Operation an.
 == Graphen ==
@@ Zeile 49: / Zeile 42: @@
 * Welchem aus der Veranstaltung bekannten Problem ähnelt dieses?
 * Passen Sie den zu dem bekannten Problem gehörenden Algorithmus an dieses Problem an.
-Geben die folgenden Algortithmen einen MST (minimal-spanning-tree) zurück?
-* Alg 1
-** initialisiere T mit der Leeren Menge
-** für jede Kante x tue
-*** Wenn T vereinigt x Zyklenfrei
-**** T <- T vereinigt x
-* Alg 2
-** initialisiere T mit der Kantenmenge
-** für jede Kante x sortiert von gross nach klein tue
-*** Wenn T ohne x verbunden
-**** T <- T ohne x
 == Dynamische Programmierung ==
@@ Zeile 70: / Zeile 50: @@
 * Laufzeit?
-[[Kategorie:Gedaechtnisprotokoll|AD]]
+[[Kategorie:Gedaechtnisprotokoll]]