Kurs Komplexitätstheorie (Sommersemester 2018)

Prof. Dr. Thomas Schneider

K4, Modulbereich Theorie, Profile SQ, KIKR

Di 12–14 SH D1020
Do 14–16 SFG 2030


Kurzbeschreibung

Die Komplexitätstheorie beschäftigt sich mit der inhärenten Komplexität von Berechnungsproblemen: wie viel Zeit (oder andere Ressourcen) benötigt man, um ein gegebenes Problem zu lösen—unabhängig davon, wie clever der Algorithmus ist, den man verwendet? Es geht also um die Grenzen der Berechenbarkeit unter beschränkten Ressourcen. Damit stellt die Komplexitätstheorie eine wichtige Grundlage für den Entwurf und das Verständnis von effizienten Algorithmen dar. Ausserdem versucht sie, die natürliche Neugierde nach dem in der Informatik prinzipiell machbaren zu befriedigen. Die Vorlesung wird sich mit folgenden Themen beschäftigen:

Folien

Kapitel 1: Einführung   4 pro Seite    
Kapitel 2: Turingmaschinen   4 pro Seite    
Kapitel 3: P versus NP   4 pro Seite    
Kapitel 4: Mehr Ressourcen, mehr Möglichkeiten?   4 pro Seite    
Kapitel 5: Platzkomplexität   4 pro Seite    
Kapitel 6: Schaltkreise   4 pro Seite    
Kapitel 7: Orakel   4 pro Seite   (bis einschließlich 3. 7.)  
Zusatzthema: Primzahltest in Polynomialzeit   4 pro Seite   (vom 3. 7.)  

Übungsaufgaben

Übungsblatt 1    (Abgabe am 17. 4. in Stud.IP, Besprechung am 19. 4.)
Übungsblatt 2    (Abgabe am 6. 5. in Stud.IP, Besprechung am 8. 5.)
Übungsblatt 3    (Abgabe am 22. 5. in Stud.IP, Besprechung am 24. 5.)
Übungsblatt 4    (Abgabe am 5. 6. in Stud.IP, Besprechung am 7. 6.)
Übungsblatt 5    (Abgabe am 19. 6. in Stud.IP, Besprechung am 21. 6.)
Übungsblatt 6    (Abgabe am 3. 7. in Stud.IP, Besprechung am 5. 7.)

Prüfungen

Die Prüfungsmodalitäten werden in der Vorlesung bekanntgegeben.

Literatur


AG Theorie der künstlichen Intelligenz 2. Juli 2018  Thomas Schneider
Valid HTML 4.0 Transitional