Komplexität von Algorithmen 2013 (Audio)

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