Humboldt-Universität zu Berlin, Institut für Informatik

Lehrstuhl für Komplexität und Kryptografie

Vorlesung: Theoretische Informatik III

Dozent: Prof. Johannes Köbler

Übungen: Olaf Beyersdorff, Hiep Han, Carsten Schwarz




Termine: VL Mi 15-17 (RUD 26, 0.115) Prof. J. Köbler

UE Di 11-13 (RUD 26, 1.305, 14tgl./1.) O. Beyersdorff

UE Di 11-13 (RUD 26, 1.305, 14tgl./2.) O. Beyersdorff

UE Do 09-11 (RUD 26, 1.305, 14tgl./1.) O. Beyersdorff

UE Do 09-11 (RUD 26, 1.305, 14tgl./2.) O. Beyersdorff

UE Fr 09-11 (RUD 26, 1.307, 14tgl./1.) C. Schwarz

UE Fr 01-11 (RUD 26, 1.307, 14tgl./2.) C. Schwarz

Zuordnung: Grundstudium, 4. Semester

Klausurtermine

Theoretische Informatik III:   15. Juli, Einlass: 13:00 Uhr, Dauer: ca. 2 Stunden, Raum: UL 6, 2116 (Auditorium Maximum)
Nachschreibeklausur Theoretische Informatik II:   22. Juli, Einlass: 10:00 Uhr, Dauer: ca. 2 Stunden, Raum: RUD 26, 0.115

Hilfsmittel (Skripte, Rechner etc.) sind zur Klausur nicht zugelassen.

Übersicht Übungen


Übung Dienstags 11-13 Uhr
Übung Donnerstags 9-11 Uhr
Übung Freitags 9-11 Uhr
Woche ab dem 5. Juli
Probeklausur
Probeklausur
keine Übung
Woche ab dem 12. Juli
Kosultation zu Theo III
Kosultation zu Theo III keine Übung

Die Kosultation zu Theo II wird am 19. Juli, 14:15 Uhr, in RUD 25, 3.113 stattfinden.

Inhalte und Lernziele

Während in der Vorlesung TI2 die Themengebiete Automaten und formale Sprachen im Mittelpunkt standen, befassen wir uns in der VL TI3 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


Aufgabenblätter


Skript (pdf)