• 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

Winter Semester 2000/2001

Lehrveranstaltungen im WS 00/01

• Grundstudium:
• Effiziente Algorithmen
• Boolsche Funktionen und Schaltkreise
• Hauptstudium:
• Pflichtvorlesungen:
• Algorithmen, Komplexitätstheorie und Formale Sprachen 
• Programmiersprachen
• Wahlpflichtvorlesungen:
• Komplexe Datenstrukturen
• Logik und Rekursionstheorie
• Kryptologie
• Seminar:
• Intelligente Sprach- und Textbearbeitung
• Sicherheit
• Algorithmen für Probleme der Molekularbiologie
• Praktika
• Effizientes Problem lösen und programmieren
• Parallelverarbeitung
• Oberseminar:
• Oberseminar Theoretische Informatik
• Grundstudium:
• Effiziente Algorithmen
Veranstalter:
Zeugmann, Jakoby
Form:
Proseminar (2S)
Termine:
Mi, 13.00h - 15.00h, Raum H3/SFS.
Inhalt:
Effiziente Algorithmen bilden ein zentrales Thema der Informatik. Mit dem Leistungszuwachs der Computer (etwa alle 18 Monate verdoppelt sich zur Zeit deren Leistung) werden die Anwendungsbereiche und Datenberge immer größer, so daß effiziente Algorithmen eine immer wichtigere Rolle spielen. So bemerken wir, daß die Verdopplung der Leistung nur für linear zeitbeschränkte Algorithmen eine Verdopplung der Anwendungsbereiche zuläßt. Linear zeitbeschränkte Algorithmen sind jedoch meist nicht zu erwarten. 
Wir werden Themen aus den folgenden Bereichen anbieten: 
• Pattern Matching Verfahren 
• Algorithmen für Graphprobleme 
• Algorithmen für geometrische Problemstellungen 
• Sortierverfahren 
• Primzahltests 
• Schnelle Multiplikation ganzer Zahlen 
• Schnelle Matrizenmultiplikation 
Die Vorbesprechung und die Vergabe der Vorträge findet in der ersten Veranstaltung im WS 00/01 statt. Interessierte Studierende können sich bereits vor Beginn des Semesters bei den Veranstaltern informieren und in die geplanten Vortragsthemen Einblick nehmen. 
Literatur: 
Ausgewählte Kapitel zu den Themen: Grundlagen von Algorithmen und Datenstrukturen, Sortieren, Suchen, Bäume, Graphen aus 
• Aho, Hopcroft, Ullman: The Design And Analysis of Computer Algorithms, Addison-Wesley, 1974 
• Sara Baase: Computer Algorithms, Addison-Wesley, 1993 
• Motwani, Raghavan: Randomized Algorithms, CUP, 1995 
• R. Sedgewick: Algorithmen, Addison-Wesley, 1992 
 

• Boolsche Funktionen und Schaltkreise
Veranstalter:
Zeugmann, Bläser
Form:
Proseminar (2S)
Termin:
Mi, 15.00h-17.00h, Raum R1/21.
Inhalt:
Schaltkreise sind die elementaren Bausteine der heutigen digitalen Rechner. Aus komplexitätstheoretischer Sicht bilden Sie ein wichtiges Modell, um die parallele Komplexität von Berechnungsproblemen zu untersuchen. Ein Boolescher Schaltkreis besteht aus Gattern (z.B. für die logischen Operationen Und, Oder und Negation), die azyklisch miteinander verbunden sind. Ein Boolescher Schaltkreis berechnet eine Boolesche Funktion, also eine Funktion, die 0-1-Vektoren auf 0-1-Vektoren abbildet. Das Proseminar behandelt exemplarisch grundlegende Aspekte von Booleschen Funktionen und Schaltkreisen. 
 
• Hauptstudium:
 
• Pflichtvorlesungen:
 
• Algorithmen, Komplexitätstheorie und Formale Sprachen
Veranstalter:
Vorlesung: Reischuk, Buntrock, Schindelhauer
Form:
Pflichtvorlesung im Bereich Informatik III (4V)
Wahlpflichtübung (2Ü)
Termine:
Vorlesung: Mi, 8.00h-10.00h und Fr, 8.00h-10.00h, Raum R3/21.
Übungen:
            Gruppe 1: Mo, 16.00h-18.00h, Raum H1/SFS
            Gruppe 2: Mo, 16.00h-18.00h, Raum H2/SFS
            Gruppe 3: Mo, 16.00h-18.00h, Raum H3/SFS
 
