www.AlgorithMan.de
where theory comes alive
2903 KiB
Meine Seminar-Ausarbeitung und -Vortragsfolien vom Hauptseminar exakte Algorithmen (WS2007/08) beim Lehrstuhl für theoretische Informatik (wo ich auch mein Diplom gemacht habe).
Mein Thema war das Minimum Quartet Inconsistency Problem (MQI) welches parametrisierbar ist (der Wikipedia Artikel über parametrisierte Algorithmen stammt übrigens von mir :-) ).
Im Rahmen des Seminars habe ich einen viel kürzeren (Widerspruchs-)Beweis für den Hauptsatz aus dem Paper von Niedermeier und Gramm gefunden und die Laufzeit von \(O(4^k\cdot n+n^4)\) verbessert auf \(O(3,561^k\cdot n+n^4)\).
16 KiB
Die Türme von Hanoi, ohne Ausprobieren mittels Backtracking, sondern mit straight forward betimmten Verlege-Anweisungen.
Die Idee ist: um n Scheiben von A nach C zu verschieben,
verschiebe n-1 Scheiben von A nach B,
dann eine Scheibe von A nach C,
dann n-1 Scheiben von B nach C.
14 KiB
Ein Programm für das Rucksackproblem, das mit Branch-and-Bound arbeitet.
11 KiB
Ein JavaScript, das Lösungen für Solitär findet (das Brettspiel, welches im Englischen "Peg Solitaire" heißt - nicht das Kartenspiel Patience, welches im Englischen "Solitaire" heisst). Blankes Backtracking, aber weil man die Berechnung (trotz JavaScript) auch beobachten können soll, rechnet es iterativ auf einem manuell verwalteten Stack, damit nach einigen Iterationen angehalten werden kann, der Bildschirm aktualisiert werden und die Berechnung dann timer-gesteuert fortgesetzt werden kann.
5 KiB
Ein Javascript, das den Baum des Pythagoras auf einer HTML5 Canvas zeichnet.
603 KiB
Ein Programm, das scramble square puzzles löst. Dadurch, dass immer die Position belegt wird, auf die die kleinste Anzahl von Puzzleteilen passt oder das Puzzleteil platziert wird, für das die kleinste Anzahl von Positionen in Frage kommt (jenachdem, was weniger ist), wird der Verzweigungs-Vektor sehr klein gehalten. Ausserdem werden Situationen erkannt und ausgenutzt, in denen mehrere Puzzleteile identisch sind und es werden symmetrische Lösungen vermieden. Das führt zu sehr guten Laufzeiten - in den Beispielen werden nur etwa 300-400 Rekursionen benötigt, obwohl es \((n\cdot 4)^n\) Kombinationen gibt. In den Rekursionsaufrufen werden jeweils \(O(4\cdot n^4)\) Schritte benötigt.
Ich habe auch eine alte Version dazu gepackt, die reines Backtracking verwendet, damit man den Unterschied in den Laufzeiten sehen kann.
Impressum, Haftungsausschluss etc. W3C Validation