Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Dozent: Prof. Johannes Köbler
Übung: Dr. Wolfgang Kössler, Sebastian Kuhnert, Stephan Verbücheln, Frank Fuhlbrück

Vorlesungsbeginn: 13.04.2010
Übungsbeginn: 20.04.2010

Prüfung:

• Die Prüfung findet in Form einer Klausur statt.
  • Voraussetzung zur Teilnahme ist der Übungsschein.
  • Die reine Klausurzeit beträgt 2 Stunden.
  • Es sind keine Hilfsmittel zugelassen.
  • Mitzubringen sind Stift und eigenes Papier, der Studierendenausweis und ein amtlicher Lichtbildausweis (Personalausweis, Reisepass oder Führerschein).
• Klausurtermin: Mo., 26.07.2010, um 14:00 Uhr in RUD26 0'115
  • Am Do., 22.07.2010, um 14:00 in RUD25 4.007 findet eine Fragestunde statt.
  • Am Mo., 9.8.2010, um 14:00 in RUD25 4.007 findet die Klausureinsicht statt.
• Nachklausurtermin: Do., 14.10.2010, um 9:00 Uhr in RUD26 0'115
  • Die Klausureinsicht findet am Donnerstag, 21.10.2010, ab 10:45 (Pause nach dem ersten Vorlesungsblock) in Raum RUD25 4.015 statt.
• Nachklausurtermin für ThI2: Fr., 30.07.2010, um 9:00 Uhr in RUD26 0'115

Inhalte und Lernziele

Während in der Vorlesung ThI2 die Themengebiete Automaten und formale Sprachen im Mittelpunkt standen, befassen wir uns in der VL ThI3 vorwiegend mit verschiedenen Entwurfsmethoden für effiziente Algorithmen. Die hierzu nötigen Kenntnisse über algebraische und relationale Strukturen wie etwa Graphen werden ebenfalls in der VL vermittelt. Da die gefundenen Algorithmen "nur" obere Schranken für den benötigten Rechenaufwand liefern, untersuchen wir auch Methoden der Komplexitätstheorie, diesen Aufwand nach unten abzuschätzen. Um auch NP-vollständige Probleme in der Praxis mit vertretbarem Aufwand bewältigen zu können, werden u.a. auch approximative und/oder randomisierte Lösungsverfahren eingesetzt, die oftmals auf heuristischen Ansätzen beruhen.

Empfohlene Literatur

• Cormen, Leiserson, Rivest, Stein: Algorithmen - Eine Einführung. Oldenbourg 2007.
• Emden-Weinert, Hougardy, Kreuter, Prömel, Steger: Einführung in Graphen und Algorithmen, Vorlesungsskript, 450 Seiten, Berlin 1996.
• Garey, Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
• Hopcroft, Ullman: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979.
• Lewis, Papadimitriou: Elements of the Theory of Computation. Prentice-Hall, 1981.
• Motwani, Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
• Ottmann, Widmayer: Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag, 2002.
• Papadimitriou: Computational Complexity. Addison-Wesley, 1994.
• Schöning: Algorithmik. Spektrum Akademischer Verlag, 2001.
• Sedgewick: Algorithmen. Pearson Studium, 2002.
• Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 2005.
• Wagner: Einführung in die Theoretische Informatik, Grundlagen und Modelle. Springer Verlag, 1994.
• Wegener: Theoretische Informatik. Teubner Verlag, 1993.
• Applets für verschiedene Sortieralgorithmen: http://www.sortieralgorithmen.de/ und http://www.sorting-algorithms.com/
• Suchbaum-Applet für verschiedene Baum-Strukturen
•  

Aufgabenblätter

Blatt 1 (mündl. Besprechung 20.-29.4.2010; schriftl. Abgabe: 04.5.2010, 15:00 Uhr)
Blatt 2 (mündl. Besprechung 04.-13.5.2010; schriftl. Abgabe: 18.5.2010, 15:00 Uhr)
Blatt 3 (mündl. Besprechung 18.-27.5.2010; schriftl. Abgabe: 01.6.2010, 15:00 Uhr)
Blatt 4 (mündl. Besprechung 01.-10.6.2010; schriftl. Abgabe: 15.6.2010, 15:00 Uhr)
Blatt 5 (mündl. Besprechung 15.-24.6.2010; schriftl. Abgabe: 29.6.2010, 15:00 Uhr)
Blatt 6 (mündl. Besprechung 29.6.-8.7.2010; schriftl. Abgabe: 13.7.2010, 15:00 Uhr)
Probeklausur (mündl. Besprechung 13.7.-15.7.2010; Lösungsvorschläge)

Skript

Folien

Konstruktion eines DFA für die Suche in Texten
Suche eines Wortes mit einem DFA
Suche eines Wortes mit dem KMP-Algorithmus
Berechnung der KMP-Präfixfunktion
Suche in einem Digraphen (inkl. Klassifikation der Kanten)
Suche in einem Graphen (inkl. Klassifikation der Kanten)
Breitensuche in einem Digraphen (inkl. Klassifikation der Kanten)
Tiefensuche in einem Digraphen (inkl. Klassifikation der Kanten)
Tiefensuche in einem Graphen (inkl. Klassifikation der Kanten)
Tiefensuche in einem Digraphen (inkl. grau/schwarz-Färbung der Knoten)
Berechnung der starken Zusammenhangskomponenten
Dijkstra-Algorithmus
Bellman-Ford-Moore-Algorithmus
Bellman-Ford-Moore-Algorithmus (mit negativem Kreis)
Floyd-Warshall-Algorithmus
Floyd-Warshall-Algorithmus (mit negativem Kreis)
Ford-Fulkerson-Algorithmus