Algorithmen & Komplexität

Arbeitsgruppe

Forschung

Lehre

Abschlussarbeiten

zurück zur Übersicht

Logbuch Algorithmen und Datenstrukturen 1 - Sommer 2022

• Vorlesung 21 -- 07.07.2022:
  RNA Sekundärstruktur, Formalisierung (keine engen Kurven, keine kreuzenden Paarungen, komplementäre Basispaare), dynamische Programmierung, Laufzeit O(n³), Lineare Programmierung (Teaser)

  Materialien und weitere Lektüre:
  • Folien Kapitel Entwurfsmethoden (Seiten 99-119)
  • Skript [TI1]: Abschnitte 4.3.4, 4.4
  • Kleinberg, Tardos. Algorithm Design. Kapitel 6.5



• Vorlesung 20 -- 05.07.2022:
  All-Pairs-Shortest-Path (Bellman-Ford Algorithmus, Wiederholung), Algorithmus von Floyd (Orakel: Enthält ein kürzester u-v-Weg den Knoten i?, Laufzeit O(n³)), paarweises Alignment (Definition, Orakel mit Alignment von Präfixen, Laufzeit O(nm) für zwei Strings mit Längen n und m, Beispiel).

  Materialien und weitere Lektüre:
  • Folien Kapitel Entwurfsmethoden (Seiten 75-98)
  • Skript [TI1]: Abschnitte 4.3.2, 4.3.3
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 25.1
  • Kleinberg, Tardos. Algorithm Design. Kapitel 6.8, 6.6



• Vorlesung 19 -- 30.06.2022:
  TSP (Orakel, Teilprobleme L(k,S), Rekursionsgleichung, Lösung mit Laufzeit O(n² 2ⁿ), Beispiel), gewichtetes Intervall-Scheduling (Orakel, Teilprobleme opt(i), Rekursionsgleichung, Lösung mit Laufzeit O(n log n)), All-Pairs-Shortest-Path (Bellman-Ford Algorithmus, Orakel: Erste Kante eines kürzesten u-v-Weges?, Laufzeit O(n²m))

  Materialien und weitere Lektüre:
  • Folien Kapitel Entwurfsmethoden (Seiten 60-80)
  • Dynamische Programmierung TSP: Beispiel
  • Skript [TI1]: Abschnitte 4.2, 4.2.1, 4.2.2, 4.3
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 25.1
  • Kleinberg, Tardos. Algorithm Design. Kapitel 6.1, 6.8



• Vorlesung 18 -- 28.06.2022:
  Stabiles Matching, Deferred-Acceptance Algorithmus, Laufzeit O(n²) und Korrektheit. Divide and Conquer, schnelle Multiplikation von Zahlen und Matrizen. Dynamische Programmierung, Orakel-Ansatz, TSP (Orakel)

  Materialien und weitere Lektüre:
  • Folien Kapitel Entwurfsmethoden (Seiten 32-62)
  • Skript [TI1]: Abschnitte 4.3, 4.3.1, 4.3.2
  • Kleinberg, Tardos. Algorithm Design. Kapitel 1.1, 5.5
  • Stabiles Matching Visualisierung



• Vorlesung 17 -- 23.06.2022:
  Intervall-Scheduling (frühe Terminierungszeiten zuerst, Umsetzung mit Laufzeit O(n log n)), Minimierung maximaler Verspätung (frühe Fristen zuerst, Beweis der Optimalität), Huffman-Codes (Huffman-Baum, Struktureigenschaften (innere Knoten Grad 2, zu codierende Zeichen an Blättern, seltenste Zeichen sind Geschwister auf maximaler Tiefe), Greedy-Algorithmus, Laufzeit O(n log n))

  Materialien und weitere Lektüre:
  • Folien Kapitel Entwurfsmethoden (Seiten 15-31)
  • Skript [TI1]: Abschnitte 4.1.1, 4.1.2
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 16.1 und 16.3
  • Huffman Code Visualisierung



• Vorlesung 16 -- 21.06.2022:
  Union-Find Datenstruktur mit Laufzeit O(1) (union) und O(log n) (find). Entwurfsmethoden, Greedy-Algorithmen für Intervall-Scheduling (frühe Terminierungszeiten zuerst, Beweis der Optimalität), Minimierung maximaler Verspätung (frühe Fristen zuerst (earliest deadline first), Laufzeit O(n log n)), Inversionen

  Materialien und weitere Lektüre:
  • Folien Kapitel Graphalgorithmen (Seiten 86-93)
  • Folien Kapitel Entwurfsmethoden (Seiten 1-15)
  • Skript [TI1]: Abschnitte 3.3, 4.1, 4.1.1
  • Skript [DS]: Abschnitt 4.6.3
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 21.1, 21.3 und 16.1
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 11.4



