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)
|
Keywords | Boyer-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 |
Kontakt | ralf_hantschel@gmx.de |
Abteilung(en) | Universität Stuttgart, Institut für Formale Methoden der Informatik, Formale Konzepte
|
Eingabedatum | 18. Mai 2007 |
---|