• Links to
• Staff

  Staff Overview

  Professors

  • Rüdiger Reischuk
  • Till Tantau
  • Maciej Liskiewicz

  Secretary

  • Elisa Merkel-Weißer

  Contact

  • Rooms • Phone • Mail

  Research assistants

  • Max Bannach
  • Katharina Dannenberg
  Zacharias Heinrich
  • Florian Thaeter
  • Benito van der Zander
  • Marcel Wienöbst

  Technical staff

  • Jens Heinrichs
• Winter semester 2020

Institute for Theoretical Computer Science

Summer semester 2003

Lehrveranstaltungen im SS 2003

• Grundstudium:
• Einführung in die Informatik IV
• Proseminar "Algorithmische Geometrie"
• Proseminar "Efficient Algorithms"
• Hauptstudium:
• Pflichtvorlesungen:
• Parallele und Verteilte Systeme
• Wahlpflichtvorlesungen
• Data Mining
• Entwurf und Analyse sicherer Protokolle
• Endliche Automaten
• Seminare:
• Kolmogorov-Komplexität
• Strategisches Handeln im Internet
• Praktikum
• Effizientes Problem lösen und programmieren
• Oberseminar:
• Oberseminar Theoretische Informatik

 
• Einführung in die Informatik IV


Veranstalter:  Reischuk

Übung:  Reischuk, Arpe

Form: Vorlesung und Übung, 4. Sem. Diplom-Studiengang & Bachelor (4V+3Ü)

Termine:   Vorlesung: Mi. 8.00h-10.00h, Raum T1/Transistorium und Fr.  8.00h-10.00h, H1.

         Übungen:   Mo. 14 -16/16-18h, H1/SFS, H2/SFS und Do. 13-14h,  H1/SFS, H2/SFS, H3/SFS, H4/SFS
 
Inhalt:

Grundlagen der Berechenbarkeit:
Maschinenmodelle, Programmiermodelle,  primitiv-rekursive und rekursive Funktionen,
Universelle Maschinen, Churchsche These Entscheidbarkeit, Aufzählbarkeit, Halteproblem,
Rekursionstheorem, Fixpunktsatz, Satz von Rice

Formale Sprachen:
Formale Grammatiken, Normalformen, kontextfreie und kontextsensitive Sprachen,  Comsky Hierarchie, reguläre Sprachen, reguläre Ausdrücke, endliche Automaten, Pumping Lemma, Wortprobleme

Komplexität algorithmischer Probleme:
Zeit- und Platzmasse, Programmierung von TM, Simulation, Reduktion, Komplexitätsabschätzungen, Beschleunigung, untere Schranken, Zeit- und Platzhierarchien, Nichtdeterminismus sequentielle Komplexitätsklassen, NP-Vollständigkeit Erfüllbarkeitsproblem für Boolesche Formeln, Optimierungsprobleme 

Auswahl Lehrbücher

• [Sm94]    C. Smith, A Recursive Introduction to the Theory of Computation, Springer 1994
• [HU94]    J. Hopcroft, J. Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Add.Wesley 1994
• [Ha78]     M. Harrison, Introduction to Formal Language. Theory, Add.Wesley 1978
• [Sa98]      J. Savage, Models of Computation, Add.Wesley 1998
• [Re98]     R. Reischuk, Komplexitätstheorie, Band I: Grundlagen, Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus, Teubner 1998 (Hörerschein zum verbilligten Bezug im Sekretariat erhältlich)
• [GJ79]     M. Garey, D. Johnson, Computers and Intractability, Freeman, 1979

 
• Algorithmische Geometrie

Form: Proseminar  (2)

Termine: Vorlesung: Do. 14.00h-16.00h, H3/SFS
 
