Übungen zur Vorlesung "Entwurf und Analyse von Algorithmen" (WS 2006/2007)
|
12.01.2007: Laufzeit-Beweis zu Goldberg&Tarjan, (Highest-Label-Impl.) im Abschnitt Skriptum. |
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 (S. Cornelsen) | Mi 08.30 - 10.00 (D 301) Fr 08.30 - 10.00 (D 436) |
| Übung (C. Pich) | Mo 14.00 - 15.30 (P 602) |
| Prüfungen | mündlich nach Vereinbarung |
Übungsblätter
Die Übungsblätter sind freitags ab 12 Uhr 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 werden als schriftliche Ausarbeitungen im Treppenhaus vor dem Sekretariat des Lehrstuhls (Raum E 214) abgegeben. 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.
| Nr. | Ausgabe | Abgabe | Besprechung | Download |
|---|---|---|---|---|
| 1 | 27.10.2006 | 03.11.2006 | 06.11.2006 | |
| 2 | 03.11.2006 | 10.11.2006 | 13.11.2006 | |
| 3 | 10.11.2006 | 17.11.2006 | 20.11.2006 | |
| 4 | 17.11.2006 | 24.11.2006 | 27.11.2006 | |
| 5 | 24.11.2006 | 01.12.2006 | 04.12.2006 | |
| 6 | 01.12.2006 | 08.12.2006 | 11.12.2006 | |
| 7 | 08.12.2006 | 15.12.2006 | 18.12.2006 | |
| 8 | 15.12.2006 | 22.12.2006 | 08.01.2007 | |
| 9 | 22.12.2006 | 12.01.2007 | 15.01.2007 | |
| 10 | 12.01.2007 | 19.01.2007 | 22.01.2007 | |
| 11 | 19.01.2007 | 26.01.2007 | 29.01.2007 | |
| 12 | 26.01.2007 | 02.02.2007 | 05.02.2007 | |
| 13 | 02.02.2007 | 09.02.2007 | 12.02.2007 |
Einige Dateien sind nur lokal an der Universität Konstanz lesbar.
Skriptum
- Skriptum zur gleichen Veranstaltung aus vergangenen Semestern
- Maximale Flüsse, Zusatzkapitel
- Highest-Label-Implementierung zu Goldberg&Tarjan, Laufzeit-Beweis
- O-Notation, aus dem Skriptum zu "Diskrete Strukturen"
- Prüfercodes, aus dem Skriptum zu "Diskrete Strukturen"
- Kapitel zur FFT (lokal)
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