ads1_2021/protocol/woche2.md

# Vorlesungswoche 2 (18.–24. Oktober 2021) #

## Agenda ##

- [x] Wdh: Laufzeitberechnung
    - Verschachtelte Blöcke
    - Blöcke hintereinander
    - Rekursion ---> Masterthm
- [x] Big-Oh Notation
    - Bestimmung von Klassen
    - Vergleiche zw. Klassen
- [x] Masterthm
    - Größen: a, b, g
    - Wie lässt sich T(n/b) definieren, wenn n/b nicht ganzzahlig ist?
        - Man benutze Floor im Masterthm:
          ```text
          Korrekte Variante: T(n) = a·T(floor(n/b)) + g(n)
          ```
        - Bemerkung: man kann einen Trick verwenden, um T und g von Funktionen ℕ ⟶ ℕ
          auf Funktionen ℝ⁺ ⟶ ℕ zu erweitern, nämlich
          ```text
          Setze T(x) := T(floor(x)) für alle x ∈ ℝ⁺
          Setze g(x) := g(floor(x)) für alle x ∈ ℝ⁺
          ```
          und kann damit den Ausdruck im Masterthm wieder vereinfachen auf:
          ```text
          T(n) = a·T(n/b) + g(n)
          ```
          und den Satz ohne Probleme beweisen.
- [ ] Suchalgorithmen
    - (diese Woche nicht dazu gekommen)


## Nächste Woche ##

- ab Suchalgorithmen

### TODOs (Studierende) ###

- VL-Inhalte aus Wochen 1–2 durchgehen
- Empfohlen: jeden Suchalgorithmus verstehen und ausprobieren (entweder per Hand oder durch Implementierung)