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

Vorlesung: Theoretische Informatik III

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

Termine: VL
UE
UE
UE
UE
UE
UE		 Mi
Di 14tgl/1
Di 14tgl/2
Mi 14tgl/1
Mi 14tgl/2
Do 14tgl/1
Do 14tgl/2		 15-17
11-13
11-13
13-15
13-15
11-13
11-13		 RUD 26, 0'115
RUD 26, 1'307
RUD 26, 1'307
RUD 26, 1'307
RUD 26, 1'307
RUD 26, 1'308
RUD 26, 1'308		 J. Köbler
S. Müller
S. Verbücheln
S. Kuhnert
S. Kuhnert
W. Kössler
W. Kössler

Zuordnung: Grundstudium, 4. Semester

Vorlesungsbeginn: 15.04.2009
Übungsbeginn: 21.04.2009

Übungen:


  • Die Lösungen der schriftlichen Aufgaben sind an dem auf dem Aufgabenblatt angegebenen Tag bis 11 Uhr im Erdgeschoss von Haus 4 abzugeben.
  • Die Übungen finden im Rhythmus von 2 Wochen statt, d.h. in jeweils zwei aufeinanderfolgenden Wochen werden die selben Aufgaben besprochen.
  • Fällt ein Feiertag auf einen der Termine, dann fällt der entsprechende Übungstermin ersatzlos aus. In diesem Fall bitte selbständig einen anderen Termin (z.B. in der Woche davor/danach) besuchen!

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: Do., 30.07.2009, um 9:00 Uhr in RUD26 0'115
    • Termin für die Klausureinsicht: Di., 4.8.2009 um 14:00 Uhr im RUD25 4.015
  • Termin der Nachklausur: Di., 06.10.2009, um 9:00 Uhr in RUD25 3.001
    • Termin für die Klausureinsicht: Mi, 14.10.2009, um 11:15 Uhr im RUD25 4.015
  • Termin der Nachklausur ThI2: Fr., 24.07.2009, um 9:00 Uhr im RUD26 0'115
    • Termin für die Klausureinsicht: Di., 4.8.2009 um 14:00 Uhr im RUD25 4.015

  •  

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 21.-30.4.2009; schriftl. Abgabe: 05.5.2009, 11:00 Uhr)
Blatt 2 (mündl. Besprechung 05.-14.5.2009; schriftl. Abgabe: 19.5.2009, 11:00 Uhr)
Blatt 3 (mündl. Besprechung 19.-28.5.2009; schriftl. Abgabe: 02.6.2009, 11:00 Uhr)
Blatt 4 (mündl. Besprechung 02.-11.6.2009; schriftl. Abgabe: 16.6.2009, 11:00 Uhr)
Blatt 5 (mündl. Besprechung 16.-25.6.2009; schriftl. Abgabe: 30.6.2009, 11:00 Uhr)
Blatt 6 (mündl. Besprechung 30.6.-9.7.2009; schriftl. Abgabe: 14.7.2009, 11:00 Uhr)
Probeklausur (mündl. Besprechung 14.-16.7.2009; 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