Inhalt:
Das Ziel der algorithmischen Geometrie ist es, effiziente Methoden zur Darstellung und Bearbeitung geometrischer Objekte zu entwickeln. Solche Probleme tauchen in vielen praktischen Anwendungen in Computer-Graphics, Robotics, und Engineering-Design auf. Wir werden in den Vorträgen des Proseminars die grundlegenden Probleme der algorithmischen Geometrie herauskristallisieren und effiziente Datenstrukturen und Algorithmen zur effizienten Lösung diskutieren.
Konkrete Problemstellungen werden sein: die Berechnung der konvexen Hülle, Schnittpunkte von großen Streckenmengen, Triangulierung, Voronoi Diagramme und Sichtbarkeitsprobleme. 

Ein interessanter Aspekt ist auch, dass die algorithmische Geometrie sogar in graphikfremden Anwendungen zum Einsatz kommt! So werden z.B. Voronoi-Diagramme in vielen Gebieten von Archäologie bis Zoologie (obwohl nicht unbedingt unter diesem Namen) genutzt. Konkrete Anwendungen zu Voronoidiagrammen findet man im Netz: http://www.Voronoi.com/ 

Literatur:

• F. Preparata, M. Shamos, Introduction to Computational Geometry, Springer 1985 
• H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer 1987 
• M. de Berg, M.V. Kreveld, M.Overmars, O. Schwarzkopf, Computational Geometry, Springer 1997 
• J. O'Rourke, Computational Geometry in C. Cambridge University Press, 1994

 

 

 
• Efficient Algorithms

Veranstalter:  Buntrock

Termine: Vorlesung: Fr. 8.00h-10.00h, H2
 
Inhalt:
  Some people say: our computers will be so fast in next future such that it plays no role how fast the algorithms will be! Fortunately in Lübeck all of the students know that this will never be true! Every machine can bring us with better technology only linear speed-up. Only algorithms can bring better speed-ups. If we speed up our algorithm more than linear, we can grow up our instances more than linear, while its solutions will consume no more time! In this proseminar Efficient Algorithms we will continue the efficient algorithms from Informatik 2. In Detail we are interested in the following topics:

Searching in lists
Searching in trees
Searching in graphs
Searching strings in texts
Sorting lists

Constructing efficient data structures for looking, sorting and storing

AVL trees
Bayer trees
2-3-trees

Finding paths in graphs
Finding minimal spanning trees
Finding matchings in graphs or digraphs

Efficient multiplication of numbers
Efficient multiplication of matrices

We will primarily use the following books for supplementary information on our topics. Please note that in this course we will communicate exclusively in English.

Please feel free to use my e-mail for any questions. It is also possible to arrange a meeting before the run starts. G. Buntrock

Literature:

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman: Data Structures and Algorithms, Addison-Wesley 
• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms, Addison-Wesley 
• Udi Manber: Introduction to Algorithms --- A Creative Approach, Addison-Wesley 
• Sara Baase: Computer Algorithms --- Introduction to Design and Analysis, Addison-Wesley

---


 
• Hauptstudium:

 

 

• Pflichtvorlesungen:

 
• Parallele und Verteilte Systeme

Veranstalter: Zeugmann

Übung: Zeugmann, Jakoby
Form: Pflichtvorlesung und Wahlpflichtübung (4V+2Ü)

Termine:   Vorlesung: Di, 12.00h - 14.00h Raum 3/Haus 21 und Fr, 14.00h - 16.00h, R3/Haus 21.

Übung: Do, 08.00h - 09.30h, Raum R1, R3 und H2 .
Inhalt:

Die Vorlesung wird sich im ersten Teil mit dem Entwurf und der Analyse von synchronen parallelen Algorithmen beschäftigen. Dabei untersuchen wir grundlegende arithmetische Operationen, fundamentale Graphalgorithmen und paralleles Sortieren. 

Wir behandeln die Beschleunigung und Effizienz der vorgestellten Algorithmen. Darüber hinaus führen wir Modelle für paralleles Rechnen ein und untersuchen die grundlegenden parallelen Komplexitätsklassen. 

Im zweiten Teil der Vorlesung studieren wir asynchrone bzw. verteilte Berechnungen. Wir exemplifizieren die grundlegend neuen Fragenstellungen (neu in Bezug auf den synchronen Fall) und stellen mathematische Modelle zur Beschreibung von verteilten Systemen vor. 

