Nächste Seite: Inhalt   Inhalt

---

• Inhalt
• Rekurrenzen
  • Euklid (Bestimmung des ggTs)
  • Binäre Suche
  • Mergesort
  • Quicksort
    • Worst-Case
    • Average Case
  
  
• Mastertheorem
  • Übersicht
  • Verständnis des Beweises
  
  
• Ableitung der untersten Schranke von Sortierverfahren
• Weitere Sortierverfahren
  • Countingsort
  • Bucketsort
  • Radixsort
  
  
• Graphen - Tiefensuche/Breitensuche
• Dijkstra-Beweis
• Bäume
  • Definition
  • Höhe und Tiefe
  • Regeln
    • Allgemeine
    • Für Binär-Bäume
  • Erzeugung von Wäldern aus Graphen
  
  
• Ungerichtete Graphen
  • Allgemeine Eigenschaften
  • Äquivalente Aussagen
  
  
• Minimumheap
  • Darstellung durch Arrays
  • Einfügen
  • Löschen
  • Heapsort
    • Algorithmus
    • Laufzeit
  
  
• Union-Find-Wälder
• Kruskal zur Erstellung des MST
  • Abbruchkriterium
  • Laufzeit
  
  
• Speichermöglichkeiten von Datenmengen mit dynamischer Größe
  • Hashing
    • Verschiedene Hashfunktionen
    • Offenes Hashing mit Kollisionslisten
    • Geschlossenes Hashing mit offener Adressierung
    • Dynamisches Hashing
  • Balancierte Bäume
    • Höhe von Bäumen
    • Suchbäume
    • AVL
    • Blatt
    • B-Bäume
  
  
• Greedy
  • Huffman-Codes
  • Graph-Färbe-Problem
  • Rucksackproblem
  
  
• Spielbäume
  • 15er-Puzzle
  • Tic-Tac-Toe
  
  
• Dynamisches Programmieren
  • Floyd
    • Beweis
    • Beispiel
    • Negative Zyklen
    • Konstruktion des Pfades
  • Warshall
  • TSP
    • TSP mit dynamischen Programmieren
    • Kosten TSP mit dynamischen Programmieren
  
  
• Graphen
  • DFS in Digraphen (Baumkante,Vorwärtskante,Rückwärtskante und Seitwärtskante)
  • Topologische Sortierung
  • SCCs - ,,strongly connected component'' - Starke Zusammenhangskomponenten
    • Algorithmus - Aho/Hopcroft/Ullman
    • Beweis des SCC-Algorithmusses
  
  
• Netzwerkflußproblem
  • Ford&Fulkerson-Algorithmus
    • Algorithmus
    • Worst Case
    • Optimierung
  • Bipartites Matching
  
  
• Mustererkennung
  • Naives Verfahren
  • KMP - Knuth, Morris und Pratt
  • Boyer-Moore
  
  
• Scanlines
  • Sichtbarkeitsproblem für horizontale Objekte
  • Schnittproblem für horizontale und vertikale Objekte
  • Geometrisches Divide&Conquer für horizontal und vertikal liegende Objekte
  • Schnittproblem für (fast) beliebig liegende Objekte
  • Voronoidiagramme (nur eine kurze Vorstellung)
  
  
• Randomisierte Algorithmen
  • Las Vegas & Monte Carlo
  • Randomisiertes Quicksort
  • Mustererkennung - Karp&Rabin
  • Universelles Hashing
  • Skip-Listen

---