Gedächtnisprotokoll AD08-1: Unterschied zwischen den Versionen
K (Bot: Kosmetische Änderungen) |
|||
| (4 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
| Zeile 12: | Zeile 12: | ||
Berechnen Sie mit dem Master-Theorem: (3 Rekurenzgleichungen folgen) | 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> | Finden Sie die geschlossene Form für folgende Rekurenzgleichung: <math>T(\sqrt{(N)})+1</math> (oder so ähnlich)<br /> | ||
Sie können annehmen dass n \in 2^{2^i} mit i \in \mathbb{N} ist. | Sie können annehmen dass <math>n \in 2^{2^i}</math> mit <math>i \in \mathbb{N}</math> ist. | ||
Stellen sie die Rekurenzgleichung für folgenden Algorithmus auf und geben Sie seine asymptotische Laufzeit an. (ein Algorithmus folgt) | 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). | Zeigen Sie anhand der Definition des O-Kalküls: <math>f(n) = O(g(n))</math>. (Natürlich für konkrete f und g). | ||
== Suchen == | == Suchen == | ||
| Zeile 31: | Zeile 31: | ||
== Hashing == | == Hashing == | ||
Gegeben: eine Zahl und ein teilweise gefülltes Array. Fügen sie die Zahl in das Array ein. Verwenden Sie die Hashfunktion h(k,i) = h_1(k) + i * h_2(k) mit h_1(k) = k mod m und k_2 = 1 + k mod (m-1). Geben Sie die Sondierungsfolge an. | 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 == | == Bäume == | ||
| Zeile 39: | Zeile 39: | ||
Algoritmus implementieren der berechnet wieviele Knoten k mit a <= k <= b es gibt. (in O(log n)) | 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 == | == Graphen == | ||
| Zeile 68: | Zeile 70: | ||
* Laufzeit? | * Laufzeit? | ||
[[Kategorie:Gedaechtnisprotokoll]] | [[Kategorie:Gedaechtnisprotokoll|AD]] | ||
Aktuelle Version vom 8. Juni 2012, 17:05 Uhr
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[Bearbeiten]
- Hashing
- P/NP
asymptotische Laufzeiten[Bearbeiten]
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)
Sie können annehmen dass <math>n \in 2^{2^i}</math> mit <math>i \in \mathbb{N}</math> 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).
Suchen[Bearbeiten]
Gegeben: Ein Array von Zahlen, Mehrere andere Arrays mit denselben Zahlen, eine Liste mit dem bekannten Sortieralgorithmen Insertion-, Selection-, Bubble- und Quicksort.
Zuordnen: Welcher Algorithmus hat welches Array als Zwischenergebnis produziert?
Quicksort
Annahme:Jedes Element steht maximal k Plätze von seinem richtigen entfernt
- Zeigen Sie, dass eine Vertauschung von A[j] und A[j+1] mit A[j] > A[j+1] diese Eigenschaft nicht zerstört.
- Passen Sie Bubble-Sort an die Zusatzbedingung an. (Bubble-Sort gegeben)
Hashing[Bearbeiten]
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[Bearbeiten]
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))
Gegeben: Ein Heap. Entfernen Sie das grösste Element (Heap-Extract-Max) und geben Sie den Heap nach der Operation an.
Graphen[Bearbeiten]
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.
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
- Wenn T vereinigt x Zyklenfrei
- 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
- Wenn T ohne x verbunden
Dynamische Programmierung[Bearbeiten]
Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen
- Randbedingungen formulieren
- Rekursionsgleichung formulieren
- Algorithmus implementieren
- Laufzeit?