50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Wintersemester 2003/2004


Diese Seite stammt aus altem Bestand.

Lehrveranstaltungen im WS 03/04


Hauptstudium:
Pflichtvorlesungen:
  • Algorithmen, Komplexitätstheorie und Formale Sprachen
  • Veranstalter:
              Vorlesung: Zeugmann
    Form: 
              Pflichtvorlesung im Bereich Informatik III (4V) Wahlpflichtübung (2Ü), 5. Fachsemester Diplom- und  Bachelor-Studiengang
    Termine:
    Vorlesung: Mi, 8.00h-10.00h und Fr, 8.00h-10.00h, Raum R3/21.
      Übungen:Völzer
      Übungsblätter
      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
      •  

  • 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
        Übung: Di. 13h - 14h, H4(Rechnerpool)/SFS
      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
        Voraussetzung
      Termine: 
        Mo. 10.00h - 12.00h H1/SFS
      Inhalt:
        Die Vorlesung gibt eine Einführung in das Gebiet der Computer-Algebra. Das symbolische Rechnen mit Zahlen, Funktionen und anderen Objekten, Differenzieren und Integrieren werden behandelt. Verschiedene Computer-Algebra-Systeme werden vorgestellt. Den Teilnehmern wird die Möglichkeit geboten,ihre Kenntnisse durch Arbeiten mit derartigen Systemen zu vertiefen. 
             
             

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


      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

      •  

         
         
         

    • Verteilte Algorithmen
    • Veranstalter:
      Reischuk, Völzer
      Form:
      Vertiefende Vorlesung (2V), 5. + 7. Fachsemester Diplom-Studiengang
        Termine:
          Mo. 14.00h-16.00h, Raum H1/SFS

           
        Inhalt:
        Verteilte Algorithmen werden zur Organisation physikalisch oder logisch verteilter Systeme benötigt. Sie dienen dort der Lösung von Koordinations- und Synchronisationsaufgaben und weniger der klassischen Berechnung von Funktionen. Sie bilden den Kern vieler technischer Informationssysteme, wie Betriebssysteme, Datenbank- und Workflowmanagementsysteme, sie kommen aber auch in Geschäfts-, Betriebs- und Produktionsabläufen sowie im täglichen Leben vor.

        In der Vorlesung werden wichtige Koordinations- und Synchronisations- probleme in verteilten Systemem vorgestellt sowie deren Lösung durch verteilte Algorithmen diskutiert. Im Vordergrund steht dabei die systematische Darstellung der wichtigsten Wirkprinzipien und weniger die Optimierung der Effizienz.

        Es werden keine Vorkenntnisse aus anderen Veranstaltungen des Hauptstudiums erwartet.


  • Proseminar:
    • Rewriting Systems
    • Veranstalter:
      Buntrock
      Form:
      Proseminar (2S), 3. Fachsemester Bachelor-Studiengang Informatik
      Termin:
      Mi, 14.00h -16.00h, Raum H3SFS


      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.benötigen, wird noch bekanntgegeben.

      Bei weiteren Fragen stehen wir gerne zur Verfügung:

      Gerhard Buntrock bunt@tcs.uni-luebeck.de



  • Hauptseminare:
    • Communication Complexity
    • Veranstalter:
      Jakoby
        Form:
        Hauptseminar (2S), 5. Fachsemester Diplom-Studiengang
        Das Seminar wird bei Bedarf oder Interesse auf Englisch angeboten.
        Termin:
          Mi, 15.00h-17.00h, H1/SFS

           
        Inhalt:

        Kommunikationskomplexität kann mit Hilfe des folgenden Szenarios beschrieben werden:

        Alice und Bob gehen mit einer Schatzkarte auf Schatzsuche. Wie es bei vielen Schatzkarten üblich ist, ist auch die Karte von Alice und Bob in zwei Teile geteilt worden, von denen Alice den einen und Bob den anderen Teil besitzt. Da sowohl Alice als auch Bob sehr wortkarg sind, gilt es jetzt, den Weg zum Schatz so zu finden, dass beide nur ein Minimum an Information austauschen müssen.

        Die zentrale Frage der Kommunikationskomplexität ist, wie viele Bits mindestens ausgetauscht werden müssen, um eine Funktion zu berechnen.

        Viele Aspekte der Funktionalität von Computern können als eine Reihe kommunizierender Prozesse angesehen werden. Die Kommunikationskomplexität ist eine Theorie zur Analyse derartiger Prozesse. Darüber hinaus wird die Kommunikationskomplexität häufig als abstraktes Modell zur Untersuchung vielseitiger Aspekte von Berechnungen verwendet.

        Dieses Seminar soll einen Überblick über die Kommunikationskomplexität geben und an einigen Beispielen die Frage untersuchen, wieviel Kommunikation für bestimmte Berechnungen notwendig ist.

        Der erste Teil des Seminars ist dem einfachen Zwei-Personen-Modell gewidmet, das 1979 von Yao eingeführt wurde. Der zweite Teil behandelt neuere Modelle der Kommunikationskomplexität, die entwickelt wurden, um schwierigere Fragestellungen kommunizierender Prozesse zu behandeln. Ferner soll auf Anwendungen dieses Modells in Computernetzen, verteilten Systemen, beim VLSI-Design und bei der Analyse von Datenstrukturen eingegangen werden.

    • Algorithmen und Sprachen zur Modellierung biologischer Systeme
      • Veranstalter: 
        Form:
        Hauptseminar (2S), 5. + 7. Fachsemester Diplom-Studiengang und Nebenfach Bioinformatik/Biomathematik
        Termin:
          Mi, 16.00h-18.00h, H2/SFS

           
        Inhalt: Interessenten bitte bei Herrn Dr. Buntrock melden!
         
    Quantum Computing
    Veranstalter: 
    Liskiewicz, Jakoby
      Form:
      Hauptseminar (2S), 5. + 7. Fachsemester Diplom-Studiengang
      Termin:
        Mo, 18.00h-20.00h, H1/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:
      Form:
        Praktikum (P3), 5. + 7. Fachsemester Diplom-Studiengang, 3. + 5. Fachsemester Bachelor-Studiengang
      Termin:
        Do, 16.00h - 19.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 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./li>
      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.