|
Komplexität von Algorithmen7.5 ECTS
Modulverantwortliche/r: Lutz Schröder Lehrende:
Lutz Schröder
Start semester: |
SS 2013 | 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: Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:
- Informatik (Bachelor of Science): 4. Semester
(Po-Vers. 2007 | Pflichtmodule | Komplexität von Algorithmen)
- Informatik (Bachelor of Science): 5. Semester
(Po-Vers. 2009s | Pflichtmodule | Komplexität von Algorithmen)
- Informatik (Bachelor of Science): 4. Semester
(Po-Vers. 2009w | Pflichtmodule | Komplexität von Algorithmen)
- Mathematik (Bachelor of Science): 3-6. Semester
(Po-Vers. 2009 | Nebenfach Informatik | Module des 2. und 3. Studienjahrs | Wahlbereich 2 | 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
- Termin: 11.10.2013, 16:00 Uhr, Ort: Mensa-Süd
Termin: 17.02.2014, 14:00 Uhr, Ort: H 5 TechF
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
|
|
|