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

• Hauptstudium:
• Pflichtvorlesungen:
• Algorithmen, Komplexitätstheorie und Formale Sprachen
• Wahlpflichtvorlesungen:
• Datenkompression
• Algorithmische Geometrie
• Seminar:
• Intelligente Sprach- und Textbearbeitung
• Quanten-Computing
• Algorithmen und Randomisierung

(gemeinsam mit dem Institut für Mathematik)
• Oberseminar:
• Oberseminar Theoretische Informatik
• Spezielle Veranstaltung:
• Graduate Colloquium

• Hauptstudium:
• Pflichtvorlesungen:
• Algorithmen, Komplexitätstheorie und Formale Sprachen
Veranstalter:
Vorlesung: Reischuk,
Übung: Genther
Form:
Pflichtvorlesung und Wahlpflichtübung (4V+2Ü)
Termine:

Vorlesung: Mi, 8.00h-10.00h und Fr, 8.00h-10.00h, Raum R3/21.

Übung:

            Gruppe 1: Mo, 16.00h-18.00h, Raum H1/SFS

            Gruppe 2: Mo, 16.00h-18.00h, Raum H2/SFS

            Gruppe 3:

Inhalt:
Pflichtveranstaltung im Bereich Informatik III (Theoretische Informatik). 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

---
• Wahlpflichtvorlesungen:
• Datenkompression
Veranstalter:

Liskiewicz, Genther
Form:
Vertiefende Vorlesung (2V)
Termine:
Vorlesung: Mi, 14.00h-16.00h, Raum H1/SFS.
Übung: Do. 15.00h-17.00h, Raum H3/SFS + Rechnerpool
Inhalt:

           In dieser Vorlesung wollen wir einige der am meisten praktisch eingesetzten Verfahren zur digitalen Datenkompression kennenlernen. Wir werden allgemeine verlustfreie sowie verlustbehaftete Komprimierungsmethoden diskutieren und zunächst spezifische Algorithmen für Text-, Fax-, Bild-, Video- und Audiokomprimierung betrachten unter anderem: Lempell-Ziv-Verfahren, Zip,  compress in Unix, das GIF-Format, JBIG-Standard zur Bildkomprimierung, JPEG zur Komprimierung bewegungsloser Bilder, MPEG für Video und MPEG/Audio  (MP3) Standard.

Inhaltlich werden wir uns eng an die u.g. Bücher halten. Einführende Information findet sich auch im WWW, z.B. unter den untenstehenden Adressen:

http://www.cs.cmu.edu/
http://www.cis.ohio-state.edu/

Literatur:

• V.  Bhaskaran and K.  Konstantinides. Image and Video Compression Standards; Algorithms and Architectures,  Second Edition, Kluwer Acadenic Publishers, 1998.
• K. Sayood. Introduction to Data Compression,  Morgan Kaufmann Publishers, Inc., 1996.

---

• Algorithmische Geometrie

Veranstalter:
           N.N.
Form:
            Vertiefende Vorlesung (2V)
Termine:
          Vorlesung: Fr. 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
 

---

 

• Seminar:
• Intelligente Sprach- und Textbearbeitung

Veranstalter:
Buntrock, Behrens, Ingenerf
Form:
            Hauptseminar (S)
Termin:
            Di, 14.00h-16.00h, Raum H1/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.

Vorbesprechung: 11. Oktober 1999, Uhr 16 ct im Hörsaal 1 der Seefahrtschule
Interessenten können auch gerne schon vorher ihr Interesse an einem Vortrag bei einem der Veranstalter bekunden.

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

---


 
• Quanten-Computing

Veranstalter:
           Liskiewicz, Genther
Form:
            Hauptseminar (S)
Termin:
            Do, 12.00h-14.00h, Raum H2/SFS
Inhalt:
            Der Quantenrechner ist ein theoretisches Berechnungsmodell, das durch quantenmechanische Effekte seine Ressourcen besonders effizient nutzen kann. So ein Rechner bietet zum Beispiel einen Zugriff  zum Speicher an, der exponentieller größer als die physikalische Hardware ist. Außerdem ist es  möglich, für ein solches Modell viele Berechnungen parallel durchzuführen, obwohl die zugehörige Hardware nur einmal vorhanden ist. Andererseits können aber nur bestimmte Operationen auf diese Weise parallelisiert werden, was den Entwurf spezieller Algorithmen erfordert.

            In diesem Seminar diskutieren wir die wichtigsten Konzepte und Methoden der Quanteninformationsverarbeitung, einschließlich der fundamentalen Ideen für Quantencomputer von David Deutsch und des berühmten Algorithmus
