2021-10-12 20:41:41 +02:00
|
|
|
|
# Vorlesungswoche 5 (8.–14. November 2021) #
|
|
|
|
|
|
|
|
|
|
## Agenda ##
|
|
|
|
|
|
2021-11-13 09:01:35 +01:00
|
|
|
|
- Gruppe 1
|
|
|
|
|
- [x] Alle Sortierverfahren durchgegangen; argumentierte, wieso die Algorithmen korrekt sind.
|
|
|
|
|
- [x] Bäume und Listendarstellung von **fast vollständige binäre Bäume**.
|
|
|
|
|
- [x] Max-Heap-Eigenschaft (MHE).
|
2021-11-13 18:30:32 +01:00
|
|
|
|
- [x] Theorem: folgende Aussagen sind äquivalent
|
2021-11-13 09:01:35 +01:00
|
|
|
|
- T hat MHE
|
2021-11-13 16:54:48 +01:00
|
|
|
|
- (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}
|
|
|
|
|
```
|
2021-11-13 09:01:35 +01:00
|
|
|
|
- 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
|
|
|
|
|
- [x] Alle Sortierverfahren durchgegangen; argumentierte, wieso die Algorithmen korrekt sind.
|
|
|
|
|
(Etwas ausführlicher, weil MHE, usw. schon in der Übung diskutiert wurden.)
|
2021-10-12 20:41:41 +02:00
|
|
|
|
|
2021-11-13 18:30:32 +01:00
|
|
|
|
**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)?).
|
|
|
|
|
</br>
|
|
|
|
|
Laut **Mastertheorem** gilt also $C(n) ∈ Θ(n·log(n))$ (warum?).
|
|
|
|
|
</br>
|
|
|
|
|
Das ist aber der Worst-case.
|
|
|
|
|
</br>
|
|
|
|
|
Wie verhält sich das beim Average-Case ($C_{av}(n)$)?
|
|
|
|
|
|
2021-10-12 20:41:41 +02:00
|
|
|
|
## Nächste Woche ##
|
|
|
|
|
|
2021-11-13 09:01:35 +01:00
|
|
|
|
- Ab VL5 + Blatt 6.
|
2021-10-12 20:41:41 +02:00
|
|
|
|
|
|
|
|
|
### TODOs (Studierende) ###
|
|
|
|
|
|
2021-11-13 09:01:35 +01:00
|
|
|
|
- VL-Inhalte aus Wochen 4 + 5 durchgehen
|
|
|
|
|
- freiwillige ÜB 5 + Pflichtserie 3.
|