LS 2

Home
Teaching (German)
Winter 04/05
Sommer 04
Diplomarbeiten (pdf)
Frühere Semester
Service
Travel
Staff
Contact
Private

External Links

Universität Dortmund
Computer Science Faculty
Collab. Research Center 531
Collab. Research Center 475
Research Cluster 1126
Student Advisory

Vorlesung "Effiziente Algorithmen"

im Sommersemester 2002

Detlef Sieling



Die Übungsscheine zur Vorlesung EA können ab sofort am Lehrstuhl Informatik 2 in R. 336 bei Frau Kühn abgeholt werden.





Informationen zur Vorlesung

  • Vorlesungstermine:

    Wochentag Uhrzeit Hörsaal
    Montag 10:15-12:00 Uhr GB 5/113
    Mittwoch 10:15-12:00 Uhr GB 5/113

  • Die erste Vorlesung findet am 15.04.2002 statt.

  • Vorlesungsinhalt:
    Effiziente Algorithmen werden in vielen Bereichen der Informatik und in anderen Wissenschaften benötigt. So besteht z. B. 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)
    • 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 oder Branch-and-Bound 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 selbst effiziente Algorithmen entwerfen und analysieren zu können. Nebenbei werden die besten bekannten Algorithmen für zentrale Probleme vorgestellt.

  • Vorlesungsskript:
    Postscript (1384k), PDF (797k)

  • Fehlerliste zum Skript:
    Postscript, PDF
    Für Verbesserungsvorschläge und die Meldung von Fehlern im Skript sind wir immer dankbar.

  • Prüfungsrelevanter Inhalt
    Die folgende Datei führt die prüfungsrelevanten Teile des Skripts auf:     Postscript, PDF.


Informationen zu den Übungen

  • Übungstermine: Es gibt 7 Übungsgruppen.

    Nr Wochentag Uhrzeit Raum Betreuer
    1 Dienstag 08:15-10:00 Uhr OH 16, E 07 Peter Bollweg
    2 Dienstag 08:15-10:00 Uhr OH 16, 205 Hubert Wagner
    3 Dienstag 10:15-12:00 Uhr OH 16, E 07 Peter Bollweg
    4 Donnerstag 08:15-10:00 Uhr GB 4, R. 113 Carsten Witt
    5 Donnerstag 10:15-12:00 Uhr OH 16, 205 Hubert Wagner
    6 Donnerstag 10:15-12:00 Uhr GB 4, R. 113 Carsten Witt
    7 Freitag 12:15-14:00 Uhr OH 16, 205 Hubert Wagner


  • Bitte melden Sie sich zu einer der sieben Übungsgruppen an. Tragen Sie sich dazu bitte ab dem 16. April um 08:00 Uhr in eine der dann vor Raum 328 im Geschossbau 4, Campus Süd, aushängenden Listen ein. Vor dem 16. April werden die Listen noch nicht aushängen und es werden noch keine Anmeldungen entgegengenommen.

  • Die erste Übung findet in der zweiten Semesterwoche statt.

  • In der ersten Vorlesung am 15. April verteilen wir Übungsblatt 1, dessen Aufgaben in der ersten Übungsgruppe besprochen werden. Ihre Lösungen zu den Aufgaben auf Blatt 1 geben Sie bitte nicht ab.

  • Die Übungsblätter 2, 3 und 5 bis 13 werden immer mittwochs in der Vorlesung verteilt. Da am 1. Mai keine Vorlesung stattfindet, geben wir Blatt 4 bereits am 29. April aus. Nach den Vorlesungen sind die Übungsblätter auch auf dieser Seite zu finden bzw. können am LS 2 (GB 4, 2. OG) auf dem Flur zwischen Raum 335 und Raum 336 abgeholt werden.

  • Die Lösungen zu den Übungsblättern 2 und 4 bis 13 müssen spätestens bis Mittwoch um 10 Uhr in der auf die Ausgabe folgenden Woche abgegeben werden (Einwurf in den für die jeweilige Übungsgruppe bestimmten Briefkasten im Pavillon 6). Wegen des Feiertages am 1. Mai sollen die Lösungen zu Blatt 3 bereits am 30. April abgegeben werden. Bitte Namen, Matrikelnummer und Übungsgruppennummer nicht vergessen.

  • Die bewerteten Übungsblätter werden je vier Aufgaben mit der Höchstpunktzahl von 4 Punkten enthalten. Durch Bearbeitung der Blätter 2 bis 13 können Sie somit insgesamt maximal 192 Punkte erreichen.

  • Um die Arbeit in Gruppen zu ermöglichen, dürfen bis zu drei Studentinnen/Studenten eine gemeinsame Lösung abgeben. Dann muss aber jede(r) dieser Gruppe in der Lage sein, die Lösung in der Übungsgruppe vorzustellen.

  • Kriterien zum Erwerb eines Scheines:

    • Insgesamt mindestens die Hälfte der erzielbaren Punkte,
    • regelmäßige Anwesenheit in der Übungsgruppe, nämlich an mindestens 10 von 13 Terminen.

    Wir behalten uns vor, die Vergabe des Scheines in Zweifelsfällen von einem Fachgespräch abhängig zu machen.

  • Bei Rückfragen wenden Sie sich an Detlef Sieling, Peter Bollweg, Hubert Wagner oder Carsten Witt.




Übungsblätter

Die Übungsblätter werden am Tag ihrer Ausgabe
automatisch um 12.00 Uhr elektronisch bereitgestellt.

Anmerkungen zu den Übungsaufgaben

  • Zu Aufgabe 7.2: Auf vielfachen Wunsch findet sich hier die in den Gruppen 4 und 6 am 06.06.02 vorgestellte Tabelle als Postscript und als PDF.

Carsten Witt
Letzte Änderung: 6. August 2002