| Albert-Ludwigs-Universität Freiburg | ||
| Mathematische Fakultät | ||
|
|
|
Zeit und Ort: Mo, Mi 9-11, SR 404, Eckerstraße 1
Übungen dazu: Fr 11-13, SR 414, Eckerstraße 1.
Die Komplexitätstheorie untersucht, mit welchem Aufwand algorithmische
Probleme auf einem Rechner gelöst werden können. Den Aufwand kann man
auf verschiedene Weise messen; für den Anwender sind in erster Linie
die Rechenzeit und der notwendige Speicherplatz von Bedeutung.
Die Vorlesung gibt einen Einblick in Methoden und Ergebnisse der
Komplexitätstheorie.
Die Vorlesung wendet sich an Studierende der Mathematik und der
Informatik im Hauptstudium. Nützlich, wenn auch nicht unabdingbar,
sind Vorkenntnisse über Algorithmen und Berechenbarkeit, wie man sie
z.B. in der theoretischen Einführungsvorlesung der Informatik oder in
der Vorlesung über mathematische Logik für Studierende der Mathematik
erwerben kann.
Mit geeigneten Erweiterungen kann sie als eines der Gebiete für das
Staatsexamen oder für Teil I der mündlichen Diplomprüfung in
Mathematik gewählt werden.
Literaturverzeichnis