Berechenbarkeit und Komplexität
» This course is given in German.
Vorlesung im Wintersemester 1998/1999
| Art | Termine/Ort | Beginn | Veranstalter |
|---|---|---|---|
| V3 | Di 08:15-09:45 AH IV Do 08:15-09:45 (14tgl.) AH II |
13.10.1998 | Thomas |
| Ü1 | Do 08:15-09:45 (14tgl.) AH II | Thomas, Matz |
Inhalt
Ziel dieser Vorlesung ist die Klärung von Grundbegriffen der Informatik wie z.B. "algorithmisches Problem", "Algorithmus" und "Rechenaufwand". Im Rahmen dieser (mathematisch aufgebauten) Theorie der Berechenbarkeit und Komplexität kann man dann beurteilen, welche algorithmischen Probleme lösbar sind bzw. mit welchen Ressourcen eine Lösung möglich ist. Auch die Methoden, die hierzu entwickelt werden, haben allgemeine Bedeutung für die Informatik, so z.B. die Technik der Simulation und die Reduzierbarkeit von Problemen.
Themenübersicht in Stichworten:
- Algorithmenbegriff und Turingmaschinen
- Äquivalenz zu programmiersprachlichen Formalismen (WHILE-Programme, GOTO-Programme, rekursive Programme)
- Church-Turing-These und algorithmisch unlösbare Probleme
- Zeitkomplexität, Polynomzeit, NP-Vollständigkeit
- Platzkomplexität, Komplexitätshierarchien
- Ausblick auf weitere Themen und aktuelle Fragen der Forschung
Die aktive Teilnahme an den Übungen ist wichtig für den erfolgreichen Besuch der Vorlesung.
Literatur
- Sipser, Michael: Introduction to the Theory of Computation; PWS Publishing Company, 1997
- Schöning, Uwe: Theoretische Informatik - kurzgefaßt; Spektrum1997
Zuordnung
Theoretische Informatik