Current entry

Logfile: Datenstrukturen

Lecture  in Summer 2012

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden sowie gelegentlich ergänzende Bemerkungen.


  1. Di, 10.04.2012
  2. Eröffnungsveranstaltung. Einführung in abstrakte Datentypen und Datenstrukturen, Ziele der Vorlesung. Organisatorisches. Kapitel 1 Mathematische Grundlagen: kleiner Gauß, geometrische Summe, Rechnen mit Logarithmen, Binomialkoeffizienten. Beginn mit Kapitel 2 Laufzeitmessung: Abschätzung der Laufzeit unabhängig von tatsächlicher Hard- und Software.
    Material:
    Skript, Seiten 3-13
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    Übungsaufgaben:
    Ein Blatt mit Präsenzaufgaben (deren Lösung in der ersten Übungsstunde besprochen wird) wurde ausgeteilt.
    Übungsblatt 1 wurde ausgeteilt.
  3. Di, 17.04.2012
  4. Weiter mit Kapitel 2 Laufzeitmessung: Ziel: verlässliche Vorhersage von Wachstumsverhalten unabhängig von Rechnerumgebung, das Teilfolgenproblem, Algorithmus A1 für Teilfolgenproblem, Laufzeitbestimmung von A1, asymptotische Notation für Vergleich von Laufzeiten, asymptotische Laufzeitbestimmung von A1, Grenzwerte von Laufzeitquotienten, Rechnen mit Grenzwerten
    Material:
    Skript, Seiten 13-18
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
  5. Di, 24.04.2012
  6. Weiter mit Kapitel 2 Laufzeitmessung: Regel von de l' Hospital zur Bestimmung des Grenzwertes von Laufzeit-Quotienten, Integralkriterium, Wachstumshierarchie von typischen Laufzeitfunktionen, Algorithmus A2 zur Lösung des Teilfolgenproblems, asymptotische Analyse der Laufzeit von A2, rekursiver Algorithmus A3 mit Divide&Conquer-Ansatz, Aufstellen der Rekursionsgleichung für Laufzeit von A3, Lösen der Rekursionsgleichung
    Material:
    Skript, Seiten 18-26
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    Übungsaufgaben:
    Übungsblatt 2 wurde ausgeteilt.
  7. Do, 26.04.2012
  8. Einzelveranstaltung zum Thema: Beweisprinzip der vollständigen Induktion.
    Material:
    Ein Großteil der besprochenen Themen findet sich im Skript von Prof. Schweikardt zur Vorlesung "Diskrete Modellierung" in Kapitel 2.5.5.
    Vortragsfolien
    Die Veranstaltung wurde nicht auf Video aufgezeichnet. Allerdings finden Sie eine ähnliche Präsentation des Themas in der Videoaufzeichnung der Vorlesung "Diskrete Modellierung" von Prof. Schweikardt in den Minuten 6 bis 66 an dieser Stelle: [Flash | QuickTime | Mobile | MP3]
  9. Di, 08.05.2012
  10. Weiter mit Kapitel 2 Laufzeitmessung: Wiederholung von Algorithmus A3 und seiner Laufzeitbestimmung, Mastertheorem zur Lösung von Rekursionsgleichungen, Grenzen des Mastertheorems: Türme von Hanoi, Algorithmus A4 für das Teilfolgenproblem, Laufzeitbestimmung von A4, Analyse der Laufzeit von C++ Programmfragmenten, Analyse von For-Schleifen, Analyse von While-Schleifen mithilfe des Mastertheorems, While-Schleife mit unbekannter Laufzeit: Collatz-Vermutung
    Material:
    Skript, Seiten 23-34
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
  11. Di, 15.05.2012
  12. Beginn mit Kapitel 3 Elementare Datenstrukturen: einfach verkettete Liste, Eigenschaften, Darstellung einer Matrix durch verkettete Liste, Addition dünn besetzter Matrizen mithilfe verketteter Listen, Deques, Stacks und Queues, Implementierung eines Deque, Implementierung von einfach verketteten Listen durch Arrays, Bäume und deren zentrale Begriffe
    Material:
    Skript, Seiten 43-51
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    Übungsaufgaben:
    Übungsblatt 3 wurde ausgeteilt.
  13. Di, 22.05.2012
  14. Weiter mit Kapitel 3 Elementare Datenstrukturen: Operationen auf Bäumen als Datenstrukturen, Repräsentation als Vater-Array, Darstellung als Adjazenzliste, Binärbaum-Implementierung, Kind-Geschwister-Implementierung, Durchsuchen von Bäumen: Postorder, Preorder sowie Inorder, nicht-rekursive Preorder-Implementierung, ungerichtete und gerichtete Graphen, Königsberger Brückenproblem, Euler-Kreis, wichtige Begriffe, Topologisches Sortieren, Algorithmen, Laufzeitanalyse
    Material:
    Skript, Seiten 51-63
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    • Implementierung von Bäumen, Postorder, Preorder, Inorder, Graphen, topologische Sortierung [Flash | QuickTime | Mobile | MP3]
  15. Di, 29.05.2012
  16. Weiter mit Kapitel 3 Elementare Datenstrukturen: Implementierung von Graphen: Adjazenzmatrix und Adjazenzliste, Vorteile und Nachteile, Suche in Graphen: Tiefensuche, die globale Tiefensuche-Struktur, die rekursive Funktion tsuche(), Tiefensuche in ungerichteten Graphen: Wald der Tiefensuche, Baumkanten und Rückwärtskanten, Charakterisierung der Zusammenhangskomponenten, Laufzeit, Anwendungen der Tiefensuche: Test auf Zusammenhang und Test auf Wald, Tiefensuche in gerichteten Graphen: Wald der Tiefensuche, Baumkanten, Rückwärtskanten, Vorwärtskanten und Querkanten
    Material:
    Skript, Seiten 65-74
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    • Adjazenzmatrix- und liste, Tiefensuche in ungerichteten und gerichteten Graphen [Flash | QuickTime | Mobile | MP3]
    Übungsaufgaben:
    Übungsblatt 4 wurde ausgeteilt.
  17. Di, 05.06.2012
  18. Weiter mit Kapitel 3 Elementare Datenstrukturen: Eigenschaften der Tiefensuche auf gerichteten Graphen, automatische Erkennung der Kantentypen, Anwendungen der Tiefensuche auf gerichteten Graphen: Test auf Kreisfreiheit, topologische Sortierung sowie Test auf starken Zusammenhang, Breitensuche, Eigenschaften, Laufzeit, Breitensuchebaum als Baum kürzester Wege, Prioritätswarteschlangen, Heap, Heap-Struktur, Heap-Ordnung, Funktion insert, Funktion repair_up
    Material:
    Skript, Seiten 75-84
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
  19. Di, 12.06.2012
  20. Weiter mit Kapitel 3 Elementare Datenstrukturen: Datenstruktur Heap: Methoden delete_max, repair_down, change_priority und remove, Tiefe eines Heaps und damit Laufzeitbestimmung der Methoden, Heapsort, beschleunigtes Laden der Elemente in Heap, single source shortest path problem, Dijkstras Algorithmus, Datenstrukturen dafür, Suchen eines minimalen Spannbaumes, Algorithmus von Prim, Datenstrukturen dafür
    Material:
    Skript, Seiten 85-92
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    Übungsaufgaben:
    Übungsblatt 5 wurde ausgeteilt.
  21. Di, 19.06.2012
  22. Abschluss von Kapitel 3 Elementare Datenstrukturen: Algorithmus von Kruskal zur Bestimmung eines minimalen Spannbaumes, Union-Find Datenstruktur; Beginn mit Kapitel 4: Das Wörterbuch, abstrakter Datentyp Wörterbuch, Motivation, Datenstruktur für dynamische Wörterbücher: Binärer Suchbaum, Struktur eines Knotens, Klasse bsbaum, Operationen lookup, insert und remove
    Material:
    Skript, Seiten 93-101
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
  23. Di, 26.06.2012
  24. Weiter mit Kapitel 4 Das Wörterbuch: binäre Suchbäume, maximale Tiefe eines binären Suchbaumes, erwartete Tiefe vs. maximale Tiefe, AVL-Bäume, Tiefe eines AVL-Baums, lazy remove Operation, Links-/Rechtsrotation, insert Operation, Zick-Zick-Fall, hier besonders: Tiefe(A)=d-2, Zack-Zack-Fall
    Material:
    Skript, Seiten 101-107
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
    Übungsaufgaben:
    Übungsblatt 6 wurde ausgeteilt. Achtung: Rückgabe bis Donnerstag, 5. Juli, 12:00 Uhr, bei Aufgabe 3 (a) ist f(x) als Hashfunktion zu benutzen.
  25. Di, 03.07.2012
  26. Abschluss von Kapitel 4 Das Wörterbuch: AVL-Bäume, Zick-Zack- und Zack-Zick-Fall, Doppelrotation, Hashing: Anwendungen, Idee, Hashing mit Verkettung, Wahl der Hashfunktion, Laufzeit der Operationen, Hashing mit offener Adressierung, Schwierigkeiten mit remove-Operation, Methode des linearen Austestens, Methode des doppelten Hashings
    Material:
    Skript, Seiten 107-109, 121-126
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen
  27. Di, 10.07.2012
  28. Abschlussveranstaltung, Wiederholung von Vorlesungsteilen, Hinweise zur Klausur, Zusammenhang von Pseudocode und C++-Code
    Material:
    Vortragsfolien
    Videoaufzeichnung der Vorlesung: Die E-Lectures zu den Themen