Am Wochenende (21.-23.11.2008) finden an der Universität in Utrecht
die nordwesteuropäischen Ausscheidungen zum International Collegiate
Programming Contest der ACM statt. 48 Teams aus Großbritannien,
Skandinavien, den Benelux und Deutschland konkurrieren um den Einzug in
die World Finals. Unser Team 'Help Desk Ugly Ogres' bestehend aus
Sebastian Hungerecker, Lukas Schmidt und Martin Schuster (3. Semester
Informatik) vertreten unsere Uni. Intensiv hat sich das Dreierteam in
den letzten Monaten auf den Contest vorbereitet. In dem fünfstündigen
Wettbewerb gilt es, für möglichst viele Problemstellungen eine
effiziente Lösungsstrategie zu entwickeln und diese auch technisch
korrekt umzusetzen.
Der Wettbewerb startet am Sonntag, den 23.11.2008 um 10:00h. Die Problemstellungen und die aktuelle Rangliste sind unter
http://2008.nwerc.eu zu finden.
31.Oktober2008, 12 Uhr c.t. Seminarraum 2021, Haus 64, 2. OG
Abstract:
Pre-processing is a humble strategy for coping with hard problems, almost universally employed. It has become clear, however, that far from being trivial and uninteresting, that pre-processing has unexpected practical power for real-world input distributions, and is mathematically a much deeper subject than has generally been understood.
It is almost impossible to talk about pre-processing in the classical complexity framework in any sensible way, and the relative neglect of this vital subject may be related to this fact (the ``lost continent'').
In the parameterized complexity framework, however, such a program can be framed in a manner that is absolutely interesting and productive way, and in fact turns out to be central to parameterized algorithmics. The effectiveness of P-time preprocessing is measured against the structure represented by the parameter.
In the last three years, the field of FPT kernelization has advanced dramatically, with strong practical payoffs, yet there are still many challenging open problems. The talk will survey the main issues and approaches, and report on new kernelization lower bound techniques.
ab sofort
16. Juli 2008, 16 Uhr s.t. Seminarraum 2021, Haus 64, 2. OG
„Textkategorisierung basierend auf der Beschreibungskomplexität von Zeichenketten“
08. Juli 2008, 16 Uhr ct, ITCS Seminarraum 2021, Geb. 64, 2. OG
Abstract:
Textkategorisierung ist ein wichtiger Forschungsbereich, um die Fülle anfallender digitaler Dokumente nach inhaltlichen Kriterien zu verwalten. Der vorherrschende Ansatz der merkmalsbasierten Klassifizierung zeichnet sich jedoch durch aufwändige Vorverarbeitung und komplexe Parametrisierung aus.
In dieser Arbeit untersuchen wir einen nicht-merkmalsbasierten Ansatz zur Textkategorisierung mit einem kNN-Klassifikator. Da keine komplexe Vorverarbeitung aufgeführt wird, kann der Klassifikator besonders einfach angewandt werden. Zur Definition eines Ähnlichkeitsmaßes für Volltexte verwenden wir die normalized compression distance (NCD). NCD basiert auf der Theorie der Kolmogorov-Komplexität und approximiert die Beschreibungskomplexität von Texten mit Hilfe von Kompressionsmethoden. Wir beleuchten in dieser Arbeit den theoretischen Hintergrund der Ähnlichkeitsmaße und untersuchen die Eigenschaften des Normal Compressors für die eingesetzten Kompressionsmethoden. In umfangreichen Experimenten führen wir erstmals kompressionsbasierte Textkategorisierung für zwei Standard-Textkorpora (RCV1, 20 Newsgroups) aus und erhalten vergleichbare Resultate zu State of the Art-Klassifikatoren. Darüber hinaus führen wir ein neues online-Bewertungsmaß für die Klassifikation basierend auf Frequenzvergleichen ein und zeigen die Bewertungsgüte anhand des Textkorpus RCV1.
„Beschleunigung von Image Matching für natürliche Bilder“
03. Juni 2008, 16 Uhr ct, ITCS Seminarraum 2021, Geb. 64, 2. OG
Image Matching ist ein Optimierungsproblem aus der digitalen Bildverarbeitung, bei dem ein gegebenes Bild A geometrisch so verzerrt werden soll, dass es möglichst deckungsgleich zu einem zweiten gegebenen Bild B wird. Anwendungen aus der Praxis erlauben häufig Rotation, Skalierung und Translation zur Verzerrung von A. Die Untersuchung des Image-Matching-Problems wird durch eine breite Palette von Anwendungen, wie z.B. Texterkennung, Videokompression und Medizinische Bildverarbeitung, motiviert. Die Berechnungskomplexität von Image Matching wurde ausgiebig untersucht. Beschränkt auf Rotation, Skalierung und Translation kann es in polynomieller Zeit gelöst werden. Die bekannten exakten und approximativen Algorithmen sind für den Einsatz in echten Anwendungen dennoch nicht geeignet.
In diesem Vortrag stellen wir einen neuen, beschleunigten Image-Matching-Algorithmus vor, der mithilfe natürlicher Annahmen über die Eingabebilder die Suche im Lösungsraum zielgerichteter zum Optimum führt. Es wird dafür ein Modell für praktisch relevante Bilder vorgestellt und analysiert. Der Algorithmus findet stets das globale Optimum. Unter Eingabe natürlicher Bilder weißt er jedoch einen deutlich reduzierten Verbrauch an Rechenzeit auf, wie die abschließende empirische Untersuchung verdeutlicht.
Der im Wissenschaftsjahr Informatik 2006 eingeführte "Algorithmus der Woche" ist jetzt als Taschenbuch im "Springer-Verlag" erschienen
