1. 1 Knoten und 2 binären Suchbäumen (linker u. rechter Teilbaum
2. Hinweise
2.1. Formeln
3. 01: Grundlagen
3.1. Algorithmusbegriff
3.1.1. Definition
3.1.2. Eigenschaften
3.2. Analyse
3.2.1. Datenstrukturen
3.2.2. Darstellung von Algorithmen
3.2.3. Abstraktionsebenen
3.3. Korrektheit
3.3.1. Bedingungen
3.3.2. Beweise
3.4. Laufzeit
3.4.1. Abstraktionsschritte
3.4.2. O-Notation
3.4.2.1. Dominierung
3.4.3. Analyse von Schleifen
4. 02: Rekursion
4.1. Prinzip
4.1.1. Abbruchkriterium
4.1.2. divide and conquer
4.2. lineare Rekursion
4.3. Rekurrente Relationen
4.3.1. Berechnung
4.3.1.1. Relation 1
4.3.1.1.1. Gleichung
4.3.1.1.2. Exakte Laufzeit
4.3.1.2. Relation 2
4.3.1.2.1. Gleichung
4.3.1.2.2. Exakte Laufzeit
4.3.1.3. Relation 3
4.3.1.3.1. Gleichung
4.3.1.3.2. Exakte Laufzeit
4.3.1.4. Relation 4
4.3.1.4.1. Gleichung
4.3.1.4.2. Exakte Laufzeit
4.3.1.5. Relation 5
4.3.1.5.1. Gleichung
4.3.1.5.2. Exakte Laufzeit
4.4. Iteration
5. 03: Elementare Sortierverfahren
5.1. Klassifikation
5.1.1. Effizienz
5.1.1.1. Primitive Sortierverfahren
5.1.1.2. Elementare Sortierverfahren
5.1.1.3. Höhere Sortierverfahren
5.1.1.4. Spezialisierte Verfahren
5.1.1.5. Spezialfälle
5.1.2. Stabilität
5.1.2.1. Stabil
5.1.2.2. Instabil
5.1.3. Intern/Extern
5.1.3.1. Intern
5.1.3.2. Extern
5.1.4. Allgemein/Spezialisiert
5.1.4.1. Allgemein
5.1.4.2. Spezialisiert
5.1.5. Speicherverbrauch
5.2. Voraussetzungen
5.2.1. Lineare Suche
5.2.2. Binäre Suche
5.3. Sortierverfahren (Beispiele)
5.3.1. BogoSort
5.3.1.1. Algorithmus
5.3.1.2. Effizienz
5.3.2. BubbleSort
5.3.2.1. Algorithmus
5.3.2.2. Effizienz
5.3.3. SelectionSort
5.3.3.1. Algorithmus
5.3.3.2. Effizienz
5.3.4. InsertionSort
5.3.4.1. Algorithmus
5.3.4.2. Effizienz
5.3.5. MergeSort
5.3.5.1. Algorithmus
5.3.5.2. Effizienz
5.3.6. ShellSort
5.3.6.1. Algorithmus
5.3.6.2. Effizienz
6. 04: Rekursive Sortierverfahren
6.1. allgemeine Vorgehensweise
6.2. Quick-Sort
6.2.1. Idee
6.2.1.1. Devide&Conquer
6.2.2. Pivot-Element
6.2.2.1. Kleinstes
6.2.2.2. Größtes
6.2.2.3. Zufällig
6.2.2.4. Median of Three
6.2.3. Effizienz
6.2.3.1. Best Case
6.2.3.2. Average Case
6.2.3.3. Worst Case
6.2.4. Verbesserungsmöglichkeit
6.2.5. Instabil
6.2.6. Vor-/Nachteile
6.2.7. Implementierung(Java)
6.3. Merge-Sort
6.3.1. Idee
6.3.2. Effizienz
6.3.3. Stabil
6.3.4. Vor-/Nachteile
6.3.5. Algorithmus
6.3.6. Implementierung(Java)
6.4. Optimalitätssatz
6.4.1. Satz
6.4.2. Ausnahmen
7. 05: Elementare Datenstrukturen
7.1. Abstrakter Datentyp
7.1.1. Signatur
7.1.2. Algebra
7.1.2.1. Modelle
7.2. Mathematik
7.2.1. Datentyp (Algebra)
7.2.1.1. Signatur
7.2.1.1.1. Sorten
7.2.1.1.2. Operationen
7.2.1.2. Algebra
7.2.1.2.1. Trägermenge
7.2.1.2.2. Funktionen
7.3. Algorithmik
7.3.1. Datenstruktur
7.3.1.1. Objekte der Trägermengen
7.3.1.2. Operationen
7.4. Programmierung
7.4.1. Typ, Modul, Klasse, ...
7.4.1.1. Beispiel: Modula-2
7.4.1.2. Beispiel: C++
7.4.1.3. Beispiel: Java
7.4.1.4. Konkrete Datentypen
7.4.1.5. Abstrakte Datentypen
7.5. Behälter
7.5.1. Stack
7.5.2. Queue
7.5.3. Verkettete Listen
7.5.3.1. Einfach verkettete Liste
7.5.3.2. Doppelt verkettete Liste
7.5.3.3. Adaptive Listen
7.5.3.4. Geordnete Listen mit Skip Listen
8. 06:Bäume
8.1. Behälter und ihre Merkmale
8.1.1. Array
8.1.2. Menge
8.1.3. Stack
8.1.4. Queue
8.1.5. Baum
8.1.6. Liste
8.2. Hierarchien
8.2.1. Wurzel
8.2.2. Knoten
8.2.3. Kanten
8.2.4. Blatt
8.2.5. (innerer Knoten)
8.3. Begrifflichkeiten
8.3.1. Pfad
8.3.2. Tiefe
8.3.3. Grad
8.4. Binärbäume
8.4.1. Definition
8.4.2. Tiefe
8.4.3. Knoten
8.4.4. Kanten
8.4.5. Implementierung
8.4.5.1. Knotenanzahl(Java)
8.4.6. Operationen
8.4.6.1. isEmpty(B)
8.4.6.2. height(B)
8.4.6.3. contains(B,E)
8.4.7. Vollständiger Baum
8.4.8. (Max)Heap
8.4.8.1. insertHeap(Char c)
8.4.8.2. upHead(Char c)
8.4.8.3. getNext()
8.4.8.4. Aufwand
8.4.8.4.1. insert
8.4.8.4.2. getNext
8.5. Traversierungen
8.5.1. Preorder
8.5.1.1. Implementierung(C)
8.5.2. Inorder
8.5.2.1. Implementierung(C)
8.5.3. Postorder
8.5.3.1. Implementierung(C)
8.5.4. Levelorder (etagenweise)
8.5.4.1. Implementierung(C)
8.6. Suchbäume
8.6.1. Binär
8.6.1.1. Aufbau entweder
8.6.1.1.1. leer
8.6.1.2. Ordnungsrelation über Knoten (Schlüssel)
8.6.1.3. linkter Teilbaum ≤ Wurzel rechter Teilbaum > Wurzel
8.6.1.4. Vergleich von Knoten
8.6.1.4.1. V1: expliziter Schlüssel (keine Duplikate)
8.6.1.4.2. V2: Ordnungsrelation für Datentyp
8.6.1.5. Datenstruktur
8.6.1.5.1. Knoten { int wert; Knoten links; Knoten rechts; }
8.6.1.6. Suche
8.6.1.7. Einfügen
8.6.1.7.1. Step 1: Position im Baum ermitteln
8.6.1.7.2. Step 2: Neuen Knoten anlegen
8.6.1.7.3. Step 3: Neuen Knoten in gefundene Position aus Step 1 einhängen
8.6.1.8. Löschen
8.6.1.8.1. Step 1: Element im Baum suchen
8.6.1.8.2. Step 2: Element löschen
8.6.1.9. Balance
8.6.1.9.1. Balance abhängig von Reinfolge der eingefügten Elemente (worst case sieht Baum aus wie eine Liste)
8.6.1.9.2. Löschen ändert ebenfalls die Form des Baums
8.6.2. Balanciert
8.6.2.1. Binärbaum hat
8.6.2.1.1. max 2^(k-1)-1 Knoten der Tiefe < k
8.6.2.1.2. max 2^k-1 Knoten der Tiefe ≤ k
8.6.2.1.3. d.h. max 2^k-1 Knoten
8.6.2.2. Ein Baum ist balanciert falls alle Schichten bis auf die unterste voll besetzt sind
8.6.2.3. Suche in O(log(N)) da gilt: #Vergleiche ≤ Tiefe des Baumes
8.6.2.4. Problem
8.6.2.4.1. Einfügen und Löschen zerstören Balance
8.6.2.4.2. Ausgleich von Balance aufwendig
8.6.2.5. Lösung
8.6.2.5.1. Schwäche Balance ab
8.6.2.5.2. ggf. Reorganisierung nach Einfügen/Löschen
8.6.2.5.3. Beispiele: AVL- und Rot-Schwarz-Bäume
8.6.3. AVL
8.6.3.1. Adelson-Velski und Landis (1962)
8.6.3.2. Tiefe des linken und rechten Teilbaums unterscheiden sich um max. 1
8.6.3.3. Balance-Zahl b(k) = Tiefe(links(k)) - Tiefe(rechts(k))
8.6.3.4. ∀ Knoten: b(k) ∈ {-1, 0, 1}
8.6.3.5. Zerstörung durch
8.6.3.5.1. Löschen
8.6.3.5.2. Einfügen
8.6.3.6. Wiederherstellung durch Rotation
8.6.3.6.1. Lokale Reorganisation
8.6.3.6.2. Enthält Suchbaum-Ordnung
8.6.3.6.3. Wiederherstellung durch einfache oder doppelte Rotation
8.6.3.7. Analyse
8.6.3.7.1. Satz: Ein AVL-Baum mit N Knoten hat die maximale Tiefe log2N
8.6.3.7.2. Suchen, Einfügen und Löschen in O()
8.6.3.7.3. n(t) = Mindest-Knotenanzahl bei Tiefe t
8.6.3.8. Zusammenfassung
8.6.3.8.1. i.A. besser balanciert als binäre Suchbäume => schnellere Suche
8.6.3.8.2. lokale Reorganisation notwendig
8.6.4. 2-3-4
8.6.4.1. Im gegensatz zu Binärbäumen lassen sich 3-, 4, ..., n-Knoten definieren
8.6.4.1.1. 3-Knoten enthalten zwei Schlüssel und drei Verweise
8.6.4.1.2. 4-Knoten enthalten drei Schlüssel und vier Verweise
8.6.4.1.3. n-Knoten enthalten (n-1) Schlüssel und n Verweise
8.6.5. Rot-Schwarz
8.6.5.1. Motivation
8.6.5.1.1. Verwaltung mehrerer Schlüssel pro Knoten ist aufwendig
8.6.5.1.2. RBT: 2-3-4-Baum als Binärbaum
8.6.5.1.3. Nutzung vorhandener Methoden
8.6.5.1.4. Alternative zu AVL-Bäumen
8.6.5.2. Prinzip
8.6.5.2.1. Knoten haben zusätzliches Feld color (red/black)
8.6.5.3. Regeln
8.6.5.3.1. Jeder Knoten ist entweder rot oder schwarz
8.6.5.3.2. Jeder Blattknoten (Null-Knoten) ist per Definition schwarz
8.6.5.3.3. Die Kinder jedes roten Knotens sind schwarz
8.6.5.3.4. Für jeden Knoten k gilt jeder Pfad von k zu einem Blatt enthält die gleiche Anzahl schwarzer Knoten (vgl. "Schwarzhöhe")
8.6.5.3.5. Die Schwarzhöhe bh(t) eines RBT t ist die Schwarzhöhe seiner Wurzel
8.6.5.4. Zusammenfassung
8.6.5.4.1. Alle Operationen logarithmisch in der Höhe des RBT
8.6.5.4.2. Laufzeitverhalten ähnlich zu AVL-Bäumen
8.6.5.4.3. Implementierung: "R. Sedgewick: Algorithmen"
9. 08: Hashing
9.1. Hash-Funktionen
9.1.1. Auftretende Anomalien
9.1.1.1. Kollisionen
9.1.1.2. Leerstellen
9.1.2. Anforderungen
9.1.3. Typische Hash-Funktionen
9.1.3.1. String
9.1.3.2. Integer
9.1.3.3. Float
9.2. Hashing mit Verkettung
9.2.1. Aufwand
9.3. Hashing mit offener Adressierung
9.3.1. Speichern
9.3.2. Sondierungsfolgen
9.3.3. Löschen
9.3.4. Wahrscheinlichkeit von Kollisionen
9.3.5. Aufwand
9.4. Dynamische Hash-Verfahren
9.4.1. Globale Reorganisation
9.4.2. Dynamisches Hashing
10. 09: Graphen
10.1. Arten
10.1.1. zyklisch
10.1.2. (un)gerichtet
10.1.2.1. Zusammenhang
10.1.2.2. Baum
10.1.2.2.1. Aufspannender Baum
10.1.3. bewertet
10.1.3.1. Wege
10.1.4. Teilgraphen
10.2. Algorithmen
10.2.1. Warshall
10.2.2. Floyd
10.2.3. Dijkstra
10.2.4. Prim
10.2.5. Kruskal
10.2.6. Suchalgorithmen
10.2.6.1. Breitensuche
10.2.6.2. Tiefensuche
10.3. Anwendung
10.3.1. Soziale Netzwerke
10.3.2. Rechnernetze
10.3.3. Routenplanung
10.4. Implementierungsarten
10.4.1. Adjazenzmatrix
10.4.2. Adjazenzlisten-Array
10.4.3. Liste von Listen
10.5. Pfade
11. 10: Kompression
11.1. Lauflängenkodierung
11.1.1. Redundanzen auflösen
11.1.1.1. Schlecht für Text
11.1.1.2. Gut für Binärdaten
11.2. Textkompression
11.2.1. ASCII & Unicode
11.2.2. Morsealphabet
11.2.3. Präfixcodes
11.2.3.1. Huffman Codes
11.2.3.1.1. Algorithmus
11.2.3.1.2. Platzeinsparung
11.2.3.1.3. fester Huffman-Code
11.2.3.1.4. individueller Huffman-Code
11.2.3.1.5. dynamic Huffman-Code
11.3. Kompressionsrate
11.3.1. Kompressionsrate
11.3.2. Platzeinsparung
11.4. Weitere Verfahren
11.4.1. LZW Algorithmus
11.4.2. PKArc/ PKUnArc
11.4.3. WinZip/PKZip...
12. 11: Textsuche
12.1. Zeichenketten
12.1.1. Problemstellung
12.2. Naiver Algorithmus
12.2.1. Pseudocode
12.2.2. Komplexitätbetrachtung
12.2.2.1. best case
12.2.2.2. avg case
12.2.2.3. worst case
12.3. Knuth-Morris-Pratt Algorithmus
12.3.1. Pseudocode
12.3.2. Aufbau des NextArrays
12.3.3. Komplexitätsbetrachtung
12.3.3.1. initNextArray
12.3.3.2. suche
12.4. Boyer-Moore-Sunday Algorithmus
12.4.1. Pseudocode
12.4.2. Aufbau des lastArrays
12.4.3. Komplexitätsbetrachtung
12.4.3.1. best case
12.4.3.2. avg case
12.4.3.3. worst case
12.5. Rabin-Karp Algorithmus
12.5.1. HashBerechnung
12.5.2. Komplexitätsbetrachtung
12.5.2.1. avg case
12.5.2.2. worst case