Nächste Seite: Rekurrenzen Aufwärts: Hauptseite Algorithmen Vorherige Seite: Hauptseite Algorithmen

Inhalt

• Rekurrenzen
  • Euklid (Bestimmung des ggTs)
  • Binäre Suche
  • Mergesort
  • Quicksort
  
  
• 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
  • Erzeugung von Wäldern aus Graphen
  
  
• Ungerichtete Graphen
  • Allgemeine Eigenschaften
  • Äquivalente Aussagen
  
  
• Minimumheap
  • Darstellung durch Arrays
  • Einfügen
  • Löschen
  • Heapsort
  
  
• Union-Find-Wälder
• Kruskal zur Erstellung des MST
  • Abbruchkriterium
  • Laufzeit
  
  
• Speichermöglichkeiten von Datenmengen mit dynamischer Größe
  • Hashing
  • Balancierte Bäume
  
  
• Greedy
  • Huffman-Codes
  • Graph-Färbe-Problem
  • Rucksackproblem
  
  
• Spielbäume
  • 15er-Puzzle
  • Tic-Tac-Toe
  
  
• Dynamisches Programmieren
  • Floyd
  • Warshall
  • TSP
  
  
• Graphen
  • DFS in Digraphen (Baumkante,Vorwärtskante,Rückwärtskante und Seitwärtskante)
  • Topologische Sortierung
  • SCCs - ,,strongly connected component'' - Starke Zusammenhangskomponenten
  
  
• Netzwerkflußproblem
  • Ford&Fulkerson-Algorithmus
  • 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

---