50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Winter Semester 2002/2003


This page was taken from an older version of this website.

Lehrveranstaltungen im WS 02/03


Hauptstudium:
Pflichtvorlesungen:
  • Algorithmen, Komplexitätstheorie und Formale Sprachen
  • Veranstalter:
              Vorlesung: Zeugmann
    Form: 
              Pflichtvorlesung im Bereich Informatik III (4V) Wahlpflichtübung (2Ü), 5. Fachsemester Diplom-Studiengang
    Termine: 
    Vorlesung: Mi, 8.00h-10.00h und Fr, 8.00h-10.00h, Raum R3/21.
      Übungen: 

      Jakoby, Bläser
                  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), 5. Fachsemester Diplom- und Bachelor-Studiengang
    Termine:
             Vorlesung: Fr, 14.00h - 16.00h, Raum R3/21
    Übung: für Bachelor-Studiengang (keine Pflichtveranstaltung für Diplom-Studiengang)
      Mi, 09.00 - 10.00h,  Raum H2
    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:
    • Algorithmische Verfahren zur Datenkompression
    • Veranstalter:
      Form: 
                Vertiefende Vorlesung im Bereich Informatik III (2V), 5.+7. Fachsemester Diplom-Studiengang und Nebenfach Medieninformatik
      Termine:
                Do. 14.00h-16.00h, Raum H1
      Inhalt:

      In dieser Vorlesung wollen wir einige der am meisten praktisch eingesetzten Verfahren zur Speicherung und Komprimierung digitaler Daten kennenlernen. Wir werden allgemeine verlustfreie sowie verlustbehaftete Komprimierungalgorithmen diskutieren und zunächst spezifische Formate zur Speicherung und Komprimierung von Text-, Fax-, Bild-, Video- und Audiodateien betrachten unter anderem: Lempell-Ziv-Verfahren, Zip, compress in Unix, das GIF-Format, JBIG und JPEG Standards zur Speicherung und Komprimierung von Bilddateien, MPEG für Video und MPEG/Audio (MP3) Standard. 
      In der Vorlesung wollen wir auch die Verfahren für die Sichercheit in Medienströme diskutieren. Wir werden u.a. Algorithmen für robuste digitale Wasserzeichen betrachten die versuchen, die Authentizität oder Integrität des Datenmaterials nachzuweisen. 
       

      Literatur:

      •  K. Sayood. Introduction to Data Compression,, Morgan Kaufmann Publishers, Inc., Second Edition, 2000. 
      •  Y. Q. Shi, H. Sun, Image and Video Compression for Multimedia Engineering, CRC Press, 2000. 
      •  Al Bovik, Ed., Handbook of Image and Video Processing, AP Series in Communication, Networking and Multimedia, AP, 2000
        •  
           
    • Computer Algebra

    • Veranstalter:
      Form:
        Vertiefende Vorlesung im Bereich Informatik III (2V), 5. + 7. Fachsemester Diplom-Studiengang
      Termine:
        Die ursprünglich für das Wintersemester 2002/2003 geplante Vorlesung wird voraussichtlich auf einen späteren Termin verschoben. Interessenten sollten sich beim Veranstalter umgehend melden. 
               
               
               

    • Kryptologie
    • Veranstalter:
      Form:
      Vertiefende Vorlesung im Bereich Informatik III (2V), 7. Fachsemester  Diplom-Studiengang
      Termine:
        Vorlesung: Di, 09.00h - 11.00h, Raum H1/SFS

        Die 1. Vorlesung findet am Dienstag, 22.10.2002 statt
         
      Inhalt:
      Die Menschheit hat sich schon lange, bevor Computer und globale Kommunikationsnetze existierten, mit der Frage beschäftigt, wie man Information sicher übertragen kann. Basierend auf der Wahrscheinlichkeitstheorie wurde vor 50 Jahren von Shannon die moderne Informationstheorie begründet, die eine der Grundlagen für die moderne Kodierungstheorie und Kryptologie bildet. 

      Neue Ergebnisse der Komplexitätstheorie einerseits und konkrete Sicherheitsbedürfnisse in globalen Netzen andererseits haben die Kryptologie in den letzten Jahren eine stürmische Aufwärtsentwicklung erleben lassen. Durch die Digitalisierung sind neuartige Aufgabenstellungen wie die digitale Unterschrift hinzugekommen. Dieser Themenkomplex hat sich zu einem Schwerpunkte im Tätigkeitsspektrum von Informatikern und Mathematikern entwickelt mit einer Verschiebung vom militärischen zum kommerziellen Bereich (E-Commerce). 

      Die Vorlesung gibt einen Überblick über die historische Entwicklung und grundlegende kryptografische Verfahren. 

         
      Literatur:
      • G. Hotz, Algorithmische Informationstheorie, Teubner 1997
      • S. Roman, Introduction to Coding and Information Theory, Springer 1997
      • A. Beutelspacher, Kryptologie, Vieweg 1991
      • A. Konheim, Cryptography - a Primer, J. Wiley 1981
      • F. Bauer, Entzifferte Geheimnisse, Springer 1997
      • J. Buchmann, Einfühung in die Kryptographie, Springer 1999

      • Weiterführende Literatur:

      • A. Salomaa, Public-Key Cryptography, Springer 1990
      • G. Brassard, Modern Cyryptology, Springer, 1988
      • D. Kahn, The Codebreakers, 1967
      • C. Meyer, Matyas, A New Dimension in Computer Data Security - Cryptography, J. Wiley 1982
      • D. Denning, Cryptography and Data Security, Addison. Wesley, 1982
      • D. Stinson, Cryptography, Theory and Practice, CRC Press 1995
      • A. Menezes, P. Oorschot, S. Vanstone, Handbook of Applied Cryptography, CRC Press 1997
      • S. Shaffer, A. Simon, Network Security, Academic Press 1994
        •  
           
           
                   
    • Kombinatorische Optimierung
    • Veranstalter:
      Reischuk, Bläser
    Form: 
               Vertiefende Vorlesung (2V), 7. Fachsemester Diplom-Studiengang 
      Termine:
        Do. 17.00h-18.30h, Raum R3.

         
      Inhalt: 
      Eine zentrale Rolle in der kombinatorischen Optimierung ist die lineare Programmierung. Neben allgemeinen Verfahren zum Lösen von linearen Programmen sowie klassischen Anwendungen der linearen Programmierung, wie z.B. Lösen von Matching- und Flußproblemen, stehen neuere Anwendungen der linearen Programmierung im Vordergrund der Vorlesung. 

      Ein Beispiel sind der Entwurf von Approximationsalgorithmen für NP-vollständige Probleme, z.B. mittels Rundungstechniken oder via Dualität. Weitere neuere Einsatzmöglichkeiten sind der Entwurf von Mechanismen und Protokollen für zukünftige Internetanwendungen, wie sie z.B. auch in dem Seminar "Strategisches Handeln im Internet" behandelt werden. 

      Voraussetzungen: Vorlesung Algorithmen, Komplexitätstheorie und Formale Sprachen

         
      Literatur:
       
      • Ch. Papadimitriou und K. Steiglitz, Combinatorial Optimization, Dover 1998
      • V. V. Vazirani, Approximation Algorithms, Springer, 2001

      •  

         
         
         

    • Nichtklassische Logik

    • Veranstalter:
      Form:
        Vertiefende Vorlesung im Bereich Informatik III (2V), 7. Fachsemester Diplom-Studiengang
      Termine:
        Vorlesung: Mo, 14.00h - 16.00h, Raum H1/SFS.

         
      Inhalt:
      Als fundamentales Teilgebiet der Informatik kann heute die Logik angesehen werden. Speziell die Temporale Logik und die Modallogik sind für informatische Anwendungen intendiert. 

      Die wesentlichen Ziele der Veranstaltung sind das Kennenlernen verschiedener Logikkalküle und die Darstellung dieser mit der üblichen Prädikatenlogik. 

      Ich gehe davon aus, dass die Teilnehmer gute Kenntnisse der Prädikatenlogik besitzen, zum Beispiel aus meiner Vorlesung im letzten Semester. 
       


                               
    • Proseminar:
    • Boolean Functions

    • Veranstalter: 
                 Buntrock, Arpe
      Form:
      Proseminar (2S), 3. + 5. Fachsemester Bachelor-Studiengang
      Termin:
        Mi, 10.00h-12.30h, H1/SFS

         
      Inhalt:
      In 1854 George Boole publishes his book "The Laws of Thought", in which he approaches logic in a new way reducing it to simple algebra. His "algebra  of logic" which is known today as "Boolean algebra" has various applications e. g. in propositional logic, computer construction, circuit design, and probability theory. In honor of the foundational work of George Boole, the values that represent "true" and "false" (mostly 1 and 0) are called "Boolean values" or just 
      "Booleans" for short. 

      In general any function from {0,1}n to {0,1}m is called a Boolean function. Clearly, these functions are the most elementary and thus highly important for informatics. They are used to model computing circuits, 
      formal reasoning, and last but not least string-to-string functions, i. e. functions that our computers are actually computing. In this course we will discuss the following topics in detail: 

      1. Foundations of Boolean functions: 
      1.1 Post's Theorem on characterizing complete bases for the set of Boolean functions
      1.2 Computing special representations of Boolean functions

      2. Circuits for arithmetic functions: 
      2.1 Circuits for addition
      2.2 Circuits for multiplication
      2.3 Circuits for devision
      2.4 Computing with matrices

      3. Some complexity aspects of VLSI design: 
      3.1 Basics in lower bound arguments
      3.2 Layout of planar graphs for wire routing

      We will primarily use the following books for supplementary information on our topics: [W87, U84, G97]. Please note that in this course we will communicate exclusively in English. 

      First meeting: We, 16 October 2002, 14:00 c.t.

      (In the first meeting we will fix the distribution of talks on the above topics to the participants. Of course, it is possible to arrange further lectures.)

      In case of any questions, please feel free to contact us via e-mail. It is also possible to arrange a meeting before the run starts.

      Jan Arpe (arpe@tcs.mu-luebeck.de) and Gerhard Buntrock (bunt@tcs.mu-luebeck.de)
       
       

      Recommended literature:

      •  [G97] Jozef Gruska, Foundations of Computing, International Thomson Computer Press, 1997. 
      •  [U94] Jeffrey D. Ullman, Computational Aspects of VLSI, Computer Science Press, 1984. 
      •  [W87] Ingo Wegener, Complexity of Boolean Functions, Wiley-Teubner Series in Computer Science. B. G. Teubner, Stuttgart and John Wiley & Sons, 1987. 

    • Hauptseminare:

    •  
    • Strategisches Handeln im Internet

    • Veranstalter: 
                 Reischuk, Bläser
        Form:
        Hauptseminar (2S), 5. Fachsemester Diplom-Studiengang
        Termin:
          Do, 10.00h-12.00h, H3

           
        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 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 teilen sich mehreren Nutzern bestimmte Links. 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. 

        Voraussetzungen: 
        Vorlesung Algorithmen, Komplexitätstheorie und Formale Sprachen
         
         
         

      • Algorithmen und Sprachen in der Biologie

      • Veranstalter: 
                   Buntrock, Kim
        Form:
        Hauptseminar (2S), 5. Fachsemester Diplom-Studiengang und Nebenfach Bioinformatik/Biomathematik
        Termin:
          Do, 15.00h-17.00h, H3/SFS

           
        Inhalt: Interessenten bitte bei Herrn Dr. Buntrock melden!
         
         
    • Quanten Computing

    • Veranstalter: 
                 Liskiewicz, Jakoby
        Form:
        Hauptseminar (2S), 5. + 7. Fachsemester Diplom-Studiengang
        Termin:
          Mo, 14.00h-16.00h, H2/SFS

           
        Inhalt:
        Obwohl quantenmechanische Effekte schon bei den heute zur Verfügung stehenden Rechnern eine große Rolle spielen basiert auch der modernste Computer noch auf einfachen Schaltungsprinzipien. Der Quantenrechner hingegen ist ein Berechnungsmodell, das durch die Ausnutzung quantenmechanische Effekte seine Ressourcen besonders effizient nutzt. So kann der Speicher eines Quantencomputers exponentiell in der Größe der tatsächlich vorhandenen physikalischen Hardware sein. Außerdem ist es möglich, viele Berechnungen parallel durchzuführen, obwohl die zugehörige Hardware nur einmal vorhanden ist. Andererseits können nur bestimmte Operationen auf diese Weise parallelisiert werden, was den Entwurf spezieller Algorithmen erforderlich macht. 

        Trotz intesiver Forschung sind noch nicht alle Schwierigkeiten überwunden, einen wirklichen Quantencomputer zu bauen, dennoch sind die Fortschritte in dieser Richtung wesentlich. Zwei Meilensteine in Richtung der Verwirklichung eines Quantenrechners überraschten in den letzten drei Jahren die Fachpresse. So wurde im Los Alamos National Laboratory - einem führenden Forschungsinstitut für experimentelle Quantenberechnungen in der Welt - im Winter 98 ein 3-qubit Quantencomputer konstruiert. Anfangs dieses Jahres stoppten Wissenschaftler zweier verschiedener Laboratorien (Harvard und Cambridge, Massachusetts) das erste Mal effektiv einen Lichtsimpuls: 

        AT LAST! LIGHT BROUGHT TO A HALT. For the first time, physicists in two separate laboratories have effectively brought a light pulse to a stop. In the process, physicists have accomplished another first: the non-destructive and reversible conversion of the information carried by light into a coherent atomic form. Sending a light pulse into specially prepared rubidium (Rb) vapor, a group at the Harvard-Smithsonian Center for Astrophysics led by Ron Walsworth and Mikhail Lukin has (1) slowed the pulse's `group velocity' to zero and (2) stored its information in the form of an atomic `spin wave', a collective excitation in the Rb atoms. [...] The atomic spin wave is coherent and long-lived, which enables the researchers to store the light pulse's information and then convert it back into a light pulse with the same properties as the original pulse. This new accomplishment in a simple system increases the promise for quantum communication, which may someday be used to connect potentially ultrafast quantum computers in a large network analogous to the Internet. [From: The American Institute of Physics Bulletin of Physics News, Number 521, January 18, 2001] 

        In diesem Seminar diskutieren wir die wichtigsten Konzepte und Methoden der Quanteninformationsverarbeitung, Quantennetzwerke, Quantenkryptographie und Suche in Datenbanken. Bekannte Ergebnisse aus diesen Gebieten sind die fundamentalen Ideen über den Quantencomputer von David Deutsch und der berühmten Algorithmus von Peter Shor für die schnelle Faktorisierung.
         
         


    • Praktikum:

      •  
      • Effizientes Problem lösen und programmieren
      • Veranstalter:
                  Liskiewicz, Manthey 
        Form:
          Praktikum (P3), 5. + 7. Fachsemester Diplom-Studiengang, 3. + 5. Fachsemester Bachelor-Studiengang
        Termin:
          Do, 16.00h - 19.00h, Raum H4(Rechnerpool)/SFS.
        Anmeldung: bis 1.10.2002
        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.

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