Einige Seminarvorträge wurden gehalten als Kolloquiumsvorträge am Mittwoch, 27.04., 15.06. und 22.06, jeweils um 17 Uhr.

Außerdem gab es noch einen Seminarabend am 07.06. ab 18:30 Uhr, an dem 2 weitere Vorträge gehalten werden, von denen einer aus der Wertung zurückgezogen wurde.

Die Vortragsvergabe für das laufende Sommersemester 2011 ist abgeschlossen. Die 8 nicht vergebenen Themen werden hier weiter aufgeführt, da sie für einen Seminarvortrag im kommenden Wintersemester zur Verfügung stehen.

Dieses Seminar gibt die Möglichkeit einer Einarbeitung in die Gebiete Algorithmik und Künstliche Intelligenz. In beiden Gebieten gibt es vielfältige Möglichkeiten, Abschlussarbeiten zu schreiben. In der Algorithmik soll der Fokus auf Parallelität und geometrischen Abwendungen liegen. In der künstlichen Intelligenz geht es im Wesentlichen um grundlegende Prinzipien, die bisher in dieser Tiefe in meinen Vorlesungen nicht behandelt wurden.

Während die Anwendungen in der Algorithmik aus praktisch allen Bereichen der Informatik kommen können, wird in der Künstlichen Intelligenz ein besonderes Augenmerk auf die Möglichkeit der Weiterentwicklung des Touristeninformationsystems gelegt, das in verschiedenen Projekten bereits von Studierenden bearbeitet wurde und das noch vieler weiterer Ausbaustufen bedarf.

Die Vortragsinhalte ergänzen die Vorlesungen Algorithmik (Masterstudium Informatik) und Künstliche Intelligenz (Bachelor- und Masterstudium Informatik und Kombinationsstudiengänge), setzen diese aber nicht zwingend voraus. Daher sind auch Bachelorstudierende der Medien- und Wirtschaftsinformatik eingeladen, an diesem Seminar teilzunehmen, um auf diese Weise die Gelegenheit zu ergreifen, sich bereits im Bachelorstudium mit Künstlicher Intelligenz zu beschäftigen, was ihnen nach Studienplan leider verwehrt ist.

Einige der Vorträge stehen nur Bachelorstudierenden zur Verfügung, weil das Niveau für einen Vortrag im Masterstudium nicht ausreicht. Bachelorstudierende dürfen aber gerne auch Vorträge aussuchen, die fürs Masterstudium geeignet sind. In einigen Themen kann man diese Vorträge durchaus auf unterschiedlichem Niveau halten, sodass auch solche Themen nicht zu schwer fürs Bachelorstudium sind. In der Notengebung wird natürlich berücksichtigt, ob es sich um einen Bachelor- oder Masterstudierenden handelte. Sprechen Sie mich in Zweifelsfragen vor der Vortragsvergabe darauf an.

Für einige Vorträge gibt es zusätzliches Material auf dem Handout-Server (nur für Angehörige der FH Wedel zugänglich).

Cormen / Leiserson / Rivest / Stein: Algorithmen - Eine Einführung, Oldenburg 2010 (3. Auflage), ISBN 978-3-486-59002-9

englische Originalausgabe ebenfalls in Bibliothek: MIT-Press 2009, ISBN 0-262-53305-7
außerdem Kap. 27 auf Handout-Server

Papadimitriou / Steiglitz: Combinatorial Optimization - Algorithms and Complexity, Dover 1998, ISBN 0-486-40258-4

Dechter: Constraint Processing, Morgan Kaufmann 2003, ISBN 978-1-55860-890-0

Studer / Grimm / Abecker: Semantic Web Services, Springer 2007, ISBN 978-3-540-70893-3

Helbig: Die semantische Struktur natürlicher Sprache, Springer 2001, ISBN 3-540-67784-4

werden im Folgenden näher beschrieben.

