empty
Lehre empty
empty
empty

Lehrveranstaltungen Wintersemester 2009/2010

 
Alg. für NP-harte Probleme,
Einführung in die Komplexitätstheorie



Algorithmen für NP-harte Probleme (4 SWS) mit Übungen (2 SWS)
ab 5. Semester


Vorlesung Mo. 15.45-17.15 und Do. 14.00-15.30 jeweils in Raum 1057N
Übungen Mo. 17.20-18.50 in Raum 1057N

NP-harte Probleme können nach heutigem Wissen nicht in polynomieller Zeit auf einem üblichen Rechner gelöst werden. Ungeachtet dessen treten solche Probleme überaus häufig in der Praxis auf, z.B. bei vielen Planungsaufgaben, und es ist von großer ökonomischer Bedeutung, sie doch noch zu lösen, zumindest "so gut wie es geht". Die Vorlesung behandelt Methoden der Algorithmentheorie, die hierfür entwickelt wurden. Einige Stichpunkte: Approximationsalgorithmen, Branch-and-Bound, Parametrisierung. Es werden auch Grenzen dieser Methoden aufgezeigt.

     Skript:

Ausgabe

Postscript
PDF

19.10.09

Kapitel 1-3
Kapitel 1-3
29.10.09

Kapitel 1-8
Kapitel 1-8
09.12.09

Kapitel 1-11
Kapitel 1-11
30.11.09

Errata
Errata
11.02.10

Kapitel 1-11 (neu)
Kapitel 1-11 (neu)


     Übungen:

Ausgabe
Abgabe
Postscript
PDF

19.10.09
22.10.09
Übung 1
Übung 1
22.10.09
28.10.09
Übung 2
Übung 2
28.10.09
02.11.09
Übung 3
Übung 3
02.11.09
09.11.09
Übung 4
Übung 4
09.11.09
16.11.09
Übung 5
Übung 5
16.11.09
23.11.09
Übung 6
Übung 6
23.11.09
30.11.09
Übung 7
Übung 7
07.12.09
14.12.09
Übung 8
Übung 8
14.12.09
21.12.09
Übung 9
Übung 9
21.12.09
11.01.10
Übung 10
Übung 10
11.01.10
18.01.10
Übung 11
Übung 11
21.01.10
27.01.10
Übung 12
Übung 12
25.01.10
01.02.10
Übung 13
Übung 13


     Zusatzmaterial:

Ausgabe

Postscript
PDF

05.11.09

Lösung zu Aufgabe 2.4
Lösung zu Aufgabe 2.4





Einführung in die Komplexitätstheorie (2 SWS) mit Übungen (1 SWS)
ab 5. Semester


Vorlesung Mo. 8.15-9.45 in Raum 1057N
Übungen Di. 14.00-15.30 (14-tägig) in Raum 1058N

Aufbauend auf den in den Grundvorlesungen Einführung in die Theoretische Informatik und Informatik III gelegten Grundlagen werden wichtige Aspekte der Komplexitätstheorie behandelt. Das Anliegen der Komplexitätstheorie ist es, die inhärente Schwierigkeit von Berechnungsproblemen zu untersuchen und somit die prinzipiellen Grenzen effizienter Algorithmen zu beleuchten.

     Skript:

Ausgabe

Postscript
PDF
19.10.09

Kapitel 1-8
Kapitel 1-8

11.01.10

Kapitel 1-10
Kapitel 1-10



     Übungen:

Ausgabe
Abgabe
Postscript
PDF

19.10.09
23.10.09
Übung 1
Übung 1
26.10.09
02.11.09
Übung 2
Übung 2
10.11.09
16.11.09
Übung 3
Übung 3
23.11.09
30.11.09
Übung 4
Übung 4
07.12.09
14.12.09
Übung 5
Übung 5
21.12.09
11.01.10
Übung 6
Übung 6
18.01.09
01.02.10
Übung 7
Übung 7




Bitte beachten Sie, dass Sie sich ggf. in Studis anmelden müssen, damit Ihre Leistungen anerkannt werden können. Das Programm Studis und Anmeldungen auf unserer Homepage stehen in keinerlei Zusammenhang. Das gesamte Lehrangebot der Informatik kann im kommentierten Vorlesungsverzeichnis eingesehen werden.
empty