Veranstaltungen im Wintersemester 2003/2004
Vorlesung "Compilerbau" (4 SWS)Compilerbau ist eine klassische Informatik-Disziplin, die sich bis in die 80er Jahre rasant entwickelt hat, und ist sicher eines der am besten erforschten Gebiete in der Informatik. Solide theoretische Grundlagen, brauchbare formale Beschreibungen, effiziente Algorithmen und Implementierungstools stehen zur Verfügung.In dieser Vorlesung befassen wir uns mit dem generellen Problem, wie ein Computerprogramm, das in einer höheren Programmiersprache vorliegt, in ein auf einer konkreten Hardware ablauffähiges Maschinenprogramm übersetzt werden kann. Das Anwendungsspektrum des Stoffs geht allerdings über die Implementierung von Compilern hinaus. Die hier entwickelten Techniken können auf vielfältige Weise eingeesetzt werden, z. B. für Assembler, Steuerung von Editoren und Textverarbeitungsprogrammen, Abfragen von Datenbanken, Aufbereitung strukturierter Daten, Druckausgabesprachen bzw. allgemein zur automatisierten Analyse hierarchisch strukturierter Dokumente. Der Aufbau eines Compilers selbst ist ein gutes Musterbeispiel für die Konzeption eines grossen Softwareprojekts durch Zerlegung in Teilaufgaben und Spezifikation von Schnittstellen zwischen den entsprechenden Modulen. Themen der Vorlesung sind Formale Sprachen, Lexikalische Analyse, Syntaxanalyse, Semantische Analyse, Codegenerierung und Codeoptimierung. Die Vorlesung wendet sich an Studierende im Haupt- oder Nebenfach Informatik. Kenntnisse aus den Grundvorlesungen Informatik werden vorausgesetzt. Zur Vorlesung wird ein Skript erhältlich sein, dass im Sekretariat erworben werden kann. Zu dieser Vorlesung kann Termine: Di 11-13 INF 368 Raum 432, Do 9-11 INF 348 Raum 013, Beginn: 16.10.2003 Übungen zur Vorlesung "Compilerbau" (2 SWS)(zusammen mit Herrn Ahr)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. Zum Erwerb des ECTS-Scheins ist - neben der schriftlichen Prüfung - die erfolgreiche Teilnahme an den Übungen obligatorisch. Termin: Do 14-16 INF 348 Raum 013 Seminar "Synergien zwischen Mathematical Programming und Constraint Programming" (2 SWS)(zusammen mit Herrn Oswald)Mit Mathematical Programming wird der Zweig der Mathematik bezeichnet, der sich mit Optimierungsproblemen beschäftigt (das Wort "Programming" bedeutet hier nicht das Programmieren eines Computers, sondern "Program" bedeutet hier eher Optimierungsproblem). Im Wesentlichen werden in diesem Gebiet mathematische Verfahren entwickelt, um auf einer Menge von Variablen eine Zielfunktion unter einer Menge von Nebenbedingungen zu minimieren oder maximieren. Der Bereich Constraint Programming ist in der Informatik entstanden, speziell in dem Forschungsgebiet der Künstlichen Intelligenz. Ursprünglich befasste man sich hier mit Problemen der Logik insbesondere dem Lösen von Erfüllbarkeitsproblemen, später wurde die Anwendung auch auf andere Bereiche ausgedehnt. Constraint Programming beschäftigt sich einerseits mit der Bereitstellung einer komfortablen Modellierungssprache oder -möglichkeit zur einfachen Formulierung des Problems. Andererseits werden Suchverfahren entwickelt bzw. bereitgestellt, die für das vorgegebene Problem die optimale Lösung bestimmen. Durch intelligente Ausnutzung der vorgegebenen Bedingungen wird der Suchraum so weit wie möglich verkleinert. Ferner kann der Benutzer zusätzliche Vorgaben für den Suchprozess machen. Die beiden Bereiche entwickelten sich bis vor wenigen Jahren unabhängig voneinander. Dann erst erkannte man die Gemeinsamkeiten und das Potenzial, das in der Kombination der Methoden beider Bereiche liegen könnte. Seitdem hat sich eine aktive Forschung entwickelt, die sich teilweise auch schon in kommerziellen Produkten niedergeschlagen hat. In diesem Seminar wollen wir sowohl den aktuellen Forschungsstand auf diesem Gebiet erarbeiten als auch Werkzeuge aus der Praxis (z.B. OPL, Optimization Programming Language) kennenlernen. 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: Di 14-16 INF 368 Raum 220 Seminar "Polyedrische Kombinatorik" (2 SWS, angewandte Mathe)(zusammen mit Herrn Oswald und Herrn Theis)Ein (konvexes) Polyeder ist der Schnitt endlich vieler Halbräume im R^n. In der Polyedrischen Kombinatorik beschäftigt man sich mit Polyedern, die als konvexe Hülle einer durch eine kombinatorische Fragestellung definierten Menge von Punkten gegeben sind. Ein Beispiel ist etwa die konvexe Hülle der charakteristischen Vektoren aller Hamiltonschen Kreise in einem ungerichteten Graphen. In diesem Seminar werden zunächst vorlesungsartig die Voraussetzungen aus der Polyedertheorie vermittelt. Anschließend werden wir uns schwerpunkmäßig mit zwei eng verwandten Klassen von Polyedern beschäftigen: eines davon ist das oben als Beispiel angesprochene. Obwohl diese beiden Klassen von Polyedern in der Kombinatorischen Optimierung (zum Nachweis der Optimalität von Lösungen für das Traveling Salesman Problem) von großer Bedeutung sind, gibt es noch eine Reihe von wichtigen offenen Fragen. Zu diesen gehört insbesondere die Naddef-Rinaldi-Vermutung, die das Verhältnis der beiden Klassen von Polyedern präzisiert und mit der wir uns am Schluss beschäftigen werden. Es können auch Vorträge zu Themen aus der allgemeinen Polyedertheorie vergeben werden. Zur erfolgreichen Seminarteilnahme sind ein mündlicher Vortrag sowie eine schriftliche Ausarbeitung erforderlich. Termin: Nach Vereinbarung Vorbesprechung: Di 21.10.2003, 16:00 Uhr, INF 368 Raum 220;
oder: bis 27.10. in Raum 106/104 INF 368 vorbeikommen
oder: eMail. Praktikum "Informatik" für Anfänger (4 SWS)Praktikum "Informatik" für Fortgeschrittene (6 SWS)(zusammen mit Herrn Ahr und 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.
Email / WWW / KontaktSekretariat: comopt{at}informatik.uni-heidelberg.deDino Ahr: dino.ahr{at}informatikuni-heidelberg.de Marcus Oswald: marcus.oswald{at}informatik.uni-heidelberg.de Gerhard Reinelt: gerhard.reinelt{at}informatik.uni-heidelberg.de Dirk Oliver Theis: dirk.theis{at}informatik.uni-heidelberg.de Homepage Diskrete Optimierung: http://www.informatik.uni-heidelberg
SprechstundeWährend der Vorlesungszeit Do 11 - 12 und nach den Vorlesungen.Weitere Termine bitte über das Sekretariat vereinbaren (Tel. 54 57 48). |
