Vorlesung: Rekursive Algorithmen und Algorithmenanalyse

Rekursive Algorithmen

• Ziel: Multiplizieren von zwei Zahlen A und B effizient gestalten.

• Ansatz:

  • Zahlen darstellen als:
    • A = A1 * B^k + A0
    • B = B1 * B^k + B0
  • Multiplikation auf vier Multiplikationen von n/2-stelligen Zahlen reduzieren.
  • Zeitkomplexität: Quadratisch, ähnlich dem Schulalgorithmus.

• Karatsuba-Algorithmus:

  • Ersetzt die vier Multiplikationen durch drei (durch Umformen der Terme).
  • Zeitkomplexität: O(n^log2(3)), ca. 1.58, schneller als der Schulalgorithmus.
  • Praxis: Schneller für große Zahlen, nicht unbedingt für kleinere.

Algorithm Engineering

• Ziel: Theorie und Praxis verbinden.
  • Methodik:
    • Algorithmen entwerfen, analysieren, implementieren und experimentell validieren.
    • Lernprozess aus Experimenten führt zur Verbesserung der Algorithmen.
  • Kopplung zur Praxis: Arbeiten mit realen Eingaben und Anwendungen.

Maschinenmodell

• Registermaschinenmodell: Vereinfachtes Modell zur Algorithmenanalyse.
  • Register: Speichern kleine ganze Zahlen, minimal log(n) Bits für Speicheradressierung.
  • Speicher: Enthält Maschinenworte unbeschränkter Größe (theoretisch).
  • Befehle: Arithmetik, logische Operationen, Speicherzugriffe.

Algorithmenanalyse

• Ziel: Laufzeit abschätzen.

  • *Worst-Case-Analyse: Maximale Laufzeit für Eingaben der Größe n.
  • Asymptotik: Vernachlässigt konstante Faktoren und fokussiert auf dominantes Wachstum.

• Rechenregeln:

  • O-Notation und Varianten (Θ, Ω, o, ω): Beschreiben das Wachstum von Funktionen.
  • Beispiel für Rechenregeln:
    • C * f(n) ist O(f(n)), Θ(f(n)), Ω(f(n)).
    • Polynome von Grad k sind O(n^k).*

Pseudo-Code

• Verwendung: Abstrakte Beschreibung von Algorithmen.
  • Syntax: Ähnlich zu Programmiersprachen, aber kompakter.
  • Dokumentation: Assertions, Vor- und Nachbedingungen, Invarianten.

Master-Theorem

• Anwendung: Analyse von rekursiven Algorithmen.
  • Form: T(n) = a * T(n/b) + f(n), Lösungen abhängig von Verhältnis f(n) zu n^log_b(a).
  • Fälle:
    • f(n) ist O(n^log_b(a)): T(n) ist Θ(n^log_b(a)).
    • f(n) ist Θ(n^log_b(a)): T(n) ist Θ(n^log_b(a) * log(n)).
    • f(n) ist Ω(n^log_b(a)): T(n) hängt stark von f(n) ab.

Diese Notizen sollten einen umfassenden Überblick über die behandelten Themen der Vorlesung bieten und als Basis für weiterführendes Lernen dienen.