Gedächtnisprotokoll AD08-1: Unterschied zwischen den Versionen

Aus Fachschaft_Informatik
Zur Navigation springen Zur Suche springen
(→‎Hashing: +math-tag)
K (sort)
Zeile 70: Zeile 70:
* Laufzeit?
* Laufzeit?


[[Kategorie:Gedaechtnisprotokoll]]
[[Kategorie:Gedaechtnisprotokoll|AD]]

Version vom 15. Juli 2008, 18:49 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

asymptotische Laufzeiten

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

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

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

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

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

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

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