-
Vorlesung (V2)
Mo 11.15 - 12.45 N3.206 F. Meyer auf der Heide
-
Übung (Ü1)
Mo 10:15 - 11:00 N3.206 1 M. Ziegler
Mo 13:00 - 13:45 N3.206 2 M. Ziegler
-
Prüfung
Wer nach der DPO 4 oder der neuen Lehramtsstudienordnung studiert,
kann im Anschluß an »Komplexitätstheorie II« benotete, mündliche,
ca. 30-minütige Prüfungen bei Prof. Meyer auf der Heide ablegen.
Für Studierende in anderen Prüfungsordnungen stehen nach dem Ende
des SS2001 Termine für mündliche Prüfungen über »Komplexitätstheorie
I+II« zur Verfügung.
Inhalt der Vorlesung
In Fortsetzung von Komplexitätstheorie I
werden u.a. folgende Themen behandelt:
- Pebble Games on Graphs
- Time versus Space
- P-completeness
- Boolean Circuits
- Asymptotics
- Simulating Turing Machines
- A lower bound for mod3
- Other parallel models of computation
Weitere Informationen
- Zur Vorlesung gibt es bereits ein Skript,
mit Updates von Seiten 9 bis 12,
Seite 14, Seiten 21+22
und Seiten 33-38.
- Übungszettel werden jeweils Donnerstags bis 16:00 herausgegeben.
Zu ihrer Bearbeitung stehen (mit Wochenende) 8 Tage zur
Verfügung: sie sind abzugeben
bis zum darauffolgenden Freitag 14:00.
Dafür steht im D3-Flur ein Kasten bereit;
elektronische Lösungen bitte per
Email.
Rückgabe der Korrekturen und Besprechung
am darauffolgenden Montag in den Übungen.
-
Für
Blatt 1,
Blatt 2,
Blatt 3,
Blatt 4,
Blatt 4,
Blatt 6,
Blatt 7,
Blatt 8,
Blatt 9,
Blatt 10
ist der Zug bereits abgefahren.
- Bei Springer kann man nachlesen,
was die Komplexitätstheorie für die Praxis leistet
(geht allerdings nur beim Surfen von der Domäne uni-paderborn.de)
- Als nützliche und interessante
Parallelveranstaltung gibt es dieses Semester
die Algebraische Komplexitätstheorie
von Prof. Bürgisser.
- Sprechstunde: Mittwochs 13:30-14:30 im F1.301 sowie nach Vereinbarung
Literatur
- C. H. Papadimitriou:
«Computational complexity», Addison-Wesley, 1994
- Rüdiger Reischuk:
«Komplexitätstheorie»
Band 1, Teubner 1999
-
Ingo Wegener
«The complexity of Boolean functions»
Wiley-Teubner 1987
-
Wolfgang Paul
«Komplexitätstheorie«
Teuber 1979
Zur Vorlesung gibt es einen Semesterapparat in der Bibliothek, in dem einige
der oben angegebenen Bücher zu finden sind.
Martin Ziegler