LS 2

Home
Lehre
Winter 04/05
Sommer 04
Diplomarbeiten (pdf)
Frühere Semester
Service
Anreise
Mitarbeiter
Kontakt
Interna

Externe Links

Universität Dortmund
Fachbereich Informatik
SFB 531
SFB 475
DFG-Schwerp. Nr. 1126
Studieninformation

Effiziente Algorithmen

Stammvorlesung 4 V + 2 Ü, Sommersemester 2001

Ingo Wegener

[Termine] [Zusammenfassung] [Skript] [Übungen]

Termine

Wann? Wo? Wer?
Vorlesungen: Mo 10:15 - 11:45 GB V, Raum 113 Ingo Wegener
Mi 10:15 - 11:45 GB V, Raum 113 Ingo Wegener
Übungen: Di 8:30 - 10:00 GB V, Raum 420 Beate Bollig
Di 12:15 - 13:45 GB IV, Raum 318 Markus Müller-Olm
Di 16:15 - 17:45 GB IV, Raum 113 Markus Müller-Olm
Mi 8:30 - 10:00 GB V, Raum 420 Beate Bollig

Beachten Sie bitte den gegenüber der Ankündigung im Vorlesungsverzeichnis geänderten Vorlesungsort.

Zusammenfassung

Effiziente Algorithmen werden in vielen Bereichen der Informatik und in anderen Wissenschaften benötigt. So besteht der wichtigste Beitrag der Informatik zur Genomforschung in der Bereitstellung guter Algorithmen.

Der Entwurf effizienter Algorithmen ist eine Disziplin, bei der Kenntnisse in dem Gebiet, aus dem das betrachtete Problem stammt, Intuition, Fingerspitzengefühl und Entwurfsmethoden für effiziente Algorithmen zusammenspielen. Letztere werden an praktisch relevanten Beispielen in der Vorlesung gelehrt. Hinzu kommen Methoden zur Analyse der untersuchten Algorithmen.

In der Vorlesung werden die wichtigsten Algorithmentypen behandelt:

  • Algorithmen, die Probleme für jede Eingabe korrekt und mit geringer worst case Rechenzeit lösen (grundlegende Graphenprobleme, Mustererkennung, Beispiele aus der Bioinformatik, Maximierung von Flüssen in Netzwerken)
  • Algorithmen, die Optimierungsprobleme fast exakt oder einigermaßen exakt lösen, aber eine geringe worst case Rechenzeit haben (Scheduling, Rucksackproblem, Traveling Salesman Problem)
  • randomisierte Algorithmen, die eine geringe worst case Rechenzeit haben, aber mit kleiner Wahrscheinlichkeit ein falsches Ergebnis liefern (Primzahltest und alle Grundlagen für das RSA-Kryptosystem)
  • heuristische Algorithmen, die das Problem lösen und hoffentlich in vielen Fällen eine geringe Rechenzeit haben (Rucksackproblem, Traveling Salesman Problem)
Dabei kommen allgemeine Entwurfsmethoden wie dynamische Programmierung, Branch-and-Bound oder die Primal-Dual-Methode ebenso zur Sprache wie verallgemeinerbare Tricks zum Entwurf effizienter Algorithmen. Der Schwerpunkt der Vorlesung besteht darin, die Hörerinnen und Hörer in die Lage zu versetzen, in vergleichbaren Situationen selber effiziente Algorithmen entwerfen und analysieren zu können. Nebenbei werden die besten bekannten Algorithmen für zentrale Probleme vorgestellt.

Skript

Das die Vorlesung begleitende Skript ist in der Skriptenverkaufsstelle erhältlich. Es war für die Hörer der Vorlesung auch online verfügbar. Externe Interessierte können bei Ingo Wegener um eine Kopie des Skriptes nachsuchen.

Wenn Du einen Fehler im Skript findest, informiere uns doch bitte in der Vorlesung oder in den Übungen oder schicke eine Mail an Beate Bollig. Eine Liste der bisher gefundenen Fehler ist als Postscript-Datei verfügbar.

Übungen

In der Vorlesung wird jeweils am Montag ein Übungsblatt ausgegeben; das erste Übungsblatt gibt es allerdings schon am Mittwoch, dem 18.4.2001. Die Lösungen müssen bis zum folgenden Montag, 10 Uhr, im für die jeweilige Übungsgruppe bestimmten Briefkasten im Pavillon 6 abgegeben werden. Bitte Namen und Übungsgruppennummer nicht vergessen! Um die Arbeit in Gruppen zu ermöglichen, dürfen bis zu drei Studentinnen/Studenten eine gemeinsame Lösung abgeben. Selbstverständlich muss dann jede/jeder Gruppenteilnehmer in der Lage sein, die Lösung in der Übungsgruppe vorzustellen.

Auf jedem Übungsblatt gibt es zwei `Kurzaufgaben' zu je 5 Punkten und 3 `Normalaufgaben' zu je 10 Punkten. Die Kurzaufgaben erlauben eine kurze Lösung und sind in der Regel einfacher als die Langaufgaben.

Scheinkriterien

  • mindestens 20 Punkte pro Blatt
  • regelmäßige Anwesenheit und Mitarbeit in der Übung
  • Vorstellen der eigenen Lösung zu einzelnen Aufgaben in der Übung

Übungsblätter

Ansprechpartnerin bzw. -partner bezüglich der Übungen sind Beate Bollig und Markus Müller-Olm.