Komplexität von Algorithmen7.5 ECTS
(Prüfungsordnungsmodul: Komplexität von Algorithmen)

Lectures:

• • Komplexität von Algorithmen
    (Vorlesung, 4 SWS, Lutz Schröder, Wed, 08:15 - 09:45, H9; Fri, 10:15 - 11:45, H9)
  • Übungen zu Komplexität von Algorithmen
    (Übung, 2 SWS, Daniel Gorin)

Inhalt:

• 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.

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Informatik (Bachelor of Science): 4. Semester
   (Po-Vers. 2009w | Pflichtmodule | Komplexität von Algorithmen)

Studien-/Prüfungsleistungen:

Komplexität von Algorithmen (Klausur)_

Klausur, Dauer (in Minuten): 90, benotet

Erstablegung: SS 2013, 1. Wdh.: WS 2013/2014, 2. Wdh.: keine Wiederholung

1. Prüfer:

Lutz Schröder

Komplexität von Algorithmen (Übungsschein)_

Leistungsschein, benotet

weitere Erläuterungen:
unbenoteter Schein, zu erwerben durch erfolgreiche Teilnahme an den Übungen

Erstablegung: SS 2013, 1. Wdh.: WS 2013/2014, 2. Wdh.: keine Wiederholung

1. Prüfer:

Lutz Schröder