Abschliessend studieren wir temporale Logiken für konkurrente Systeme. 

Es wird von Woche zu Woche ein Übungsblatt geben, das dann in der Übung besprochen wird. Die Bearbeitung der Aufgaben ist zum Scheinerwerb obligatorisch. Am Semesterende wird eine Rücksprache über die Aufgaben stattfinden.

Auswahl Lehrbücher
• J. JaJa, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
• N. Lynch, Distributed Algorithms, Morgan Kaufmann 1996
• Z. Manna and A. Pnueli, The Temporal Logic of Reactive and Concurrent Systems, Springer 1992
• W. Reisig, Elements of Distributed Algorithms : Modeling and Analysis with Petri Nets, Springer 1998
 

---

 

• Wahlpflichtvorlesungen:

 

• Data Mining

Veranstalter: Zeugmann

Form: Vertiefende Vorlesung (2V)

Termine: Vorlesung: Do, 14.00h - 16.00h, Raum H1/SFS.


Inhalt:
Die Fähigkeit lernen zu können wurde für Computer bereits als Ziel formuliert, nachdem dem der erste praktische Einsatz eines Rechners gelungen war. Für Alan Turing war die Lernfähigkeit eines Computers die wichtigste Intelligenzleistung. 

In der Vorlesung werden wir die wichtigsten grundlegenden Entwicklungen und Erkenntnisse, die zur Umsetzung dieses anspruchsvollen Zieles in den vergangenen 50 Jahren verfolgt bzw. gewonnen wurden, unter einem einheitlichen Gesichtspunkt behandeln und aktuelle Anwendungen im Data Mining aufzeigen. 

Im ersten Teil der Vorlesung spezifizieren wir zunächst allgemeinste Anforderungen an die Modellierung des intuitiven Begriffes ``Lernen''. Danach stellen wir die wichtigsten Lernmodelle exemplarisch vor. Es folgen vertiefende Untersuchungen, die insbesondere die Frage klären, unter welchen Bedingungen ein angestrebtes Lernziel erreicht werden kann. Abschließend wird das Problem der Wissensentdeckung in großen Datenbanken behandelt (Data Mining). 

Zur Vorlesung wird ein Skript bereitgestellt. 

---

 

• Entwurf und Analyse sicherer Protokolle

Veranstalter:  Jakoby

Form: Vertiefende Vorlesung

Termine: Vorlesung: Mo, 12.00h - 14.00h, Raum H1/SFS.


Inhalt:
Der Entwurf und die Analyse sicherer Protokolle sind zentrale Themen der Kryptographie und beim Umgang mit privaten Daten. Zero-Knowledge Verfahren spielen hierbei eine entscheidende Rolle. Die faszinierende Natur solcher Verfahren liegt in der scheinbaren Unvereinbarkeit ihrer Definition; Zero-Knowledge Protokolle "beweisen" die Korrektheit einer Aussage, ohne dass mehr Wissen als die Gültigkeit übertragen wird. Ein solcher Verhalten wird Beispielsweise bei der Identifikation benötigt. In der Vorlesung werden wir einige Varianten von Zero-Knowledge vorstellen und anhand von Beispielen diskutieren. 

Ein zweiter Schwerpunkt der Vorlesung ist das Private Computation. Ziel einer solchen Berechnung ist die Auswertung einer Funktion auf verteilen und geheimen Daten. Hierbei gilt es, das Ergebnis der Funktion so zu bestimmen, dass die an der Berechnung beteiligten Komponenten keine Informationen ueber die privaten Daten der anderen Komponenten erhalten, die sie nicht aus dem Ergebnis ableiten koennen. 

Literaturhinweise:

• aktuelle Artikel
 

---

 
• Endliche Automaten

Veranstalter: Buntrock

Form: Vertiefende Vorlesung (2V)

Termine: Vorlesung: Fr. 10.30h - 12.00h, Raum H1/SFS.