von Peter Shor für die schnelle Faktorisierung. Außerdem werden wir Quantennetzwerke, Kommunikationsprobleme für  Quanteninformationsverarbeitung, Quantenkryptographie und Suche in Datenbanken (einschließlich Algorithmus
von Grover) betrachten.
            Es sind noch nicht alle Schwierigkeiten überwunden, einen wirklichen Quantencomputer zu bauen, dennoch sind die Fortschritte in dieser Richtung wesentlich. So wurde z. B. im  Los Alamos National Laboratory - einem führenden Forschungsinstitut für experimentelle Quantenberechnungen in der Welt -  im Winter 1998 ein 3-qubit Quantencomputer (mit Hilfe von Nuclear Magnetic Resonance) konstruiert.

---

 

• Algorithmen und Randomisierung
Veranstalter:
Dümbgen, Reischuk
Form:
Hauptseminar (S)
Termine:
Fr, 15.00h-17.00h, Raum H1/SFS.
Inhalt:
Randomisierung ist eine moderne Technik im Algorithmenentwurf mit dem Ziel, die Laufzeit zu beschleunigen und den Implementationsaufwand zu verringern. Dies geschieht durch Zufallsentscheidungen und hat häufig den Effekt, daß selbst Eingabekonstellationen mit ungünstiger Laufzeit für feste Lösungsstrategien im Mittel effizient behandelt werden. Ein klassisches Beispiel hierfür ist randomisiertes QuickSort.

Im Seminar behandeln wir Algorithmen für die folgenden Aufgaben:
Algorithmische Geometrie:
Die Berechnung der konvexen Hülle von Punkten in der Ebene sowie in höherdimensionalen Räumen. Genau gesagt, geht es um die Bestimmung der Eckpunkte und Seitenflächen. Dieses Problem steht in engem Zusammenhang mit der Berechnung des Durchschnitts von Halbräumen. ([MR95], Kapitel 9.1-4)
Raumzerlegungen: Angenommen, man möchte Ansichten eines dreidimensionalen Objektes aus verschiedenen Blickrichtungen zügig auf dem Bildschirm darstellen. Dabei geht man davon aus, daß das Objekt, beziehungsweise die Oberfläche einzelner Teile, als Vereinigung von Dreiecken gegeben ist. Aus technischen Gründen, die im Seminar erläutert werden, ist es hilfreich, den Raum induktiv in Teilgebiete zu zerlegen: Solange ein Teilgebiet mehr als ein Dreieck schneidet, wird es durch eine Ebene in zwei Teilmengen zerlegt. Die Qualität einer solchen Zerlegung ist umso größer, je kleiner die Zahl der erzeugten Teilgebiete ist. ([MR95], Kapitel 1.3 und 9.7)

Graph-Algorithmen:
Ein Standardproblem bei der Planung von Netzwerken ist die Berechnung eines minimal erzeugenden Baumes (minimal spanning tree) für gewichtete Graphen. Durch Randomisierung kann dieses Problem auf einfache Weise gelöst werden. ([MR95], Kapitel 10.3)
Ein weiteres Thema sind Irrfahrten (random walks) in Graphen, bei denen durch eine zufällige Auswahl von Kanten ein unbekannter Graph möglichst schnell durchsucht werden soll. Eine Erweiterung in Richtung auf schnell mischende Markov-Ketten, eine elegante Technik um große Zustandsräume zu untersuchen, ist möglich. ([MR95], Kapitel 6)

Online-Algorithmen:
Beim Paging-Problem geht es darum, Datenblöcke so in der Speicherhierarchie eines Prozessors abzulegen, daß er möglichst schnell auf sie zugreifen kann. Wir betrachten den Fall eines großen Hauptspeichers mit langsamem Zugriff kombiniert mit einem schnellen Cache, der allerdings nur Platz für höchstens k Blöcke bietet. Eine Caching-Strategie legt fest, welche Datenblöcke zu jedem Zeitpunkt im Cache gehalten werden. Dabei unterscheidet man zwischen off-line-Verfahren, die die gesamte Datenzugriffssequenz vorab benötigen, und on-line-Verfahren, die jeweils auf eine neue Datenanfrage hin entscheiden, was im Cache gehalten wird, ohne nachfolgende Anfragen zu kennen. Für den on-line Fall gibt es keine deterministischen Paging-Strategien mit einem guten worst-case Verhalten. Randomisiert kann man dieses Problem jedoch nachweisbar besser lösen. ([MR95], Kapitel 13.1-3)

(II) Je nach Teilnehmerzahl und Interesse können noch weitere Aspekte und Beispiele von Algorithmen und Randomisierung behandelt werden, etwa die Frage, wie sich Lösungen bestimmter Optimierungsprobleme verhalten, wenn die Eingabedaten zufällig sind. Ein Beispiel ist das

