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?