Gedächtnisprotokoll AD08-1

Aus Fachschaft_Informatik
Zur Navigation springen Zur Suche springen

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
  • 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[Bearbeiten]

Fragestellung: Verbindungen zwischen Städten mit der Bahn, minimaler Pfad mit max. k Mal umsteigen

  • Randbedingungen formulieren
  • Rekursionsgleichung formulieren
  • Algorithmus implementieren
  • Laufzeit?