50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Summer semester 2004


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

Lehrveranstaltungen im SS 2004

Grundstudium

Einführung in die Informatik IV          
Übungen:  
Gruppe 2 : Mo. 12-16 h + Do. 11-12 h Seminarraum Cook + Karp (m. geöffneter Trennwand)
                             Mi. 12-13 h Seminarraum Cook + Karp (m. geöffneter Trennwand)
  
Unterlagen zur Vorlesung (Script, Übungen) können hier runtergeladen werden (allerdings NUR von Rechnern der Universität)




Algorithmen und Programmierung

Veranstalter:  Liskiewicz, Manthey



Program Verification

We practise the presentation of scientific content through examples from the area of program verification. The challenge we will face is to present, in a short talk, a problem, its algorithmic solution, and its proof of correctness in such a way that your audience is fully convinced that you have indeed presented a solution to the presented problem.



Hauptstudium: Pflichtvorlesungen:



Parallele und Verteilte Systeme

Wahlpflichtvorlesungen: Data Mining
Modellierung und Spezifikation Verteilter Systeme

Die Vorlesung kann als Vertiefung für Theoretische Informatik oder für Softwaretechnik gewählt werden.

Literaturhinweise:




Randomisierte Algorithmen

Veranstalter:Jakoby

Form: Vertiefende Vorlesung (2V)

Termine: Vorlesung: Fr. 10.30h - 12.00h, Raum H2.

Inhalt: Für viele Probleme stellen randomisierte Algorithmen die einzigen bekannten effizienten Lösungsverfahren dar. Für manches andere Problem erhalten wir mit einem solchen Verfahren Algorithmen, die um vieles einfacher und verständlicher sind als alle bekannten deterministischen Verfahren. Es ist daher nicht verwunderlich, dass wir randomisierte Algorithmen in viele Anwendungsgebieten finden, wie z.B. in

Literatur:
 R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995
Alan Gibbons, Paul Spirakis, The Probabilistic Method,Wiley-Interscience Series, 1991

Skript ( ps , pdf )

Ausgewählte Kapitel der Theoretischen Informatik

Veranstalter: Buntrock

Form: Vertiefende Vorlesung (2V)

Termine: Vorlesung: Fr. 10.00h - 12.00h, Raum Seminarraum Informatik 4


Themen:
      • Aus den Formalen Sprachen: Die wachsenden kontextsensitiven Sprachen
      • Aus der Automatentheorie: Der Zweikellerautomat
      • Aus der Theorie der Ersetzungssysteme: Die Church-Rosser-Sprachen
      • Aus der Komplexitätstheorie: Realzeit und Linearzeit
      • Aus der Logik: Der Satz von Gödel
Voraussetzungen: Algorithmen, Komplexitätstheorie und Formale Sprachen sowie Parallele Verteilte Systeme



Seminar:

      Perlen der Theoretischen Informatik

        Veranstalter:  Reischuk, Manthey, Arpe

        Form: Hauptseminar (2S)

        Termine: Mi, 12.15h - 13.45h, Seminarraum 21 (2. Stock, Neubau Informatik) 1. Termin 6.4.2004

        Inhalt:
        Die Theoretische Informatik beschäftigt sich u.a. mit den folgenden Gebieten:

      • Strukturelle Komplexitätstheorie
      • Kryptographie
      • Graphentheorie
      • Algorithmische Lerntheorie
      • Randomisierte Algorithmen
      • Boolesche Funktionen und Schaltkreise

In diesem Seminar wollen wir uns mit einigen herausragenden Ergebnissen der Theoretischen Informatik beschäftigen, die allesamt in ein oder mehrere der oben aufgezählten Kategorien fallen. Ziel ist es dabei, dass die Seminarteilnehmer möglichst vielseitige und interessante Resultate kennen lernen. Die Vorträge bauen nicht aufeinander auf, sondern jeder Vortrag behandelt ein eigenständiges Thema. In den Vorträgen soll zunächst eine Motivation des Ergebnisses (evtl. mit einer kurzen Einführung in ein Gebiet der Theoretischen Informatik) gegeben werden sowie eine ausführliche Präsentation des Ergebnisses und eine Erläuterung von dessen Bedeutung im Kontext der Theoretischen Informatik erfolgen. Anschließend soll ein Beweis des Ergebnisses präsentiert werden. Hierbei werden wir eine ganze Reihe interessanter, oftmals raffinierter und auch erstaunlicher Techniken kennen lernen. Ein Seminarvortrag kann sich durchaus als Einstieg für eine Studien- oder Diplomarbeit anbieten!

Literatur:

        • Lance Fortnow: My Favorite Ten Complexity Theorems of the Past Decade .Electronic Colloquium on Computational Complexity (ECCC), Technical Report 94-021, 1994.
        • Uwe Schöning: Perlen der Theoretischen Informatik. BI-Wissenschafts-Verlag, Mannheim, 1995.

Praktikum:


Programming Challenges 

Veranstalter:Liskiewicz, Manthey

Termin: Do.16.00-18.00h/ 18.00h - 21.00h, PC-Pool 1 und Seminarraum 21(2.Stock Neubau Informatik)

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, Zeugmann

Form:Oberseminar (3S)

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

Inhalt:

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