Logbuch Datenstrukturen - Sommer 2017
18.07.2017:
Materialien und weitere Lektüre:
Besprechung von Übungsblatt 7 und von (Teilen) der Erstklausur von 2006- Folien Was ist wichtig?
- Skript: Abschnitt 6 (Seiten 176 und 177)
11.07.2017:
Materialien und weitere Lektüre:
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ücher04.07.2017:
Materialien und weitere Lektüre:
(a,b)-Bäume ((a,b)-Eigenschaft, Tiefe, Suchstruktur, insert (Zellteilung), remove (Schlüsselklau, Fusion))27.06.2017:
Materialien und weitere Lektüre:
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); (a,b)-Bäume (Definition, Beispiel)- Folien Kapitel 3, Seiten 19-34
- Skript: Abschnitt 5.2 und 5.4 (bis Seite 162)
- 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) und Kapitel 18
- Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 7.1 und 7.2
20.06.2017:
Materialien und weitere Lektüre:
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; AVL-Bäume (Definition, Tiefe eines AVL-Baums mit n Schlüsseln ist höchstens 2 log(n))- Folien Kapitel 2, Seiten 111-113
- Folien Kapitel 3, Seiten 1-19
- Skript: Abschnitt 4.6, 5.1 und 5.2 (bis Seite 149)
- Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 23.2 und 12 (in Kapitel 13 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 11.3, 11.4 (ohne Pfadkompression) und 7.1
13.06.2017:
Materialien und weitere Lektüre:
Priority-Queues und Heaps (Wiederholung, Tiefe eines Heaps, BuildHeap in Linearzeit, Heapsort); Killerapplikationen für Heaps (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- Folien Kapitel 2, Seiten 94-113
- Skript: Abschnitt 4.5 und 4.6
- Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 6, 21.3, 23.2 und 24.3.
- Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 6, 10.3, 11.2, 11.3 und 11.4
(in der Vorlesung ohne Pfadkompression)
06.06.2017:
Materialien und weitere Lektüre:
Anwendungen der Tiefensuche für gerichtete Graphen (Ist ein Graph azyklisch? Ist ein Graph stark zusammenhängend? Berechne eine topologische Sortierung!); Breitensuche (Laufzeit, Baum kürzester Wege); 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.30.05.2017:
Materialien und weitere Lektüre:
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, Bestimmung der Kantentypen mit Anfang- und Ende-Nummerierung); Anwendungen für gerichtete Graphen (Ist ein Graph azyklisch? Berechne eine topologische Sortierung!)23.05.2017:
Materialien und weitere Lektüre:
Besuchsreihenfolge für Postorder und Präorder; Graphen (gerichtet, ungerichtet, Wege und Kreise); topologische Sortierung (Adjazenzlistendarstellung); Implementierung von Graphen (Adjazenzlisten und Adjazenzmatrix); Einführung Tiefensuche (Ariadne-Faden)16.05.2017:
Materialien und weitere Lektüre:
Implementierung von Deques und Listen (zirkuläre Arrays für Deques; 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 und nicht-rekursive Implementierung)09.05.2017:
Materialien und weitere Lektüre:
Mastertheorem (Baum der Rekursionsgleichung; Anzahl der Blätter; dominiert über den Overhead t(n) an der Wurzel?); Listen (einfache Verkettung; schnelle Implementierung aller Operationen bis auf Suche); Stacks und Queues und Deques, Implementierung von Deques mit zirkulären Arrays- Folien Kapitel 1, Seiten 66-73
- Folien Kapitel 2, Seiten 1-10
- Skript: Abschnitte 3.4, 4.1 und 4.2 (siehe auch Abschnitt 3.9 für einen Beweis des Mastertheorems)
- Cormen, Leiserson, Rivest, Stein. Algorithmen - Eine Einführung. Kapitel 4, 10.2
- Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen. Kapitel 2.6, 3.1
02.05.2017:
Materialien und weitere Lektüre:
Asymptotik (Grenzwerte, Rechenregeln, eine Wachstumshierarchie), Laufzeitanalyse für C++-Programme und Pseudocode (dominierende Anweisungen, Matrizenmultiplikation, While-Schleifen), Laufzeitanalyse rekursiver Programme mit Rekursionsgleichungen25.04.2017:
Materialien und weitere Lektüre:
Binärsuche (Korrektheit und Laufzeit), Logarithmus (Definition und Rechenregeln), Pseudocode, Messung von Laufzeit (Eingabelänge, Worst-Case Laufzeit), Asymptotik (Größenwachstum von Funktionen, Definition O/o/Θ/Ω/ω Notationen, Grenzwerte, Rechenregeln)18.04.2017:
Materialien:
Organisatorisches, Mathematische Grundlagen (Vollständige Induktion, Fibonacci-Zahlen, Rekursionsbäume), Binärsuche (Korrektheit und Laufzeit mit vollständiger Induktion)