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, D. Schlatter


Termine: VL Do 10-12 (UL, 3094) Prof. J. Köbler
UE Mo 10-12 (Dor 24, 403, ab 23.04.) O. Beyersdorff
UE Mo 10-12 (Dor 24, 403, ab 07.05.) O. Beyersdorff
UE Mo 12-14 (Dor 24, 403, ab 23.04.) O. Beyersdorff
UE Mo 12-14 (Dor 24, 403, ab 07.05.) O. Beyersdorff
UE Do 08-10 (Dor 24, 403, ab 26.04.) D. Schlatter
UE Do 08-10 (Dor 24, 403, ab 10.05.) D. Schlatter
Klausurtermin: 28.07.2001, 10 Uhr, Audimax
Zuordnung: Grundstudium, 4. Semester

Inhalte und Lernziele

Wärend 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)


JK
Erstellt am 11.02.2001