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, Martin Stigge, Sebastian Kuhnert

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 25, 3.001
RUD 26, 1'307
RUD 26, 1'307
RUD 26, 1'305
RUD 26, 1'305
RUD 26, 1'307
RUD 26, 1'307
 J. Köbler
W. Kössler
W. Kössler
M. Stigge
M. Stigge
S. Kuhnert
S. Kuhnert

Zuordnung: Grundstudium, 4. Semester

Vorlesungsbeginn: 16.04.2008
Übungsbeginn: 22.04.2008

Übungen:
  • 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!
  • Kriterien für einen Übungsschein:
    • Lösen von mindestens 50% der schriftlichen Aufgaben (via Punkte)
    • Lösen von mindestens 50% der mündlichen Aufgaben (via Kreuze)
  • Es wird 6 Aufgabenblätter im Abstand von 2 Wochen geben
  • Abgabe bitte bis 11 Uhr am angegebenen Mittwoch bei Frau Sandig im Büro (RUD25 3.320)
  • Bearbeitung der schriftlichen Aufgaben kann in Gruppen bis zur Größe 3 erfolgen. Diese sollten über das ganze Semester gleich bleiben. Gruppengröße 2 wird empfohlen.
  • In der letzten Woche wird eine freiwillige Probeklausur anstatt eines Aufgabenblattes ausgeteilt

Prüfung:
  • Die Prüfung findet in Form einer Klausur statt.
    • Voraussetzung zur Teilnahme ist der Übungsschein.
    • Reine Klausurzeit ist 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., 28.07.2008, um 9:00 Uhr in RUD26 0'115
  • Termin der Nachklausur: Mo., 29.09.2008, 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.
  • Suchbaum-Applet für verschiedene Baum-Strukturen

Aufgabenblätter


Blatt 1 (mündl. Besprechung 22.-30.4.2008; schriftl. Abgabe: 7.5.2008, 11:00 Uhr)
Blatt 2 (mündl. Besprechung 6.-15.5.2008; schriftl. Abgabe: 21.5.2008, 11:00 Uhr)
Blatt 3 (mündl. Besprechung 20.-29.5.2008; schriftl. Abgabe: 4.6.2008, 11:00 Uhr)
Blatt 4 (mündl. Besprechung 4.-12.6.2008; schriftl. Abgabe: 18.6.2008, 11:00 Uhr)
Blatt 5 (mündl. Besprechung 18.-26.6.2008; schriftl. Abgabe: 2.7.2008, 11:00 Uhr)
Blatt 6 (mündl. Besprechung 2.-10.7.2008; schriftl. Abgabe: 15.7.2008, 11:00 Uhr)

Probeklausur (mündl. Besprechung 15.-17.7.2008)
Beispiellösung der Aufgaben 31a und 31b
Beispiellösung der Aufgabe 42 von B. Kees

Skript