Programmierpraktikum: Effiziente Algorithmen
für Optimierungsprobleme und Planungsaufgaben
(SS 97)

Prof. Dr. A.B. Cremers
Dipl. Math. C. Hundack
Dipl. Inf. (Univ. Paris XI) J. Lüssem

(gemeinsames Praktikum mit Prof. Dr. M. Karpinski u. Mitarbeitern)

Noch einige Praktikumsplätze zu vergeben (Stand: 1. März 1997)

Inhalt 
Informationen

Inhalt des Programmierpraktikums:

  • Timetabling: Timetabling umfaßt Probleme aus der Routen- Standort- und Ablaufplannung. Die vielfältigen Lösungsverfahren basieren u.a. auf Graphfärbungen, Threshold Acceptance, Simulated Annealing und Genetischen Algorithmen. Es werden Algorithmen für ein konkretes Planungsproblem formuliert und prototypisch implementiert. (6 - 8 Personen)

  • Online Algorithmen (Navitationsproblem): Im allgemeinen wird bei der algorithmischen Behandlung von Problemen davon ausgegangen, daß die gesamte Eingabe a priori vorliegt. Bei vielen praktischen Problemen ist jedoch ein Algorithmus erforderlich, der, ohne verläßliche Informationen über die zukünftige Eingabe zu haben, Entscheidungen auf der Basis der bisherigen Informationen trifft. Diese Algorithmen werden Online-Algorithmen genannt. Die Qualität der Lösung eines Online-Algorithmus' wird durch den Vergleich zu der des besten Offline-Algorithmus' für alle möglichen Eingaben bestimmt ( competitive analysis).

    Konkret soll das Durchsuchen eines unbekannten Polygons mit einem (sehenden) Roboter betrachtet werden. Dieses Problem entspricht dem Auffinden einer Optimal Watchman Tour, das in O(n) Zeit gelöst werden kann. (ca. 2 Personen)

    Zeit und Ort: wird mit den Teilnehmern vereinbart

    Beginn: Erste Woche

    Vorbesprechung: Dienstag, 04.02.97, 13 Uhr, N327

    Bereich: C

    Voraussetzungen: Vordiplom, praxisnahe Kenntnisse der Programmiersprachen C++ und Visual C++. Je nach Thema sind Kenntnisse in den Bereichen Graphentheorie oder der stochastischen/kombinatorischen Optimierung erforderlich.

    Nachfolge-/Begleitveranstaltungen: Diplomarbeiten können aufbauend auf einigen Themen bearbeitet werden.

    Vortragsmodus: Vorträge der Projektgruppen, schriftliche Ausarbeitung in LaTeX

    Plätze: 16

    URL: Nähere Informationen sind ab dem 1. Februar unter http://www.informatik.uni-bonn.de/~jens erhältlich.

    Literatur: Wird bei der Vorbesprechung bekanntgegeben (Vorwiegend Zeitschriftenartikel)

    Weitere Informationen:

     Zeit und Raum  Genauer Termin nach Absprache mit den Teilnehmern.
      erste Semesterwoche (auf Wunsch in den Semesterferien)
     Vorbesprechung  Dienstag, 04.02.1997, 13 Uhr s.t.
     Seminarraum N327
     Anmeldungen nachträglich per email jens@uran.informatik.uni-bonn.de möglich  
     Zuordnung  Bereich A/B/C
     Modus  Vorträge der Projektgruppen, schriftliche Ausarbeitung in LaTeX
    vierzehntägige Treffen
     Voraussetzungen
     Vordiplom, praxisnahe Kenntnisse der Programmiersprachen C++ und Visual C++.
    Je nach Thema sind Kenntnisse in den Bereichen Graphentheorie oder der
    stochastischen/kombinatorischen Optimierung erforderlich.
     Anzahl der Plätze  16
     Literatur
     Eine Bibliographie zum Thema Timetabling (mit Einträgen bis 1995) ist hier zu finden.
     Eine Bibliographie zum Thema Online-Algorithmen ist als .bib-file (compressed 32KB) verfügbar.

    [Uni-Bonn] [Informatik] [III]