Inhalt:
Der Besuch wird im 5. Semester empfohlen. Die Vorlesung setzt das Verständnis des Stoffes der Grundstudiumvorlesungen Einführung in die Informatik I - IV voraus.

Eingehend behandelt wird der Entwurf effizienter Algorithmen, die Komplexität algorithmischer Probleme sowie Formale Sprachen als Grundlage für die Entwicklung und Übersetzung von Programmiersprachen.
Die Vorlesung wird ergänzt durch Übungen, in denen die Teilnehmer Übungsaufgaben zur Anwendung und Vertiefung des Vorlesungsstoffes bearbeiten.
Literatur:
• Knuth, The Art of Computer Programming, Vol. 1-3, Add. Wesley
• Aho, Hopcroft, Ullman, Design and Analysis of Computer Algorithms, Add. Wesley 1978
• Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press 1990
• Mehlhorn, Daten Structuren und Algorithmen, Teubner 1986
• Reischuk, Komplexitätstheorie Band 1: Grundlagen, Teubner 1998
• Savage, Models of Computation, Add. Wesley 1998
• Hopcroft, Ullman, Introduction to Automata Theory, Languages and Computation, Add. Wesley 1979
• Harrison, Introduction to Formal Language Theory, Add. Wesley 1978

 

 

• Programmiersprachen
Veranstalter:
Zeugmann
Form:
Pflichtvorlesung im Bereich Informatik I  (2V)
Termine:
Vorlesung: Fr, 14.00h - 16.00h, Raum R3/21.
Inhalt:
Die Vorlesung behandelt allgemeine Grundlagen von Programmiersprachen und deren Verknüpfung mit realen Computern. Dabei wird besonderer Wert auf die fundamentalen Konzepte des Entwurfs von Programmiersprachen gelegt. 

Wir beginnen mit einer Retrospektive der Entwicklung weit verbreiteter bzw. in ihrem Entwurf bedeutender Programmiersprachen, wobei besonderer Wert auf die unterschiedlichen Entwurfsansätze und ihrer Vor- bzw. Nachteile gelegt wird. 

Danach behandeln wir die grundlegenden Konzepte zur Beschreibung der Syntax und Semantik von Programmiersprachen. 

Im Hauptteil der Vorlesung studieren wir detaillierter die Entwurfsprinzipien imperativer, funktionaler, logischer und objektorientierter Programmiersprachen. 

Zur Vorlesung wird ein Skript erstellt. 
 

Literatur:

• R. W. Sebesta, Concepts of Programming Languages, Bejamin/Cummings Publ., 1992 
• J. M. Mitchel, Foundations of Programming Languages, MIT Press 1996 

 

---

• Wahlpflichtvorlesungen:
 
• Komplexe Datenstrukturen
Veranstalter:
Jakoby
Form:
Vertiefende Vorlesung  im Bereich Informatik III (2V)
Termine:
Mo. 14.00h-16.00h, Raum H1/SFS.
Inhalt:

Der Entwurf und die Analyse komplexer Datenstrukturen sowie ihr Einsatz in effizienten Algorithmen steht im Mittelpunkt dieser Veranstaltung. Für viele einfache Problemstellungen, wie z.B. in der Datenverwaltung zeigt es sich, dass eine direkte, einfache Umsetzung in einem Programm weniger effizient ist, als die Verwendung ausgefeilter Methoden. So kann bei der Implementierung eines Wörterbuches die Verwendung von perfekten Hashfunktionen zu einem schnellen Datenzugriff auf der einen Seite und einer Minimierung des Speicherbedarfs auf der anderen Seite führen, wohingegen eine naheliegende Implementation entweder sehr speicheraufwendig ist oder nur einen zeitaufwendigen Zugriff auf gespeicherte Daten zulässt. Diese Veranstaltung ist richtet sich an Studenten des Hauptstudiums, die sich neue Programmier-Techniken aneignen wollen die über das Grundstudium hinausgehen. Spezielle Kenntnisse aus der Mathematik oder der Theoretischen Informatik werden nicht vorausgesetzt.
Skript:
Das Skript

