Veranstaltungen im Winter-
semester 2009/2010
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 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 und Mathematik 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.
Das Skript zu Effiziente Algorithmen I ist bei der Fachschaft erhältlich.
Das Skript zu Effiziente Algorithmen II wird in den Elektronischen Semesterapparat (ESEM) der UB gestellt.
Termin: Mo 11-13, Mi 11-13, Raum: U 013, INF 350, Beginn: Mi.
14.10.2009
*** Die Klausur findet am Mo. 1. Februar statt. ***
Klausuranmeldung in den Übungen oder im Sekretariat ab sofort möglich bis zum Mi. 27 Januar
Die zur Vorlesung gehörigen Übungen dienen der Vertiefung des
Stoffes, durch Bearbeitung von Aufgaben. Die persönliche Anwesenheit ist obligatorisch.
Termin: Mo. 14-16, Di 16-18 Raum: U 013, INF 350
***ACHTUNG! Am Mo 11. und 18. Januar 2010 findet die Übung ausnahmsweise im Raum 013 im INF 348 statt!***
Beginn: Mo. 26.10 bzw. Di. 27.10.2009
Das Modul wird mit 9 LP gewertet.
Diese Lehrveranstaltung behandelt die aktuelle Theorie und Praxis der
gemischt-ganzzahligen Optimierung. Themen der Veranstaltung sind:
Optimierungsmodelle, Grundlagen der
linearen Optimierung und polyedrischen Kombinatorik, Dualität,
Relaxierungen, Schnittebenengenerierung, Preprocessing,
Dekompositionsverfahren, Heuristiken, Branch-and-Bound,
Branch-and-Cut, Anwendungen in der Praxis. Die Veranstaltung umfasst
einen Vorlesungsteil und einen integrierten
Übungsteil mit praktischen Übungen am Computer. In
den Übungen wird insbesondere vermittelt, Optimierungsmodelle zu
formulieren, Modellgeneratoren zu benutzen und mit
Hilfe von Optimierungsbibliotheken eigene Spezialalgorithmen zu
entwickeln.
Die Vorlesung wendet sich an Studierende der Informatik oder
Mathematik in Haupt- oder
Nebenfach sowie an Lehramtsstudenten und Doktoranden.
Außer mathematischem Grundwissen
und Programmierkenntnissen in C oder C++ werden keine Kenntnisse
vorausgesetzt.
Die erfolgreiche Teilnahme an der Veranstaltung wird mit 3
LP bescheinigt.
*** Dieser Kurs wird auf Englisch gehalten! This course is held in English! ***
Ein Kursprogramm finden Sie hier.
You find the program here.
Termin: Mo 8. bis Do 11. Februar 2010 ganztags, 09-13: Raum: U 013, INF 350 +
14-18: Raum: U 012, INF 350
|
If you are interested in participating in this course please send an email to comopt{at}informatik.uni-heidelberg.de with your name and status (HGS-member, GK-member, EMMA/Bachelor/Master-student in Computer Science/Mathematics). Your registration - best until January 31 - facilitates our organization. Of course, you can cancel your registration anytime. |
In immer mehr Anwendungen werden komplexe Zusammenhänge als Netzwerk
modelliert, wie z.B. metabolische Netzwerke, Transportnetzwerke, soziale Netzwerke, usw.
Wir werden uns in diesem Seminar mit der Frage beschäftigen, wie mit Hilfe
von mathematischen und informatischen Methoden Informationen aus solchen
Netzwerken gezogen werden können. Solche Eigenschaften von Netzwerken
sind beispielsweise lokale Dichte, Konnektivität, Modularität, Robustheit.
Als Grundlage der Vorträge dient das Buch Network Analysis (Brandes, Erlebach).
Die Veranstaltung richtet sich an Studierende von
Diplom und Lehramt Mathematik, Lehramt, Bachelor und Master Informatik.
Zur erfolgreichen Seminarteilnahme sind ein mündlicher Vortrag
sowie eine schriftliche Ausarbeitung erforderlich. Das Seminar wird mit 3 LP bewertet.
Vorbesprechung: Do 05.07.2009, 14 Uhr Raum: U 013, INF 350
Termin: Di 14-16, Raum: 013, INF 348
Beginn: Di. 20.10.2009
Hauptseminar "Optimierung" (Reinelt, 2 SWS)
Dieses Seminar ist für Mitarbeiter sowie die Studenten gedacht, die eine Abschlussarbeit im Bereich Informatik und Algorithmische Optimierung schreiben. Es wird über die laufenden bzw. abgeschlossenen Arbeiten berichtet. Vorträge werden jeweils durch Aushang angekündigt.
Termin: n.V.
"Softwarepraktikum Optimierung für Fortgeschrittene" (6 SWS)
(Reinelt,Oswald)
In den Software-Praktika werden Projekte aus dem Bereich Optimierung
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 über 6 (Anfängerpraktikum) bzw. 9 LP
(Fortgeschrittenenpraktikum) 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 Di 11-12 und nach den Vorlesungen. Weitere Termine bitte über das Sekretariat vereinbaren (Tel. 54 57 48)
mod. 22.01.10, CP
comopt{at}informatik.uni-heidelberg.de
