HEINZ NIXDORF INSTITUT
Universität Paderborn
Theoretische Informatik
AG Meyer auf der Heide


Perlen der Theoretischen Informatik

WS 04/05

 

Friedhelm Meyer auf der Heide

Termine


Anmeldung und Themenvergabe
war am 27. Oktober 2004  16h15  im  F1.310
mit dem unten aufgeführten Ergebnis.

 
Abgabe der schriftlichen Ausarbeitungen
(8-12 Seiten)
bis 16. Januar 2005

Blockseminar (S2)
 
Mittwochnachmittag, 26. Januar 2005 im F1.110;
Mittwoch und Donnerstag, 2.+3. Februar 2005 im Schloß Gehrden bei Brakel/Höxter.

Kosten (Unterkunft+Verpflegung) voraussichtlich ca. 60 Euro.


Bewertung

als ein MuA-Punkt im dritten Abschnitt (Master-Studiengang) bzw. Hauptstudium (DPO4).

 

Zeitplan

Beginn am Mittwoch, dem 26.1.2005 im F1.110:
13h15 Jens Golombek (Martin Ziegler) "LIFE ist unentscheidbar"
14h15 Martin Meeser (Martin Ziegler) "Eine Komplexitätstheorie von Adventure-Spielen"
15h15 Pause
15h30 Matthias Hilbig (Martin Ziegler) "C++ Parser sind universell"
16h30 Sven Köhler (Martin Ziegler) "Der Computer programmiert sich selbst"
 

Mittwoch, dem 2.2.2005 in Schloß Gehrden:
9h30 Ankunft
10h00 Dennis Hannwacker (Christian Schindelhauer) "Graphenfärbung in erwartet konstanter Zeit"
11h00 Frank Nillies (Christian Schindelhauer) "A (fairly) simple Circuit that (usually) Sorts"
12h00 Mittach
14h00 Özkurt Oguzhan (Martin Ziegler) "Abgeschlossenheit von Büchi-Automaten unter Komplement"
15h00 Andre Höing (Bettina Rehberg) "Das AKS-Netzwerk: Sortieren in O(log N)"
16h00 Tobias Bräutigam (Klaus Volbert) "Obere und untere Schranken beim Broadcasting in Funknetzwerken"
 
Donnerstag, dem 3.2.2005 in Schloß Gehrden:
9h00 Senay Kaynar (Valentina Damerow) "Umweg-Faktor ebener geometrischer Wegesysteme"
10h00 Tim Süß (Gereon Frahling) "Aroras PTAS für das euklidische TSP"
11h00 Jürgen Brinkmann (Miroslaw Korzeniowski) "Skip Graphen"
12h00 Mittach/Ende


Inhalt

In diesem Seminar soll anhand einer Reihe ausgewählter Aufsätze und Lehrbuch-Abschnitte die Schönheit von Problemlösungen aus dem Bereich der Theoretischen Informatik demonstriert werden und daß die Beschäftigung mit raffinierten Beweistechniken, eleganten Argumenten und überraschenden Konstruktionen höchst vergnüglich ist.
Inspiriert wird dieses Seminar durch das Buch ,,Perlen der Theoretischen Informatik`` von Uwe Schöning, in dem er eine Sammlung von Ergebnissen vorstellt, die seiner Meinung nach Highlights der Theoretischen Informatik darstellen.
Natürlich wird die Themenauswahl unseres Seminars durch den Geschmack der Themensteller und ihre Arbeitsgebiete geprägt sein.

Um für etwas Abwechslung zu sorgen, sind hier nur Themen aufgelistet, die im letzten oder vorletzten Jahr nicht vergeben wurden:

 

Themen

 

Literatur

Dieses Buch gibt es im Semesterapparat in der Bibliothek.


Martin Ziegler