Inhalt:
In der Grundstudiumsveranstaltung Informatik 4 wird im Rahmen des Themengebietes der Formalen Sprachen der "Endliche Automat" eingeführt. Die Endlichen Automaten sind einerseits ein sehr theoretisches Modell und werden von vielen in nächster Nähe der Logik gesehen, andererseits sind sie sehr anwendungsorientiert und werden z.B. von einigen Ingenieuren als Beschreibungsmodell für Geräte mit einfachen Funktionalitäten gesehen (Selbstbedienungsautomaten, Fahrstühle, Ladenkassen, ...) In dieser Vorlesung Endliche Automaten wird dieses Modell genauer untersucht. So werden Robustheitseigenschaften des Modells betrachtet und einerseits die bekannten Charakterisierungen kurz wiederholt und andererseits weitere Charakterisierungen vorgestellt. Im Anschluss werden Erweiterungen des Modells betrachtet und mit anderen Begriffen aus anderen Theorien (Formale Sprachen, Logische Schaltkreise, Komplexitätstheorie, Logik) charakterisiert. So erweitern wir das Modell durch Hinzufügen weiterer Köpfe oder Speicherstrukturen. Aber auch das Berechnungsmodell wird verändert: hier stellen wir neben den bekannten deterministischen und nichtdeterministischen Berechnungsmodellen auch probabilistische vor.

Literatur:

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979 
• Wilfried Brauer, Automatentheorie, Teubner,1984 
• Howard Straubing, Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser, Boston, 1994 
• R. G. Bukharayev, Theorie der Stochastischen Automaten, Teubner, 1995
• Volker Claus, Stochastische Automaten, Teubner, 1971
 

---

 
• Seminare:
 
 
• Kolmogorov-Komplexität

Veranstalter:  Reischuk, Manthey, Arpe

Form: Hauptseminar (2S)

Termine: Di, 14.00h - 16.00h, Raum H3/SFS

Inhalt:
Die Kolmogorov-Komplexität eines Strings ist die Länge der kürzesten Beschreibung dieses Strings. Beispielsweise kann der String, der aus 1000 Nullen besteht, sehr einfach beschrieben werden (z. B. mit diesen sieben Worten), hat also eine geringe Kolmogorov-Komplexität. Ebenso kann die Zahl Pi einfach beschrieben werden. Andererseits haben zufällige Strings eine hohe Kolmogorov-Komplexität. Es stellt sich heraus, dass die meisten Strings nicht komprimierbar sind, ihre kürzeste Beschreibung also schon durch sie selbst gegeben ist. 

 In den letzten Jahren wurde mit Hilfe der Kolmogorov-Komplexität das Average-Case-Verhalten von Algorithmen untersucht. Auch viele untere Schranken für die Komplexität von Problemen können einfach mit Hilfe der Kolmogorov-Komplexität bewiesen werden. 

 Das vielleicht bekannteste Resultat ist, dass alle Probleme, die mit randomisierten  Polynomialzeit-Algorithmen mit beschränktem Fehler gelöst werden können (BPP), in der zweiten Stufe der Polynomialzeithierarchie liegen. Themen dieses Seminars sind Grundlagen der Kolmogorov-Komplexität und ihre Anwendungen. 
 

---


 
• Strategisches Verhalten im Internet

Veranstalter:  Reischuk, Bläser

Form:Hauptseminar (2S)

Termine: Do, 16.00h - 18.00h, Raum H3/SFS.

Inhalt:

Das Internet ist eine in seiner Komplexität bis dato unübertroffene Platform zur Verarbeitung von Daten. Im Gegensatz zu klassischen (von Neumann) Rechnern wird es von einer Vielzahl von Personen und Institutionen ausgebaut, betrieben und genutzt, die angetrieben von eigenen, meist wirtschaftlichen Interessen miteinander agieren, Koalitionen bilden, aber auch konkurrieren. Dieser ``sozio-ökonomische'' Aspekt wird in der Zukunft einen erheblichen Einfluß auf den Entwurf von Protokollen haben, da Rechner im Internet verschiedenen Personen und Institutionen gehören und meist so eingesetzt werden, daß sie ihren Besitzern einen möglichst großen Nutzen bringen. Daher scheint es naiv zu erwarten, daß sich jeder Rechner an die vorgegebenen Protokolle hält, sondern diese auch bricht, wenn es von Nutzen für den Besitzer erscheint. Ebenso werden viele zur Zeit kostenlosen Serviceleistungen, wie z.B. das Durchrouten von Paketen, mit zunehmend größeren Datenströmen nicht mehr kostenlos bleiben, da die tatsächlich entstehenden Kosten nicht mehr marginal sind. 