• Vorlesung 15 -- 09.06.2022:
  Minimale Spannbäume, Anwendungen (Netzwerkdesign, Heuristik für das Travelling Salesman Problem), Optimalitätskriterium: S-kreuzende Kanten mit minimalem Wert, Algorithmus von Jarnik-Prim-Dijkstra (Laufzeit O((n+m) log n) mit binären Heaps, Analogie zum Dijkstra-Algorithmus für kürzeste Wege), Algorithmus von Kruskal und Union-Find Datenstruktur

  Materialien und weitere Lektüre:
  • Folien Kapitel Graphalgorithmen (Seiten 69-89)
  • Skript [TI1]: Abschnitt 3.3
  • Skript [DS]: Abschnitte 4.6.2, 4.6.3
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 21.1, 21.3 und 23
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 11.1, 11.2, 11.3, 11.4



• Vorlesung 14 -- 07.06.2022:
  Breitensuche (Laufzeit, Baum kürzester Wege); Single-Source-Shortest-Path Problem, Bindfadenmodell, Algorithmus von Dijkstra (Korrektheit, Laufzeit O((n+m) log n) mit binären Heaps)

  Materialien und weitere Lektüre:
  • Folien Kapitel Graphalgorithmen (Seiten 50-68)
  • Skript [TI1]: Abschnitt 3.2
  • Skript [DS]: Abschnitte 4.4.4, 4.6.1
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 22.2, 24.3
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 9.1, 10.1, 10.3



• Vorlesung 13 -- 02.06.2022:
  Tiefensuche für gerichtete Graphen (Baumkanten, Vorwärtskanten, Rückwärtskanten, Querkanten, Bestimmung der Kantentypen mit Anfang- und Ende-Nummerierung); Anwendungen für gerichtete Graphen (Ist ein Graph azyklisch? Berechne eine topologische Sortierung! Starker Zusammenhang)

  Materialien und weitere Lektüre:
  • Folien Kapitel Graphalgorithmen, Seiten 37-49
  • Skript [DS]: Abschnitt 4.4.3
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 22.3
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 9.2



• Vorlesung 12 -- 31.05.2022:
  Tiefensuche (Ariadne-Faden, Farbeimer, rekursive Implementierung); Tiefensuche für ungerichtete Graphen (Baumkanten und Rückwärtskanten, Wald der Tiefensuche, Bäume des Walds entsprechen den Zusammenhangskomponenten)

  Materialien und weitere Lektüre:
  • Folien Kapitel Graphalgorithmen, Seiten 21-37
  • Skript [DS]: Abschnitt 4.4.3
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 22.3
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 9.2



• Vorlesung 11 -- 24.05.2022:
  Erwartete Laufzeit doppeltes Hashing 1/(1-λ); Universelles Hashing; Zusammenfassung Wörterbücher. Graphen (Definitionen), Topologische Sortierung (Adjazenzlistendarstellung); Implementierung von Graphen (Adjazenzlisten und Adjazenzmatrix)

  Materialien und weitere Lektüre:
  • Folien Kapitel Wörterbücher, Seiten 70-80
  • Folien Kapitel Graphalgorithmen, Seiten 1-20
  • Skript [DS}: Abschnitte 5.5.2, 5.5.4, 4.4, 4.4.1 und 4.4.2
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 11.4, 22.1 und 22.4
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 4.2, 4.4, 8.3. und 8.4



• Vorlesung 10 -- 19.05.2022:
  Hashing mit Verkettung (Hashfunktionen), Hashing mit offener Adressierung (lineares Austesten, doppeltes Hashing), Analyse erwartete Laufzeit für Hashing mit Verkettung O(1+λ)

  Materialien und weitere Lektüre:
  • Folien Kapitel Wörterbücher, Seiten 50-69
  • Skript [DS]: Abschnitte 5.5, 5.5.1 und 5.5.2
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 11
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 4



• Vorlesung 09 -- 17.05.2022:
  (a,b)-Bäume ((a,b)-Eigenschaft, Tiefe, Suchstruktur, insert (Zellteilung), remove (Schlüsselklau, Fusion))

  Materialien und weitere Lektüre:
  • Folien Kapitel Wörterbücher, Seiten 35-49
  • Skript [DS]: Abschnitt 5.4
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 18
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 7.2



• Vorlesung 08 -- 05.05.2022:
  AVL-Bäume (Tiefe eines AVL-Baums mit n Schlüsseln ist höchstens 2 log(n); Lookup und Lazy Remove); Insert im AVL-Baum (Linksrotation, Rechtsrotation; Zick-Zick, Zack-Zack, Zick-Zack, Zack-Zick)

  Materialien und weitere Lektüre:
  • Folien Kapitel Wörterbücher, Seiten 15-34
  • Skript [DS]: Abschnitt 5.2
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 13 (dort werden Rot-Schwarz-Bäume beschrieben: alle Wörterbuchoperationen lassen sich wie für AVL-Bäume in logarithmischer Zeit ausführen)
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 7.1



