Menü

Informatik » Bachelor » Algorithmen der Informatik

Bachelor Rekurrenzen

Algorithmen

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 $n\log(n)$
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
- Balancierte Bäume
Greedy
- Huffman-Codes
- Graph-Färbe-Problem
- Rucksackproblem
Spielbäume
- 15er-Puzzle
- Tic-Tac-Toe
Dynamisches Programmieren
- Floyd
- 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
- 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
Randomisierte Algorithmen
- Las Vegas & Monte Carlo
- Randomisiertes Quicksort
- Mustererkennung - Karp&Rabin
- Universelles Hashing
- Skip-Listen

Bachelor Rekurrenzen