Dozent: Dr. Stefan Hougardy
Termine
| PS | Dienstag | 09:00 - 11:00 | (Rud 25, IV.111) |
|---|
Zuordnung
- Grundstudium, Proseminar
Inhalte und Lernziele
Wir werden in diesem Proseminar Algorithmen behandeln, die in ihrer einfachsten Form entscheiden, ob ein bestimmtes Wort in einem gegebenen Text vorkommt. Jeder der schon mal mit einem Editor gearbeitet hat oder aber z.B. das UNIX-Kommando 'grep' benutzt hat, hat solche Algorithmen angewendet. Ausgehend von der brute-force Methode zur Lösung dieses Problems, werden wir eine Reihe von effizienteren Algorithmen kennenlernen und zudem auch verallgemeinerte Probleme lösen können, wie z.B. das Suchen nach bestimmten Mustern in Texten.
Folgende Themen sollen behandelt werden:- Grundlagen, Brute Force Algorithmen
- die Algorithmen von Knuth-Morris-Pratt und Boyer-Moore(-Horspool)
- Simultanes Pattern Matching
- Stringabstände
- längste gemeinsame Teilstrings
- Suffix Trees
- kürzester Superstring
- sich wiederholende Teilstrings
- approximatives Patternmatching
Empfohlene Literatur
- , String Searching Algorithms, World Scientific 1994
- , How to Present a Paper in Theoretical Computer Science: A Speaker's Guide for Students, Technical Report, Department of Computer Sciences, University of North Texas, July 1993
