Allgemeine Informationen

Typ	Zeit / Ort	Start	Dozent
V3	Di, 16:30 - 18:00 / AH V Do, 12:30 - 14:00 / AH V	08.10.2019 10.10.2019	Unger / Woeginger
Ü2	Mi, 12:30-14:00 / 5052 Mi, 14:30-16:00 / S01 Fr, 10:30-12:00 / 5054	30.10.2019	Fischer
Prüfung 1	Di 04.02.2020. 17:30 - 19:30 / Großer Hörsaal
Prüfung 2	Di 10.03.2020. 10:30 - 12:30 / Roter Hörsaal

ECTS:	6
RWTHonline:	Link
Moodle:	Link

---

Die Vorlesung "Effiziente Algorithmen" ist Teil des Bachelor-Studiums der Informatik.
Für das Master-Studium der Informatik wird diese Vorlesung nicht angerechnet.
(Einzige Ausnahme: Master-Studenten der Informatik, die diese Vorlesung als Auflage erhalten haben.)

---

News

---

Prüfung

Die Prüfung findet in Form einer schriftlichen Klausur statt.

---

Übungen

Um für die Klausur zugelassen zu werden müssen mindestens 50% aller möglichen Punkte auf den Übungsblättern erreicht werden. Die Übungsblätter sollen in Gruppen der Größe 3-5 abgegeben werden. Die Übungsblätter werden im Moodle ud hier auf der Homepage veröffentlicht.

Übungsblatt	Veröffentlicht	Abgabefrist
Blatt 01	17.Oktober	23. Oktober 16:00
Blatt 02	23.Oktober	30. Oktober 16:00
Blatt 03	30.Oktober	06. November 16:00
Blatt 04	06.November	13. November 16:00
Blatt 05	13.November	20. November 16:00
Blatt 06	20.November	27. November 16:00
Blatt 07	27.November	4. Dezember 16:00
Blatt 08	4.Dezember	11. Dezember 16:00
Blatt 09	19.Dezember	8. Januar 16:00
Blatt 10	8.Januar	15. Januar 16:00
Blatt 11	8.Januar	22. Januar 16:00

---

Material

	Vortragender	Thema	Folien / Handout	Anmerkungen
Teil 1
Kapitel 01	Woeginger	Suchprobleme	Folien 01 / Handout 01	--- --- --- ---
Kapitel 02	Woeginger	Algebraische Algorithmen	Folien 02 / Handout 02	Mehr zum Schur Komplement
Kapitel 03	Woeginger	Zahlentheoretische Algorithmen	Folien 03 / Handout 03	--- --- --- ---
Teil 2
Kapitel 01	Unger	Grundlagen zu Flüssen	Folien 01 / Handout 01 / Kompakt 01 (Weniger Animationen) / Mit Markierungen 01	--- --- --- ---
Kapitel 02	Unger	Weitere Flüsse	Folien 02 / Handout 02 / Kompakt 02 (Weniger Animationen) / Mit Markierungen 02	--- --- --- ---
Kapitel 03	Unger	Matchings	Folien 03 / Handout 03 / Kompakt 03 (Weniger Animationen) / Mit Markierungen 03	--- --- --- ---
Kapitel 04	Unger	Lineare Programme 1	Folien 04 / Handout 04 / Kompakt 04 (Weniger Animationen) / Mit Markierungen 04	--- --- --- ---
Kapitel 05	Unger	Lineare Programme 2	Folien 05 / Handout 05 / Kompakt 05 (Weniger Animationen) / Mit Markierungen 05	--- --- --- ---
Teil 3
Kapitel 01	Woeginger	Matroide	Folien 01 / Handout 01	9. Januar
Kapitel 02	Woeginger	Schnitt von Matroiden	Folien 02 / Handout 02	--- --- --- ---

Überblick zur Organisation der Vorlesung

---

Literatur

Suchprobleme / Algebraische Algorithmen / Zahlentheoretische Algorithmen:

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009.
  Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press.

Flüsse und Matchings:

• Ahuja, Magnanti, Orlin: Network Flows - Theory, Algorithms, and Applications. Prentice Hall, 1993.
• Cormen, Leiserson, Rivest: Introduction to Algorithms. MIT Press, 1990.
• Ottmann, Widmayer: Algorithmen und Datenstrukturen. BI-Wiss.-Verl., 1990.

Lineare Programmierung:

• Chvátal: Linear Programming. Freeman, 1983.
• Korte, Vygen: Combinatorial Optimization - Theory and Algorithms. Springer, 2000.