Friedhelm Meyer auf der Heide

Termine

Vorlesung (V2)

Di 11.00 s.t. - 12.45    E2.310        F. Meyer auf der Heide

Übung (Ü2)

Do 16.00      - 17:30    D1.303  2     M. Ziegler

jede ungerade Woche, d.h. abwechselnd mit Effiziente Algorithmen I

Prüfung

(bitte per Email absprechen)

Mo 21.2. 15:30h - 18:00h
Mo 13.3. 15:30h - 18:00h
Mo  3.4. 15:30h - 18:00h

Inhalt der Vorlesung

• Pebble Games on Graphs
• Time versus Space
• PSPACE-completeness
• P-completeness
• Arithmetic is undecidable
• Boolean Circuits
  • Asymptotics
  • Simulating Turing Machines
  • A lower bound for mod₃
• other parallel models of computation

Weitere Informationen

• Die Vorlesung und die Übungen beginnen in der zweiten Vorlesungswoche.
• Erster Vorlesungstermin ist also der 19.10.99 (dort gibt es dann auch bereits den ersten Übungszettel),
• erster Übungstermin ist der 28.10.
• Skript zur Vorlesung. Jetzt neu: Abschnitt 5.4
• Übungsblätter: Blatt 1, Blatt 2, Blatt 3, Blatt 4, Blatt 5, Blatt 6, Blatt 7
• Für das Selber-Löten von Schaltkreisen sind, z.B. bei Conrad Elektronik, eine ganze Reihe von preisgünstigen Standard-Gattern erhältlich.
• 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)
• Musterlösungen zu ausgewählten Übungsaufgaben
• Letztes Semester: Komplexitätstheorie I

Termine

Literatur

• C. H. Papadimitriou: «Computational complexity«, Addison-Wesley, 1994
• Ingo Wegener: «The complexity of Boolean functions«, Wiley-Teubner 1987
• Rüdiger Reischuk: «Komplexitätstheorie« Band 1, Teubner 1999
• Wolfgang Paul: «Komplexitätstheorie«, Teubner 1979