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

Lehrveranstaltungen:

• • Komplexität von Algorithmen
    (Vorlesung, 4 SWS, Lutz Schröder, Mi, 12:15 - 13:45, H14; Do, 8:30 - 10:00, H4)
  • Übungen zu Komplexität von Algorithmen
    (Übung, 2 SWS)

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 2012, 1. Wdh.: WS 2012/2013, 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 2012, 1. Wdh.: WS 2012/2013, 2. Wdh.: keine Wiederholung

1. Prüfer:

Lutz Schröder