HEINZ NIXDORF INSTITUT
Universität Paderborn
Theoretische Informatik
AG Meyer auf der Heide

Komplexitätstheorie II

Sommersemester 2003

Friedhelm Meyer auf der Heide

 

Navigation     [Aktuelles]   [Termine]   [Inhalt]   [Skript]   [Übungen]
    Zurück zur AG Seite mit dem Lehrangebot   [Teaching]
 


Aktuelles

Prüfungstermine !!!  

No tutorial on June 10 !  

Form now on the tutorials will start at 1 o'clock.  

Until further notice, the lecture will be held in English!  

Terminänderung! Die Übung findet dienstags statt, Ort und Zeit bleiben gleich.  

Raumänderung! Vorlesung und Übung finden in Raum F1.110 statt.  

Die erste Übung findet am 29.04.2003 zur angegebenen Zeit statt.  

Die erste Vorlesung findet am 28.04.2003 zur angegebenen Zeit statt.  


Termine

Vorlesung (V2)        
  Montag   09:15 - 10:45     F1.110     Friedhelm Meyer auf der Heide
Übung (Ü1)        
  Dienstag   13:00 - 13:45     F1.110     Valentina Damerow
 

Prüfungstermine     01. August 2003   26. September 2003
    09:00    
    10:00    
    11:30    
 

Anmeldung zur mündlichen Prüfung bei Friedhelm Meyer auf der Heide (Sprechstunde Mittwoch 13-14 Uhr) oder Valentina Damerow (jederzeit). Dauer und Art der Prüfung je nach DPO bzw LPO verschieden.  


Inhalt der Vorlesung

Komplexitätstheorie II ist die Fortsetzung von Komplexitätstheorie I.
Es 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 mod 3
  • Other parallel models of computation

Literatur

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

[Anfang der Seite]  

 

Weitere Informationen

 

Begleitmaterial zur Vorlesung     ps   ps.gz   pdf
Time versus Space     Lecture nodes on a course by Oded Goldreich  
Boolean Circuits     Lecture nodes on a course by Uri Zwick  
Carry Look Ahead Adder     Lecture nodes on a course by Cetin Kaya Koc  

 

Übungsblätter   Abgabe   (Gruppenabgabe ist möglich und erwünscht) 
  Blatt 01     Präsenz-Übung (keine Abgabe)     ps   pdf
  Blatt 02     Montag, 05.05. in der Vorlesung     ps   pdf
  Blatt 03     Montag, 12.05. in der Vorlesung     ps   pdf
  Blatt 04     Montag, 19.05. in der Vorlesung     ps   pdf
  Blatt 05     Montag, 26.05. in der Vorlesung     ps   pdf
  Blatt 06     Montag, 02.06. in der Vorlesung     ps   pdf
  Blatt 07     Montag, 16.06. in der Vorlesung     ps   pdf
  Blatt 08     Montag, 23.06. in der Vorlesung     ps   pdf
  Blatt 09     Montag, 30.06. in der Vorlesung     ps   pdf
  Blatt 10     Montag, 07.07. in der Vorlesung     ps   pdf
  Blatt 11     Montag, 14.07. in der Vorlesung     ps   pdf
  Blatt 12     Montag, 21.07. in der Vorlesung     ps   pdf
  Blatt 13     Montag, 28.07. in der Vorlesung     ps   pdf
 

 

[Anfang der Seite]  

 

Prüfung

Wer nach 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 SS 2003 Termine für mündliche Prüfungen über «Komplexitätstheorie I+II» zur Verfügung.  

 

 

Valentina Damerow