Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik
der Ludwig-Maximilians-Universität München
Vorlesung im Hauptstudium: Komplexitätstheorie (WS 08/09)
- Die Scheine liegen mittlerweile bei Sigrid
Roden zur Abholung bereit.
- Vorlesung:
- Martin Hofmann, 4-stündig
- Zeit und Ort: Mo 10-12 Uhr (Raum Oe 15), Do 12-14 Uhr (Raum Oe
0.33) (Oettingenstr. 67)
- Beginn: 13.10. 2008
- Übung:
- Jan Hoffmann, 2-stündig
- Zeit und Ort der Übung: Mi 14-16 Uhr (Raum Oe 0.37) (Oettingenstr. 67)
- Beginn: 22. 10. 2008
- Vorkenntnisse:
-
Informatik IV
-
Effiziente Algorithmen (Algorithmen und Datenstrukturen) empfehlenswert aber nicht Voraussetzung
- Hörerkreis:
- Studierende der Informatik im Hauptstudium
- Studierende mit Nebenfach Informatik
- Schein:
- Schein gilt für Diplomprüfung in
Haupt- und Nebenfach Informatik
- Scheinerwerb durch Abgabe von Hausaufgaben und
Vorführung in der Präsenzübung.
zurück zum
Inhaltsverzeichnis dieser Seite
Die Komplexitätstheorie beschäftigt sich mit der Klassifikation von
Algorithmen und Berechnungsproblemen nach ihrem Ressourcenverbrauch,
z.B. Rechenzeit oder benötigtem Speicherplatz. Probleme
mit gleichartigem Ressourcenverbrauch werden zu Komplexitätsklassen
zusammengefasst. Die bekanntesten Komplexitätsklassen sind sicherlich
P und NP, die die in polynomieller Zeit deterministisch bzw.
nicht-deterministisch lösbaren Probleme umfassen.
P und NP sind jedoch nur zwei Beispiele von
Komplexitätsklassen. Andere Klassen ergeben sich etwa bei der
Untersuchung der effizienten Parallelisierbarkeit von Problemen, der
Lösbarkeit durch zufallsgesteuerte oder interaktive Algorithmen, der
approximativen Lösung von Problemen, um nur einige Beispiele zu
nennen.
- Motivation und Einführung
- Turingmaschinen, Berechenbarkeit, Komplexitätsklassen
- Die Klassen P und NP
- Platzkomplexität
- Alternierung und Hierarchien
- Komplexität von Schaltkreisen
- Programmiersprachen und Komplexität
- Interaktive und probabilistische Algorithmen
- Bovet, Crescenzi. Introduction to the Theory of Complexity. Prentice
Hall. New York.1994.
- C. Papadimitriou. Computational Complexity. Addison-Wesley.
Reading. 1995.
- I. Wegener. Komplexitätstheorie: Grenzen der Effizienz von
Algorithmen. Springer. 2003.
- Ein hervorragendes
Vorlesungsskript
von
Oded Goldreich, das weit
mehr, aber auch nicht alles abdeckt, als wir in der Vorlesung
behandeln werden.
- S. Arora und B. Barak.
Complexity Theory: A
Modern Approach
(fast fertige Vorabversion hier).
In diesem Buch sind fast alle Themen der Vorlesung abgedeckt.
- Zur Motivation: Heribert Vollmer, Was leistet die
Komplexitätstheorie für die Praxis?,
Informatik Spektrum 22 Heft 5, 1999.
- Originalarbeiten, die in der Vorlesung nach Bedarf bekannt gegeben werden.
zurück zum
Inhaltsverzeichnis dieser Seite
zurück zum
Inhaltsverzeichnis dieser Seite
Zur Seite der Übung und den Aufgabenblättern
Bei Fragen zu den Übungen wenden Sie sich bitte an
Jan Hoffmann.
zurück zum
Inhaltsverzeichnis dieser Seite