Einführung in die
Algorithmen und Komplexität (SS 2003)

Inhalt

• Klassen P und NP
• NP-Vollständigkeit
• Satz von Cook
• Reduktionen
• Approximationsalgorithmen
• randomisierte Algorithmen
• randomisierte Komplexitätsklassen
• kurze Einführung in die Kryptographie

Klausur

• Termin : Montag, der 08. März 2004
• Ort      : AudiMax
• Uhrzeit : 09:00 Uhr

Optional mitgebracht werden kann:

• ein beidseitig handbeschriebener DIN A4 Zettel mit eigenen Notizen

Die Online-Anmeldung wird ab Anfang Februar freigeschaltet: Online-Anmeldung (und auch Abmeldung)

Ergebnis der 1. Klausur

• Klausureinsicht: 15.09.03 um 15:00 Uhr im F0.530.

Ergebnis der 2. Klausur

• Klausureinsicht: Freitag, den 17.10.2003, 14:30-15:30 Uhr in F0.231

Ergebnis der 3. Klausur

• Klausureinsicht: 02.04.2003 von 14:00-15:00 Uhr in F1.110

Zur Ansicht: Die 1. Klausur

Vorlesung:
Mo. 11:00 - 13:00 Raum C1

Zentralübung:
Mo. 13:00 - 14:00 Raum C1

Die nächste Zentralübung ist am 23.06.2003.

Übungen

In den abschließenden Tutorien des Semesters soll die Gelegenheit gegeben werden, offene Fragen zu EBFS/Auk zu klären. Zur besseren Vorbereitung der Tutorien werden deshalb alle Studenten gebeten, ihre Fragen schon vorher per Mail an den betreffenden Tutor zu schicken.

Nummer	Zeit	Raum	Betreuer
Ü1/Ü2	Di 07-09 g/u	N3.206	Olaf Bonorden
Ü3/Ü4	Di 07-09 g/u	D1.303	Eike Schwindt
Ü5/Ü6	Di 09-11 g/u	N3.206	Olaf Bonorden
Ü7/Ü8	Di 09-11 g/u	D1.303	Marcel Ackermann
Ü9/Ü10	Mi 14-16 g/u	E2.316	Daniel Kuntze
Ü11/Ü12	Mi 16-18 g/u	E2.316	Christian Soltenborn

Skript

Im Laufe des Semesters wird an dieser Stelle ein Skript erscheinen. Dieses Skript kann jedoch das Lesen mindestens eines der unten aufgeführten Lehrbücher nicht ersetzen.

• Einführung und Zeitkomplexität
• Die Klasse P
• Verifizierer, nichtdeterministische Turingmaschinen und die Klasse NP
• Exkurs über Entscheidungs- und Optimierungsprobleme
• Polynomielle Reduktionen, NP-vollständigkeit und der Satz von Cook-Levin
• Beispiele für NP-vollständige Sprachen
• Approximationsalgorithmen

An dieser Stelle erscheinen im Laufe des Semesters die Übungen und die Musterlösungen.

Übung	Musterlösung
1.Übung	1.Musterlösung
2.Übung	2.Musterlösung
3.Übung (korrigierte Version)	3.Musterlösung
4.Übung (mit Knotenüberdeckung)	4.Musterlösung
5.Übung	5.Musterlösung
6.Übung	6.Musterlösung
7.Übung

Prüfung

Im Anschluß an die Vorlesung "Komplexität und Algorithmen" im kommenden Sommersemester wird es eine Prüfung über beide Vorlesungen geben. Die Prüfung erfolgt durch eine Klausur. Wenn Sie aktiv in den Übungen mitarbeiten, können Sie Ihre Klausurnote wie folgt verbessern:

• Erreichen Sie mindestens 50% der Punkte der Übungen, so verbessert sich die Note um 1/3.
• Erreichen Sie mindestens 75% der Punkte der Übungen, so verbessert sich die Note um 2/3.

WICHTIG: Eine Verbesserung der Klausurnote 5 (nicht bestanden) ist nicht möglich.

Literatur

• Introduction to the Theory of Computation, Michael Sipser, PWS, 1997.
• Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addsion Wesley, 2. Auflage 2001.
• Elements of the Theory of Computation, Harry R. Lewis, Christos H. Papadimitriou, Prentice Hall, 2. Auflage 1998.
• Theoretische Informatk - kurzgefaßt, Uwe Schöning, Spektrum, akad. Verlag, Heidelberg, 3. Auflage 1997.
• Theoretische Informatik - Eine algorithmenorientierte Einführung, Ingo Wegener, Teubner, 1993.

Die Vorlesung wird sich hauptsächlich an den drei zuerst genannten Büchern orientieren. Besonders empfohlen wird das Buch von M.Sipser.

Gruppenarbeit:

Wir fordern Sie ausdrücklich auf, in kleinen Gruppen (2-4 Personen) gemeinsam die Vorlesung nachzuarbeiten und die Übungen zu bearbeiten. Für den Lernerfolg (und den Spaß am Studieren) ist das sehr förderlich. Sie dürfen Ihre Übungen auch in solchen Gruppen abgeben.