www.AlgorithMan.de
Where theory comes alive
Automaten
Selbstverständlich habe ich auch eine Klasse für Automaten (immerhin stammen einige der tiefergehenden Artikel über Automaten auf Wikipedia von mir). Die Klasse ist z.Z. aber Work-In-Progress.
65 KiB
Ein extrem kleines Programm (ohne Kommentare hat der Quellcode nur 370 Bytes, die kompilierte Binary 8,3 KiB), das prüft, ob ein gegebener String ein wohlgeformter arithmetischer Ausdruck ist. Das Programm entspricht einem Kellerautomaten für die Kontextfreie Grammatik
S ---> ( S ) | S+S | S-S | S*S | S/S | Num
Num ---> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Num Num
Da solch ein Automat mit einem Keller-Alphabet auskommt, das nur 1 Element hat, kann man den Keller durch ein einzelnes Zählregister ersetzen. Dann hat man die folgende Register-Maschine: arith_check
19 KiB
Ein Programm, das zu zwei Zahlen n und b einen Automaten konstruiert, der Zahlen im b-adischen Zahlensystem erkennt, die durch n teilbar sind. So, wie zum Beispiel dieser Automat coset_dfa
Binärzahlen erkennt, die durch 3 teilbar sind.
513 KiB
Generiert aus Dateien einen (bzgl. zeichenweiser Kodierung) optimalen Codebaum mit der Huffman-Kodierung. Formal ist ein Codebaum ein Moore- oder Mealy-Automat.
Unsere Seminar-Ausarbeitung und Vortrags-Folien vom Proseminar Datenkompression, WS 2004/05 am Lehrstuhl i6 sind auch enthalten (auf aktuellen LaTeX compilern lassen sich die Folien nicht mehr ganz richtig kompilieren).
23 KiB
Ein Programm, das (basierend auf dem Algorithmus string_search) die Bereiche zwischen einem gegebenen start-string und einem end-string aus stdin extrahiert und auf stdout ausgibt. Damit kann man z.B. so
cat foo.html | ./string_extract 'href="' '"'
die Ziele von Hyperlinks aus HTML-Dateien extrahieren.
22 KiB
Ein Programm, das prüft, ob ein String in einem anderen vorkommt. Dazu baut es einen minimalen deterministischen Automaten für den gesuchten String.

Das interessante daran ist, dass die Konstruktion des deterministischen Automaten nicht über die Minimierung der Potenzmengen-Konstruktion nach Thompson-Konstruktion realisiert ist, sondern der Automat direkt aus dem String konstruiert wird, wofür lediglich eine Laufzeit von \(O(n^2)\) benötigt wird, entgegen der Potenzmengen-Konstruktion, die \(O^*(2^n)\) benötigt. Dass der Automat trotzdem minimal ist, lässt sich leicht dadurch beweisen, dass alle Präfixe des gesuchten Strings in verschiedenen Myhill-Nerode Äquivalenzklassen liegen.

Wie ich inzwischen erfahren habe, ist das der Knuth-Morris-Pratt-Algorithmus.