Obige Tatsachen stellen eine interessante Herausforderung an die Informatik dar, das Internet unter sozio-ökonomsichen Gesichtspunkten zu modellieren und zu verstehen und hat sich innerhalb der letzten Jahre zu einer lebhaften Teildisziplin der Informatik entwickelt.  Ein Beispiel ist das sogenannte Selfish Routing Problem: hier versenden Nutzer Daten in einem Netzwerk und tun dies so, daß ihre eigenen Pakete möglichst schnell ans Ziel gelangen. Die Frage ist hier, um wie viel solch ein egoistisches Vorgehen schlechter ist als ein global optimales Protokoll, daß den Gesamtnutzen optimiert. Eine weiteres Beispiel ist das sogenannte Multcast Pricing.

Hier soll eine Transmission von einem Provider an eine Reihe von Nutzern gesandt werden. Wir nehmen an, daß die Knoten des   Netzwerks Multicast-fähig sind, d.h. eine eingehende Transmission kann von einem Knoten dupliziert und an mehrere seiner Nachbarn versandt werden. Dadurch werden Links von mehreren Nutzern verwendet. Wenn für die Links nun Nutzungsgebühren verlangt werden, so sind Mechanismen gesucht, die die anfallenden Kosten fair auf die Nutzer verteilen. 

In dem Seminar sollen aktuelle Arbeiten zu den oben genannten sowie weiteren Problemem bearbeitet und vorgestellt werden.     Interessenten können sich ab sofort bei M. Bläser melden und ein Thema fuer einen Vortrag wählen. Letztmöglicher Termin um Erhalt eines Vortragsthemas ist die erste Veranstaltung im Semester, also Do., der 3.4.03, 10 Uhr. 




---


 
• Praktikum
 
• Effizientes Problemlösen und Programmieren 

Veranstalter: Liskiewicz, Manthey

Form: Praktikum (P3)

Termin: Do. 18.00h - 21.00h, Raum H3 + Do. 16.00 - 18.00h, Raum H4(Rechnerpool)/SFS

Inhalt: 
Gegenstand des Praktikums ist es, für konkrete anspruchsvolle Probleme algorithmische Lösungen zu entwickeln und effizient zu implementieren. Dieser Prozess soll in möglichst kurzer Zeit durchgeführt werden. Den Teilnehmern wird die Möglichkeit gegeben, entsprechende Fähigkeiten zu trainieren. Diverse Implementierungen von Algorithmen für grundlegende kombinatorische Probleme wie z.B. Wegeprobleme in Graphen, Pattern Matching oder geometrische Probleme wie konvexe Hüllen bilden die Basisbausteine. Die Teilnehmer üben anschliessend an konkreten Aufgabenstellungen, siehe dazu folgendes Beispiel

Literatur:

•  T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms, The MIT Press, 1990. 
•   A. Aho, J. Hopcroft, J. Ullman, Design and Analysis of Computer Algorithms, Add. Wesley 1978. 


Voraussetzungen:
gute Kenntnisse über effiziente Algorithmen und Datenstrukturen, Programmiererfahrung in C, C++ Pascal oder JAVA.

---

• Oberseminar Theoretische Informatik

Veranstalter: Reischuk, Zeugmann

Form: Oberseminar (3S)

Termin: Di, 16h - 19h, H3/SFS

Inhalt:

Die Mitglieder und Studenten der Arbeitsgruppe Theoretische Informatik
tragen über aktuelle Forschungsresultate vor.