Literatur:

• Knuth, The Art of Computer Programming, Vol. 1-3, Add. Wesley
• Aho, Hopcroft, Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974
• Purdom, Brown, The Analysis of Algorithms, Holt, Rinehart, Winston, 1984
• Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press, 1990
• Sedgewick, Algorithms, Addison-Wesley, 1991
• Kozen, The Design and Analyses of Algorithms, Springer, 1991

 
 

• Logik und Rekurionstheorie

Veranstalter:
Buntrock
Form:
Vertiefende Vorlesung im Bereich Informatik III (2V)
Termine:
Vorlesung: Mi, 14.00h - 16.00h, Raum H1/SFS.
Inhalt:
Diese Vorlesung dient zur Vertiefung der theoretischen Grundlagen. Der Inhalt kann als Prüfungsstoff im theoretischen Teil der Diplomprüfung eingebracht werden. 
 
Die Logik ist eine Disziplin, die ursprünglich von den Philosophen, dann mehr von den Mathematikern nd heute am meisten von den Informatikern betrieben wird. 
Nach einem kurzen einführenden Kapitel mit einer historischen Übersicht und verschiedenen Beispielen eginnen wir mit einer überblicksartigen Wiederholung der Aussagenlogik. Im ersten zentralen Teil der orlesung wenden wir uns der Prädikatenlogik zu. Hier lernen wir den Sequenzenkalkül aus dem Buch von Ebbinghaus, Flum und Thomas kennen. Einen Höhepunkt wird sicher der wichtige Satz über die unvollständigkeit der Arithmetik von Gödel bieten. Dieser Satz hat auch erhebliche erkenntnistheoretische Bedeutung und signalisiert gewisse Grenzen für eine künstliche Intelligenz.
Hieran anknüpfend werden wir die Bedeutung des Gödelschen Satzes für die Informatik untersuchen und die rekursionstheoretischen Grundlagen studieren. Damit ist ein für sich selbst interessanter Einblick in die eleganten Themen der Rekursionstheorie verbunden, dies ist der zweite zentrale Gegenstand der Vorlesung. 

Ausgehend vom Sequenzenkalkül werden wir Ausflüge in die Themen "automatisches Beweisen" und "Ableitungskalküle für nicht-klassische Logiken" unternehmen. Diese Themen haben auch erhebliche Relevanz für die Logikprogrammierung. Hierzu liest demnächst Herr Zeugmann eine vertiefende orlesung, die mit ihren praktischen Komponenten zu dieser Vorlesung eine hervorragende Ergänzung darstellen wird.

Literaturhinweise:

• Heinz-Dieter Ebbinghaus/Jörg Flum/Wolfgang Thomas: Einführung in die Mathematische Logik, 3. Auflage, BI Wissenschaftsverlag, 1992. 
• Piergiorgio Odifreddi: Classical Recursion Theory. Studies in Logic and the Foundations of Mathematics. North Holland, 1989. 
• Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw Hill, 1967. Erneut aufgelegt bei MIT Press, Cambridge 1987. 
• Uwe Schöning: Logik für Informatiker. 4. Auflage, Spektrum Akademischer Verlag, 1995 
•  Raymond~M. Smullyan: Gödel's Incompleteness Theorems. Oxford Logic Guides. Oxford University Press, New York, 1992. 
• Raymond~M. Smullyan: Diagonalization and Self-Reference. Oxford Logic Guides. Oxford University Press, New York, 1994. 
 

• Kryptologie
Veranstalter:
Zeugmann
Form:
Vertiefende Vorlesung im Bereich Informatik III (2V)
Termine:
Vorlesung: Do, 14.00h - 16.00h, Raum R1/21.
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. 

Die Vorlesung wird zunächst einen Einblick in die klassischen Zwei-Weg Kryptosysteme vermitteln und dabei die Grundlagen der Kryptographie und Kryptanalyse legen. 

Anschliessend wenden wir uns kurz der Theorie fehlertoleranter effizienter Kodes zu, ohne die eine brauchbare Übertragung digitaler Daten nicht realisierbar ist. 