Bin Packing-Problem: Gegeben sei eine Menge gleicher Behälter mit einer gewissen Kapazität und eine Menge von n Elementen mit Volumen X₁, X₂, ..., X_n. Aufgabe ist es, diese Elemente in möglichst wenigen Behältern unterzubringen. Die exakte Berechnung der Minimalzahl L ist NP-schwierig, aber es gibt verschiedene Approximationsalgorithmen (offline und online), welche eine Einteilung in L' Gruppen liefern, so daß der Quotient L'/L bestimmte Schranken nicht überschreitet. ([H97], Kapitel 2.1-2)
Schließlich betrachten wir die Zahlen L und L' im Falle von zufälligen und unabhängigen Eingabedaten X_i. Mithilfe einer sehr eleganten Methode von M. Talagrand kann man zeigen, daß L/n und L'/n bei großem n nahezu konstant sind. Talagrands Methode kann man auf viele Probleme der kombinatorischen Optimierung anwenden. ([H97], Kapitel 2.3; [S97], Kapitel 6; [D96]).

Literatur

[MR95] R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995
[H97] D. Hochbaum (Ed.). Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997
[S97] M. Steele. Probability Theory and Combinatorial Optimization. SIAM, 1997
[D96] L. Dümbgen. Isoperimetrie und Konzentrationsungleichungen für Wahrscheinlichkeitsmaße. Manuskript, 1996

sowie verschiedene Zeitschriftenartikel.

 

---

 
• Oberseminar
• Oberseminar Theoretische Informatik
Veranstalter:
Reischuk,
Form:
Oberseminar (S3)
Termin:
Di, 16h-19h, Raum 18/SFS.
Inhalt:
Die Mitglieder und Diplomanden des Instituts für Theoretische Informatik tragen über aktuelle Forschungsresultate vor.

• Spezielle Veranstaltung

• Graduate Colloquium
 
Nächste Veranstaltung:
07. Februar 2000, 13.00h c.t. Raum H1/SFS

Vortrag: The Digital Library and Future Technologies, Judith Klavans, Columbia University

Lecture Summary: The concept of the digital library is both intuitive and complex. On the intuitive and complex. On the intuitive side, as more and more information becomes available in digital format, the digital library is playing a major role in organizing and delivering this information, much in the same way that it has played for centuries. Electronic books, journals, images, music, and video are now becoming a standard resource, and thus from part of the information pool to which libraries traditionally provide access. In contrast, on the complex side, both the quantity and format of this new digital information presents technical and user-related problems never before encountered by libraries. .

Speaker Information: Judith Klavans is the director of the Center for Research on Information Access (CRIA) at Columbia University. She won a post-doctoral research appointment at MIT, followed by a position in 1983 at the IBM T.J. Watson Research Center. She joined the Columbia University Department of Computer Science in 1992. Klavans was appointed the first director of the newly formed CRIA in 1995. The purpose of CRIA is to foster technical collaboration between research and working applications in the creation of the digital library. Her combined background in linguistics and computer science has provided her with the broad perspective required to lead this innovative interdisciplinary research center. KlavanÇs research focuses on natural language processing, emphasizing the use of large semantic lexicon for extracting and structuring information in monolingual and multilingual texts. She has published more than 40 technical articles and two books..

Als Diskussionssprache wurde Deutsch festgelegt

Weitere Interessenten für das Graduate Colloquium sind herzlich willkommen.


 
 
Veranstalter:
Reischuk
 
Date:
1st meeting: Wednesday 20th October 1999, 16 h, H1/SFS

Contents:
           This class will deal with a variety of central topics in computer science. We will have various guest speakers, all experts in their fields who present their material in a well prepared and profound way. The lectures are given in English, video-taped and distributed by Stanford University Video Communications. The following list ernumerates the speakers and topis:

Bell, Gordon                The Computer Museum, The First Computers

Dijkstra, Edsger W.      Reasoning About Programs
Agerwala, Tilak K.       Parallel Processing
Allen, Frances E.          Optimizing Compilers for Parallel Computers
Graham, Ronald L.       The Shortest Network Problem
Karlin, Anna R.            On Online Computation
Stroustrup, Bjarne        The Design of C++
Oehler/Blasgen             Evolution of Power PC Architecture
Ditzel, David R.            SPARC Version 9: Adding 64-Bit Adressing and
                                       Robustness to an Existing RISC Architecture
Hillis, Daniel                Architecture of the CM-5
Watanabe, Tadashi       Toward the Ultra High-Speed Computing System
Sun Microsystems        Sunergy 22: The Future of Computing Architectures
Lenoski, Daniel E.        Scalable Shared-Memory Multiprocessing and the
                                       Silicon Graphics S2MP Architekture
Fisher, Joseph A.           Instruction-Level Parallelism (ILP)
Forster, James               Multiprotocol Routing in Large Networks
Fraser, A.G.                  The Origins of ATM
Feigenbaum, Joan          Security and Privacy in the Information Economy
Pfitzmann, Birgit          Digital Cash
Klavans, Judith             The Digital Library and Future Technologies
Lee, Kai-Fu                  Automatic Speech Recognition

In the first meeting we will select those topics we want to discuss. Each presentation lasts between 45 and 60 minutes. The remaining time will be used to discuss the subjects in more detail and to answer questions that are left open. The discussion may be in German or English depending on the preferences of the participants.