Komplexität von Algorithmen7.5 ECTS

Lehrveranstaltungen:

• • Komplexität von Algorithmen
    (Vorlesung, 4 SWS, Volker Strehl, Mi, 8:15 - 9:45, H4; Fr, 10:15 - 11:45, H14 (0.61); Beginn am 4.5.2011)
  • Ü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:
Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:

1. Computational Engineering (Rechnergestütztes Ingenieurwesen) (Bachelor of Science)
   (Po-Vers. 2007 | Bachelorprüfung | Technische Wahlmodule | Komplexität von Algorithmen)
2. Informatik (Bachelor of Science): 4-5. Semester
   (Po-Vers. 2007 | Pflichtmodule | Komplexität von Algorithmen)
3. Informatik (Bachelor of Science): 4-5. Semester
   (Po-Vers. 2009s | Modulverzeichnis für Studienbeginn zum Sommersemester | Pflichtmodule | 5. Semester | Komplexität von Algorithmen)
4. Informatik (Bachelor of Science): 4-5. Semester
   (Po-Vers. 2009w | Modulverzeichnis für Studienbeginn zum Wintersemester | Pflichtmodule | 4. Semester | Komplexität von Algorithmen)
5. Mathematik (Bachelor of Science)
   (Po-Vers. 2007 | Bachelorprüfung Mathematik | Nebenfach Informatik | Wahlbereich 2 | Komplexität von Algorithmen)
6. Mathematik (Bachelor of Science)
   (Po-Vers. 2009 | Nebenfach Informatik | Module des 2. und 3. Studienjahrs | Wahlbereich 2 | Komplexität von Algorithmen)

Studien-/Prüfungsleistungen:

schriftlich, Dauer (in Minuten): 90, benotet

Erstablegung: SS 2011, 1. Wdh.: WS 2011/2012, 2. Wdh.: keine Wiederholung

1. Prüfer:

Volker Strehl

Leistungsschein, benotet

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

Erstablegung: SS 2011, 1. Wdh.: WS 2011/2012, 2. Wdh.: keine Wiederholung

1. Prüfer:

Volker Strehl