Zusätzlich können jederzeit eigene Vortragsthemen zur Seminarthematik  vorgeschlagen werden. Auch in diesem Semester sind zwei solche Vortragsthemen entstanden, die als individuell vereinbart gekennzeichnet sind.

Die im Folgenden verlinkten Ausarbeitungen und Vortragsunterlagen sind im Original dargestellt und ausschließlich von den Verfassern bearbeitet worden. Daher kann der Lehrveranstalter keine Gewähr für die Qualität und Richtigkeit geben.

1) Individuell vereinbarter Vortrag:
Evaluierung der C++-Algorithmenbibliothek LEDA
LEDA ist eine kommerzielle Software-Bibliothek, die am Max-Planck-Institut für Informatik (verbunden mit der Uni Saarbrücken) unter der Leitung von Prof. Kurt Mehlhorn entstanden ist.
Der Vortrag soll wesentliche Bestandteile vorstellen. Besonderer Wert wird auf den Vergleich mit open-source-Bibliotheken wie Boost gelegt. Auch der Mehrwert für eine kommerzielle Nutzung soll angesprochen werden.

Vortragender: Marcus Riemer
Termin: Mittwoch, 27.04., 17 Uhr, HS 5
Vortrag   Ausarbeitung   Quellcode (nur für Angehörige der FH Wedel zugänglich)

2) Algorithmen für parallele Prozessoren (Bachelor und Master)
Inhaltliche Grundlage ist Kap. 27 von Cormen et al. (nur in der 3. Auflage enthalten). Es sollen sowohl die Grundlagen bezüglich Komplexitätsüberlegungen als auch mindestens ein Anwendungsbeispiel vorgestellt werden (Matrizenmultiplikation oder Sortieren).

Vortragender: Markus Wanke
Termin: Dienstag, 07.06., 18:30 Uhr, HS 5
Vortrag   Ausarbeitung

3) Probabilistisches Matching von Figuren (eher Master)
Weitere Forschungsergebnisse der Arbeitsgruppe Theoretische Informatik der FU Berlin auf dem Gebiet der algorithmischen Geometrie.
Grundlage sind Originalarbeiten auf dem Handout-Server von 2007-2009

Vortrag aus Wertung zurückgezogen
Termin: Dienstag, 07.06., 19:45 Uhr, HS 5

4) Individuell vereinbarter Vortrag:
Fuzzy Control in technischen Systemen
Der Vortrag stellt den wesentlichen Inhalt einer Lehrveranstaltung zum Thema Künstliche Intelligenz unserer Partnerhochschule University of Abertay, Dundee (Schottland), vor. Der Referent besuchte diese Lehrveranstaltung von Januar bis April als Ersatzleistung für die Lehrveranstaltung Grundlagen der KI.

Außerdem wird er uns nach seinem Vortrag für Fragen zu seinem Auslandsaufenthalt zur Verfügung stehen.

Vortragender: Jakob Schomann
Termin: Mittwoch, 15.06., 17 Uhr, HS 5
Vortrag   Ausarbeitung

5) Abschlussvortrag: Parallele Algorithmen für ein geometrisches Problem

Vortragender: Prof. Dr. Helmut Alt (FU Berlin)

Parallele Algorithmen waren in den 1980er Jahren ein sehr aktiv bearbeitetes Forschungsgebiet auch in der theoretischen Informatik. Diese Aktivitäten sind in den Jahren danach allerdings stark zurückgegangen. Zum einen waren die theoretischen Modelle noch zu weit von der Wirklichkeit entfernt, zum anderen ist es der Computer-Technologie gelungen, die Leistung sequentieller Rechner ständig deutlich zu verbessern, so dass paralleles Rechnen eigentlich nicht erforderlich war.

In den letzten Jahren allerdings werden die Grenzen der möglichen Beschleunigung sequentieller Rechner erreicht, und die Computerhersteller produzieren bereits größtenteils Rechner mit mehreren Prozessorkernen. Auch Graphikprozessoren haben eine Architektur mit hoher Parallelität und werden inzwischen auch für allgemeine Aufgaben eingesetzt. Durch diese Entwicklung wird der Entwurf paralleler Algorithmen wieder interessant und wichtig.