Im Hauptteil der Vorlesung werden moderne Kryptosysteme mit öffentlichen Schlüsseln dargestellt, Verfahren für digitale Unterschriften behandelt und weitere krytographische Anwendungen diskutiert. Dabei gehen wir insbesondere auf die diesen Verfahren zugrunde liegenden Ergebnisse der Komplexitätstheorie, der Kombinatorik und der Theorie der Pseudorandomisierung ein. 

Zur Vorlesung wird ein Skript erstellt. 

Literatur:

• S. Roman, Introduction to Coding and Information Theory, Springer 1996
• F. Bauer, Kryptologie, Methoden und Maximen, Springer 1991
• A. Salomaa, Public-Key Cryptography, Springer 1990 
• O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudorandomness, Springer 1999 
 

 

 

---

• Seminare:
• Intelligente Sprach- und Textbearbeitung
Veranstalter:
Buntrock,
Form:
Hauptseminar (S)
Termin:
Vorlesung: Di, 14.00h-16.00h, Raum H3/SFS.
Inhalt:
Die Generierung von Texten entwickelt sich von der reinen Layoutgestaltung hin zur intelligenten Speicherung von Wissen.  Hierbei steht die Absicht im Vordergrund, die so gespeicherten Dokumente mit verschiedensten Werkzeugen  weiter zu verarbeiten.  Unter diesen Werkzeugen finden wir intelligente Information-Retrieval-Systeme und damit im Zusammenhang stehend auch Tools zur aktiven Entscheidungshilfe (z.B. im medizinischen Bereich) in Produktions- oder Behandlungsprozessen.
So kann man darauf aus sein, die Informationen so abzuspeichern, daß wir sie in speziell genormten Fachsprachen (z.B. im medizinischen Bereich) ausgeben können. Eine konkrete Anwendung wäre hier, aus einer kundenspezifischen Zusammenstellung eines Produktes (z.B. Kfz) die Erstellung einer passenden Betriebsanleitung zu automatisieren.

Die Themenstellung des Seminars umfaßt

Erkennen verschiedener Begriffe trotz unterschiedlicher Wortbildungen  und -beugungen (Morphologie).
Vorstellung von Begriffsystemen vornehmlich aus der Medizin (etwa zur Modellierung der Anatomie)
Techniken zur Speicherung von "Wissen".  Hier sollen Hypertexttechniken und speziell grammatikbasierte Systeme (XML und SGML) vorgestellt werden.

Auf unserer Web-Seite gibt es detailierte Informationen zu den einzelnen Problemkreisen und Vortragsthemen.
Interessenten können auch gerne schon vorher ihr Interesse an einem Vortrag bei dem Veranstalter bekunden.

Die Einstiegsseite:
http://www.medinf.mu-luebeck.de/SeminarWS9900.html

 

 
• Sicherheit
Veranstalter:
   Reischuk,Liskiewicz
Form:
Hauptseminar (2S)
Termin:
Do, 12.00h-14.00h, Raum H3/SFS


Anmeldung und Themenvergabe bei Herrn Liskiewicz
1. Sitzung: 19.10.00, 12 Uhr

Inhalt:
Es werden folgende Themen behandelt: 

Rechnersicherheit 
Gefährliche Software: Viren, 
Trojanische Pferde,Würmer 

Systemsicherheit - Protokolle
Secure Email: Key-Management, PGP, 
Finanzanwendungen: Smart Cards, Electronic Cash 
Watermarking, Fingerprinting 

Netzsicherheit
Firewalls 
Internet-Privacy 

Als Grundlage dient die folgende Literatur, sowie
weitere aktuelle Publikationen: 

• S. Fischer, A. Steinacker, R. Bertram, R.

Steinmetz, Open Security, Springer 1998
• B. Preneel, V. Rijmen (Eds.), State of the Art in

Applied  Cryptology, LNCS 1528, Springer
1997
• A. Menezes, P. Oorschot, S. Vanstone,

Handbook of Applied Cryptography, CRC
Press 1997
• Abrams, Jajodia, Podel, Information Security

(Eds), IEEE CS 1995
• S. Shaffer, A. Simon, Network Security, AP

Professional, 1994
• R. Farrow, Unix System Security, Addison

Wesley 1991
• W. Cheswick, S. Bellowin, Firewalls and

 Internet Security, Adison Wesley-ATT 1994 
