**Dies ist eine alte Version des Dokuments!**
Kombinatorik
Idee
- Komplexitätsrechnung an einem einfachen Beispiel einführen (z.B. 2x2x2 Rubik)
- Wieviele Kombinationen gibt es?
- Brute-Force-Ansätze
- Wie kann ich alle systematisch durchprobieren?
- Suchbaum
- Tiefensuche (DFS)
- Breitensuche (BFS) (s.a. Graphenalgorithmen)
- Pruning (wenn der Zustand bereits auf anderem Weg erreicht wurde - Speicherbedarf?)
- Wie lange dauert es?
- Grenzen von Brute-Force
- Transfer zu Passwort-Attacke: 8 vs. 12 Zeichen
- 3x3x3-Rubik
- Schach
- Probleme mit unbekanntem Zustand (Markov-Probleme)
hof