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 |
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.