Diplomarbeit DIP-2557

Bibliograph.
Daten
Hantschel, Ralf: Über das Wachstum von Boyer-Moore-Automaten.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Diplomarbeit Nr. 2557 (2007).
150 Seiten, deutsch.
CR-Klassif.F.1.1 (Models of Computation)
F.1.2 (Modes of Computation)
G.1.6 (Numerical Analysis Optimization)
I.2.8 (Problem Solving, Control Methods, and Search)
I.5.4 (Pattern Recognition Applications)
K.5.2 (Legal Aspects of Computing Governmental Issues)
KeywordsBoyer-Moore-Automat; Evolution; Evolutionäre Algorithmen; Genetischer Algorithmus; vollständige Suche; Automaten
Kurzfassung

In dieser Arbeit wird untersucht, in welchem Ausmaß Boyer-Moore-Automaten, abhängig vom zu suchenden Suchwort wachsen. Von manchen wird ein exponentielles Wachstum vermutet, andere behaupten dagegen, dass das Wachstum nur polynomiell ist. Es wird für einfache Fälle (kleines Alphabet, kurzes Suchwort) das Suchwort ermittelt, für welches die Anzahl der Zustände des zugehörigen Boyer-Moore-Automaten maximal wird. Bei einem zweielementigen Alphabet ist dies bis zur Suchwortlänge 30 möglich, bei einem dreielementigen Alphabet bis zur Suchwortlänge 19. Für längere Suchworte wird ein Genetischer Algorithmus entwickelt, der versucht die Suchworte zu finden, die sehr große Boyer-Moore-Automaten erzeugen.

Volltext und
andere Links
PDF (3220394 Bytes)
Zugriff auf studentische Arbeiten aufgrund vorherrschender Datenschutzbestimmungen nur innerhalb der Fakultät möglich
Kontaktralf_hantschel@gmx.de
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Formale Konzepte
Eingabedatum18. Mai 2007
   Publ. Institut   Publ. Informatik