• Mathematische Hilfsmittel der Algorithmenanalyse: Abschätzung des asymptotischen Wachstums von Funktionen, Summationen, Anzahlen, divide-and-conquer-Rekursionen, etc.

• Grundbegriffe der quantitativen Algorithmenanalyse: worst-case- und average-case-Analsyse, obere und untere Schranken, Algorithmen- und Problemkomplexität

• Exemplarische Analysen von Sortieralgorithmen

• Sortierkomplexität und Entropie

• Quellcodierung und Datenkompression

• Komplexität von arithmetischen Operationen und Problemen (Multiplikation, Primtest, Faktorisierung)

• modulare Arithmetik und schnelle Fouriertransformation

• Kryptographie und Komplexität

Lernziele und Kompetenzen:

Die Studierenden

• erwerben fundierte Kenntnisse über die Grundbegriffe der quantitativen Algorithmenanalyse (Laufzeit) und die benötigten mathematischen Methoden

• verstehen die Komplexität (Laufzeitverhalten) von Standardalgorithmen (z.B. Sortieren, arithmetische Algorithmen) und können deren praktische Bedeutung erklären

• sind in der Lage, an einfachen, exemplarischen Algorithmen Analysen des worst-case-Verhaltens und des average-case-Verhaltens durchzuführen

• können exemplarisch Algorithmenkomplexität und Problemkomplexität in Bezug setzen

• können die Beziehungen zwischen Sortier- und Suchkomplexität und dem Entropiebegriff darstellen

• erwerben Grundkenntnisse über algebraische Strukturen der Arithmetik und die Komplexität arithmetischer Operationen

• können die Rolle von Komplexitätsaussagen für die Beurteilung der Sicherheit einfacher kryptografischer Protokoll darstellen

Literatur:

Graham, Knuth, Patashnik, Concrete Mathematics, Addison-Wesley, 1994.
Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, MIT-Press, 2001.
Heun, Grundlegende Algorithmen, Vieweg, 2001.