Gedächtnisprotokoll AD08-1: Unterschied zwischen den Versionen
(→Graphen: +%-DAG) |
|||
Zeile 8: | Zeile 8: | ||
* Hashing | * Hashing | ||
* P/NP | * P/NP | ||
== O-Kalkül == | |||
Zeigen Sie anhand der Definition des O-Kalküls: f(n) = O(g(n)). (Natürlich für konkrete f und g). | |||
== Suchen == | == Suchen == |
Version vom 18. Februar 2008, 20:38 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
- Hashing
- P/NP
O-Kalkül
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
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?