• Vorlesung 07 -- 03.05.2022:
  Tiefe eines Heaps, BuildHeap in Linearzeit, Heapsort; Wörterbücher, Binäre Suchbäume (lookup, insert, remove, sortieren); im Worst-Case zu große Tiefe

  Materialien und weitere Lektüre:
  • Folien Kapitel Datenstrukturen, Seiten 49-55
  • Folien Kapitel Wörterbücher, Seiten 1-14
  • Skript [DS]: Abschnitte 4.5 und 5.1
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 6 und 12
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 6.1 und 7.1

  Aufgrund einer Verspätung wurden die ersten ca. 35 Minuten der Vorlesung nicht aufgezeichnet.




• Vorlesung 06 -- 28.04.2022:
  Präorder (rekursive und nicht-rekursive Implementierung), Besuchsreihenfolge für Postorder und Präorder; Priority-Queues (insert, delete_max, change_priority, remove); Heaps (Heap-Struktur, Heap-Ordnung), Umsetzung von insert (repair_up), delete_max (repair_down), change_priority und remove

  Materialien und weitere Lektüre:
  • Folien Kapitel Datenstrukturen, Seiten 27-48
  • Skript [DS]: Abschnitte 4.3.2 und 4.5.
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 6
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 6.1



• Vorlesung 05 -- 26.04.2022:
  Implementierung von Deques und Listen (zirkuläre Arrays, Speicherverwaltung über zwei Arrays Daten und Zeiger für Listen); gewurzelte Bäume (Definition, wichtige Begriffe und Operationen); Implementierungen von Bäumen (Elternarray, Binärbaum-Darstellung, Kind-Geschwister-Darstellung), Suche (Präorder, Postoder, Inorder, rekursive Implementierung)

  Materialien und weitere Lektüre:
  • Folien Kapitel Datenstrukturen, Seiten 9-29
  • Skript [DS]: Abschnitte 4.3, 4.3.1 und 4.3.2
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 10.3 und 10.4.
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 2.9



• Vorlesung 04 -- 21.04.2022:
  Mastertheorem; Laufzeitanalyse für C++-Programme (dominierende Anweisungen, Matrizenmultiplikation, While-Schleifen); Listen (einfache Verkettung; schnelle Implementierung aller Operationen bis auf Suche); Stacks und Queues und Deques

  Materialien und weitere Lektüre:
  • Folien Kapitel Grundlagen, Seiten 68-80
  • Folien Kapitel Datenstrukturen, Seiten 1-8
  • Skript [DS]: Abschnitte 3.4, 3.5, 4.1 und 4.2
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 4, 10.1 und 10.2
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 2.6, 3.1, 3.4 und 3.6



• Vorlesung 03 -- 19.04.2022:
  Asymptotik (Grenzwerte, Rechenregeln), Laufzeitanalyse rekursiver Programme mit Rekursionsgleichungen, Mastertheorem (Baum der Rekursionsgleichung; Anzahl der Blätter; dominiert über den Overhead t(n) an der Wurzel?)

  Materialien und weitere Lektüre:
  • Folien Kapitel Grundlagen, Seiten 49-68
  • Skript [DS]: Abschnitte 3.2.1, 3.2.2, 3.3 und 3.4
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 4
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 2.6



• Vorlesung 02 -- 14.04.2022:
  Logarithmus (Rechenregeln), Pseudocode, Messung von Laufzeit (Eingabelänge, Worst-Case Laufzeit), Asymptotik (Größenwachstum von Funktionen, Definition O/o/Θ/Ω/ω Notationen, Grenzwerte, Rechenregeln)

  Materialien und weitere Lektüre:
  • Folien Kapitel Grundlagen, Seiten 28-49
  • Skript [DS]: Abschnitte 2.4.4, 3.1 und 3.2
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 3
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 2.1, 2.2 und 2.3



• Vorlesung 01 -- 12.04.2022:
  Organisatorisches, Mathematische Grundlagen (Vollständige Induktion, Beispiele), Binärsuche (Korrektheit und Laufzeit mit vollständiger Induktion), Logarithmus (Definition und Rechenregeln)

  Materialien und weitere Lektüre:
  • Folien Kapitel Grundlagen, Seiten 1-29
  • Skript [DS]: Abschnitte 2.3.4, 2.4.3 und 2.4.4.
  • Für den mathematischen Hintergrund, formale Sprache und Notation, die in der Vorlesung genutzt werden, gibt es eine Einführung in Abschnitten 2.1, 2.2 und 2.3 im Skript [DS].