• J. Dittman, Digitale Wasserzeichen, Springer 2000 
• P. Denning (Ed.) Computers under Attack,

Addision Wesley 1990




 
• Algorithmen für Probleme der Molekularbiologie
Veranstalter:
   Reischuk, Bläser
Form:
Hauptseminar (2S)
Termin:
Fr, 14.00h-16.00h, Raum H1/SFS.
Inhalt:
Ein grosser Teil der Funktionalität von DNA und Proteinen ist einzig durch die Abfolge der Basen in den Molekülen festgelegt. Aus dreidimensionalen Molekülen werden so eindimensionale lineare Ketten. Es stellt sich also das Problem der Analyse und Verarbeitung von Zeichenketten (z.B. über dem Alphabet G, A, T, C), einem klassischen Gebiet der Informatik. 

Viele der mittlerweile sehr komplexen Aufgabenstellungen in der Molekularbiologie, die ohne Rechnereinsatz nicht mehr zu lösen sind, lassen sich daher sehr gut abstrakt modellieren. Eine effiziente Lösung dieser Probleme verlangt in vielen Fällen anspruchsvolle algorithmische und komplexitätstheoretische Methoden. 

In diesem Seminar werden exemplarisch einige wichtige algorithmische Problem in der Molekularbiologie behandelt und Algorithmen zur Ihrer Lösung oder Approximation einer Lösung erarbeitet. 

Mögliche Themen sind u.a.: Pattern Matching, Sequence Alignment, DNA fragment assembly, physikalische Kartierung, phylogenetische Bäume, DNA Computing. 

---

• Praktika:

 
 
• Effizientes Problem lösen und programmieren
Veranstalter:
Reischuk, Liskiewicz
Form:
Praktikum (P3)
Termin:
Mo, 17.00h - 20.00h, Raum H4(Rechnerpool)/SFS.
Anmeldung: bis 1.10.2000
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 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++ oder PASCAL.

 
 
• Parallelverarbeitung
Veranstalter:
Reischuk, Liskiewicz, Schindelhauer
Form:
Praktikum (P3)
Termin:
Mi, 15.00h - 18.00h, Raum H3/SFS.
Inhalt:

Auf dem Lübecker Hochleistungs-Parallelrechner sollen praktische Aspekte der Parallverarbeitung mit Cache-cohärentem Shared Memory eingehender untersucht werden. Die folgenden Thematiken können unter Berücksichtigung der Interessen der Teilnehmer behandelt werden: 

Algorithmische Entwurfsmethoden:
Dekompositionstechniken 
Datenpartitionierung 
Präfix-Operationen, List-Ranking, Pointer-Jumping 

Programmierung:
Programmiermodelle 
Programmiersprachen: paralleles Fortran, C, 
Parallelisierende Compiler 
Effiziente Shared Memory Implementierungen 

Konkrete Problemstellungen:
Matrix-Multiplikation 
Paralleles Sortieren 
Kombinatorische Optimierungsprobleme 

Leistungsmessungen:
Überwachungstools 
Standard Benchmarks 
Entwurf eigener Benchmarks für Kommunikationsbandbreiten 

Literatur:

• M. Snir et al., MPI - The Complete Reference Vol 1, MIT Press 1998 
• J. Gropp, E. Lusk, A. Skjellum, Using MPI, MIT Press 1997 
• G. Wilson, Practical Parallel Programming, MIT Press 1995 
• H. Stone, High-Performance Computer Architecture, Adison Wesley 1990 
• T. Bräunl, Parallele Programmierung, Vieweg 1993 
• J. JaJa, An Introduction to Parallel Algorithms, Adison Wesley 1992 
• Kumar, Grama, Gupta, Karypis, Introduction to Parallel Computing, Benjamin/Cummings 1994 
• G. Almasi, A. Gottlieb, Highly Parallel Computing, Benjamin/Cummings, 1989 

---

 
• Oberseminar Theoretische Informatik
Veranstalter:
Reischuk, Zeugmann
Form:
Oberseminar (3S)
Termin:
Di, 16h - 19h, H1/SFS
Inhalt:
Die Mitglieder und Studenten der Arbeitsgruppe Theoretische
Informatik tragen über aktuelle Forschungsresultate vor.