Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik
der Ludwig-Maximilians-Universität München
Vorlesung im Hauptstudium: Komplexitätstheorie (WS 06/07)
- Vorlesung:
- Jan Johannsen, 4-stündig
- Zeit und Ort: Di 8:30 - 10 s.t., Raum 1.31 ; Fr 10 - 12 c.t., Raum 1.39
(Oettingenstr. 67)
- Beginn: 17. 10. 2006
- Übung:
- Hermann Gruber, 2-stündig
- Zeit und Ort der Übung: Do 16 - 18 c.t., Raum 1.43
(Oettingenstr. 67)
- Beginn: 26. 10. 2006
- Vorkenntnisse:
-
Informatik IV
-
Effiziente Algorithmen 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
- Kommunikationskomplexität
- Bovet, Crescenzi. Introduction to the Theory of Complexity. Prentice
Hall. New York.1994.
Dieses Buch liegt ab sofort zur kurzzeitigen Ausleihe
in Raum Z1.05, dem Sekretariat des Lehrstuhls Theoretische
Informatik, bereit.
Wer es ausleiht sollte es spätestens zur Vorlesung wieder
mitbringen und bei Bedarf an seine Mitstudenten abgeben.
Die Bibliothek hat inzwischen ebenfalls ein Exemplar angeschafft.
- 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.
- Nochwas zur Motivation: Stephen Cook
(ja, der Cook) schreibt in der Jubiläumsausgabe des Journal of the ACM
(Vol. 50 No. 1) über
The Importance of the P versus NP Question.
- Originalarbeiten, die in der Vorlesung nach Bedarf bekannt gegeben werden.
zurück zum
Inhaltsverzeichnis dieser Seite
-
Vorlesung, 20.10.2006, Skriptum von Hendrik Grallert
-
Vorlesung, 24.10.2006, Skriptum
und Ergänzung von Kuniko Yoshida
-
Vorlesung, 27.10.2006, Skriptum von Oliver Friedmann
-
Vorlesung, 31.10.2006, Skriptum von Andreas Abel
-
Vorlesung, 07.11.2006, Skriptum von Sebastian Jost
-
Vorlesung, 24.11.2006, Skriptum von Hermann Gruber
-
Vorlesung, 09.01.2007, Skriptum
von Kuniko Yoshida
- Zur Motivation: Scott Aaronson,
ten reasons to believe in P!=NP
- Diskussionsforum
zu Veranstaltungen der LFE Theoretische Informatik auf
die-informatiker.net.
- The Complexity Zoo
von Scott Aaronson,
Greg Kuperberg und anderen.
zurück zum
Inhaltsverzeichnis dieser Seite
Zur Seite der Übung und den Aufgabenblättern
Bei Fragen zu den Übungen wenden Sie sich bitte an
Hermann Gruber.
zurück zum
Inhaltsverzeichnis dieser Seite