Veranstaltungen im
Wintersemester 2004/2005
Vorlesung
"Effiziente
Algorithmen I" (4 SWS) (Reinelt)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 oder Mathematik in Haupt- oder Nebenfach. sowie an Lehramtsstudenten. Programmierkenntnisse werden vorausgesetzt. Zusammen mit den Übungen können für den Bachelor-Studiengang "Informatik" 9 Leistungspunkte nach ECTS erworben werden. Hierzu ist die erfolgreiche Teilnahme an den Übungen sowie an einer schriftlichen Prüfung erforderlich.
Termine: Mo 11-13, Mi 11-13 Raum: U013, INF 350, Beginn: 20.10.2004
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 Schein erworben werden.
Termin: Mi. 14-16 Raum: 015, INF 348
Vorlesung und Übung bilden zusammen das Modul "Effiziente Algorithmen" für den Master-Studiengang "Informatik". Für die Absolvierung dieses Moduls wird ein Arbeitsaufwand über 9 ECTS Leistungspunkte bescheinigt. Hierzu ist die erfolgreiche Teilnahme an den Übungen sowie an einer schriftlichen Prüfung erforderlich.
Vorlesung "Gemischt-ganzzahlige Optimierung" (4 SWS) (Reinelt / Oswald)
Eines der zentralen Themen der Optimierung ist die gemischt-ganzzahlige und kombinatorische Optimierung, d.h. die Lösung von Optimierungsaufgaben, bei denen für einen Teil der Variablen oder für alle nur ganzzahlige Werte zulässig sind. Gemischt-ganzzahlige lineare Modelle und zugehörige Software sind die am häufigsten in der Praxis verwendet Optimierungswerkzeuge. Sie werden z. B. intensiv zur Lösung von Problemen in Logistik, Produktionsplanung und Tourenplanung eingesetzt.
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. Außer mathematischem Grundwissen und Programmierkenntnissen in C oder C++ werden keine Kenntnisse vorausgesetzt.
Die erfolgreiche Teilnahme an der Veranstaltung wird mit 6 ECTS-Leistungspunkten bescheinigt.
Termin: Di 14-16, CIP Pool, R U011, INF 350, Do 11-13, Raum U013, INF 350
Für die Anmeldung im Pool bitte folgendes Formular ausfllen und drucken: http://www.iwr.uni-heidelberg.de/services/equipment/pool/Kurs-Teilnehmer.php. Der Kurs steht nicht in der Kursauswahl aber kann per Hand eingetragen werden. Mit dem Ausdruck melden ins Sekretariat . Gegen eine Leihgebhr von 25,-- Euro erh�t man eine Karte die in den n�hsten Tagen fr den Raum freigeschaltet wird.
Proseminar "Algorithmen und Datenstrukturen" (2 SWS) (Reinelt / Oswald)
Das Proseminar behandelt einführende Themen aus dem Bereich Algorithmen und Datenstrukturen. Es wendet sich besonders an Studierende des Bachelor-Studiengangs "Informatik"
Zur erfolgreichen Seminarteilnahme sind ein mündlicher Vortrag sowie eine schriftliche Ausarbeitung erforderlich. Es kann ein Nachweis nach ECTS über 3 Leistungspunkte erworben werden.
Termin: Mo. 14-16, Raum 015, INF 348, Beginn: 25.10.04
Oberseminar "Algorithmische Optimierung"Dieses Seminar ist für Mitarbeiter sowie die Studenten gedacht, die eine Diplom- oder Masterarbeit im Bereich Informatik und Algorithmische Optimierung schreiben. Es wird über die laufenden bzw. abgeschlossenen Arbeiten berichtet. Termine und Vorträge werden jeweils durch Aushang angekündigt.
Kurs "Introduction to Mixed-Integer Programming"
Dieser Blockkurs gibt eine Einführung in Theorie und Praxis der gemischt-ganzzahligen Optimierung. Er umfasst sowohl Vorlesungen als auch Übungen am Computer. Außer mathematischem Grundwissen und Programmierkenntnissen in C oder C++ werden keine Kenntnisse vorausgesetzt.
Der Kurs wird als 3-tägiger Blockkurs auf Englisch abgehalten. Er wendet sich speziell an die Mitglieder des Internationalen Graduiertenkollegs "Komplexe Prozesse: Modellierung, Simulation und Optimierung", steht aber auch anderen Interessenten offen.
Termin: 16.02. - 18.02.2005, jeweils ganztägig, Raum U012, INF 350 (OMZ), Beginn: 16.02.05
Softwarepraktikum "Informatik" für Anfänger (4 SWS)
Softwarepraktikum "Informatik" für Fortgeschrittene (6 SWS) (zusammen mit Herrn Oswald)
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 Praktikumsteilnahme 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 Di 11 - 12 und nach den Vorlesungen. Weitere Termine bitte über das Sekretariat vereinbaren (Tel. 54 57 48)
mod. 11.10.04, CP
comopt{at}informatik.uni-heidelberg.de
