|
Komplexität von Algorithmen7.5 ECTS (Prüfungsordnungsmodul: Komplexität von Algorithmen)
Modulverantwortliche/r: Volker Strehl Lehrende:
Lutz Schröder
Start semester: |
SS 2012 | Duration: |
1 semester |
Präsenzzeit: |
90 Std. | Eigenstudium: |
135 Std. | Language: |
Deutsch |
Lectures:
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:
- Informatik (Bachelor of Science): 4. Semester
(Po-Vers. 2009w | Pflichtmodule | Komplexität von Algorithmen)
Dieses Modul ist daneben auch in den Studienfächern "Computational Engineering (Rechnergestütztes Ingenieurwesen) (Bachelor of Science)", "Mathematik (Bachelor of Science)" verwendbar. Details
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
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
|
|
|