Veranstaltungen im Winter-
semester 2007/2008
Die Vorlesung ist der zweite Teil einer 2-semestrigen Vorlesung, die sich mit Entwurf, 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. Nachdem wir uns im ersten Teil mit grundlegenden (polynomialen) Algorithmen beschäftigt haben, liegt nun der Schwerpunkt auf der Behandlung NP-schwerer Probleme. Themen sind etwa approximative Algorithmen und Heuristiken (Bin-Packing, Scheduling, Knapsack, Traveling Salesman), Relaxierungen (lineare, kombinatorische, Lagrange-Relaxierungen), Verfahren zur Bestimmung optimaler Lösungen (dynamische Optimierung, Branch-and-Bound), lineare 0/1-Optimierung (Modellierung, Schnittebenen).
Die Vorlesung wendet sich an Studierende der Informatik in Haupt-
oder Nebenfach sowie an Lehramtsstudenten. Kenntnisse im Gebiet
Algorithmen und Datenstrukturen und Programmierkenntnisse werden
vorausgesetzt. Zum großen Teil baut die Vorlesung nicht auf der
Vorlesung "Effiziente Algorithmen I" auf, benötigter Stoff kann
mittels eines Skriptes nachgelesen werden.
Der erste Teil des Skriptes finden Sie im Elektronischen SEMesterapparat (ESEM) der UB .
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: Di
16.10.2007
Übungen zur Vorlesung "Effiziente Algorithmen II" (Reinelt, 2 SWS)
(zusammen mit Herrn Oswald)
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: Mi 14-16, Raum: U013, INF 350
Graphen spielen bei der Modellierung sehr vieler Anwendungsprobleme eine wichtige Rolle. Diese Vorlesung beschäftigt sich mit den Grundlagen der Graphentheorie. Themen sind Struktur von Graphen, Bäume und Zusammenhang, Eulersche und Hamiltonsche Graphen und Digraphen, planare Graphen, Matchings und Zerlegungen, Graphfärbungen, Ramsey-Theorie und Zufallsgraphen.
Literatur:
- G. Chartrand, L. Lesniak: Graphs and Digraphps (fourth edition), Chapman and Hall / CRC. 2005. ISBN 1-58488-390-1.
- W. Kocay, D.L. Kreher: Graphs, Algorithms, and Optimization. Chapman and Hall / CRC. 2005. ISBN 1-584888-396-0.
- Béla, Bollobás: Graph
Theory, An Introductory Course.
Springer-Verlag, Berlin Heidelberg. 1979. ISBN 3-540-90399-2.
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: Mo 14-16, Di. 14-16, Raum: U 013, INF 350
Übungen zur Vorlesung "Graphentheorie" (Galambos, 2 SWS)
Die zur Vorlesung angebotenen Übungen dienen der Vertiefung des
Stoffes. Die
Teilnahme an den Übungen wird empfohlen. Durch Bearbeitung von
Aufgaben und Teilnahme an den Übungsstunden kann ein
Übungsschein erworben werden.
Termin: Mi 16-18, Raum: U013, INF 350
 |
 |
|
Zur erfolgreichen Seminarteilnahme sind ein mündlicher Vortrag
sowie eine schriftliche Ausarbeitung erforderlich. Es kann ein Nachweis
nach ECTS über 3 Leistungspunkte erworben werden.
Vorbesprechung: Di 24.07, 14 Uhr Raum: U 014, INF 350
Termin: Do 14-16, Raum: 013, INF 348
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. 12.07.07, CP
comopt{at}informatik.uni-heidelberg.de
