Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Wintersemester 2006/2007
Algorithmentechnik

Algorithmentechnik

Allgemeines

Die Vorlesung Algorithmentechnik vertieft die wichtigsten Teilgebiete der Algorithmik. Dazu gehören Graphenalgorithmen, Algorithmische Geometrie, Algebraische Algorithmen, Kombinatorische Optimierung sowie fortgeschrittene Datenstrukturen. Es werden verschiedene methodische Richtungen vertieft, z.B. randomisierte Algorithmen, Approximationsalgorithmen, parallele Algorithmen, Online-Algorithmen und Algorithm Engineering.

Neueste Meldungen

  • Lösung zu Klausur2: Download
  • Klausur2: Download
  • Klausureinsicht: Mi, 25.04.07, 13:30-15:30, SR 301 im Infobau
  • 16. Apr: Klausurergebnisse der 2. Klausur vom 12.4.07 hängen in Gebäude 50.34 im Foyer und im dritten Stock aus
  • 5. Apr: Klausureinteilung: Alle Teilnehmer der Nachklausur schreiben im HSaF (Gebäude 50.35).
  • Klausureinsicht: Di, 13.03.07, 10:00-12:00, SR 301 im Infobau
  • 2. Mär: Klausurergebnisse der 1. Klausur vom 1.3.07 hängen in Gebäude 50.34 im Foyer und im dritten Stock aus
  • 2. Mär: Klausur 1 vom 01.03.07, und Loesung 1
  • 23. Feb: Klausureinteilung: Alle Teilnehmer schreiben im HMU.
  • 16. Feb: Eine aktualisierte Liste der erreichten Bonuspunkte hängt neben dem Briefkasten zur Klausuranmeldung aus.
    Hinweis: Auf dem ersten Übungsblatt reichten 3,5 Punkte aus, um einen Klausurbonus zu erhalten.
  • 15. Feb: Separates Kurzskript als Kapitel zu parallelen Algorithmen
  • 12. Feb: Links zu parametrisierter Komplexität
  • 06. Feb: Update des Skripts (Bugs, Verbesserungen, Kommentare willkommen)
  • 04. Feb: 6. Übungsblatt: Die Abgabe ist bis Mittwoch, den 7.Februar, möglich.
  • 02. Feb: 6. Übungsblatt: Zeigen Sie in Aufgabe 2(b) nur, dass ein PAS existiert (statt ein FPAS). Das Blatt wurde dementsprechend angepasst.
  • 16. Jan: 5. Übungsblatt online. Die Abgabe ist bis 24.1. 15:30 möglich
  • 09. Jan: 5. Übungsblatt kommt erst am 16. Jan.
  • 12. Dez: 4. Übungsblatt online. Die Abgabe ist bis 20.12. 15:30 möglich
  • 12. Dez: Entgegen der ursprünglichen Ankündigung ist am 19.12. Vorlesung und somit am 14.12. Übung
  • 28. Nov: 3. Übungsblatt online. Die Abgabe ist bis 6.12. 15:30 möglich
  • Kleine Änderung auf dem Übungsblatt 2, Aufgabe 3: Findmax soll eine Laufzeit von O(k) haben, anstatt O(log(k)). (Beachte auch den geänderten Titel der Aufgabe.)
  • 31. Okt: 1. Übungsblatt online. Die Abgabe ist bis 8.11. 15:30 möglich
  • Termine aktualisiert

Termine

Di Do
24.10. Vorlesung 26.10. Vorlesung
31.10. Vorlesung 2.11. Übung
7.11. Vorlesung 9.11. Vorlesung
14.11. Vorlesung 16.11. Übung
21.11. Vorlesung 23.11. Vorlesung
28.11. Vorlesung 30.11. Übung
5.12. Vorlesung 7.12. Vorlesung
12.12. Vorlesung 14.12. Übung
19.12. Vorlesung 21.12. Vorlesung
9.1. Vorlesung 11.1. Vorlesung
16.1. Vorlesung 18.1. Übung
23.1. Vorlesung 25.1. Vorlesung
30.1. Vorlesung 1.2. Übung
6.2. Vorlesung 8.2. Vorlesung
13.2. Vorlesung 15.2. Übung

Änderungen vorbehalten!

Klausur

PunkteNoteAnzahl
48 1 12
45 1,3 7
42 1,7 5
39 2 3
36 2,3 6
33 2,7 4
30 3 5
29 3,3 6
24 3,7 0
20 4 0
<20 5 0
PunkteNoteAnzahl
42 1 7
39,5 1,3 1
37 1,7 4
34,5 2 6
32 2,3 5
29,5 2,7 3
27 3 7
+24,5 3,3 7
22 3,7 8
20 4 3
<20 5 11

