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

Lehrveranstaltungen im SS 2000

• Grundstudium:
• Einführung in die Informatik IV
• Proseminar "Effiziente Algorithmen"
• Hauptstudium:
• Pflichtvorlesungen:
• Parallele und Verteilte Systeme, Logik
• Wahlpflichtvorlesungen:
• Algorithmische Geometrie
• Algorithmisches Lernen, Data Mining
• Sprachen im Web: Formalsprachliche Eigenschaften der Sprachen im Internet
• Seminar:
• Sicherheit in Rechner- und Kommunikationsnetzen
• Computer Algebra
• Praktikum
• Oberseminar:
• Oberseminar Theoretische Informatik
• Grundstudium:
 
• Einführung in die Informatik IV
Veranstalter:
Reischuk, Bläser
  Übung: Reischuk und Mitarbeiter
Form:
Vorlesung und Übung (4V+3Ü)
Termine:
Vorlesung: Mi, 8.00h-10.00h Raum H1/Transistorium und
                   Fr,  8.00h-10.00h, Raum R3/21.
Übungen:   Mo 10 -12/14-16h/16-18h und Do 15-16h, 16-17h, 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

---

• Effiziente Algorithmen
Veranstalter:
           Buntrock
Form:
Proseminar (2S)
Termin:
Fr, 11.00h - 13.00h, Raum H1 /SFS.
Inhalt:
Es gibt zahlreiche algorithmische Techniken, die ganz grundlegend die Effizienz unserer Programme erheblich verbessern können. Angesichts der immer schneller werdenden Rechner, wird die Bedeutung effizienter Algorithmen immer mehr zunehmen, da im Bereich von Giga-Byte grossen Eingaben die Effizienz der Bearbeitung immer wichtiger wird. Wir werden uns mit Themen wie Sortieren und Mischen, Suchen mit Hashing, Suchbäume, Suchen in Zeichenfolgen, Pattern Matching, Bestimmung der konvexen Hülle, Minimal spannende Bäume, Matching in paaren Graphen, Dynamisches Programmieren und anderen auseinandersetzen.
Durchführung:
Zum ersten Termin werden Themen vergeben. Zu den weiteren Terminen werden die Teilnehmer ihre Algorithmen mit besonderer didaktischer Aufbereitung den anderen vermitteln.
Literaturhinweise:
• Robert Sedgewick: Algorithmen. Addison Wesley, 1992
• Thomas Ottmann und Peter Widmayer: Algorithmen und Datenstrukturen. BI Wissenschaftsverlag 1993

---

 

• Pflichtvorlesungen:

 
• Parallele und Verteilte Systeme, Logik

Veranstalter:
          Buntrock,  Liskiewicz
Übung: Genther
Form:
Pflichtvorlesung und Wahlpflichtübung (4V+2Ü)
Termine:
Vorlesung: Mi, 10.00h - 12.00h und Fr, 14.00h - 16.00h, Raum H1/SFS.
Übung: Di, 17.00h - 19.00h, Raum H2 + H3/SFS.
Inhalt:
Logische Kalküle, Temporale Logiken, Petri-Netze, Synchronisationsprobleme und logisches Schliessen in Verteilten Systemen, parallele Programmier- und Maschinenmodelle, Verifikation paralleler Programme, Entwurf paralleler Algorithmen, Beschleunigung und Effizienz, Parallele Komplexitätsklassen.

Es wird von Woche zu Woche ein Übungsblatt geben, das dann in der Übung besprochen wird. Die Bearbeitung der Aufgaben ist zum Scheinerwerb obligatorisch (in der Regel in Zweiergruppen). Am Ende des Semesters findet eine Rücksprache über die Aufgaben statt.
Auswahl Lehrbücher
• [B93]    M. Ben-Ari, Mathematical Logic for Computer Science, Prentice Hall 1993
• [MP92] Z. Manna, A. Pnueli, The Temporal Logic of Reactive and Concurrent Systems - Specification, Springer 1992
• [L96]     Lynch, Distributed Algorithms, Morgan Kaufmann 1996
• [AG89] Almasi, Gottlieb, Highly Parallel Computing, Benjamin/Cummings 1989
• [S90]     Stone, High-Performance Computer Architecture, Add. Wesley 1990
• [J92]      JaJa, An Introduction to Parallel Algorithms, Add. Wesley 1992
 

