50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Winter Semester 2004/2005


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

Lehrveranstaltungen im WS 2004/2005




Grundstudium Informatik
Computational Geometry
Veranstalter:Jakoby

Form: Proseminar in englischer Sprache (2 PS) , 3 ETCS

Einordnung: Bachelor-Studiengang 1. + 3. Semester

Termine: Mi 14h - 16h, Seminarraum Informatik 1 (Gödel)

Inhalt:
The subject of computational geometry is to develop efficient methods for representing and manipulating geometric objects. These kinds of problems occur in several academic and applied areas of computer science like computer graphics, robotics, molecular biology, and engineering design. Within the talks of this seminar we will focus ourself on the main problems of computational geometry and discuss several efficient data structures and algorithms.
Some of the considered problems are: convex hull computation, paths problems, testing intersections of lines, triangulation, Voronoi diagrams, and visibility problems.

An interesting aspect of computational geometry is that we can find applications in topic that seams to be only slightly connections to geometry. E.g. Voronoi diagrams have applications in areas like archaeology and zoology (often known under different names). Some applications can be found in the internet (http://www.Voronoi.com/).

Literatur:
  • 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
  • J. O'Rourke, Computational Geometry in C. Cambridge University Press, 1999


Hauptstudium Informatik


Pflichtmodule:


Algorithmen, Komplexitätstheorie und Formale Sprachen

Termine: Vorlesung: Mi. + Fr. 8h -10h, Raum R3
 
Übungen:  Reischuk, Balbach,  Manthey

Inhalt:
Auswahl Lehrbücher:

  • Aho, Hopcroft, Ullman, Design and Analysis of Computer Algorithms, Add. Wesley 1978
  • Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press 1990
  • R. Reischuk, Komplexitätstheorie, Band I: Grundlagen,  Teubner 1998
  • Hopcroft, Ullman, Introduction to Automata Theory, Languages and Computation, Add. Wesley 1979
  • Harrison, Introduction to Formal Language Theory, Add. Wesley 1978

Algorithmik


Veranstalter: Reischuk

Form: 2V + 1Ü, 4 ETCS

Termine: Do. 10h - 12h, ITCS Seminarraum Nr. 21

Übung: Do. 14h - 15h, ITCS Seminarraum Nr. 21

Einordnung: Masterstudiengang Informatik, Pflichtmodul im Bereich Grundlagen der Informatik

Voraussetzung für Vertiefungsmodule Komplexitätstheorie und Parallelverarbeitung

Inhalt:

  • Entwurf und Analyse effizienter Algorithmen, Methodiken
  • komplexe Datenstrukturen
  • Komplexität algorithmischer Probleme
  • Online-Algorithmen
  • Randomisierung
  • Approximationsverfahren
  • algorithmische Probleme in Netzwerken
  • Optimierungsprobleme
Auswahl Lehrbücher:
  • Aho, Hopcroft, Ullman, Design and Analysis of Computer Algorithms, Add. Wesley 1978
  • Cormen, Leiserson, Rivest, Introduction to Algorithms, MIT Press 1990
  • R. Reischuk, Komplexitätstheorie, Band I: Grundlagen,  Teubner 1998




Wissensbasierte und lernende Systeme

Veranstalter: Liskiewicz

Form: 2V + 1Ü, 4 ETCS

Einordnung: Masterstudiengang Informatik, Pflichtmodul im Bereich Informatik der Systeme
Termine: Di. 10h - 12h, R1

Übung: Mi. 14h -15h, R3

Inhalt: 

  • Konzeptlernen
  • Induktive Inferenz
  • Lernen im Limes
  • PAC-Lernen
  • Entscheidungsbaumverfahren
  • Naive-Bayes-Verfahren
  • Instance-Bases-Learning
  • Anwendungsbeispiele im Data Mining

Auswahl Lehrbücher:
  • Michalski, Bratko, Kubat, Machine Learning and Data Mining, John Wiley 1999
  • Kearns, An Introduction to Computational Learning Theory, MIT Press 1994
  • Gammerman, Computational Learning and Probabilistic Reasoning, John Wiley 1996
  • Anthony, Biggs, Computational Learning Theory, Cambridge University Press 1992
  • Schapire, The Design and Analysis of Efficient Learning Algorithms, MIT Press 1991
  • Jain et al., Systems That Learn, MIT Press 1999
  • Han, Kamber, Data Mining, Morgan Kaufmann 2001

Wahlpflicht-/Vertiefungsmodule:
Veranstalter:Jakoby

Form: 2V + 1Ü, 4 ETCS

Einordnung:  Diplomstudiengang Informatik: Wahlpflichtmodul im Hauptstudium Bereich Informatik III
                        Masterstudiengang Informatik: Vertiefungsmodul im Bereich Angewandte Informatik
Termine: Mi. 12.30h - 14h, ITCS Seminarraum Nr. 21

Übung: Mo. 9h -10h, Seminarraum I

Inhalt:
Die Schwerpunkte dieser Vorlesung können wir wie folgt gliedern:

Information: Was ist Information? Wie kann Information gemessen werden? Wie können wir von diesen Maßen Gebrauch machen?

Kodierung: Wie können wir Informationen kodieren, so dass sie auch bei fehlerhafter Übertragung rekonstruiert werden können?

Die Kodierungs- und Informationstheorie bilden die Grundlage bei der Analyse von effizienten Codes in der Nachrichtenübermittlung. Unser heutiges Verständnis von Information ist im Wesentlichen durch die Arbeiten von Shannon geprägt.

In der Vorlesung Kodierung und Sicherheit werden wir eine Einführung in die Informationstheorie geben sowie deren Auswirkungen auf die Kodierungstheorie diskutieren. Ausgehend vom Shannonschen Informationsbegriff wollen wir verschiedene Kodierungsverfahren vorstellen und deren Einsatz bei fehlerfreier sowie fehlerbehafteter Datenübertragung analysieren.
Literatur:
  • J. H. van Lint, Introduction to Coding Theory, Springer-Verlag, 1999S.
  • S. Roman, Introduction to Coding and Information Theory, Springer-Verlag, 1997
  • D. Welsh, Codes and Cryptography, Oxford Science Publications, 1995
Skript ( ps , pdf )

Verteilte Algorithmen

Veranstalter: Reischuk, Völzer


Form: 2 V, 3 ETCS

Einordnung: Diplomstudiengang Informatik: Wahlpflichtmodul im Hauptstudium Bereich Informatik III

Termine:  Mo. 10h - 12h, Seminarraum Informatik 4 (Minsky)


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 Betriebs- und Kommunikations- systeme sowie Datenbank- und Workflowmanagementsysteme, sie kommen aber auch in Geschäfts-, Betriebs- und Produktionsabläufen sowie im täglichen Leben vor.

In der Vorlesung werden grundlegende Probleme in verteilten Systemen vorgestellt sowie deren Lösung durch verteilte Algorithmen diskutiert. Im Vordergrund steht dabei die systematische Darstellung der wichtigsten Wirkprinzipien verteilter Algorithmen.

Es werden keine Vorkenntnisse aus anderen Veranstaltungen des Hauptstudiums erwartet.



Algorithmische Verfahren zur Datenkompression

Veranstalter:  Liskiewicz,

Form: 2V + 1Ü, 4 ETCS

Einordnung: Hauptstudium Informatik: Wahlpflichtmodul im Bereich Informatik III, im Nebenfach Medieninformatik und im Bachelorstudiengang Computational Life Science

Termine: Vorlesung: Do. 14h -16h, H1

Übung: Di. 14h - 15h, Rechnerpool des ITCS, Raum Nr. 20

 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


Seminar:
        Algorithmische Spieltheorie

        Veranstalter:  Reischuk,  Völzer, Arpe

        Form: Hauptseminar (2S), 3 ETCS

        Termine: Mi. 14h - 16h, Informatik Seminarraum 4 (Minsky);
                        Anmeldung und Themenvergabe in der Vorbesprechung am Mi, 20.10., 14-16h, Seminarraum Informatik 4 (Minsky)

        Einordnung: Diplomstudiengang Informatik, Wahlpflichtmodul

        Inhalt:
          In immer mehr Netzwerkanwendungen wird das Systemverhalten vom egoistischen Handeln ihrer Nutzer bestimmt, z.B. in Internet-Tauschbörsen, Online-Auktionen und pay-per-view Diensten.

Die algorithmische Spieltheorie untersucht, wie man Anwendungen so entwirft, daß sie trotz des egoistischen Verhaltens der einzelnen Nutzer für die Gesamtheit so nützlich wie möglich sind.

In diesem Seminar geben wir einen einführenden Einblick in das Gebiet und diskutieren einige ausgewählte Probleme im Detail.

Weitere Informationen gibt es hier!



Praktikum:

Programming Challenges

Veranstalter:Liskiewicz, Manthey

Form: Praktikum (3P), 4 ETCS

Einordnung: Diplomstudiengang Informatik, Wahlmodul
                       Bachelorstudiengang Informatik: Wahlmodul

Termin: Do.16h -19h, Rechner-Pool des ITCS, Raum Nr. 20

Inhalt: 

Ziel ist des Praktikums ist es, für konkrete Probleme algorithmische Lösungen zu entwickeln und in möglichst kurzer Zeit zu implementieren. Hiermit wird einerseits das Verständnis für grundlegende effiziente Algorithmen vertieft, andererseits das Anwenden der Algorithmen und Programmieren unter Zeitdruck geübt. Wir werden unter anderem Beispiele für

  • Breiten- und Tiefensuche,
  • Berechnung kürzester Wege,
  • Flussprobleme,
  • Berechnung konvexer Hüllen und
  • vieles mehr
behandeln. Das Praktikum dient außerdem zur Vorbereitung auf den internationalen ACM-Programmierwettbewerb
(ACM ICPC). Der Nord-West-Europa-Wettbewerb findet dieses Jahr wieder im November in Lund, Schweden, statt.

Literatur:

  •  T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. MIT Press, 2001.
  • S. Skiena: The Algorithm Design Manual. Springer, 1998
  • S. Skiena, M. Revilla: Programming Challenges. Springer, 2003.


Voraussetzungen:
gute Kenntnisse über effiziente Algorithmen und Datenstrukturen, Programmiererfahrung in C, C++ Pascal oder JAVA.


Oberseminar:
Oberseminar Theoretische Informatik

Veranstalter:Reischuk,  

Form:Oberseminar (3S)

Termin:Di, 16h - 19h, ITCS Seminarraum/Besprechungsraum

Inhalt:

Die Mitglieder und Studenten der Arbeitsgruppe Theoretische Informatik
tragen über aktuelle Forschungsresultate vor.