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

Vorlesung: Theoretische Informatik III

Dozent: Dr. Wolfgang Kössler
Übung: Dr. Wolfgang Kössler


Termine: VL Di 9-11 RUD 25, 3.101 W. Kössler
  UE Di 11-13 14tgl./1 RUD 25, 3.101 W. Kössler
  UE Di 11-13 14tgl./2 RUD 25, 3.101 W. Kössler
  UE Do 9-11 14tgl./1 RUD 25, 3.101 W. Kössler
  UE Do 9-11 14tgl./2 RUD 25, 3.101 W. Kössler

 

Zuordnung: Grundstudium, 4. Semester


Vorlesungsbeginn: 12.04.2011
Übungsbeginn: 19.04.2011
(Gruppe 1 nach Goya in der Woche ab dem 19., Gruppe 2 in der Woche ab dem 26.)

Klausur war am Montag, 18.7.2011. Die Klausureinsicht findet am Donnerstag, den 21.7.2011 um 15:15 Uhr im RUD25 4.007 statt.
Nachklausur war am Mittwoch, 17.8.2011. Die Klausureinsicht findet am Donnerstag, den 18.8.2011 um 15:15 Uhr im RUD25 4.007 statt.

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

Aufgabenblatt 1
Aufgabenblatt 2
Aufgabenblatt 3
Aufgabenblatt 4
Aufgabenblatt 5
Aufgabenblatt 6
Probeklausur (Lösungsvorschläge)

Skript

Skript: Theoretische Informatik III

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
Korrektheit des DFA-String-Matchers
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)