---

 


• Wahlpflichtvorlesungen:

• Algorithmische Geometrie
Veranstalter:
  Reischuk
Form:
Vertiefende Vorlesung
Termine:
Vorlesung: Mo, 12.00h - 14.00h, Raum H1/SFS.
Inhalt:
Die algorithmische Geometrie beschäftigt sich mit der Verarbeitung geometrischer Daten auf dem Computer. Probleme der konstruktiven Geometrie waren bereits im griechischen Altertum von Interesse. Effiziente Datenstrukturen und Algorithmen zur maschinellen Lösung von geometrischen Problemen haben sich in den letzten 20 Jahren zu einer wichtigen Thematik der Informatik entwickelt.

Die Vorlesung behandelt grundlegende Methodiken und Problemstellungen in diesem Bereich. Diese sind Grundlagen in der grafischen Datenverarbeitung und finden neuerdings auch vermehrt Anwendung in intelligenten Informationssystemen. Konkrete Fragestellungen werden sein: die Berechnung der konvexen Hülle, Voronoi Diagramme, geometrisches Suchen, Schnitt- und Sichtbarkeitsprobleme.


Literaturhinweise:
 

• K. Mehlhorn,  Data Structures and Algorithms, Vol. 3: Multidimensional Data Structures and Computational Geometry, Springer 1984 (deutsche Ausgabe, Teubner 1987)
• 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

 

---

 


• Algorithmisches Lernen, Data Mining
Veranstalter:
Zeugmann
Form:
Vertiefende Vorlesung
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.
 

---

 

• Sprachen im Web: Formalsprachliche Eigenschaften der Sprachen im Internet
Veranstalter:
Buntrock
Form:
Vertiefende Vorlesung
Termine:
Vorlesung: Do, 10.00h - 12.00h, Raum H1/SFS.
Inhalt:
Anhand der Datenformate einiger Textverarbeitungssysteme werden wir den Begriff vollstrukturierte Daten motivieren. Im WorldWideWeb gibt es den vom W3C festgelegten HTML-Standard, der aus SGML entstanden ist. Lange bevor es das Web gab, haben hier bereits Untersuchungen stattgefunden, die zum Gegenstand hatten, Daten so zu strukturieren, dass möglichst keine Metainformation über diese Daten vorhanden sein muss. Der SGML-Standard war jedoch ungeeignet für das Web, so dass hier zunächst HTML als sehr restriktive Einschränkung definiert wurde. Im letzten Jahr wurde ein neuer Standard vom W3C eingeführt: XML, die extended markup language. In dieser besteht ein Dokument aus einem grammatikalischen Anteil und einem Rumpf, der die eigentlichen Daten enthält. Damit können Daten so gut repräsentiert werden, dass diese Sprache sogar als Datenmodell für Datenbanken geeignet ist.

Wir werden uns in der Veranstaltung mit den verschiedenen Formaten dieser Sprachen befassen und ihre formalen Eigenschaften kennenlernen, die uns Einsichten verschaffen in die Grenzen der Ausdrückbarkeit und die Komplexität des Parsierens.
 

Literaturhinweise:
• Henning Behme und Stefan Mintert: XML in der Praxis. Addison-Wesley 1998
• Brian E. Travis und Dale C. Waldt: The SGML Implementation Guide. Springer 1995
• W3C: Die verschiedenen Spezifikationen der einzelnen Formate stehen unter:   http://www.w3.org/TR
 

