Kombinatorik

Komplexitätsrechnung an einem einfachen Beispiel einführen (z.B. 2x2x2 Rubik)
- Wieviele Kombinationen gibt es?
  - Upper Bound: $7!\cdot8^3 = 2580480$ Kombinationen
    1. 8 Steine ohne Zurücklegen, also $(8-1)!$ Kombinationen
    2. jeder Stein kann in 3 verschiedenen Lagen sein, also $8^3$ Möglichkeiten für jede Kombination
  - Aber nicht alle Kombinationen sind möglich, und andere sind äquivalent unter einer Farb-Permutation.
- Wie lässt sich ein Würfel darstellen / codieren?
  - Buchstabe für jede Farbe (Red, Green, Blue, Yellow, White, Orange) oder Seite (Up, Down, Front, Back, Left, Right)
  - Koordinatennetz mit planarer Sicht
  - String oder Array mit Länge $6*4 = 24$
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)

Dies ist eine alte Version des Dokuments!