This page was taken from an older version of this website.
Lehrveranstaltungen im SS 2004
Grundstudium
Einführung in die
Informatik IV
Übung: Reischuk, Arpe
Form: Vorlesung und Übung, 4. Sem.
Diplom-Studiengang & Bachelor (4V+3Ü)
Termine: Vorlesung: Mi. 8.00h-10.00h,
Raum T1/Transistorium und Fr. 8.00h-10.00h, H1
Übungen:
- Gruppe
1: Mo. 14 -16 h + Do. 11-12 h Seminarraum Minsky
Gruppe 2 : Mo.
12-16 h + Do. 11-12 h Seminarraum Cook + Karp (m. geöffneter
Trennwand)
- Gruppe
3: Mo. 14-16 h Seminarraum 21,
2. Stock Neubau Informatik
Mi. 12-13 h Seminarraum
Cook + Karp (m. geöffneter Trennwand)
- Inhalt:
Grundlagen der Berechenbarkeit:
Maschinenmodelle, Programmiermodelle, primitiv-rekursive und
rekursive Funktionen,
Universelle Maschinen, Churchsche These Entscheidbarkeit,
Aufzählbarkeit, Halteproblem,
Rekursionstheorem, Fixpunktsatz, Satz von Rice
Formale Sprachen:
Formale Grammatiken, Normalformen, kontextfreie und kontextsensitive
Sprachen, Comsky Hierarchie, reguläre Sprachen, reguläre
Ausdrücke, endliche Automaten, Pumping Lemma, Wortprobleme
Komplexität algorithmischer Probleme:
Zeit- und Platzmasse, Programmierung von TM, Simulation, Reduktion,
Komplexitätsabschätzungen, Beschleunigung, untere Schranken,
Zeit- und Platzhierarchien, Nichtdeterminismus sequentielle
Komplexitätsklassen, NP-Vollständigkeit
Erfüllbarkeitsproblem für Boolesche Formeln,
Optimierungsprobleme
Auswahl Lehrbücher
- [Sm94] C. Smith, A Recursive
Introduction to the Theory of Computation, Springer 1994
- [HU94] J. Hopcroft, J. Ullman,
Einführung in die Automatentheorie, Formale Sprachen und
Komplexitätstheorie, Add.Wesley 1994
- [Ha78] M. Harrison, Introduction
to Formal Language. Theory, Add.Wesley 1978
- [Sa98] J. Savage, Models of
Computation, Add.Wesley 1998
- [Re98] R. Reischuk, Komplexitätstheorie,
Band I: Grundlagen, Maschinenmodelle, Zeit- und
Platzkomplexität, Nichtdeterminismus, Teubner 1998
(Hörerschein zum verbilligten Bezug im Sekretariat erhältlich)
- [GJ79] M. Garey, D. Johnson,
Computers and Intractability, Freeman, 1979
Unterlagen zur Vorlesung
(Script, Übungen) können hier
runtergeladen werden (allerdings NUR von Rechnern der Universität)
Algorithmen und
Programmierung
Form: Proseminar (2)
Termine: Vorlesung: Fr. 10.00h-12.00h, Seminarraum
Informatik 1 (Neubau Informatik)
Inhalt:
Ziel des Proseminars ist
eine integrierte Behandlung von Algorithmen und effizientem
Programmieren. Ausgangspunkt ist ein konkretes Problem (z.B. vom ACM-Programmierwettbewerb
2003) . Dazu soll eine
Lösung erarbeitet und programmiert werden. Im Vortrag sollen das
Problem, der verwendete Algorithmus und wie er auf das Problem angewandt
wurde und das Programm vorgestellt werden. Wir werden unter Anderem
Beispiele für
- Erreichbarkeit in Graphen,
- Berechnung kürzester
Wege,
- Flussprobleme,
- Berechnung konvexer
Hüllen,
- dynamische Programmierung
und
- vieles mehr
behandeln.
Literatur:
- A. Aho, J. Hopcroft,
J. Ullman: Design and Analysis of Computer Algorithms. Addison Wesley,
1978
- T. Cormen, C.
Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. MIT Press,
2001
- S. Skiena: The
Algorithm Design Manual. Springer, 1998
Program Verification
Veranstalter: Völzer
Form: Proseminar Bachelor-Studiengang (2)
Termine: Vorlesung: Mo.
10.00h-12.00h, Seminarraum 21, 2. Stock (Neubau Informatik)
Inhalt:
Exercises in program correctness and presentation
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
- Form: Pflichtvorlesung und Wahlpflichtübung
(4V+2Ü)
-
Termine: Vorlesung: Di, 12.00h -
14.00h und Fr, 14.00h - 16.00h, Seminaraum Informatik 4 (Neubau
Informatik)
- Übung: Do, 08.00h - 09.30h, Raum R1, R3 und H2 .
-
- Inhalt:
Die Vorlesung wird sich im ersten Teil mit dem Entwurf und der Analyse
von synchronen parallelen Algorithmen beschäftigen. Dabei
untersuchen wir grundlegende arithmetische Operationen, fundamentale
Graphalgorithmen und paralleles Sortieren.
Wir behandeln die Beschleunigung und Effizienz der
vorgestellten Algorithmen. Darüber hinaus führen wir Modelle
für paralleles Rechnen ein und untersuchen die grundlegenden
parallelen Komplexitätsklassen.
Im zweiten Teil der Vorlesung studieren wir asynchrone bzw.
verteilte Berechnungen. Wir exemplifizieren die grundlegend neuen
Fragenstellungen (neu in Bezug auf den synchronen Fall) und stellen
mathematische Modelle zur Beschreibung von verteilten Systemen
vor.
Abschliessend studieren wir temporale Logiken für
konkurrente Systeme.
Es wird von Woche zu Woche ein Übungsblatt geben, das
dann in der Übung besprochen wird. Die Bearbeitung der Aufgaben
ist zum Scheinerwerb obligatorisch. Am Semesterende wird eine
Rücksprache über die Aufgaben stattfinden.
Auswahl Lehrbücher
- J. JaJa, An Introduction to Parallel Algorithms,
Addison-Wesley, 1992.
- N. Lynch, Distributed Algorithms, Morgan Kaufmann 1996
- Z. Manna and A. Pnueli, The Temporal Logic of Reactive
and Concurrent Systems, Springer 1992
- W. Reisig, Elements of Distributed Algorithms : Modeling
and Analysis with Petri Nets, Springer 1998
Wahlpflichtvorlesungen:
Data Mining
-
Veranstalter: Liskiewicz
-
Form: Vertiefende Vorlesung (2V)
-
Termine: Vorlesung: Do, 14.00h - 16.00h, ab sofort: Seminarraum 21, 2. Stock
Neubau-Informatik!!!
-
-
Inhalt:
-
Die Fähigkeit lernen zu
können wurde für Computer bereits als Ziel formuliert,
nachdem dem der erste praktische Einsatz eines Rechners gelungen war.
Für Alan Turing war die Lernfähigkeit eines Computers die
wichtigste Intelligenzleistung.
In der Vorlesung werden wir
die wichtigsten grundlegenden Entwicklungen und Erkenntnisse, die zur
Umsetzung dieses anspruchsvollen Zieles in den vergangenen 50 Jahren
verfolgt bzw. gewonnen wurden, unter einem einheitlichen Gesichtspunkt
behandeln und aktuelle Anwendungen im Data Mining aufzeigen.
Im ersten Teil der Vorlesung
spezifizieren wir zunächst allgemeinste Anforderungen an die
Modellierung des intuitiven Begriffes ``Lernen''. Danach stellen wir
die wichtigsten Lernmodelle exemplarisch vor. Es folgen vertiefende
Untersuchungen, die insbesondere die Frage klären, unter welchen
Bedingungen ein angestrebtes Lernziel erreicht werden kann.
Abschließend wird das Problem der Wissensentdeckung in
großen Datenbanken behandelt (Data Mining).
-
Zur Vorlesung wird ein Skript
bereitgestellt.
Modellierung und Spezifikation
Verteilter Systeme
-
Veranstalter: Völzer
-
Form: Vertiefende Vorlesung
-
Termine: Vorlesung: Mo, 12.00h - 14.00h,
Seminarraum 21, 2. Stock (Neubau Informatik)
-
Inhalt:
Modellierung und Spezifikation eines Systems sind Grundlagen eines
korrekten Systementwurfs. Ist ein Modell erstellt, so kann es
analysiert werden, ist das Modell hinreichend formal, so kann die
Analyse durch Rechner unterstützt, oft sogar vollautomatisch
durchgeführt werden.
Wir lernen in der Vorlesung die speziellen Herausforderungen bei der
Modellierung und Analyse verteilter Systeme kennen sowie spezielle
Techniken, um diesen Herausforderungen zu begegnen. Die Modellierung
basiert auf Petrinetzen, die in der Praxis unter anderem zur
Modellierung von Hardware, Arbeits- und Produktionsabläufen sowie
von Geschäftsprozessen eingesetzt werden. Petrinetze sind in Form
von Aktivitätsdiagrammen auch Teil der Spezifikationssprache UML.
Zur Spezifikation werden wir unter anderem temporale Logik verwenden.
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
- Datenstrukturen,
- geometrische Algorithmen,
- Graphenalgorithmen,
- parallelen und verteilen Systemen,
- Online-Algorithmen und
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
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.
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 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.
