Komplexität von Algorithmen (SS 2006)

• Umfang: TV 2 + TU 1
• Wert: 4 CP
• Prüfungsform: Klausur (75 min); Klausur zusammen mit „Grundlagen der Theoretischen Informatik“ (2 x 75 min = 150 min)
• Bachelor Informatik: Pflichtkatalog
• Mathematik mit Studienrichtung Informatik: Hauptstudium

In dieser Vorlesung beschäftigen wir uns mit der Frage, welche Berechnungsprobleme effizient algorithmisch lösbar sind. Dazu werden wir die Komplexitätsmaße Laufzeit und Speicherbedarf formal einfüren und untersuchen. Eine zentrale Rolle werden dabei die Komplexitätsklassen P und NP sowie sogenannte NP-vollständige Probleme spielen. Dies sind Probleme, für die weder ein effizienter Algorithmus bekannt ist noch bewiesen wurde, dass keiner existieren kann.

NP-vollständige Probleme kommen in vielen Bereichen der Informatik vor (zum Beispiel VLSI-Design, Netzwerk-Optimierung und Operations-Research) Erstaunlicherweise zeigt sich, dass alle diese Probleme äquivalent sind in dem Sinne, dass sie alle effizient lösbar sind, wenn man nur für eines von ihnen einen effizienten Algorithmus entdeckt.

Gliederung:

• Raum- und Zeitkomplexität
• Beziehungen zwischen den Komplexitätsklassen
• Die Hierarchiesätze
• Die Klasse P
• Die Klasse NP
• NP-Vollständigkeit
• Der Satz von Cook
• Weitere NP-vollständige Probleme
• Approximierbarkeit
• Das Problem des Handlungsreisenden
• Das Partitionierungsproblem.

Diese Lehrveranstaltung baut auf die Inhalte der Lehrveranstaltung „Grundlagen der Theoretischen Informatik“ auf.

1. Michael Sipser: Introduction to the Theory of Computation (Second Edition, US-Ausgabe). PWS Publishing Company, 2005.
2. Christos Papadimitriou: Computational Complexity. Addison-Wesley, 1994.
3. Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela und Marco Protasi: Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999.
4. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie (Zweite Auflage). Pearson Studium, 2002.
5. Michael R. Garey und David S. Johnson: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, 1979.

Zur Vorlesung „Komplexität von Algorithmen“ im Sommersemester 2005 wurde ein Skript veröffentlicht. Dieses kann parallel zur aktuellen Vorlesung verwendet werden. Aufgrund des Wechsels der Lehrperson wird die Vorlesung jedoch an vielen Stellen von diesem Skript abweichen. Eine aktualisierte Version des Skriptes wird in diesem Semester voraussichtlich nicht veröffentlicht.

Woche	Datum der Vorlesung	Inhalt in Stichworten	Literatur	Materialien
1	12.4.2006	Zeitbedarf, Zeitaufwand, Platzbedarf, Platzaufwand, O-Notation, o-Notation, TIME, SPACE, Bandreduktion, Speedup, Alphabetreduktion.	[1] 247–255, 303–305.	Organisatorische Hinweise Übung 1 Ergänzung zur Vorlesung
			[2] 29–36, 139‒142.
2	19.4.2006	Nichtdeterministische Turingmaschinen, NTIME, NSPACE, Beziehung zwischen NTIME und TIME, Normalisierung von nichtdeterministischen Turingmaschinen auf Verzweigungsgrad 2, Beziehung zwischen NTIME und SPACE.	[1] 150–152, 255–256, 267, 303–304.	Übung 2
			[2] 45–50, 139–142, 147–148.
			[4] 350–352.
3	26.4.2006	Beziehung zwischen TIME und SPACE, Platzkonstruierbarkeit, Zeitkonstruierbarkeit, Beziehung zwischen NSPACE und TIME, Beziehung zwischen NSPACE und SPACE (Satz von Savitch), Platzhierarchiesatz.	[1] 305–307, 336–340.	Übung 3
			[2] 145–151.
4	3.5.2006	NEXP, EXP, NPSPACE, PSPACE, NP, P, NL, L, Beziehungen zwischen diesen Klassen, Robustheit von P, Abschluß von P unter Vereinigung, Schnitt und Komplement, PATH und FEVAL liegen in P, polynomielle Überprüfbarkeit, NP ist die Klasse der polynomiell überprüfbaren Sprachen.	[1] 256–258, 264–269, 308–309, 320–321.	Übung 4
			[2] 141–146, 181–183.
			[4] 424–430.
5	10.5.2006	CLIQUE, HAMPATH und SAT liegen in NP, das P-NP-Problem, polynomielle Reduzierbarkeit und ihre Eigenschaften, NP-Vollständigkeit.	[1] 264–265, 267–273, 276.	Übung 5
			[2] 159–161, 165–166, 181–183.
			[4] 430–433.
			[5] 34–38.