Skripte und Material

  • parallele Algorithmen
  • Skript
  • Ergänzte Folien aus den zwei Vorlesungen zu LP: Download
  • Kurzskripte zur Wiederholung wichtiger Begriffe: Algorithmen und ihre Laufzeit, Begriffe zu Graphen, Die Komplexitätsklassen P, NP und NPC: Materialseite

Übungsblätter, Übungsfolien und Musterlösungen

Übungsblatt Übungsfolien Musterlösung
- Folien vom 2.11. -
Übungsblatt 1 Folien vom 16.11. Musterlösung 1
Übungsblatt 2 Folien vom 30.11. Musterlösung 2
Übungsblatt 3 Musterlösung 3
Übungsblatt 4 Folien vom 19.1. Musterlösung 4
Übungsblatt 5 Musterlösung 5
Übungsblatt 6 Folien vom 15.2. Musterlösung 6

Vorlesungen

Datum Thema Material Literatur
24.10. Worst-case- und Average-case-Laufzeit, untere Schranke für Laufzeiten Skript [CLR01]
26.10. Amortisierte Analyse, Rekursionsabschäzungen SkriptAlt (6.3, 2, 1) [CLR01]
31.10. Mastertheorem, Union-Find Skript [CLR01]
7.11. Laufzeitanalyse von Union-Find Skript [CLR01]
9.11. Anwendungsbeispiele für Union-Find Skript [CLR01]
14.11. Minimale Spannbäume Skript [CLR01]
21.11. MST, Kruskal, Prim, Matroide Skript [CLR01]
23.11. Min-Cut, Stoer und Wagner Skript [CLR01]
28.11. Flüsse Skript [CLR01]
5.12. Ford Fulkerson, Goldberg Tarjan Skript [CLR01]
7.12. Goldberg Tarjan Skript [CLR01]
12.12. Kreisbasen Skript [Hor87],[D05]
14.12. Kreisbasen Skript [Kav04],[D05]
19.12. Cyclic Timetables Skript [P03]
9.1. Lineare Programme Skript, Folien [CLR01]
11.1. Lineare Programme Skript, Folien [CLR01]
16.1. Approximationsalgorithmen Skript [CLR01]
23.1. Approximationsalgorithmen Skript [CLR01]
25.1. Approximationsalgorithmen Skript [CLR01]
30.1. Randomisierte Algorithmen Skript [CLR01]
6.2. Randomisierte Algorithmen Skript [CLR01]
8.2. Parametrisierte Komplexität Tübinger Skript, Kurzskript Karlsruhe [DF99]
13.2. Parallele Algorithmen chapterparallel.pdf [CLR01]

Literatur

[CLR01] T. H. Cormen, C. E. Leiserson, R. L. Rivest u.a. Introduction to Algorithms / Algorithmen -- eine Einführung. MIT Press, 1990-2001 / Oldenburg 2004.
[OW90] Thomas Ottmann und Peter Widmayer. Algorithmen und Datenstrukturen. Spektrum, Akad. Verl., 1990-2002.
[Tar83] Robert E. Tarjan. Data structures and network algorithms. Society for Industrial and Applied Mathematics, 1983.
[S01] Uwe Schöning. Algorithmik. Spektrum Akademischer Verlag, 2001.
[B05] Norbert Blum. Algorithmen und Datenstrukturen. Oldenbourg Verlag, 2004.
[A99] Giorgio Ausiello et al. Complexity and Approximation. Springer Verlag, 1999.
[H01] Juraj Hromkovic. Algorithmics for Hard Problems. Springer Verlag, 2001.
[O98] Thomas Ottmann. Prinzipien des Algorithmenentwurfs. Spektrum Akademischer Verlag, 1998.
[Hor87] J. D. Horton A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM Journal on Computing Vol. 16, Issue 12, 1987.
[Kav04] T. Kavitha, K. Mehlhorn, D. Michail, K. Paluch. A faster algorithm for Minimum Cycle Basis of graphs. Proc. ICALP 2004, Turku, Finland, 2004.
[V04] Berthold Vöcking. Crashkurs Lineare Programmierung. Vorlesungsnotizen, 2004.
[D05] Reinhard Diestel. Graph Theory. Springer-Verlag, 2005.
[P03] Leon Peeters. Cyclic Railway Timetable Optimization. Dissertation, 2003.
[DF99] R. G. Downey, M. R. Fellows, Parameterized Complexity. Springer, 1999.