ads1_2021/protocol/woche5.md

Vorlesungswoche 5 (8.–14. November 2021)

Agenda

• Gruppe 1
  • Alle Sortierverfahren durchgegangen; argumentierte, wieso die Algorithmen korrekt sind.
  • Bäume und Listendarstellung von fast vollständige binäre Bäume.
  • Max-Heap-Eigenschaft (MHE).
  • Theorem: folgende Aussagen sind äquivalent
    • T hat MHE
    • (Definition) alle Unterbäume von T haben Max in Wurzel, d. h. für alle Knoten, e, gilt

      value(e) ≥ max{value(e') | e' Unterhalb von e in T}
      

    • für alle Knoten, e, gilt

      value(e) ≥ max{value(e') | e' Tochterknoten von e in T}
      

    • L[i] = L[2i+1] und L[i] = L[2i+2] (jeweils solange Indexes in Listendarstellung L, wobei L = Listendarstellung von Baum T).
• Gruppe 2
  • Alle Sortierverfahren durchgegangen; argumentierte, wieso die Algorithmen korrekt sind. (Etwas ausführlicher, weil MHE, usw. schon in der Übung diskutiert wurden.)

Anmerkung. Bei Quicksort konnten wir sehen, dass die Zeit- (und Satzbewegungs!) komplexität durch C(n) = 2C(n/2) + Θ(n) gegeben ist (warum diese Koeffizienten, warum Θ(n)?).
Laut Mastertheorem gilt also C(n) ∈ Θ(n·log(n)) (warum?).
Das ist aber der Worst-case.
Wie verhält sich das beim Average-Case (C_{av}(n))?

Nächste Woche

• Ab VL5 + Blatt 6.

TODOs (Studierende)

• VL-Inhalte aus Wochen 4 + 5 durchgehen
• freiwillige ÜB 5 + Pflichtserie 3.