Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik der Ludwig-Maximilians-Universität München

Vorlesung im Grundstudium: Effiziente Algorithmen (SS03)

Inhaltsverzeichnis dieser Seite

  • Organisatorisches
  • Inhalt
  • Gliederung
  • Literatur
  • Vorlesungslogbuch
  • Material zur Vorlesung
  • Übungsblätter
  • Klausuren
  • Statistik
  • Feedback, Diskussionsforum
    •

    Organisatorisches

    Vorlesung:
    Dr. Jan Johannsen: Vorlesung: Effiziente Algorithmen, 4-stündig
    Zeit und Ort: Di 12 - 14 Uhr, HS E.51 ; Do 12 - 14 Uhr, HS E.52

    Übungen:
    Dr. Ralph Matthes
    Übungsblätter werden Donnerstags in der Vorlesung ausgegeben und sind elektronisch auf der Vorlesungsseite verfügbar. Die Übungen werden in der folgenden Woche in den Übungsgruppen besprochen. Die Hausaufgaben können in den Übungsgruppen abgegeben werden, sie werden in der folgenden Woche korrigiert zurückgegeben, aber nicht bewertet.

    Übungsgruppen:
    Nr.TagZeitOrtTutor
    1Mo14:00-15:30 UhrE.46Roman Flammer
    2Mo16:00-17:30 UhrE.46Roman Flammer
    3Do14:15-15:45 Uhr1.35Flavia Moser
    4Do14:15-15:45 Uhr1.39Ralph Matthes
    5Do16:15-17:45 Uhr1.05Flavia Moser
    6Fr16:15-17:45 Uhr1.27Ralph Matthes

    Hörsäle E.46, E.51 und E.52 in der Theresienstraße 39
    Alle übrigen Hörsäle in der Oettingenstraße 67


    Der Übungsbetrieb ist beendet.

    Vorkenntnisse:
    Informatik I + II

    Hörerkreis: :
    Studierende der Informatik, Medieninformatik und Computerlinguistik
    Studierende mit Nebenfach Informatik

    Schein:
    Scheinerwerb durch Klausur
    gilt für: Diplomvorprüfung im Haupt- und Nebenfach Informatik

    zurück zum Inhaltsverzeichnis dieser Seite

    Inhalt

    Die Vorlesung führt in grundlegende Algorithmen und Datenstrukturen ein, welche in fast allen Gebieten der Informatik und verwandten Disziplinen Anwendung finden. Wir lehnen uns eng an das unten angegebene Lehrbuch von Cormen et al. an, das in mehreren Präsenzexemplaren in der Bibliothek vorhanden ist.

    Gliederung

    Literatur

    zurück zum Inhaltsverzeichnis dieser Seite

    Vorlesungs-Log

    Datum behandelte Themen
    8.4.Organisatorisches, Übersicht, Literatur, Einführung, Beispiel: Insertion-Sort.
    10.4.Asymptotische Notation. Entwurfsmethode Divide-and-conquer, Beispiel: Merge-Sort. Master-Methode zum Lösen von Divide-and-conquer Rekursionen, mit Beispielen.
    15.4.Divide-and-conquer-Verfahren zur Multiplikation von Matrizen nach Strassen. Übersicht Kapitel 2: Sortieren und Suchen. Datenstruktur Heap, Prozeduren Heapify, Build-Heap und Heap-Sort.
    24.4.Quicksort: Algorithmus, best-case O(n log n), worst-case O(n^2). Probabilistisches Quicksort, erwartete Laufzeit ist O(n log n). Vorführung animierter Sortieralgorithmen. Untere Schranke von Omega(n log n) für vergleichsbasiertes Sortieren.
    29.4.Obere und untere Schranken für Bestimmung des Maximums, und des Maximums und Minimums simultan. Selektion: Problemstellung, Probabilistischer und deterministischer Algorithmus zur Selektion in erwarteter bzw. worst-case Linearzeit.
    6.5.Übersicht Kapitel 3: Datenstrukturen. Prioritätswarteschlangen und ihre Realisierung durch Heaps. Dynamische Mengen, Realisierung durch binäre Suchbäume. Rot-Schwarz-Bäume: Definition, Eigenschaften, 2log(n+1) obere Schranke an die Höhe, Einfügeoperation.
    8.5.Einfüge- und Löschoperationen für Rot-Schwarz-Bäume. Hashtabellen: Motivation durch direkte Adressierung, Häufigkeit von Kollisionen, Kollisionsbehandlung durch Verkettung, Hashfunktionen: Divisions- und Multiplikationsmethode.
    13.5.Offen adressierte Hashtabellen: Einfüge und Suchprozedur. Lineares und Quadratisches Sondieren, double hashing. Berechnung der mittleren Zahl von Sondierungen bei erfolgloser und erfolgreicher Suche. Übersicht Kapitel 4: Entwurfs- und Analysemethoden. Einführung in dynamische Programmierung und Optimierungsprobleme.
    15.5. Dynamische Programmierung, Konzept und Beispiele: optimale Klammerung bei der Multiplikation von mehreren (nichtquadratischen) Matrizen, Berechnung einer längsten gemeinsamen Teilfolge zweier Folgen.
    20.5. Greedy-Algorithmen: Konzept und einfache Beispiele, Auswahlproblem als künstliches Beispiel. Huffman-Codes: Definition, Nutzen zur Datenkompression, Greedy-Algorithmus zur Konstruktion.
    22.5. Verbesserte Behandlung von Greedy-Algorithmen: abstrakter Greedy-Algorithmus und Bedingungen, unter denen er eine optimale Lösung liefert. Beispiele vom 20.5. als Spezialfälle, damit Beweis der Korrektheit des Huffman-Algorithmus.
    27.5. Amortisierungs-Analyse: Konzept, Beispiel Binärzähler, Methoden: Aggregat-, Konto- und Potenzialmethode. Weiteres Beispiel: Realisierung einer queue durch zwei stacks. Abstrakte Datenstruktur für Familien disjunkter Mengen (union-find).
    3.6.Realisierung der union-find Datenstruktur durch Wälder. Analyse der Komplexität der union-find Wälder mit Rangfunktion, obere Schranke für Wälder mit Pfadkompression erwähnt. Übersicht Kapitel 5: Graphalgorithmen.
    12.6. Graphalgorithmen: Breiten- und Tiefensuche, topologische Sortierung von gerichteten azyklischen Graphen, Zerlegung in starke Zusammenhangskomponenten.
    17.6. Beweis der Korrektheit des Algorithmus zur Zerlegung in starke Zusammenhangskomponenten. Minimale Spannbäume: Algorithmen von Kruskal und Prim. Kürzeste Wege: Problemstellung.
    24.6. Kürzeste Wege: Relaxation, Invarianten beliebiger Folgen von Relaxationen, Algorithmen von Dijkstra und für kürzeste Wege in dags, mit Beweis der Korrektheit.
    26.6. Kürzeste Wege: Algorithmus von Bellman-Ford, Korrektheit. Algorithmen zur Berechnung der Minimaldistanzen zwischen je zwei Knoten (all pairs shortest path), mit Matrizenmultiplikation und à la Floyd-Warshall.
    1.7. Flüsse in Netzwerken: Problemstellung, Definitionen. Restnetzwerk und Erweiterungspfade, Methode von Ford-Fulkerson. Konkretisierung als Edmonds-Karp-Algorithmus.
    3.7. Algorithmische Geometrie: Übersicht, Einführung. Punkte, Geraden und Strecken, Kreuzprodukt mit Anwendungen. Schnitte zweier Strecken, Verfahren zum Finden von Schnitten in einer Menge von Strecken.
    8.7. Algorithmische Geometrie: Konvexe Hülle einer endlichen Punktmenge, Algorithmen zur Berechnung: Graham's scan und Jarvis' march. Divide-and-conquer Algorithmus zum Finden zweier Punkte minimaler Distanz in einer endlichen Punktmenge.
    10.7. String Matching: Problemstellung, Anwendungen. Naiver Algorithmus, Algorithmus von Rabin-Karp mittels fingerprints. String matching mit endlichen Automaten.

    zurück zum Inhaltsverzeichnis dieser Seite

    Material zur Vorlesung

    zurück zum Inhaltsverzeichnis dieser Seite

    Übungsblätter

    Ausgewählte Lösungen

    Klausuren

    Die Bearbeitungszeit beträgt jeweils 120 Minuten.

    Zur ersten Klausur

    Keinerlei Hilfsmittel sind erlaubt. Bringen Sie aber unbedingt passende Schreibgeräte mit. Ein amtlicher Lichtbildausweis und Ihr Studentenausweis sind unbedingt zur Klausur mitzubringen. Sollten Sie aus gesundheitlichen Gründen am Mitschreiben verhindert sein, so müssen wir auf der unverzüglichen Vorlage eines ärztlichen Attests bestehen. Auch dann werden wir einen Weg der Leistungsfeststellung finden.
    Die Anmeldung war bis zum 26. Mai möglich, es haben sich 123 Teilnehmer zur Klausur angemeldet.

    Hinweise für die Vorbereitung

    Bedenken Sie, dass die Klausur vor allem darauf abzielt, Ihre Fähigkeiten im Umgang mit dem Stoff der Vorlesung zu erkennen. Es ist nicht unser Ziel, auswendig gelerntes Wissen abzuprüfen. Insbesondere müssen Sie nicht die Transformationen auf Rot-Schwarz-Bäumen auswendig können. Andererseits verlangt natürlich jedes verstandene Konzept ein gewisses Wissen, um damit arbeiten zu können. Wer die Übungen ernsthaft verfolgt hat, sollte dieses Wissen allerdings damit erworben haben. Fragen Sie sich beim Durchlesen von Vorlesungen und Übungen, welche Methoden neu eingeführt wurden. Davon werden vermutlich möglichst viele verschiedene in einer Klausur behandelt werden. Je besser Sie sie beherrschen, desto schneller kommen Sie mit den Aufgaben zurecht. Zeitmangel ergibt sich vor allem aus mangelnder Übung.

    Ergebnisse

    Erreichte Punktzahlen in der Zwischenklausur (ohne Gewähr).
    Beachten Sie, dass mit dieser Klausur noch keine Entscheidung über das Bestehen gefallen ist. Die hypothetische Mindestpunktzahl zum Bestehen beträgt 18 Punkte. Die zweite Klausur wird, wie versprochen, 60% des Gesamtgewichts haben. Das regeln wir so, daß es statt diesmal 72 Punkten sogar 108 maximal erreichbare Punkte gibt. Wiederum wird es eine hypothetische Mindestpunktzahl zum Bestehen geben. Die Scheinbedingung ist dann erfüllt, wenn Ihre Punktzahlen aus beiden Klausuren zusammen mindestens die Summe der beiden hypothetischen Mindestpunktzahlen ergeben.

    Klausureinsicht

    war am Mittwoch, dem 25. Juni, von 13:30 bis 16:00 im Raum Z1.09.

    Zur zweiten Klausur

    Die Anmeldung zur zweiten Klausur ist nicht nötig für die Teilnehmer an der ersten Klausur und diejenigen, die aus Krankheitsgründen eine mündliche Nachprüfung mitgemacht haben. Falls jemand nicht zu diesem Personenkreis gehört und dennoch die zweite Klausur mitschreiben möchte, so ist eine formlose Anmeldung per Email mit Angabe von Matrikelnummer, Hauptfach und Fachsemesterzahl beim Übungsleiter Voraussetzung für die Teilnahme.

    Keinerlei Hilfsmittel sind erlaubt. Bringen Sie aber unbedingt passende Schreibgeräte mit. Ein amtlicher Lichtbildausweis und Ihr Studentenausweis sind unbedingt zur Klausur mitzubringen. Sollten Sie aus gesundheitlichen Gründen am Mitschreiben verhindert sein, so müssen wir auf der unverzüglichen Vorlage eines ärztlichen Attests bestehen. Auch dann werden wir einen Weg der Leistungsfeststellung finden.

    Hinweise für die Vorbereitung der zweiten Klausur

    Der Stoffumfang ist der des gesamten Semesters. Es soll nun im Gegensatz zur ersten Klausur auch verlangt werden können, einen der ausführlich besprochenen Algorithmen an einem Beispiel anzuwenden. Wieder aber schliessen wir die Transformationen auf den Rot-Schwarz-Bäumen davon aus.

    Ergebnisse der zweiten Klausur

    Achtung: Bei der Klausureinsichtnahme wurde nachkorrigiert und die hypothetische Mindestpunktzahl zum Bestehen der zweiten Klausur neu auf 36 Punkte von 108 erreichbaren Punkten herabgesetzt. Damit ist die mindeste Gesamtpunktzahl für den Scheinerwerb bei 18+36=54 Punkten von 180 erreichbaren Punkten.
    Erreichte Punktzahlen in den Klausuren mit Gesamtpunktzahl und Noten (ohne Gewähr). Nur Teilnehmer der zweiten Klausur werden aufgelistet. Teilnehmer nur der ersten Klausur haben alle nicht die erforderliche Gesamtpunktzahl erreicht.

    Einsichtnahme und Scheinausgabe

    Beide Klausuren konnten am Dienstag, den 5. August von 17:00 Uhr bis 19:00 Uhr im Raum Z1.09 (Oettingenstr. 67) eingesehen werden (und die Scheine empfangen werden).
    Ab Mi, 6.8., liegen die Scheine im Sekretariat des Lehrstuhls (Frau Nentwich-Mertel).

    Statistik

    153 Teilnehmer haben sich zu den Übungen angemeldet.

    123 Teilnehmer haben sich zur ersten Klausur angemeldet, 18 von diesen sind nicht Übungsteilnehmer.

    63 Teilnehmer haben die erste Klausur mitgeschrieben.

    29 Teilnehmer haben die zweite Klausur mitgeschrieben. Dafür gab es keine Zulassungsbeschränkung.

    75,9 Prozent der Teilnehmer der zweiten Klausur haben die hypothetische Bestehensgrenze der zweiten Klausur erreicht.

    1 Teilnehmer hat bereits mit der ersten Klausur den Schein erworben.
    16 Teilnehmer haben mit der zweiten Klausur alleine den Schein erworben, davon zwei Teilnehmer, die in der ersten Klausur nicht die hypothetische Bestehensgrenze erreichten.
    1 Teilnehmer erhält den Schein trotz Nichterreichens der hypothetischen Bestehensgrenze der zweiten Klausur.
    5 Teilnehmer erhalten den Schein trotz Nichterreichens der hypothetischen Bestehensgrenze der ersten Klausur.

    23 Teilnehmer erhalten einen Schein.

    Feedback, Diskussionsforum

    Vorlesungen und Übungen können durch intelligente Fragen aus dem Publikum sehr gewinnen, die Dozenten und Tutoren aus (am besten konstruktiver) Kritik nach der Lehrveranstaltung viele Anregungen beziehen. Für Fragen und Antworten von allgemeinem Interesse steht auch ein Diskussionsforum zur Verfügung:

    Mailingliste EFFIZIENTE ALGORITHMEN