Institute for Computer Science I Prof. Dr. Christian Sohler
General Home Contact People Research Projects Teaching Winter 08/09 Summer 08 Topics for Diploma Thesis Links Bonn Research Platform on Algorithmics Institute of Computer Science International MSc Program	Themenvorschläge für Diplomarbeiten:
	Um aktuelle Themenvorschläge für Diplomarbeiten zu erhalten, wenden Sie sich bitte an Christian Sohler oder eine/n seiner Mitarbeiter/Innen. Unten aufgeführt sind einige Themenvorschläge, die aber nur sporadisch aktualisiert werden. Sie dienen jedoch dazu, sich ein Bild über mögliche Diplomarbeitsthemen zu machen. Falls Sie bereits eigene Vorschläge und/oder Vorstellungen zu Diplomarbeitsthemen haben, so können Sie sich ebenfalls gerne an uns wenden.
	Berechnung optimaler Kernmengen
	Sei P eine Punktmenge im euklidischen Raum. Aufgabe beim k-Median Clustering Problem ist das Finden einer Menge von k Punkten, so dass die Summe der Distanzen zum jeweils nächstgelegenen dieser k Punkte minimiert wird. Wir   Eine Kernmenge ist eine kleine gewichtete Untermenge einer Punktmenge P, die die Punktmenge bzgl. eines Clusteringproblems approximiert. Aufgabe ist, einen Algorithmus zur Berechnung einer kleinsten Kernmenge einer gegebenen Punktmenge für ein vorgegebenen Fehlerparameter e zu finden.
	Clustering von Textdokumenten mit Hilfe von Kernmengen
	Die Strukturierung großer Mengen von Textdokumenten (z.B. Webseiten) dient zur Unterstützung der gezielten Suche nach Dokumenten. Häufig wird eine solche Strukturierung mit Hilfe von Clustering Algorithmen berechnet, die die Eingabemenge in Gruppen ähnlicher Dokumente aufteilen. Bei sehr großen Eingabemengen sind die meisten Clusteringalgorithmen nicht sonderlich effizient. Ziel dieser Diplomarbeit ist daher die Entwicklung eines effizienten Algorithmus zum Clustering von Textdokumenten. Dabei sollen in der theoretischen Informatik entwickelte Techniken wie Kernmengen und der k-Means++ Algorithmus auf die neue Problemstellung angepasst und zur Effizienzsteigerung verwendet werden. Die entwickelten Algorithmen sollen experimentell evaluiert werden.