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)\).
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 bestimmten
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.
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.
Ein JavaScript, das die
Hilbert-Kurven
auf einer HTML5 Canvas zeichnet.
Ein JavaScript, das die
Peano-Kurven
auf einer HTML5 Canvas zeichnet.
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.
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.
Ich habe auch eine alte Version dazu gepackt, die reines Backtracking verwendet, damit man den Unterschied in den Laufzeiten sehen kann.
Ein JavaScript, das die
Sierpiński-Kurven
auf einer HTML5 Canvas zeichnet.