Hasso-Plattner-Institut
  
    • de
 

Vorlesung und Übung

(Wintersemester 2003/2004)

FBIV- Theoretische Informatik
Universität Trier


Allgemeines
News
Live-Übertragung
Vorlesungen und Übungsaufgaben
Literatur


Ziel der Komplexitätstheorie ist die Quantifizierung von Computerressourcen (Rechenzeit, Speicherplatz, Hardwareaufwand, Kommunikationsaufwand,...), die zur algorithmischen Lösung konkreter Probleme bzw. von Problemklassen benötigt werden. Die Vorlesung, die sich an Studenten des Informatik- bzw. Mathematikhauptstudiums wendet und Kernvorlesung für den Bereich theoretischen Informatik ist, bietet eine fundierte Einführung in die Komplexitätstheorie. Schwerpunktmäßig wird die Bedeutung komplexitätstheoretischer Aussagen für den Algorithmenentwurf herausgearbeitet.

Die Wiederholung der Rücksprache findet am Freitag, den 23.04.04 ab 14:00 Uhr (H412) statt.
Die Anmeldung kann ab sofort über LCMS erfolgen.

Vorlesungen und Übungsaufgaben:
Die Vorlesung wird mittels Tele-TASK aufgezeichnet und kann online abgerufen werden. Zu den Vorlesungszeiten findet eine Live-Übertragung der Vorlesung statt.   

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
  • Cook'sches Theorem
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


Allgemeines:

Fernstudenten (ULI) können dieser Seite weitergehende Informationen entnehmen.   


Vorlesung: Dienstag und Donnerstag von 8:00 -- 10:00 Uhr, Raum H406.
Übung: Mittwoch 8:00 -- 10:00 Uhr, Raum HZ 203.

Die Voraussetzung für einen Scheinerwerb ist

  • die aktive Teilnahme an der Übung,
  • die erfolgreiche Bearbeitung von 50% der Übungsaufgaben in der ersten bzw. zweiten Hälfte des Semesters, sowie
  • eine Rücksprache am Ende des Semesters.

 

Die Vorlesung wird mittels Tele-TASK aufgezeichnet und kann online abgerufen werden. Zur Vorlesung ist ein Skript vorhanden.  
Bei Fragen oder Anmerkungen wenden Sie sich bitte an Volker Klotz, H415, Tel.: 2837.