Lehrstuhl i1

• » Startseite
• » Adresse
• » Personen

Forschung

• » Schwerpunkte
• » Projekte
• » Veröffentlichungen

Lehre

• » Winter 09/10
• » Sommer 09
• » Frühere Semester
• » Vorlesungen am i1
• » Prüfungen
• » Bachelorarbeiten
• » Diplomarbeiten
• » Promotionen

Links

• » i1 intern
• » Schulprojekt
• » Fachgruppe
• » RWTH Aachen
• » Campus
• » Webmail

Sonstiges

• » Haftung

Aktuelles

• Die Übungsscheine können ab sofort im Sekretariat (Raum 4023) abgeholt werden. Öffnungszeiten: 9-12 Uhr (außer mittwochs).
• Einige Studierende benötigen als Voraussetzung für den Übungsschein noch ein Fachgespräch mit Prof. Vöcking. Eine Anmeldung für ein solches Fachgespräch kann bei Heiko Röglin (roeglin(at)cs.rwth-aachen.de) erfolgen, mögliche Termine sind der 22. Februar und der 8. März.

Termine

Inhalt

Die Vorlesung gibt einen Überblick über verschiedene Gebiete der Algorithmik. Im Zentrum der Vorlesung steht die theoretische Analyse der vorgestellten Algorithmen bezüglich ihrer Korrektheit, Laufzeit und Güte. Die Themenauswahl berücksichtigt insbesondere die praktische Relevanz der vorgestellten algorithmischen Konzepte. Im Einzelnen widmen wir uns den folgenden Themen.

• Flüsse und Matchings
• Lineare Programmierung
• Algorithmische Geometrie
• Randomisierte Algorithmen
• Approximationsalgorithmen
• Online-Algorithmen

Material

• Skript
  • Kapitel 1: Maximale Flüsse
    • Skript [PS] [PS-verkleinert] [PDF-verkleinert]
    • Beispiel Ford-Fulkerson 1 [PS] [PDF]
    • Beispiel Ford-Fulkerson 2 [PS] [PDF]
    • Beispiel Dinic [PS] [PDF]
  • Kapitel 2: Maximum Matchings
    • Skript [PS] [PDF]
    • Beispiel Hopcroft-Karp [PS] [PDF]
  • Crashkurs: Lineare Programmierung
    • Skript [PS] [PS-verkleinert] [PDF-verkleinert]
    • mehr Details zu diesem Thema in der Vorlesung Optimierung und Spieltheorie im nächsten Semester
  • Kapitel 3: Approximationsalgorithmen
    • Skript (1. Teil) [PS] [PS-verkleinert] [PDF-verkleinert]
    • Beispiel Set-Cover [PS] [PDF]
    • Skript (2. Teil) [PS] [PS-verkleinert] [PDF-verkleinert]
    • Beispiel Pseudobaum [PS] [PDF]
  • Kapitel 4: Online Algorithmen
    • Skript [PS] [PS-verkleinert] [PDF-verkleinert]
  • Kapitel 5: Randomisierte Algorithmen
    • Skript [PS] [PS-verkleinert] [PDF-verkleinert]
  • Kapitel 6: Algorithmische Geometrie
    • Skript (korrigierte Version vom 2. Febr.) [PS] [PDF]
    • Exkurs 2-3-Bäume [PS] [PDF]
• Übungsaufgaben
  
  • Übungsblatt 1: [ps-Version] [ps.gz-Version] [pdf-Version]
  • Übungsblatt 2: [ps-Version] [ps.gz-Version] [pdf-Version]
  • Übungsblatt 3: [ps-Version] [ps.gz-Version] [pdf-Version]
  • Übungsblatt 4: [ps-Version] [ps.gz-Version] [pdf-Version]
  • Übungsblatt 5: [ps-Version] [ps.gz-Version] [pdf-Version]
  • Übungsblatt 6: [ps-Version] [ps.gz-Version] [pdf-Version]
  • Übungsblatt 7: [ps-Version] [ps.gz-Version] [pdf-Version]
  • Übungsblatt 8: [ps-Version] [ps.gz-Version] [pdf-Version]
  • Übungsblatt 9: [ps-Version] [ps.gz-Version] [pdf-Version]
  • Übungsblatt 10: [ps-Version] [ps.gz-Version] [pdf-Version]
  • Übungsblatt 11: [ps-Version] [ps.gz-Version] [pdf-Version]
  • Übungsblatt 12: [ps-Version] [ps.gz-Version] [pdf-Version]

Einteilung in die Übungsgruppen

• Nachträgliche Anmeldungen sind in Ausnahmefällen bei H.-J. Böckenhauer (Raum 4021) möglich.
• Raumänderung: Wegen der großen Teilnehmerzahl in den Gruppen 1 und 4 finden diese Übungen (soweit möglich) in anderen Räumen statt:
  • Gruppe 1: AH IV (außer am 4.11.,18.11, 9.12, Räume für diese Termine werden kurzfristig bekanntgegeben)
  • Gruppe 4: AH I (außer am 3.12, der Raum für diesen Termin wird kurzfristig bekanntgegeben)