Forschungsseminar Informatik und Mathematik (Wintersemester 2008/2009)

Folgende Termine und Vorträge sind bisher vorgesehen:
(Beim Klicken auf den Vortragstitel erscheint eine kurze Zusammenfassung des Vortrags.)

04.11.08

Nicole Schweikardt (Goethe-Universität Frankfurt am Main)
Lower bounds for multi-pass processing of multiple streams

Abstract: In this talk I consider the following machine model: Two streams S and T are processed by k cursors (i.e. "heads"). Each cursor either processes S or T, and each cursor can move one-way only (either forward or backward). Note, however, that cursors are allowed to move asynchronously. Throughout the computation, internal memory that consists of log(m) bits may be used. During each computation step, the machine sees the elements of S and T at the current cursor positions, and the current content of internal memory. Depending on these pieces of information, a deterministic transition function tells the machine (a) the new content of internal memory, and (b) which of the k cursors should be advanced to the next position.
The main result presented in this talk is a lower bound for solving the set-disjointness problem DISJ_n. The precise definition of DISJ_n is as follows: Let U be a set of size at least 2n. The input of DISJ_n consists of two subsets S and T of U with |S|=|T|=n. These two sets are represented by two streams that enumerate the elements in an arbitrary order. The goal is to decide whether S and T are disjoint.
THEOREM: If ( k^5 log(m) + k^6 log(n) ) < n/2, then no machine of the above kind can solve the problem DISJ_n.

Material: N. Schweikardt, Lower bounds for mulit-pass processing of multiple data streams. To appear in Proc. STACS'09. Preliminary version: here.

25.11.08

Thorsten Theobald (Goethe-Universität Frankfurt am Main)
Geradenprobleme in der algorithmischen Geomtrie

Abstract: Eine aktuelle Herausforderung in der algorithmischen Geometrie ist es, existierende Methoden, Strukturen und Algorithmen, die für polyedrische (= linear begrenzte) Objekte wohluntersucht und gut verstanden sind, auf durch Kurven und Flächen definierte Objekte zu übertragen. Diese Forschungsrichtung wird auch als nichtlineare algorithmische Geometrie bezeichnet.
In diesem Vortrag werden einige natürliche Probleme für 3- und n-dimensionale Geraden betrachtet, deren algorithmische Behandlung auf grundlegende Probleme zu Kurven und Flächen führt. Insbesondere soll ein Einblick in die in den letzten Jahren von dem Dozenten mitentwickelten reell-algebraischen Methoden zur Behandlung dieser Probleme gegeben werden.

09.12.08

Georg Schnitger (Goethe-Universität Frankfurt am Main)
Automaten und Kommunikation

Abstract: Wieviel Zustände benötigt ein nichtdeterministischer endlicher Automat (NFA), wenn eine vorgegebene Sprache erkannt werden soll? Insbesondere untersuchen wir den Einfluss eingeschränkter Mehrdeutigkeit auf die Größe von NFAs. Ein zentrales Hilfsmittel ist die Kommunikationskomplexität.

Material: Vortragsfolien zum Thema "Automata and Communication", Vortragsfolien zum Thema "Ambiguity and Communication"

13.01.09

Roberto Avanzi (Ruhr-Universität Bochum)
Impliziter Parallelismus in Yaos Skalarmultiplikationsverfahren und Anwendungen auf Elliptischen Kurven

Abstract: In diesem Vortrag wird eine Methode vorgestellt, die zur Beschleunigung der Berechnung von Vielfachen von Elementen aus bestimmten algebraischen Varietäten dient.
Sie ist eine Variante vom Algorithmus von Yao, die vom impliziten Parallelismus dieses Algorithmus Gebrauch macht.
Das resultierende Verfahren findet Anwendung auf die Skalarmultiplikation auf verschiedenen Klassen von (hyper)elliptischen Kurven, insbesondere mit relativ kleinen Parametern. Die Analyse dieser Methode führt zu interessanten kombinatorischen Fragen (occupancy of boxes).

27.01.09

Ralph Neininger (Goethe-Universität Frankfurt am Main)
Suchbäume, Fragmentierungen und Periodizitäten

Abstract: In diesem Vortrag werden verwandte Parameter von zufälligen Bäumen und Fragmentierungen besprochen, die asymptotisch auf periodisches Verhalten und Phasenübergänge führen.
Im Gebiet der Suchbäume wurden asymptotische Untersuchungen dazu von D.E. Knuth begonnen. Erst in den letzten Jahren konnten Grenzverteilungen nach und nach bewiesen bzw. Periodizitäten identifiziert werden. Verwandte stetige Modelle wurden nun auch in der Physik auf ihre Phasenübergänge hin untersucht mit ähnlichen Phasenübergängen.
Ich stelle diese Entwicklungen und Phänomene vor und bespreche rigoros bewiesene Ergebnisse für das stetige Modell aus der Arbeit Janson und Neininger, Probability Theory and Related Fields, 142 (2008), 399-442.

03.02.09

Markus Schmid (Goethe-Universität Frankfurt am Main)
Algorithmische Überlegungen zum Membership-Problem für Patternsprachen

Abstract: Der Vortrag präsentiert die Ergebnisse meiner Bachelorarbeit über das Membership-Problem für Patternsprachen. Ein Pattern ist ein Wort über einem Alphabet, welches aus Variablen und Terminalsymbolen besteht. Als die von einem Pattern p erzeugte (Pattern-)Sprache wird die Menge aller Terminalwörter bezeichnet, die durch eine uniforme Ersetzung der Variablen in p durch Terminalwörter erzeugt werden können. So beschreibt das Pattern p der Form p = xyx (wobei x und y Variablen sind) die Menge aller Wörter die aufgeteilt werden können in ein Präfix, einen Mittelteil und ein Suffix wobei Präfix und Suffix identisch sind. Als Membership-Problem wird das Entscheidungsproblem bezeichnet, welches bei Eingabe eines Pattern und eines Wortes danach fragt, ob das Wort in der von dem Pattern erzeugten Sprache liegt (d.h. ob das Wort von dem Pattern erzeugt werden kann). Das Membership-Problem für Patternsprachen ist NP-vollständig.
Es werden im Wesentlichen zwei Ansätze vorgestellt: Der erste besteht aus der Verbesserung eines naiven Algorithmus durch die Ausnutzung einfacher kombinatorischer Eigenschaften. Der zweite Ansatz besteht aus einer Reduktion des Membership-Problems auf das Erfüllbarkeits-Problem für Aussagenlogische Formeln (SAT). Des Weiteren werden die Ergebnisse einer experimentellen Analyse dieser beiden Ansätze vorgestellt.