• Links zu
• Mitarbeitern

  Zum Überblick Mitarbeiter

  Professoren

  • Rüdiger Reischuk
  • Till Tantau
  • Maciej Liskiewicz

  Sekretariat

  • Elisa Merkel-Weißer

  Kontakt

  • Räume • Telefon • E-Mail

  Wissenschaftliche Mitarbeiter

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

  Technische Mitarbeiter

  • Jens Heinrichs
• Wintersemester 2020

Institut für Theoretische Informatik

Sommersemester 2002

Lehrveranstaltungen im SS 2002

• Grundstudium:
• Einführung in die Informatik II
• Einführung in die Informatik IV
• Proseminar "Algorithmen und Programmierung"
• Proseminar "Rewriting"
• Hauptstudium:
• Pflichtvorlesungen:
• Parallele und Verteilte Systeme
• Wahlpflichtvorlesungen
• Data Mining
• Interaktive Protokolle: Arthur-Merlin-Games und andere
• Logik
• Seminare:
• Komplexität und Algorithmen
• Kryptologie
• Praktika
• Effizientes Problem lösen und programmieren
• Oberseminar:
• Oberseminar Theoretische Informatik

 

 
 
• Einführung in die Informatik II

 Algorithmenentwurf, Datenstrukturen, Programmierung 
Veranstalter:

  Übung:  Reischuk, Buntrock, Feldtmann, Kempa, Kim

Vorlesung und Übung (4V+3Ü)
Termine:
Vorlesung: Di, 8.00h-10.00h Raum H1 und
                   Fr,  10.00h-12.00h, H1.
Übungen:   Mo 14 -16/16-18h H2 / R1 und Mi 10-11h, T1, R3, H4a, S3b
 
     Themen: 
 
     Elementare algorithmische Probleme: 
     Suchen, Mischen, Sortieren, 
     Suche in Graphen: DFS, BFS, spannende Bäume 
     Topologisches Sortieren, Transitive Hülle, Zusammenhang 
     Wege- und Flußprobleme in Netzwerken 
     String Matching 
     Geometrische Algorithmen 

     Algorithmenentwurf und Analyse: 
     Greedy-Strategien, Divide-and-Conquer 
     Dynamisches Programmieren, Sweeping Line 
     Randomisierung 

     Effiziente Datenstrukturen: 
     Balanzierte Bäume, Heaps, Hashing 

     Methodiken in der Programmierung: 
     Prozedural, objektorientiert 
 

 
Empfohlene Literatur 

     Begleitende Lehrbücher 

•      T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, Spektrum 2002 
•      S. Skiena, The Algorithmic Design Manual, Springer 1998 
•      A. Aho, J. Hopcroft, J. Ullman, Design and Analysis of Computer Algorithms, Addison-Wesley 1978 
•      T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms, MIT-McGraw Hill 1990 
•      N. Wirth, Algorithmen und Datenstrukturen - mit Modula 2, Teubner 1986 
•      D. Ratz, J. Schefler, D. Seese, Grundkurs Programmieren in Java, Ban I, Der Einstieg in Programmierung und Objektorientierung, Hauser 2001 
•      M. Campione, K. Walrath, A. Hunt, The Java Tutorial, Addison-Wesley 2001 

•      J. Chabert et al., A History of Algorithms, Springer 1994 
•      D. Knuth, The Art of Computer Programming, Band 3: Sorting and Searching, Addison-Wesley 1998 
•      R. Sedgewick, Algorithmen, Addison-Wesley 1992 
•      G. Brassard, P. Bratley, Algorithmics, Prentice Hall 1988, deutsch: Algorithmik, Prentice Hall 1993 
•      S. Baase, A. Van Gelder, Computer Algorithms, Addison-Wesley 2000 
•      J. Nievergelt, K. Hinrichs, Algorithms and Data Structures, Prentice Hall 1993 
•      V. Heun, Grundlegende Algorithmen, Vieweg 2000 
•      U. Schöning, Algorithmik, Spektrum 2001 
•      N. Wirth, Programmieren in Modula 2, Teubner 1986 
•      C. Wolff, Einführung in Java, Teubner 1999 
•      A. Solymosi, U. Grude, Grundkurs Algorithmen und Datenstrukturen: Eine Einführung in die praktische Informatik mit Java, Vieweg 2000 
•      R. Dumke, Software Engineering, Vieweg 2001 

 

  Skripte aus der Vorlesung (ps-files)
  Zugriff nur über Uni-Account
 

  Übung:  Reischuk, Bläser

