Veranstaltungen im Winter-
semester 2006/2007
Die Vorlesung ist der erste Teil einer 2-semestrigen Vorlesung, die sich mit Enwurf, Analyse und Implementierung von Algorithmen zur Lösung kombinatorischer Probleme beschäftigt. Viele dieser Probleme, insbesondere solche mit praktischen Anwendungen, sind NP-schwer, erlauben also nach dem gegenwärtigen Kenntnisstand keine polynomialen Algorithmen zu ihrer exakten Lösung. Andererseits gibt es aber auch viele durchaus anspruchsvolle Probleme, für die polynomiale Algorithmen existieren. Diese Probleme haben sowohl eigene Anwendungen, treten aber auch häufig als Teilprobleme komplexerer Fragestellungen auf. Diese Vorlesung beschäftigt sich in erster Linie mit polynomial lösbaren Problemen (z.B. kürzeste-Wege-Probleme, Matching- und Transportprobleme, Netzwerkflussprobleme) und diskutiert den Entwurf und die Implementierung effizienter Lösungsverfahren. Im zweiten Teil wird dann der Schwerpunkt auf der Behandlung NP-schwerer Probleme liegen.
Die Vorlesung wendet sich an Studierende der Informatik in Haupt-
oder Nebenfach. sowie an Lehramtsstudenten. Kenntnisse über Algorithmen
und Datenstrukuren sowie Programmierkenntnisse werden vorausgesetzt. Zur Vorlesung ist ein Skript erhältlich,
das im Sekretariat erworben werden kann.
a) ein Übungsschein oder
b) ein Leistungsnachweis über 6 ECTS Leistungspunkte oder
c) ein Leistungsnachweis über 9 ECTS Leistungspunkte
erworben werden. Zum Erwerb des ECTS-Scheins über 6 LP ist das
Bestehen
einer schriftlichen Prüfung erforderlich, für den Schein
über 9 LP
ist zusätzlich die erfolgreiche
Teilnahme an den Übungen Voraussetzung.
Termin: Di 11-13, Do 11-13, Raum: U 013, INF 350,
Beginn: Do. 19.10.06
Literaturverzeichnis zur Vorlesung.
Übungen zur Vorlesung "Effiziente Algorithmen I" (Reinelt, Oswald, 2 SWS)
Die zur Vorlesung angebotenen Übungen dienen der Vertiefung des Stoffes. Sie umfassen insbesondere auch Programmieraufgaben. Die Teilnahme an den Übungen wird empfohlen. Durch Bearbeitung von Aufgaben und Teilnahme an den Übungsstunden kann ein Übungsschein erworben werden.
Termin: Di 14-16, Raum: U013, INF 350 oder Mi 14-16, Raum: 013, INF 348
Beginn: Di. 31.10.06
Vorlesung:
Termin: n. Vereinbarung>
Übung:
Termin:
Zur erfolgreichen Seminarteilnahme sind ein mündlicher Vortrag
sowie eine schriftliche Ausarbeitung erforderlich. Es kann ein Nachweis
nach ECTS über 3 Leistungspunkte erworben werden.
Mehr Informationen finden Sie hier.
Vorbesprechung: Mi 26.07, 14-16, Raum: U014, INF 350
Termin: Do 14-16 s.t., Raum: 220, INF 368
Praktikum "Informatik" für Anfänger (4 SWS)
Praktikum "Informatik" für Fortgeschrittene (6 SWS)
(Oswald/Seitz/Reinelt)
In den Software-Praktika werden Projekte mit Informatikinhalten
bearbeitet. Die Arbeit im Praktikum umfasst die Implementierung
entsprechender Algorithmen, ihre ausführliche Dokumentation und
einen Kurzvortrag über das bearbeitete Thema. Der
Schwierigkeitsgrad ist davon abhängig, ob es sich um ein
Anfänger- oder um ein Fortgeschrittenenpraktikum handelt. Für
die Anfängerpraktika sind Grundkenntnisse in Informatik
ausreichend, im Praktikum für Fortgeschrittene werden in der Regel
Kenntnisse zu Effizienten Algorithmen vorausgesetzt.
Die erfolgreiche Teilnahme wird durch einen Nachweis nach
ECTS über 6 (Anfängerpraktikum) bzw. 9
(Fortgeschrittenenpraktikum) Leistungspunkte bestätigt.
Praktikumsthemen können jederzeit ausgegeben werden. Gruppenarbeit
ist möglich bzw. erwünscht. Es können auch eigene Themen
vorgeschlagen werden.
Sprechstunde Prof. Dr. Gerhard Reinelt
Während der Vorlesungszeit Mi 11-12 und nach den Vorlesungen. Weitere Termine bitte über das Sekretariat vereinbaren (Tel. 54 57 48)
mod. 26.10.06, CP
comopt{at}informatik.uni-heidelberg.de
