Algorithmische Anwendungen Prof. Dr. Heiner Klocke
WS 2006/07
 |
VorschlŠge: Themenbereiche fŸr Referate
Auch eigene VorschlŠge von Ihnen sind erwŸnscht!
1. Mehrdimensionale BŠume. EinfŸhrung in die Datenstrukturen und Eigenschaften mehrdimensionaler BŠume.
o k-dimensionale BinŠrbŠume (kd-trees)
o speziell: Quadtrees, Octees.
2. Algorithmen mit kd-trees. Nachbarschaften, AbstŠnde, Schnittprobleme, kd-tree search
3. String-Searching mit dem Boyer-Moore-Algorithmus.
4. Algorithmen der Bioinformatik: Sequence-Alignment
o globales u. lokales Alignment
o multiples Alignment
o Alignment-Algorithmen
5. Algorithmen fŸr nicht-analytische Probleme
o Genetische Algorithmen
o evolutionŠre Algorithmen
o Evolutionsstrategien
6. Lineare Programmierung. Optimierungsalgorithmen zur Lšsung linearer Gleichungssysteme.
o Simplex-Algorithmus (George Dantzig, 1947)
o Innere-Punkte-Verfahren (Narendra Karmarkar, 1984)
o Ellipsoidmethode (David Yudin and Arkadi Nemirovski, 1976)
7. Traveling Salesman Problem (TSP)
o Mathematische Beschreibung
o Beispiel: Die optimierte Odyssee (http://elib.zib.de/pub/UserHome/Groetschel/Spektrum/index2.html)
o Algorithmische KomplexitŠt, NP-VollstŠndigkeit
o Lšsungsverfahren
¤ exakte
¤ heuristische
8. Algorithmische Geometrie (R. Klein: Algorithmische Geometrie. Addison-Wesley (1997))
o Konvexe HŸllen von Punktmengen
¤ Graham-Scan-Algorithmus
¤ Jarvis-March-Algorithmus
¤ Quickhull-Algorithmus
9. Graph-Layout-Algorithmen
o Planar eingebettete Graphen, Maps und Faces
o Der Spring-Algorithmus (Feder-Algorithmus)
o JGraph
10. Kryptografische Algorithmen
11. Datenstrukturen und Algorithmen im Audiobereich
Um Themen aus diesem Bereich zu bearbeiten sind musikalische Vorkenntnisse erforderlich
o Midi – Musical Instrument Digital Interface
o Midi-Schnittstellen und Sequenzer
o Software-Sequenzer
o Audio-Formate
¤ verlustfreie
¤ verlustbehaftete
12. ...
Sie kšnnen sich selbst Themen suchen und mit mir absprechen. Falls Sie sich fŸr ein bestimmtes Thema besonders interessieren, kšnnen Sie mich auch per E-Mail (klocke@gm.fh-koeln.de) informieren. Bitte recherchieren Sie aber vorher ausfŸhrlich nach geeigneter Literatur zum Thema. Besorgen Sie sich vor allem die PrimŠrliteratur Ÿber die Fernleihe der Bibliothek
Beachten Sie: Vom 4. – 8.10.2006 bin ich nicht erreichbar.
Stand: 2.10.2006