Vorlesung und Übung (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 und Do 13-14h, 17-18h
 
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

 
• Algorithmen und Programmierung
Veranstalter:
            Liskiewicz, Siebert
Form:
Proseminar  (2)
Termine:
Vorlesung: Do., 14.00h-16.00h H3/SFS
 
Inhalt:
Ziel dieses Proseminars ist eine integrierte Behandlung von Algorithmen und effizientem Programmieren. 
Ausgangspunkt ist ein konkretes Problem. Im Rahmen des Proseminars soll dan anhand bekannter Algorithmen ein Lösung für dieses Problem erarbeitet und programmiert werden. Im Vortrag sollen dann das Problem, der verwendete Algorithmus und das konrete Programm zur Lösung des Problems vorgestellt werden.

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.

 
 
 
• Rewriting
Veranstalter:
            Buntrock
Form:
Proseminar Bachelor-Studiengang (2)
Termine:
Vorlesung: Fr., 8.00h-10.00h H2
 
Inhalt:
Every computing consists in three parts: mapping the reality into symbols, substituting step by step some symbols by some others, interpretation of the result. In general we denote the second step `rewriting'. In this seminar course we are going to present several different rewriting systems: string rewriting, term rewriting, grammars and L-systems and rewriting perfomed by biological processes. In detail we will discuss the following topics: 

     1. Thue Systems 
     2. Confluent Rewriting 
     3. Church-Rosser-Systems 
     4. Chomsky grammars 
     5. Finite Automata 
     6. Term Rewriting 
     7. Propositional Calculus 
     8. Lindenmeyer-Systems 
     9. Splicing Systems 
 

     For every topic we will have up to two talks.

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

• 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. 

 

• Interaktive Protokolle: Arthur-Merlin-Spiele und andere
Veranstalter:
 Jakoby
Form:
Vertiefende Vorlesung
Termine:
Vorlesung: Mo, 12.00h - 14.00h, Raum H1/SFS.
Inhalt:
Die Idee eines Arthur-Merlin Spiels kann durch folgende Situation am Hofe dieses mystischen Königs beschrieben werden: 

König Arthur (A), ein gerechter König, regiert England mit Hilfe seines allwissenden Ratgebers Merlin (M). Oft treffen die beiden mystischen Gestalten aufeinander und diskutieren über vielerlei anstehende Fragen. Hierbei versucht Merlin Arthur immer wieder von seiner Allwissenheit mit Hilfe von Frage- und Antwortspielen zu überzeugen. 

Diese Spiele haben den folgenden Ablauf: Arthur stellt mit Hilfe von randomisierten Bits sukzessive verschiedene Fragen, die von Merlin auf die bestmögliche Art und Weise beantwortet werden. Merlin hat bei einem solchen Spiel eine Gewinnstrategie, wenn es ihm gelingt Arthur mit einer Wahrscheinlichkeit von 2/3 zu überzeugen. 

Basierend auf dieser Idee läßt sich nun eine neue Form probabilistischer Maschinen beschreiben, bei der es möglich ist, die Fehlerwahrscheinlichkeit beliebig zu verkleinern. In der Vorlesung Arthur-Merlin Games und andere Interaktive Protokolle werden wir unter anderem untersuchen inwieweit die Anzahl der Interaktionen zwischen Arthur und Merlin die Berechnungskapazität derartiger Maschinen beeinflußt. 

Weitere Modelle, die in der Vorlesung vorgestellt werden sind: Interaktive Beweissysteme, Zero-Knowledge Beweiser und das Modell von Games-Against-Nature. 

Skript

• Logik
Veranstalter:
  Buntrock
Form:
Vertiefende Vorlesung (2V)
Termine:
Vorlesung:Mi, 17.00h - 19.00h, Raum H2/SFS.
Inhalt:
Aus der Philosophie über die Mathematik ist die Logik in die Informatik gekommen. In der Logik lernen wir, wie weit wir Prozesse der Realität durch Symbolmanipulationen abbilden können. Dies drücken die Vollständigkeitssätze der Aussagenlogik, der Prädikatenlogik und der Temporalen Ausagenlogik positiv aus - der Satz von Gödel über die Unvollständigkeit der Arithmetik zeigt hier eine wichtige Grenze. Dies führt schließlich zu den Grenzen der Berechenbarkeit. Auch komplexitätstheoretische Grenzen lassen sich in der Logik modellieren. Wir konzentrieren uns auf die folgenden Themen:
 

     1. Aussagenlogik 
     2. Prädikatenlogik 
     3. Berechenbarkeit 
     4. Modallogik/Temporale Logik

Literatur

• M. Ben-Ari: Mathematical Logic for Computer Science. Prentice Hall. 
• Egon Börger: Berechenbarkeit, Komplexität, Logik. Vieweg. 
• Heinz-Dieter Ebinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik, BI Wissenschaftsverlag Mannheim. 
• Uwe Schöning: Logik für Informatiker. Spektrum Verlag. 
• Joseph R. Shoenfield: Mathematical Logic. Addison-Wesley. 
• Dirk Siefkes: Formalisieren und Beweisen --- Logik für Informatiker. Vieweg
 

---

 
• Seminare:

 
• Komplexität und Algorithmen
Veranstalter:
Liskiewicz
Form:
Hauptseminar (2S)
Termine:
Mo, 16.00h - 18.00h, Raum H3/SFS
Inhalt:
In diesem Seminar diskutieren wir die aktuellen Forschungsergebnisse der algorithmischen Komplexitätstheorie. Wir werden unter anderem die folgenden Themen behandeln: 
                   Effiziente Algorithmen für Quantenrechner, 
         Interaktive Protokolle und der Satz von Shamir, 
        Approximationsalgorithmen für NP-vollständige Probleme, 
        "Zählende Komplexitätsklassen"

Literatur:

• Originalarbeiten nach Absprache und Themenstaltung

• Kryptologie

 
Veranstalter:
Zeugmann, Bläser
Form:
Hauptseminar (2S)
Termine:
Do, 16.00h - 18.00h, Raum H3/SFS.
Inhalt:
Kryptologie ist die Wissenschaft von Geheimschriften und ihrer unberufenen Entzifferung, die bis vor wenigen Jahren noch überwiegend im Verborgenem betrieben wurde. Mit der Entwicklung moderner globaler Netze und den damit verbundenen Sicherheitsbedürfnissen hat die Kryptologie in den letzten Jahren enorm an Bedeutung gewonnen. Die potentielle kommerzielle Verwertbarkeit kryptographischer Verfahren stimulierte einen gewaltigen Aufschwung öffentlicher kryptographischer Forschungen, die zu einer Fülle hoch interessanter und zum Teil mehr als verblüffenden Resultaten führte. 

Inhalt des Seminars sind aktuelle Arbeiten ueber moderne Kryptosysteme. Im Vordergrund stehen dabei vor allem kryptographische Protokolle, die weit ueber das verschluesselte Versenden von Nachrichten hinausgehen.

Interessenten koennen ab sofort die Themenliste einsehen und ein Vortragsthema erhalten.
 

• Praktika

 
• Effizientes Problemlösen und Programmieren 

Veranstalter:
Liskiewicz, Siebert
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.

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.