Wintersemester 2008/2009
Prof. Dr. Manfred Kunde

[Mitteilungen] [Inhalte] [Termine] [Scheinerhalt] [Literatur] [Materialien]

Mitteilungen

Die Studierenden mit den folgenden Matrikelnummern sind für die Approximationsalgorithmenklausur am 10.3.2009 um 12:30 Uhr im K-Hs zugelassen:

2 SWS

34290     34719     34889     36302     36552     37649     38032     39673

Achtung!

Die, wie vorher angekündigte Zulassung für 3 SWS war ein Tippfehler! Alle Zulassungen sind für 2 SWS!

Inhalte

1. Grundlagen der Approximation
   
   
2. Approximation mit absoluter Gütegarantie
1. Konzepte
2. Knotenfärbung
3. Schwierigkeit der Approximation des Rucksackproblems
   
   
3. Approximation mit relativer Gütegarantie
• Konzepte
• Traveling Salesperson
• Knotenfärbungen und Independent Set
  
  
4. Approximationsschemata
• Pseudopolynomielle Algorithmen
• Strenge Approximationsschemata
• Unmöglichkeitsergebnisse für Approximationsschemata
  
  
5. Techniken zur Approximation
   

Termine

• Vorlesung (Prof. Dr. M. Kunde)
• Montag, 15:00-16:30 Uhr, Sr HU 211/212
  
  
• Übung (Dr. M. Brinkmeier)
• Montag (U), 13:00-14:30, Sr HU 211/212

Kriterien für den Scheinerhalt

Der Schein Approximationsalgorithmen kann in zwei Varianten erworben werden, einer vierstündigen (2V+1Ü) und einer dreistündigen (2V).

Übersicht über die Schein-Kriterien

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:
1. Mindestens vier Aufgaben der Übungsblätter 1-6 müssen erfolgreich bearbeitet worden sein.
2. Mindestens eine Aufgabe der Übungsblätter 1 und 2 muss erfolgreich bearbeitet worden sein.
3. Mindestens eine Aufgabe der Übungsblätter 3 und 4 muss erfolgreich bearbeitet worden sein.
4. 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.


• 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ätter

Dokumente zur Vorlesung

Folien zur Vorlesung vom 13.10.2008

Folien zur Vorlesung vom 20.10.2008

Folien zur Vorlesung vom 27.10.2008

Folien zur Vorlesung vom 03.11.2008

Folien zur Vorlesung vom 10.11.2008

Folien zur Vorlesung vom 17.11.2008

Folien zur Vorlesung vom 24.11.2008

Folien zur Vorlesung vom 01.12.2008

Folien zur Vorlesung vom 08.12.2008

Folien zur Vorlesung vom 15.12.2008

Folien zur Vorlesung vom 05.01.2009

Folien zur Vorlesung vom 12.01.2009

Folien zur Vorlesung vom 19.01.2009

Folien zur Vorlesung vom 26.01.2009

Folien zur Vorlesung vom 02.02.2009

Übungsblätter

• Übungsblatt 1
  Optimierungsprobleme, Knotenfärbung, Newton
  Abgabe: Mo 27.10.08, 10 Uhr, Briefkasten ITI
  
  
• Übungsblatt 2
  GreedyCol, GreedyEdgeCol, Färbekanten, Bin Packing
  Abgabe: Mo 10.11.08, 10 Uhr, Briefkasten ITI
  
  
• Übungsblatt 3
  Kantenfärbung, Scheduling, TSP
  Abgabe: Mo 24.11.08, 10 Uhr, Briefkasten ITI
  
  
• Übungsblatt 4
  TSP, Vertex Cover, Unapproximierbarkeit
  Abgabe: Mo 8.12.08, 10 Uhr, Briefkasten ITI
  
  
• Übungsblatt 5
  BinPacking, NearestNeighbor, Independent Set
  Abgabe: Mo 5.1.2009, 10 Uhr Briefkasten ITI
  
  
• Übungsblatt 6
  Lokale Suche, Max-2-Sat, Max Cut, Lineare Programmierung
  Abgabe: Mo 19.1.2009, 10 Uhr Briefkasten ITI