28.10.03
| Einführung in die Vorlesung |
30.10.03
| Konzepte der Komplexitätstheorie: Probleme und Algorithmen - Das Graph-Erreichbarkeitsproblem
- Abschätzung des Wachstums: O-Notation
- MAX FLOW - Problem
- Traveling Salesman - Problem (TSP)
|
31.11.03
| 1. Übungsblatt (ps,pdf) (Abgabe am Freitag, den 07.11.03, 15:00 Uhr)
|
04.11.03
| Konzepte der Komplexitätstheorie: Berechnungsmodell Turing Maschine - Church'sche These
- Turing Maschine
- Komplexitätsmaß: TIME
|
06.11.03
| Konzepte der Komplexitätstheorie: Lineare Speed-Ups - Simulation einer k-Band TM durch eine 1-Band TM
- Das Linear Speed-Up Theorem
- Beweis des Theorems
|
07.11.03
| 2. Übungsblatt (ps,pdf) (Abgabe am Freitag, den 14.11.03, 15:00 Uhr)
|
11.11.03
| Konzepte der Komplexitätstheorie: Raumschranken und Platzsparen - Speicherkomplexitätsklasse: SPACE
- Turingmaschinen mit Ein- und Ausgabeband
- PSPACE
|
13.11.03
| Konzepte der Komplexitätstheorie: Nichtdeterministische Turing Maschinen - Nichtdeterministische Berechnungen
- NTM und probabilistische TM
- NTM und deterministische TM
|
16.11.03
| 3. Übungsblatt (ps, pdf) (Abgabe am Freitag, den 21.11.03, 15:00 Uhr)--Musterlösung zur 3. Aufgabe (ps, pdf)
|
18.11.03
| Konzepte der Komplexitätstheorie: Komplexitätsklassen - Schrankenfunktionen
- Präzise Turing Maschinen
- Wichtige Komplexitätsklassen
- Hierarchie-Theoreme
|
20.11.03
| Konzepte der Komplexitätstheorie: Erreichbarkeitsmethode - NTIME vs. SPACE
- NSPACE vs. TIME
- Erreichbarkeitsmethode
- Satz von Savitch
|
23.11.03
| 4. Übungsblatt (ps, pdf) (Abgabe am Freitag, den 28.11.03, 15:00 Uhr) |
25.11.03
| Konzepte der Komplexitätstheorie: Erreichbarkeitsmethode(2) - Satz von Immerman-Szelepcsenyi
- NSPACE vs. coNSPACE
|
27.11.03
| Die heutige Vorlesung fällt leider aus. |
30.11.03
| 5. Übungsblatt (ps, pdf) (Abgabe am Freitag, den 05.12.03, 15:00 Uhr) |
|
02.12.03
| Konzepte der Komplexitätstheorie: Reduktion - Grundidee
- Logspace Reduktion
- Hamilton Path <= SAT
|
04.12.03
| Konzepte der Komplexitätstheorie: Reduktion - Reachability
- Reduktion durch Verallgemeinerung
- Circuit SAT
- Komposition von Reduktionen
|
08.12.03
| 6. Übungsblatt (ps, pdf) (Abgabe ausnahmsweise am Montag, den 15.12.03, 15:00 Uhr)
Erklärung zu Aufgabe 4.d siehe News
Musterlösung zur dritten Aufgabe (ps, pdf). |
|
09.12.03
| Konzepte der Komplexitätstheorie: Reduktion - K-Vollständigkeit
- Berechnugstabellen-Methode
- P-Vollständigkeit von CIRCUIT VALUE
- P-Vollständigkeit von MONOTONE CIRCUIT VALUE
|
11.12.03
| Die Klassen P und NP: NP Vollständigkeit |
11.12.03
| Die Klassen P und NP: Weitere Characterisierungen von NP - Polynomial entscheidbare Relation
- Polynomial balancierte Relation
- Charakterisierung von NP mittels Relationen
- Polynomiale Zeugnisse
|
15.12.03
| 7. Übungsblatt (ps, pdf) (Abgabe am Mittwoch, den 7.01.04, 15:00 Uhr)
Frohe Weihnachten. |
16.12.03
| Diese Vorlesung fällt leider aus. Die nächste Vorlesung findet am Donnerstag, den 18.12.03 statt. |
18.12.03
| Die Klassen P und NP: Weitere NP-vollständige Probleme - NP-vollständige SAT-Varianten
- 2-SAT gehört zu P
- 2-SAT gehört zu NL
- MAX-2-SAT ist NP-vollständig
- NAE-SAT ist NP-vollständig
|
06.01.04
| Die Klassen P und NP: Weitere NP-vollständige Probleme (2) - Independent Set Problem
- Clique und Node Cover
- Schnitt-Probleme
|
07.01.04
| Die nächste Übung findet am Mittwoch, den 14.01.04 statt. |
08.01.04
| Die Klassen P und NP: Weitere NP-vollständige Probleme (3) - Pfad-Probleme
- Färbungsprobleme
- Matching
|
07.01.04
| 8. Übungsblatt (ps, pdf) (Abgabe am Freitag, den 16.01.04, 15:00 Uhr)
|
13.01.04
| Die Vorlesung fällt leider aus. Die nächste Vorlesung findet am Donnerstag den 15.01.04 statt. |
15.01.04
| Die Klassen P und NP: Weitere NP-vollständige Probleme (4) - Set Cover
- Integer Programming
- Knapsack
- Bin Packing
|
18.01.04
| 9. Übungsblatt (ps, pdf) (Abgabe am Freitag, den 23.01.04, 15:00 Uhr)
Musterlösung (ps, pdf) |
20.01.04
| NP und coNP: - Einführung
- coNP-vollständige Probleme
- ? NP=coNP ?
- Durchschnitt von NP und coNP
- Pratt's Theorem
- Sensation 2002: PRIMES gehört zu P
|
22.01.04
| Die Vorlesung fällt leider aus. |
26.01.04
| Das 10. Übungsblatt wird am Mittwoch, den 28.01. ausgegeben. (Die Ausgabe verschiebt sich auf den 31.01.)
|
27.01.04
| Leider müssen wir die Vorlesung kurzfristig ausfallen lassen. |
28.01.04
| Randomisierte Berechnungen: - Symbolische Determinanten
- Gauß'sche Elimination
- Abschätzung der Zahl der Nullstellen
- Randomisierter Algorithmus PERFECT MATCHING
- Random Walks
- Fermat Test
|
31.01.04
| 10. Übungsblatt (ps, pdf) (Abgabe am Freitag, den 06.02.04, 15:00 Uhr)
|
03.02.04
| Randomisierte Berechnungen(2): - Fehlersituation
- Probabilistische Turing Maschinen
- Klasse PP
- Klasse BPP
- Klasse RPP
- Klasse ZPP
- Landkarte der probabilistischen Komplexiätsklasse
|
05.02.04
| Polynomialzeithierarchie: - Orakel Turing Maschine
- Aufbau der polynomialzeithierarchie
- Charakterisierung
- logische Charakterisierung
|
08.02.04
| 11. Übungsblatt (ps, pdf) (Abgabe am Freitag, den 13.02.04, 15:00 Uhr)
Das Zustzblatt wird morgen ausgegeben.
Hinweis: In den Aufgaben werden nur QBFs in Pränez Normal Form betrachtet, in denen keine freie (also unquantifizierte) Variablen auftreten. |
09.02.04
| 12. Übungsblatt --- Zusatzblatt(ps, pdf) (Abgabe am Dienstag, den 17.02.04, 15:00 Uhr)
|
10.02.04
| Polynomialzeithierarchie (2): - Kollabiert Polynomialzeithierarchie?
- Minimum Circuit
- Charakterisierung
- Vollständige Probleme
- Verhältnis zu PSPACE
- Verhältnis zu BPP
- Landkarte der Polynomialzeithierarchie
|
12.02.04
| Approximation: - e-Approximation
- NODE-COVER
- MAXIMUM SATISFIABILITY
- Traveling Salesman Problem
- Knapsack
- Polynomiale Approximation
- Approximationskomplexitätsklassen
|
17.02.04
| Ploynomiale Schaltkreise: - Schaltkreiskomplexität
- Typische Schaltkreisgröße
- Schaltkreisfamilien
- Polynomiale Schaltkreisfamilien
- Uniforme Polynomiale Schaltkreise
- Nichtuniforme Turing Maschinen
- Polynomiale Schaltkreise für BPP
|
19.02.04
| P versus NP: - Landkarte von NP
- NP-vollständige unäre Sprachen
- Dünnbesetzte Sprachen
|
