Übungen zur Vorlesung "Entwurf und Analyse von Algorithmen"
|
Übungsblatt 14 |
Entwurf und Analyse von Algorithmen sind zentrale Aufgaben der Informatik. Diese Vorlesung behandelt wichtige Fragestellungen und Methoden der Algorithmik und schafft eine allgemeine Grundlage für die Beschäftigung mit spezielleren algorithmischen Problemen. Es werden Algorithmen und Datenstrukturen aus verschiedenen Bereichen und insbesondere Graphenalgorithmen behandelt. |
Termine
| Vorlesung (U. Brandes) | Mi 8:30-10:00 (D 406) Fr 08:30-10:00 (D 301) |
| Übung (J. Lerner/B. Schlieper) | Mo 14:15-15:45 (M 627) |
| Prüfungen | mündlich nach Vereinbarung |
Übungsblätter
Übungsblätter werden freitags in der Vorlesung ausgegeben, sind aber auch im Treppenhaus vor dem Sekretariat des Lehrstuhls (Raum E 214), sowie im PDF-Format auf dieser Seite erhältlich.
Die Aufgaben sind innerhalb einer Woche zu bearbeiten. Abgabe ist jeweils
bis Freitag 10:00 Uhr möglich. Die Aufgaben können entweder
als schriftliche Ausarbeitungen im Treppenhaus vor dem Sekretariat des
Lehrstuhls (Raum E 214), oder in einem plattformunabhängigen Format
(PDF oder PS) per Email an schliepe@inf.uni-konstanz.de
abgegeben werden. Die Besprechung der Aufgaben und die Rückgabe der
korrigierten und mit Punkten bewerteten Abgaben erfolgt in der Übung.
Das Erlangen von mindestens der Hälfte der möglichen Punkte und die
aktive Teilnahme an den Übungen ist Voraussetzung für einen
Übungsschein.
Alle Aufgaben können und sollen in Zweiergruppen abgegeben werden.
- Übungsblatt 1: Ausgabe: 24.10.2005, Abgabe: 28.10.2005, 10 Uhr.
- Übungsblatt 2: Ausgabe: 28.10.2005, Abgabe: 04.11.2005, 10 Uhr.
- Übungsblatt 3: Ausgabe: 04.11.2005, Abgabe: 11.11.2005, 10 Uhr.
- Übungsblatt 4: Ausgabe: 11.11.2005, Abgabe: 18.11.2005, 10 Uhr.
- Übungsblatt 5: Ausgabe: 18.11.2005, Abgabe: 25.11.2005, 10 Uhr.
- Übungsblatt 6: Ausgabe: 25.11.2005, Abgabe: 02.12.2005, 10 Uhr.
- Übungsblatt 7: Ausgabe: 02.12.2005, Abgabe: 09.12.2005, 10 Uhr.
- Übungsblatt 8: Ausgabe: 09.12.2005, Abgabe: 16.12.2005, 10 Uhr.
- Übungsblatt 9: Ausgabe: 16.12.2005, Abgabe: 23.12.2005, 10 Uhr.
- Übungsblatt 10: Ausgabe: 21.12.2005, Abgabe: 13.01.2006, 10 Uhr.
- Übungsblatt 11: Ausgabe: 13.01.2006, Abgabe: 20.01.2006, 10 Uhr.
- Übungsblatt 12: Ausgabe: 20.01.2006, Abgabe: 27.01.2006, 10 Uhr.
- Übungsblatt 13: Ausgabe: 27.01.2006, Abgabe: 03.02.2006, 10 Uhr.
- Übungsblatt 14: Ausgabe: 03.02.2006, Abgabe: 10.02.2006, 10 Uhr.
Skript
Zu der entsprechenden Vorlesung in den vergangenen Semestern wurde ein Skript (ps, pdf) erstellt. Zusätzlich steht ein Kapitel über maximale Flüsse (ps.gz, pdf) sowie Ergänzungen zur Highest-Label-Implementation des Algorithmus von Goldberg und Tarjan (pdf) zur Verfügung.
Literaturhinweise
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. McGraw-Hill, 2001 (2nd ed.)
- T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. BI-Wissenschaftsverlag, 1993
- D. Jungnickel: Graphen, Netzwerke und Algorithmen. BI-Wissenschaftsverlag, 1994
Weitere Informationen
- Eintrag im Vorlesungsverzeichnis
- Hinweise zur Benutzung des Account-Tools
- O-Notation (aus dem Skript zu "Diskrete Strukturen")
- Kurzskript über Flüsse