6	17.5.2006	Tableaus, SAT ist NP-vollständig.	[1] 276–282.	Übung 6
			[4] 438–443.
			[5] 38–44.
7	24.5.2006	3SAT und CLIQUE sind NP-vollständig.	[1] 274-275, 282–283.	Übung 7
			[2] 183, 188-190.
			[4] 453–454.
			[5] 45–50, 53–56.
8	31.5.2006	HAMPATH und HAMCIRC sind NP-vollständig	[1] 286-291.	Übung 8
			[2] 193-198.
			[4] 462–466.
			[5] 56–60.
9	14.6.2006	SUBSET-SUM, PART, KNAPSACK, TSP und BIN-PACKING sind NP-vollständig	[1] 291-294.	Übung 9
			[2] 198, 202-206.
			[5] 60-62.
10	21.6.2006	Optimierungsprobleme, MinTSP, die Klassen PO und NPO.	[3] 22-30.	Übung 10
11	28.6.2006	Approximationsalgorithmen, MinTSP ist nicht c-approximierbar, MinMTSP, Begriffe aus der Graphentheorie.	[3] 87-96.	Übung 11
12	5.7.2006	Approximationsalgorithmus TreeTSP für MinMTSP, MinMTSP ist 2-approximierbar, Approximationsalgorithmus von Christofides für MinMTSP, MinMTSP ist 3/2-approximierbar.	[3] 96-100.	Übung 12
13	12.7.2006	MinPART, Approximationsalgorithmus PartAS(r), MinPART ist r-approximierbar, die Klassen PTAS und APX, MaxSAT, Approximationsalgorithmus GSAT, MaxSAT ist 2-approximierbar.	[3] 93, 102-105.	Übung 13
14	19.7.2006	Zusammenfassung, Überblick und Ausblick.		–

Vorlesung:

mittwochs, 10.30‒12.00 Uhr, Raum F102, Hauptgebäude.

Übungen:

Die Übungen werden in fünf Gruppen abgehalten und finden ab Donnerstag, den 13. April 2006 statt.

• Übung A: donnerstags, 9 Uhr bis 9.45 Uhr, Raum F309 (43 Plätze), Michael Bauland
• Übung B: donnerstags, 10.15 Uhr bis 11 Uhr, Raum F442 (85 Plätze), Michael Bauland
• Übung C: dienstags, 16.15 Uhr bis 17 Uhr, Raum F428 (85 Plätze), Henning Schnoor
• Übung D: mittwochs, 8 Uhr bis 8.45 Uhr, Raum G117 (20 Plätze), Henning Schnoor
• Übung E: mittwochs, 8 Uhr bis 8.45 Uhr, Raum F107 (94 Plätze), Arne Meier

Die Übungen A und B fallen am 25. Mai 2006 wegen eines Feiertages aus, weichen Sie bitte auf die Übung C (am 30. Mai 2006), die Übung D oder die Übung E (beide am 31. Mai 2006) aus.

Die Übungen C, D und E finden am 25. Juli 2006 beziehungsweise am 26. Juli 2006 wegen des Endes der Vorlesungszeit nicht statt, weichen Sie bitte auf die Übung A oder die Übung B (beide am 20. Juli 2006) aus.

In diesem Semester findet eine Testatregelung Anwendung.

Jeder Studierende kann sich für diese Testatleistungen anmelden und bekommt im Verlauf des Semesters per E-Mail eine Reihe von Übungsaufgaben zugesandt. Nach drei bis vier Wochen erfolgt die schriftliche Abgabe der zu diesen Aufgaben gehörigen Lösungen. Etwa eine Woche später werden diese Lösungen bei einem der Institutsmitarbeiter mündlich vorgestellt und von diesem bewertet.

Sowohl für die schriftliche Ausarbeitung als auch die mündliche Vorstellung der Aufgaben werden Punkte vergeben. Wird dabei eine festgelegte Mindestpunktzahl erreicht, so gilt das Testat als bestanden. In der Klausur wird dem jeweiligen Studierenden dann (sofern die Klausur bestanden wurde) ein Notenbonus von 0,3 gewährt. Dies ist allerdings nur für Studierende von Studiengängen möglich, deren Prüfungsordnung eine solche Regelung erlaubt.

Die Testataufgaben werden allen angemeldeten Studierenden am 19. Juni 2006 per E-Mail zugesandt. Die Lösungen zu diesen Aufgaben sind bis zum 6. Juli 2006 in schriftlicher Form im Institut für Theoretische Informatik abzugeben. Zu den in der folgenden Tabelle genannten Terminen finden die mündlichen Vorstellungen dieser Lösungen statt. Sollten Sie Ihren Termin verlegen wollen, so wenden Sie sich bitte direkt an den Ihnen zugeordneten Mitarbeiter.

Weitere Details zu den Testaten werden zusammen mit den Aufgaben veröffentlicht.