---

 
• Seminar:
• Sicherheit in Rechner- und Kommunikationsnetzen
Veranstalter:
Reischuk. Liskiewicz
Form:
Seminar (2S)
Termine:
Mo, 16.00h - 18.00h, Raum H3/SFS.
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:
 

• Internet Privacy, Communication of ACM 42, 2, 1999, 28-67
• 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
• P. Denning (Ed.) Computers under Attach, Addision Wesley 1990

 
Interessenten sollten sich zwecks Themenwahl möglichst früh mit den Veranstaltern in Verbindung setzen.

1. Sitzung: 10.4.00, 16 Uhr

 

---

• Computer Algebra
Veranstalter:
Reischuk, Bläser
Form:
Seminar (2S)
Termine:
Di, 10.00h - 12.00h, Raum H3/SFS.
Inhalt:
Viele Probleme in der Mathematik, Informatik und vielen anderen Naturwissenschaften lassen sich auf das Lösen einer Menge von Gleichungen zurückführen. Während in der numerischen Mathematik versucht wird, solche Gleichungen näherungsweise zu lösen, sucht man in der Computeralgebra nach exakten Lösungen. Oftmals existieren solche exakten Lösungen nicht oder sind wesentlich aufwendiger zu berechnen als eine näherungsweise Lösung, doch immer wenn es möglich ist, eine exakte Lösung zu berechnen, so vermittelt sie weitaus mehr Einsichten in die Natur des Problems als eine näherungsweise Lösung.
Moderne Computeralgebra-Systeme, wie z.B. Mathematica, Maple oder Axiom, bieten eine Vielzahl von bereits vorhandenen Datentypen und Algorithmen für mathematische Probleme, auf die man beim Implementieren und Testen eigener Algorithmen zurückgreifen kann.
In einem ersten Teil des Seminars soll jeder Teilnehmer sich mit einem Problem (und dessen Lösung) aus der Computeralgebra bzw. einem Anwendungsbereich der Computeralgebra vertraut machen (anhand von Originalliteratur) und darüber vortragen. Im zweiten Teil soll dann der vorgestellte Algorithmus mit Hilfe eines Computeralgebra-Systems implementiert werden.

---

• Praktikum
Veranstalter:
Reischuk, Liskiewicz, Genther
Termin:
Mi, 14.00h - 17.00h, Raum H3/SFS.
Inhalt:
Mit dem Frühjahr 2000 wird die die Lübecker Informatik einen Hochleistungs Shared Memory Cache-Cohärenten Parallelrechner neuester Technologie in Betrieb nehmen. Wir wollen dies zum Anlaß nehmen, um praktische Aspekte der Parallverarbeitung eingehender zu studieren. Die folgenden Thematiken werden behandelt:

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

Programmierung
Programmiermodelle: Message Passing versus Shares Memory
Programmiersprachen: paralleles  Fortran, C, Java
Programmier- und Entwicklungsumgebungen: MPI, (PVM)
Parallelisierende Compiler
Effiziente Shared Memory Implementierungen mit Cache Cohärenz

Algebraische Berechnungen: MM
Paralleles Sortieren
Graphalgorithmen
Kombinatorische Optimierungsprobleme

Leistungsmessungen
Überwachungstools
Standard Benchmarks
Entwurf eigener Benchmarks für Kommunikationsleistung und Cache-Cohärenz
 

• 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


Es werden nicht alle Punkte behandelt werden können. Unter Berücksichtigung der Interessen der Teilnehmer werden wir zu Anfang eine Auswahl treffen. Zunächst sollen gemeinsame Grundlagen erarbeitet werden.  Sobald die Maschine verfügbar ist, werden zu den verschiedenen Punkten kleinere Projekte durchgeführt.

Interessenten sollten sich mit Herrn Liskiewicz in Verbindung setzen.
1. Sitzung: 12.4.00, 14 Uhr

---

 
• Oberseminar Theoretische Informatik

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