This page was taken from an older version of this website.
Lehrveranstaltungen im SS 2002
Grundstudium:
-
Einführung in die Informatik II
Algorithmenentwurf, Datenstrukturen, Programmierung
-
Veranstalter:
Reischuk
Form:
-
Vorlesung und Übung (4V+3Ü)
-
Termine:
-
Vorlesung: Di, 8.00h-10.00h Raum H1 und
-
Fr, 10.00h-12.00h, H1.
-
Übungen: Mo 14 -16/16-18h H2 / R1 und Mi 10-11h, T1, R3,
H4a, S3b
-
-
Themen:
Elementare algorithmische Probleme:
Suchen, Mischen, Sortieren,
Suche in Graphen: DFS, BFS, spannende Bäume
Topologisches Sortieren, Transitive Hülle,
Zusammenhang
Wege- und Flußprobleme in Netzwerken
String Matching
Geometrische Algorithmen
Algorithmenentwurf und Analyse:
Greedy-Strategien, Divide-and-Conquer
Dynamisches Programmieren, Sweeping Line
Randomisierung
Effiziente Datenstrukturen:
Balanzierte Bäume, Heaps, Hashing
Methodiken in der Programmierung:
Prozedural, objektorientiert
Empfohlene Literatur
Begleitende Lehrbücher
-
T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen,
Spektrum 2002
-
S. Skiena, The Algorithmic Design Manual, Springer
1998
-
A. Aho, J. Hopcroft, J. Ullman, Design and Analysis
of Computer Algorithms, Addison-Wesley 1978
-
T. Cormen, C. Leiserson, R. Rivest, Introduction
to Algorithms, MIT-McGraw Hill 1990
-
N. Wirth, Algorithmen und Datenstrukturen - mit
Modula 2, Teubner 1986
-
D. Ratz, J. Schefler, D. Seese, Grundkurs Programmieren
in Java, Ban I, Der Einstieg in Programmierung und Objektorientierung,
Hauser 2001
-
M. Campione, K. Walrath, A. Hunt, The Java Tutorial,
Addison-Wesley 2001
Ergänzende Literatur
Einführung in die Informatik
IV
Veranstalter:
Reischuk
Form:
-
Vorlesung und Übung (4V+3Ü)
-
Termine:
-
Vorlesung: Mi, 8.00h-10.00h Raum T1/Transistorium und
-
Fr, 8.00h-10.00h, H1.
-
Übungen: Mo 14 -16/16-18h und Do 13-14h, 17-18h
-
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
-
Algorithmen und Programmierung
-
Veranstalter:
-
Liskiewicz,
Siebert
-
Form:
-
Proseminar (2)
-
Termine:
-
Vorlesung: Do., 14.00h-16.00h H3/SFS
Inhalt:
Ziel dieses Proseminars ist eine integrierte Behandlung von Algorithmen
und effizientem Programmieren.
Ausgangspunkt ist ein konkretes Problem. Im Rahmen des
Proseminars soll dan anhand bekannter Algorithmen ein
Lösung für dieses Problem erarbeitet und programmiert werden.
Im Vortrag sollen dann das Problem, der verwendete Algorithmus und das
konrete Programm zur Lösung des Problems vorgestellt werden.
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.
-
Buntrock
-
Form:
-
Proseminar Bachelor-Studiengang (2)
-
Termine:
-
Vorlesung: Fr., 8.00h-10.00h H2
-
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.
Please feel free to use my e-mail for any questions. It is also possible
to arrange a meeting before the run starts. G.
Buntrock
Hauptstudium:
-
Parallele und Verteilte Systeme
-
Veranstalter:
-
Zeugmann
-
Übung: Zeugmann, Jakoby
-
Form:
-
Pflichtvorlesung und Wahlpflichtübung (4V+2Ü)
-
Termine:
-
Vorlesung: Di, 12.00h - 14.00h Raum 3/Haus 21 und Fr, 14.00h - 16.00h,
R3/Haus 21.
-
Ü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:
-
Zeugmann
-
Form:
-
Vertiefende Vorlesung (2V)
-
Termine:
-
Vorlesung: Do, 14.00h - 16.00h, Raum H1/SFS.
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.
-
Interaktive Protokolle: Arthur-Merlin-Spiele und andere
-
Veranstalter:
-
Jakoby
-
Form:
-
Vertiefende Vorlesung
-
Termine:
-
Vorlesung: Mo, 12.00h - 14.00h, Raum H1/SFS.
Inhalt:
Die Idee eines Arthur-Merlin Spiels kann durch folgende Situation am
Hofe dieses mystischen Königs beschrieben werden:
König Arthur (A), ein gerechter König, regiert England mit
Hilfe seines allwissenden Ratgebers Merlin (M). Oft treffen die beiden
mystischen Gestalten aufeinander und diskutieren über vielerlei anstehende
Fragen. Hierbei versucht Merlin Arthur immer wieder von seiner Allwissenheit
mit Hilfe von Frage- und Antwortspielen zu überzeugen.
Diese Spiele haben den folgenden Ablauf: Arthur stellt mit Hilfe von
randomisierten Bits sukzessive verschiedene Fragen, die von Merlin auf
die bestmögliche Art und Weise beantwortet werden. Merlin hat bei
einem solchen Spiel eine Gewinnstrategie, wenn es ihm gelingt Arthur mit
einer Wahrscheinlichkeit von 2/3 zu überzeugen.
Basierend auf dieser Idee läßt sich nun eine neue Form probabilistischer
Maschinen beschreiben, bei der es möglich ist, die Fehlerwahrscheinlichkeit
beliebig zu verkleinern. In der Vorlesung Arthur-Merlin Games und andere
Interaktive Protokolle werden wir unter anderem untersuchen inwieweit die
Anzahl der Interaktionen zwischen Arthur und Merlin die Berechnungskapazität
derartiger Maschinen beeinflußt.
Weitere Modelle, die in der Vorlesung vorgestellt werden sind: Interaktive
Beweissysteme, Zero-Knowledge Beweiser und das Modell von Games-Against-Nature.
Skript
-
Seminare:
-
Komplexität und Algorithmen
-
Veranstalter:
-
Liskiewicz
-
Form:
-
Hauptseminar (2S)
-
Termine:
-
Mo, 16.00h - 18.00h, Raum H3/SFS
-
Inhalt:
In diesem Seminar diskutieren wir die aktuellen Forschungsergebnisse
der algorithmischen Komplexitätstheorie. Wir werden unter anderem
die folgenden Themen behandeln:
Effiziente Algorithmen für Quantenrechner,
Interaktive Protokolle
und der Satz von Shamir,
Approximationsalgorithmen
für NP-vollständige Probleme,
"Zählende Komplexitätsklassen"
Literatur:
-
Originalarbeiten nach Absprache und Themenstaltung
-
Kryptologie
-
Veranstalter:
-
Zeugmann, Bläser
-
Form:
-
Hauptseminar (2S)
-
Termine:
-
Do, 16.00h - 18.00h, Raum H3/SFS.
Inhalt:
Kryptologie ist die Wissenschaft von Geheimschriften und ihrer unberufenen
Entzifferung, die bis vor wenigen Jahren noch überwiegend im Verborgenem
betrieben wurde. Mit der Entwicklung moderner globaler Netze und den damit
verbundenen Sicherheitsbedürfnissen hat die Kryptologie in den letzten
Jahren enorm an Bedeutung gewonnen. Die potentielle kommerzielle Verwertbarkeit
kryptographischer Verfahren stimulierte einen gewaltigen Aufschwung öffentlicher
kryptographischer Forschungen, die zu einer Fülle hoch interessanter
und zum Teil mehr als verblüffenden Resultaten führte.
Inhalt des Seminars sind aktuelle Arbeiten ueber moderne Kryptosysteme.
Im Vordergrund stehen dabei vor allem kryptographische Protokolle, die
weit ueber das verschluesselte Versenden von Nachrichten hinausgehen.
Interessenten koennen ab sofort die Themenliste einsehen und ein Vortragsthema
erhalten.
-
Praktika
-
Effizientes Problemlösen und Programmieren
Veranstalter:
Form:
Termin:
Do. 18.00h - 21.00h, Raum H3 + Do. 16.00 - 18.00h, Raum H4(Rechnerpool)/SFS.
Oberseminar Theoretische Informatik
-
Veranstalter:
-
Reischuk, Zeugmann
-
Form:
-
Oberseminar (3S)
-
Termin:
-
Inhalt:
-
Die Mitglieder und Studenten der Arbeitsgruppe Theoretische Informatik
-
tragen über aktuelle Forschungsresultate vor.