| | |
| LVR-Nr | 150220 |
| Veranstaltung | Effiziente Algorithmen
| 4 std. | NA 02/99 Di 10h-12h |
| | NA 02/99 Do 10h-12h |
|
| Dozent | Hans U. Simon |
| Übungsgruppen | NA 01/64 Mo 12h-14h |
| Übungsgruppenleiter | Nikolas List |
|
|
 | | Aktuelle Hinweise |
|
| | |
- Die Vorlesung am Donnerstag, den 12.7. fällt aus.
- Beachte die Bekanntgabe der Prüfungsbedingungen.
|
|
 Seitenanfang |
| | Übersicht |
|
|
|
| Seitenanfang |
| | Kommentar |
|
| | |
Es handelt sich um eine Lehrveranstaltung des Hauptstudiums
Mathematik. Sie kann sowohl in das Gebiet der angewandten als
auch in das Gebiet der theoretischen Informatik eingeordnet
werden. Sie richtet sich an Studierende der Mathematik
(insbesondere auch an solche mit Schwerpunkt oder Nebenfach
Informatik) und an Studieredne der Angewandten Informatik.
Das Hauptanliegen der Vorlesung ist, einen Vorrat grundlegender
Datenstrukturen und effizienter Algorithmen zu vermitteln und
Analysetechniken einzufuehren (Korrektheitsbeweis und Laufzeitanalyse).
Die Vorlesung über Effiziente Algorithmen vertieft die Kenntnisse, die
in der Vorlesung über Datenstrukturen erworben wurden. Zu den zentralen
Themen zählen zum Beispiel die folgenden:
- Berechnung kürzester Pfade in einem Graphen bei ganzzahligen
Kantenkosten.
- Berechnung eines maximalen Flusses in einem Transportnetzwerk.
- Berechnung einer optimalen Lösung bei einem Zuordnungsproblemen
(auch Matching-Probleme genannt).
- Effiziente Approximationsalgorithmen fuer ausgesuchte
Optimierungsprobleme
Darüberhinaus beschäftigen wir uns mit Anwendungen dieser
grundlegenden Probleme.
|
|
| Seitenanfang |
| | Voraussetzungen |
|
| | |
Grundkenntnisse in Mathematik und Informatik; insbesondere Kenntnisse
wie sie in einer Vorlesung über Datenstrukturen vermittelt werden.
|
|
| Seitenanfang |
| | Empfohlene Literatur |
|
| | |
- Skriptum zur Vorlesung
- Ravindra K. Ahuja, Thomas L. Magnanti und James B. Orlin,
Network Flows (Theory, Algorithms, and Applications,
Prentice Hall, 1993. ISBN 0-13-617549-X.
- Thomas H. Cormen/Charles E. Leiserson/Ronald Rivest/Clifford Stein,
Algorithmen - Eine Einführung.
Oldenbourg Wissenschafsverlag, 2004. ISBN 3-486-27515-1
- Jon Kleinberg und Eva Tardos, Algorithm Design, Addison Wesley, 2005.
|
|
| Seitenanfang |
| | Materialien |
|
| | |
Alle Materialien, die im Laufe der
Vorlesung auf der Webseite bereitgestellt werden, sind im
pdf-Format [.pdf] oder komprimiert im Postscript Format
[.ps.gz]. Einen Viewer für ps-files gibts z.B. hier.
|
|
| Seitenanfang |
| | Prüfungsmodalitäten |
|
| | |
Übungsbetrieb
- Auf der Homepage werden wöchentlich (jeweils mittwochs) Übungsaufgaben bereitgestellt.
- Die Aufgaben können in Gruppen bis zu 3 Personen bearbeitet werden.
- Termin für die Abgabe der Übungsaufgaben ist
mittwochs 12h im Kasten NA 01.
- Die Aufgaben werden korrigiert und in den Übungen besprochen.
Prüfungsbedingungen
-
Einen benoteten Leistungsnachweis über 9CP erhält,
wer am Ende des Semsters eine halbstündigen mündlichen
Prüfung über den Vorlesungsstoff erfolgreich absolviert.
-
Einen unbenoteten Übungsschein erhält, wer
bei der schriftlichen Bearbeitung der Übungsaufgaben
mindestens 50% der insgesamt zu erreichenden Punkte
erzielt, regelmäßig an den Übungen teilnimmt und
mindestens zwei Mal vorrechnet.
|
|
| Seitenanfang |
| | Kontakt |
|
|
|
| Seitenanfang |
