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
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?