Im Vortrag werden an einem Beispiel aus der algorithmischen Geometrie, nämlich die tiefste Stelle in einer Vereinigung von Rechtecken in der Ebene zu finden, die Denkweisen und Techniken bei Entwurf und Analyse paralleler Algorithmen aufgezeigt.

Der Referent baute die Forschungsgruppe Theoretische Informatik an der FU Berlin auf, aus der zahlreiche Wissenschaftler hervorgegangen sind. Auch ich habe bei Prof. Alt auf dem Gebiet der algorihmischen Geometrie promoviert. Die Forschungsgruppe bietet exzellente Möglichkeiten für eine Promotion im Anschluss an ein Masterstudium.

Termin: Mittwoch, 22.06., 17 Uhr, HS 5

Außerdem übernimmt Prof. Alt die Algorithmik-Vorlesung am 23.06. um 09:30 Uhr im HS 1.

Die folgenden Vorträge wurden im SS 2011 nicht vergeben und stehen im WS 2011/2012 zur Verfügung.

1) Algorithmus von Edmonds für Matching in allgemeinen Graphen (Bachelor und Master)
Der Algorithmus wird in meiner Mastervorlesung nur skizziert und soll hier ausführlich (und mit einem Beispiel) vorgestellt werden. Grundlage ist Kap. 10 von Papadimitriou.

2) Matching in bewerteten Graphen (eher Master)
Dieser Vortrag wird nur vergeben, wenn Vortrag 1) vergeben wurde. Er geht darauf ein, wie man algorithmische Prinzipien von unbewerteten auf bewertete Graphen überträgt. Grundlage ist Kap. 11 von Papadimitriou. 

3) Frechet-Distanzen zum Messen der Ähnlichkeit von Polygonen (eher Master)
Hier geht es um Forschungsergebnisse der Arbeitsgruppe Theoretische Informatik der FU Berlin auf dem Gebiet der algorithmischen Geometrie. Dort gibt es sehr gute Promotionsmöglichkeiten für Interessierte.
Grundlage ist eine Originalarbeit auf dem HandoutServer von 1995 sowie eine Übersichtsarbeit von 1997. Im Zweifelsfall stehen auch die Autoren an der FU Berlin zur Verfügung. 

4) Verschiedene Konsistenztypen bei der Constraint Propagation (nur Bachelor)
Inhaltliche Grundlage sind Kap. 3 und 4 von Dechter. Besser als im zitierten Buch soll der Vortrag aber die Sachverhalte an einem konkretem Beispiel erklären. 

5) Vergleich der Suchstrategien Look-Ahead vs. Look-Back (nur Bachelor)
Inhaltliche Grundlage sind Kap. 5 und 6 von Dechter. Besser als im zitierten Buch soll der Vortrag aber die Sachverhalte an einem konkretem Beispiel erklären. 

6) Wissensrepräsentation mit Ontologiemanagement (Bachelor und Master)
Dieser Vortrag erklärt die in meiner KI-Vorlesung nur angerissene Intention des Touristen-Informationssystems mit etwas mehr Tiefgang. Grundlage ist Kap. 3 (und angrenzende Kapitel) von Studer et al.

7) Anwendungen von Semantic Web Services (Bachelor und Master)
Hier sollen andere Anwendungen als das Touristen-Informationssystem vorgestellt werden, die aber ähnliche theoretische Zielsetzungen verfolgen. Es wird erwartet, dass sich der Referent deutlich über die in Kap. 13 und 14 von Studer et al. dargestellten Inhalte hinaus informiert. 

8) Grundlagen der systematischen Erfassung der Bedeutung natürlichsprachiger Sätze (nur Bachelor)
Grundlage sind die Ausführungen von Kap. 3 und 4 von Helbig. Das dort verwendete Werkzeug MultiNet soll nicht im Fokus des Vortrags stehen.