Seminar Property Testing im Sommersemester 2010

Kontaktpersonen:

Peter Rossmanith

Joachim Kneis (kneis@cs.rwth-aachen.de)

Alexander Langer (langer@cs.rwth-aachen.de)

Somnath Sikdar (sikdar@cs.rwth-aachen.de)

---

Einordnung

Theoretische Informatik (für B.Sc. Informatik)

Ort und Zeit

11.06.2010, 13:15-15:30 in 5052, 15:30 - 17:00 Uhr, Seminarraum I1.

Inhalt

Kann man entscheiden, ob ein Array sortiert ist, ohne sich alle Elemente des Arrays anzuschauen?

Das Prinzip von Approximationsalgorithmen fuer Optimierungsprobleme ist jedem Informatiker wohlbekannt. Wie aber approximiert man Fragestellungen, auf die es nur Ja/Nein-Antworten gibt, also Entscheidungsprobleme wie die o.g. Fragestellung, ob ein gegebenes Array sortiert ist.

Eine Moeglichkeit ist bekannt unter dem Namen property testing: Es gibt Algorithmen, welche verblüffend schnell (z.B. in konstanter oder sublinearer Zeit) entscheiden können, ob die Eingabe eine gewisse Eigenschaft hat - oder zumindest "fast" hat - oder noch "weit davon entfernt" ist.

Wie das funktioniert und funktionieren kann, und was wahrscheinlich doch nicht funktionieren wird, das moechten wir in diesem Seminar kennen- und liebenlernen.

Mehr zu Property Testing: Laieninformationen auf Wikipedia, ernstzunehmende Informationen auf der Property Testing Homepage von Oded Goldreich.

Voraussetzungen

Im Diplomstudiengang: Vordiplom. Interesse an Mathematik und theoretischer Informatik. Bereitschaft und Fähigkeit zur Begeisterung und Selbstmotivation. Von Vorteil sind Vorkenntnisse in algorithmischen Aspekten der theoretischen Informatik und Wahrscheinlichkeitsrechnung.

Deadlines

Spätestens zwei Wochen vor dem jeweiligen Vortrag muß ein Probevortrag gehalten werden. Spätestens einen Monat nach dem Vortrag muß die Ausarbeitung abgegeben werden, und spätestens nach einem weiteren Monat müssen alle unsere Anmerkungen zu unserer Zufriedenheit in die Ausarbeitung eingearbeitet sein. Außerdem muß uns jeder Teilnehmer möglichst schnell ein Konzept seiner Ausarbeitung präsentieren.

Ausarbeitungen

Unsere Hinweise zum Verfassen schriftlicher Arbeiten sind unbedingt zu beachten!

Einige mit LaTeX-Beamer erzeugte Beispielfolien finden sich hier. Zum Kompilieren benötigt man diese Quellen. Lesenswert ist zudem die Anleitung für das Beamerpaket. Im wesentlichen für Linux: Einige Hinweise und Quelldateien zum Schreiben einer LaTeX-Arbeit gibt es hier. Neben den wichtigsten Textelementen werden auch der Formelsatz sowie das Erzeugen und Einbinden von Metapost-Abbildungen behandelt. Außerdem liegt ein einfaches, aber praktisches Makefile bei.