Approximationsalgorithmen
Wintersemester 2007/2008
Prof. Dr. Manfred Kunde 
[Mitteilungen] [Inhalte] [Termine] [Scheinerhalt] [Literatur] [Materialien]
MitteilungenDie Studierenden mit den folgenden Matrikelnummern sind für die Klausur am 3.3. um 13 Uhr im K-Hs zugelassen:
25187 26463 30454 32690 32878
33351 34719 34889 35333 36552
36625 36745 37033 38362 38665
Sollten Sie auf der Liste fehlen, melden Sie sich bitte möglichst bald bei Michael Brinkmeier.
Inhalte- Grundlagen
- Approximation mit absoluter Gütegarantie
- Konzepte
- Knotenfärbung
- Schwierigkeit der Approximation des Rucksackproblems
- Approximation mit relativer Gütegarantie
- Konzepte
- Traveling Salesperson
- Knotenfärbungen und Independent Set
- Approximationsschemata
- Pseudopolynomielle Algorithmen
- Strenge Approximationsschemata
- Unmöglichkeitsergebnisse für Approximationsschemata
- Techniken zur Approximation
Termine- Vorlesung (Prof. Dr. M. Kunde)
- Dienstag, 11:00-12:30 Uhr, Sr HU 211/212
- Übung (Dr. M. Brinkmeier)
- Dienstag (U), 13:00-14:30, Sr HU 211/212
- Freitag (G), 13:00-14:30, Sr HU 211/212
Kriterien für den ScheinerhaltDer Schein Approximationsalgorithmen kann in zwei Varianten erworben werden, einer vierstündigen (2V+1Ü) und einer dreistündigen (2V).
Übersicht über die Schein-Kriterien
Scheinvariante
| min. Anwesenheiten in der Vorlesung
| min. Anwesenheiten in der Übung
| Übungsprogramm
| Klausur
| 2V + 1Ü
| 7 (von 15)
| 3 (von 6)
| Ja
| Ja
| 2V
| 7 (von 15)
| -
| -
| Ja
|
Erläuterungen zu den Kriterien
- Anwesenheiten: Bei den ogen angegebenen Zahlen handelt es sich um die minimale Anzahl an Teilnahmen für die jeweilige Veranstaltungsform.
- Klausur: Die Klausur muss bestanden werden. Für die Zulassung zur Klausur ist die Teilnahme an mindestens 7 (von 15) Vorlesungen erforderlich.
- Übungsprogramm: Insgesamt werden 6 Übungsblätter ausgegeben werden, die in Gruppen mit bis zu zwei Mitgliedern bearbeitet werden können. Um das Übungsprogramm erfolgreich zu absolvieren, müssen die folgenden Kriterien erfüllt sein:
- Mindestens vier Aufgaben der Übungsblätter 1-6 müssen erfolgreich bearbeitet worden sein.
- Mindestens eine Aufgabe der Übungsblätter 1 und 2 muss erfolgreich bearbeitet worden sein.
- Mindestens eine Aufgabe der Übungsblätter 3 und 4 muss erfolgreich bearbeitet worden sein.
- Mindestens eine Aufgabe der Übungsblätter 5 und 6 muss erfolgreich bearbeitet worden sein.
Erfolgreich heisst dabei nicht vollständig richtig, sondern lediglich sinnvoll und im Wesentlichen korrekt.
Die Übungsblätter werden jeweils Dienstags in den ungeraden Wochen als PDF zur Verfügung gestellt. Ihre Veröffentlichung wird über die ITI News bekannt gegeben.
- Scheinvariante: Die mögliche Scheinvariante wird, abhängig von den erbrachten Vorleistungen, vor der Klausur bekannt gegeben. D.h. insbesondere, dass Studierende, die nicht genügend Aufgaben gelöst haben, trotzdem den 3V Schein erhalten können.
Wiederholer
Für Studierende, die bereits zu einer "Approximationsalgorithmen"-Klausur zugelassen waren und nicht bestanden haben, gibt es zwei
Möglichkeiten:
- 2V+1Ü: Erfolgreiche Teilnahme an den Übungen und Klausur (Vorlesungsteilnahme entfällt)
- 2V: Teilnahme an der Klausur.
Literatur und Links- Rolf Wanka: Approximationsalgorithmen - Eine Einführung
Leitfäden der Informatik, B.G. Teubner Verlag, 2006
ISBN-10 3-519-00444-5
ISBN-13 978-3-519-00444-8
Materialien und ÜbungsblätterDokumente zur Vorlesung
Musterlösungen
Übungsblätter
- Übungsblatt 1
Formalisierung von Optimierungsproblemen, Numerische Approximation, Knotenfärbung
Abgabe am 30.10.2007 um 10 Uhr, Briefkasten ITI
- Übungsblatt 2
Knotenfärbung und Kantenfärbung, Gap Amplification, Set Cover, Binpacking
Abgabe am 9.11.2007 um 10 Uhr, Briefkasten ITI
-
Übungsblatt 3
TSP, Metrisches TSP
Abgabe am 27.11.2007 um 10 Uhr, Briefkasten ITI - Übungsblatt 4
Abgabe am 12.12.2007 um 10 Uhr, Briefkasten ITI
- Übungsblatt 5
Abgabe am 9.1.2008 um 10 Uhr, Briefkasten ITI
Übungsblatt 6
Abgabe am 24.1.2008 um 10 Uhr, Briefkasten ITI
|
