Seminar WS 03/04
Algorithmen auf Zeichenketten
Zeit: Dienstag 10-12 (ab 2.
Vorlesungswoche)
Ort : M3-115
Belegnummer: 392022
Sequenzen sind allgegenwärtig. Texte und Programme, Gene und
Proteine, Polygonzüge, Sprach- und Bildsignale und digitalisiertes
Vogelzwitschern werden dargestellt als Zeichenfolgen über einem
endlichen Alphabet. Entsprechend vielfältig sind die
algorithmischen Fragestellungen. Oft ist dabei der Datenumfang sehr
groß, so daß die algorithmische Komplexität von
entscheidender praktischer Bedeutung ist. In der Vorlesung werden
Algorithmen für schnelle (exakte und approximative) Suche und ihre
Komplexität analysiert.
Geplante Themen:
- klassische Verfahren (BMH, KMP) und deren Erweiterungen
- seminumerische Suchalgorithmen
- Index basierte Verfahren
- schnelle Heuristiken (BLAST, FASTA)
Eine genauere Vortragsuebersicht liegt
hier!
Weitere Literatur findet ihr hier.
Literatur:
Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer
Science and Computational Biology, Cambridge Press, New York, 1997
Voraussetzung: Algorithmen und Datenstrukturen I