Algorithmen & Komplexität

Arbeitsgruppe

Forschung

Lehre

Abschlussarbeiten

zurück zur Übersicht

Logbuch Datenstrukturen - Sommer 2019

• 16.07.2019:
  Besprechung von Übungsblatt 7 und von (Teilen) der Nachklausur von 2017

  Materialien und weitere Lektüre:
  • Nachklausur SoSe 2017



• 09.07.2019:
  Hashing mit Verkettung (Hashfunktionen), Hashing mit offener Adressierung (lineares Austesten, doppeltes Hashing), Analyse erwartete Laufzeit für Hashing mit Verkettung O(1+λ), erwartete Laufzeit doppeltes Hashing 1/(1-λ); Zusammenfassung Wörterbücher

  Materialien und weitere Lektüre:
  • Folien Kapitel 3, Seiten 50-76
  • Skript: 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



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

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



• 25.06.2019:
  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 3, Seiten 16-34
  • Skript: 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



• 18.06.2019:
  Wiederholung Algorithmus von Dijkstra für kürzeste Wege, Algorithmus von Jarnik-Prim für minimale Spannbäume; Algorithmus von Kruskal für minimale Spannbäume und Union-Find Datenstruktur; Binäre Suchbäume (lookup, insert, remove, sortieren); im Worst-Case zu große Tiefe

  Materialien und weitere Lektüre:
  • Folien Kapitel 2, Seiten 116-129
  • Folien Kapitel 3, Seiten 1-15
  • Skript: Abschnitt 4.6 und 5.1
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 21.3, 23.2 und 12
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 10.3, 11.2, 11.3, 11.4 (ohne Pfadkompression) und 7.1



• 11.06.2019:
  Priority-Queues und Heaps, Umsetzung von insert (repair_up), delete_max (repair_down), change_priority und remove; Tiefe eines Heaps, BuildHeap in Linearzeit, Heapsort; Anwendung im Algorithmus von Dijkstra für kürzeste Wege

  Materialien und weitere Lektüre:
  • Folien Kapitel 2, Seiten 97-117
  • Skript: Abschnitt 4.5, 4.6 und 4.6.1.
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 6 und 24.3.
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 6 und 10.3



• 04.06.2019:
  Tiefensuche für gerichtete Graphen (Bestimmung der Kantentypen mit Anfang- und Ende-Nummerierung); Anwendungen für gerichtete Graphen (Ist ein Graph azyklisch? Berechne eine topologische Sortierung!); Breitensuche (Laufzeit, Baum kürzester Wege); Priority-Queues (insert, delete_max, change_priority, remove); Heaps (Heap-Struktur, Heap-Ordnung)

  Materialien und weitere Lektüre:
  • Folien Kapitel 2, Seiten 76-96
  • Skript: Abschnitt 4.4.3, 4.4.4, und 4.5
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 22.2 und 6.5
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 9.1 und 6



• 28.05.2019:
  Tiefensuche für ungerichtete Graphen (Baumkanten und Rückwärtskanten, Wald der Tiefensuche, Bäume des Walds entsprechen den Zusammenhangskomponenten); Tiefensuche für gerichtete Graphen (Baumkanten, Vorwärtskanten, Rückwärtskanten, Querkanten)

  Materialien und weitere Lektüre:
  • Folien Kapitel 2, Seiten 59-75
  • Skript: Abschnitt 4.4.3
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 22.3 und 22.4
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 9.1 und 9.2.1



• 21.05.2019:
  Topologische Sortierung (Adjazenzlistendarstellung); Implementierung von Graphen (Adjazenzlisten und Adjazenzmatrix); Tiefensuche (Ariadne-Faden, Farbeimer, rekursive Implementierung)

  Materialien und weitere Lektüre:
  • Folien Kapitel 2, Seiten 38-61
  • Skript: Abschnitt 4.4, 4.4.1, 4.4.2 und 4.4.3 (Seiten 98-104)
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 22.3 und 22.4
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 9.1 und 9.2.1



• 14.05.2019:
  Bäume (Operationen), Implementierungen von Bäumen (Elternarray, Binärbaum-Darstellung, Kind-Geschwister-Darstellung), Suche (Präorder, Postoder, Inorder, rekursive und nicht-rekursive Implementierung), Besuchsreihenfolge für Postorder und Präorder; Graphen (gerichtet, ungerichtet, Wege und Kreise)

  Materialien und weitere Lektüre:
  • Folien Kapitel 2, Seiten 17-37
  • Skript: Abschnitte 4.3, 4.3.1, 4.3.2 und 4.4
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 10.4 und 22.1.
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 2.9



• 07.05.2019:
  Listen (einfache Verkettung; schnelle Implementierung aller Operationen bis auf Suche); Stacks und Queues und Deques, 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)

  Aufgrund von Verspätung des Aufnahmepersonals fand leider keine Videoaufzeichnung statt.

  Materialien und weitere Lektüre:
  • Folien Kapitel 2, Seiten 1-16
  • Skript: Abschnitte 4.1, 4.2 und 4.3
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 10.1, 10.2 und 10.3
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 3.1, 3.4 und 3.6



• 30.04.2019:
  Laufzeitanalyse rekursiver Programme mit Rekursionsgleichungen, Mastertheorem (Baum der Rekursionsgleichung; Anzahl der Blätter; dominiert über den Overhead t(n) an der Wurzel?); Laufzeitanalyse für C++-Programme (dominierende Anweisungen, Matrizenmultiplikation, While-Schleifen)

  Materialien und weitere Lektüre:
  • Folien Kapitel 1, Seiten 52-77
  • Skript: Abschnitte 3.3, 3.4 und 3.5
  • Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 4
  • Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 2.6



• 23.04.2019:
  Binomialkoeffizienten, 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 1, Seiten 27-51
  • Skript: Abschnitte 2.4.3, 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



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

  Materialien:
  • Folien Kapitel 1, Seiten 1-33
  • Skript: 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.