This page was taken from an older version of this website.
Lehrveranstaltungen im WS 01/02
Grundstudium:
-
Effiziente Algorithmen
-
Veranstalter:
-
Buntrock,
-
Form:
-
Proseminar (2S)
-
Termine:
-
Mi, 16.00h - 18.00h, Raum H2/SFS.
Inhalt:
- Effiziente Algorithmen bilden ein zentrales Thema der Informatik. Mit
dem Leistungszuwachs der Computer (etwa alle 18 Monate verdoppelt sich
zur Zeit deren Leistung) werden die Anwendungsbereiche und Datenberge immer
größer, so daß effiziente Algorithmen eine immer wichtigere
Rolle spielen. So bemerken wir, daß die Verdopplung der Leistung
nur für linear zeitbeschränkte Algorithmen eine Verdopplung der
Anwendungsbereiche zuläßt. Linear zeitbeschränkte Algorithmen
sind jedoch meist nicht zu erwarten.
Wir werden Themen aus den folgenden Bereichen anbieten:
-
Pattern Matching Verfahren
-
Algorithmen für Graphprobleme&
-
Algorithmen für geometrische Problemstellungen
-
Sortierverfahren
-
Primzahltests
-
Schnelle Multiplikation ganzer Zahlen
-
Schnelle Matrizenmultiplikation/li>
Die Vorbesprechung und die Vergabe der Vorträge findet in der ersten
Veranstaltung im WS 01&02 statt. Interessierte Studierende können
sich bereits vor Beginn des Semesters bei den Veranstaltern informieren
und in die geplanten Vortragsthemen Einblick nehmen.
-
Literatur:
-
Ausgewählte Kapitel zu den Themen: Grundlagen von Algorithmen und
Datenstrukturen, Sortieren, Suchen, Bäume, Graphen aus/dt>
-
Aho, Hopcroft, Ullman: The Design And Analysis of Computer Algorithms,
Addison-Wesley, 1974
-
Sara Baase: Computer Algorithms, Addison-Wesley, 1993
-
Motwani, Raghavan: Randomized Algorithms, CUP, 1995
-
R. Sedgewick: Algorithmen, Addison-Wesley, 1992
Modellierung in der Informatik
Veranstalter:
Buntrock,
Form:
Proseminar (2S)
Termin:
Mi, 14.00h-16.00h,
Raum H1/SFS
Inhalt:
Wir beschäftigen uns in diesem Proseminar mit Modellierungen verschiedener
Fragestellungen.
-
Aufwandsklassen
Stets sind wir an Aufwandsfragen interessiert: Wie lange dauert das?
Wieviel Speicher benötigt das? Die Informatiker haben hierzu eine
präzise Notation, die in diesem Vortrag eingeführt und motiviert
werden soll.
Literartur: Donald E. Knuth: Big Omicron and Big Omega and Big
Theta
-
Rechnen mit DNA-Molekülen
Adleman hat 1994 in einem aufsehenerregenden Experiment eine Aufgabe
des Travelling-Salesman-Problems mit Hilfe von DNA-Molekülen gelöst.
In diesem Vortrag sollen die grundsätzliche Methoden von Adleman vorgestellt
werden.
Literatur: Gheorghe Paun, Grzegorz Rozenberg, Arto Salomaa: DNA
Computing: New Computing Paradigms. Texts in Theoretical Computer Science.
An EATCS Series. Springer 1998.
-
Lindenmayer hat Ende der 60er Jahre ein System entworfen zur Simulation
des Zell- und Pflanzenwachstums durch formale Ersetzungssysteme, die heute
nach ihm benannten Lindenmayer-Systeme. In dem Vortrag sollen einige Beispiele
und Anwendungen vorgestellt werden.
Literatur: Prusinkiewicz, Hammel, Hanan, Mech: Visual Models
of Plant Development. In: Grzegorz Rozenberg, Arto Salomaa: Handbook of
Formal Language I, Springer 1997.
-
Rechnen mit Schaltkreisen
Mit booleschen Funktionen werden in Schaltkreisen Berechnungen dargestellt.
Bereits das Berechnen der Addition setzt hier interessante Techniken um,
wenn es denn auch schnell gehen soll.
Literatur: Wegener: Complexity of Boolean Functions. Teubner
1987.
-
Folgen ohne Kubische Sequenzen --- Folgen ohne Quadrate
Thue untersuchte die Möglichkeiten der reinen Symbolmanipulationen.
Diese Manipulationen bilden heute die Grundlage aller formalen Ableitungen
und Berechnungen in der digitalen Welt. Er stieß dabei auf interessante
Eigenschaften von unendlichen Zeichenreihen.
Literatur: Konrad Jacobs: Einführung in die Kombinatorik.
Walter de Gruyter 1983.
-
Verbandstheorie: Darstellungen und Beispiele
Wir kennen den Mengenverband oder den Verband der Teiler einer Zahl.
In diesem Vortrag wollen wir uns einführen lassen in die Verbandstheorie.
-
Kryptographische Protokolle
Die Kryptographie ist unzweifelhaft ein zentrales und wichtiges Thema.
Hier soll es nicht um die Methode der Verschlüsselung selbst gehen
sondern, wie diese geeignet eingesetzt werden können um verschiedene
Dinge zu modllieren: So sollen Protokolle für den Münzwurf
über das Internet und das Knobeln am Telefon vorgestellt werden.
-
Der Satz vom Diktator
In verschieden Bereichen müssen wir "gerecht entscheiden". Sollen
beispielsweise mehrere Jobs von einer Maschine bearbeitet werden, so wollen
wir hier gerecht vorgehen. Manchmal lohnt es sich die Grundlagen
hier genauer zu betrachten. Wir betrachten hier einen berühmten
mathematischen Satz aus dser Theorie der sozialen Entscheidungen.
Literatur: Konrad Jacobs: Einführung in die Kombinatorik.
Walter de Gruyter 1983.
-
Grundlagen zum Matching oder der Heiratssatz und seine Verwandten
Matchingprobleme sind besondere Zuordnugsprobleme. Meist hat
man den Objekten einer Menge jeweils einen Gegenstand einer anderen Menge
in eindeutiger Weise zuzuordnen. Solche Zuordnungen werden gelegentlich
auch Verheiratunegn genannt. Oft können aus bestimmten Eigenschaften
der Problemstellung qualitative Aussgen über mögliche Verheiratungen
gewonnen werden.
Literatur: Konrad Jacobs: Einführung in die Kombinatorik.
Walter de Gruyter 1983.
Hauptstudium:
Pflichtvorlesungen:
-
Algorithmen, Komplexitätstheorie und Formale Sprachen
-
Veranstalter:
-
Vorlesung: Zeugmann
-
Form:
-
Pflichtvorlesung
im Bereich Informatik III (4V) Wahlpflichtübung (2Ü)
-
Termine:
-
Vorlesung: Mi, 8.00h-10.00h und Fr, 8.00h-10.00h, Raum R3/21.
-
Übungen:
Jakoby,
Bläser
-
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
-
Programmiersprachen
-
Veranstalter:
-
Zeugmann
-
Form:
-
Pflichtvorlesung im Bereich Informatik I (2V)
-
Termine:
-
Vorlesung: Fr, 14.00h
- 16.00h, Raum R3/21.
Inhalt:
Die Vorlesung behandelt allgemeine Grundlagen von Programmiersprachen
und deren Verknüpfung mit realen Computern. Dabei wird besonderer
Wert auf die fundamentalen Konzepte des Entwurfs von Programmiersprachen
gelegt.
Wir beginnen mit einer Retrospektive der Entwicklung weit verbreiteter
bzw. in ihrem Entwurf bedeutender Programmiersprachen, wobei besonderer
Wert auf die unterschiedlichen Entwurfsansätze und ihrer Vor- bzw.
Nachteile gelegt wird.
Danach behandeln wir die grundlegenden Konzepte zur Beschreibung der
Syntax und Semantik von Programmiersprachen.
Im Hauptteil der Vorlesung studieren wir detaillierter die Entwurfsprinzipien
imperativer, funktionaler, logischer und objektorientierter Programmiersprachen.
Zur Vorlesung wird ein Skript erstellt.
Literatur:
-
R. W. Sebesta, Concepts of Programming Languages, Bejamin/Cummings Publ.,
1992
-
J. M. Mitchel, Foundations of Programming Languages, MIT Press 1996
-
Wahlpflichtvorlesungen:
Parallele Algorithmen
-
Veranstalter:
-
Form:
-
Vertiefende Vorlesung
im Bereich Informatik III (2V)
-
Termine:
-
Fr. 12.00h-14.00h,
Raum H1/SFS.
-
Skript:
-
Inhalt:
Diese Vorlesung gibt eine Einführung
in das Gebiet effizienter paralleler Algorithmen und
stellt Techniken zur effizienten Parallelisierung
vor. Diese werden anhand einer Sammlung
von effizienten parallelen Algorithmen vorgestellt.
Verschiedenartige Parallelrechner-Architekturen
wie Netzwerke, Shared-Memory-Architekturen
oder über einen Bus verbundene Systeme
verlangen angepaßte Algorithmen. Hierzu
werden Modelle für solche Architekturen
eingeführt und verglichen. Hierbei spielen auch
Probleme wie Synchronisation oder Nebenläufigkeit
eine wesentliche Rolle.
Eine effiziente parallele Umsetzung von Problemen
ist oft nicht möglich. Ursachen und Folgen
werden mit Methoden der Komplexitätstheorie
diskutiert.
Literatur:
-
John H. Reif, Synthesis of Parallel Algorithms
-
F. Thomson Leighton, Introduction to Parallel
Algorithms and Architectures
-
Joseph JaJa, An Introduction to Parallel Algorithms
-
Michel J. Quinn, Algorithmenbau und Parallelcomputer
-
Alan Gibbons, Wojciech Rytter, Efficient Parallel
Algorithms
-
Alan Gibbons, Paul Spirakis, Lectures on Parallel
Computation
-
Formale Sprachen in der Biologie
Veranstalter:
-
Form:
-
Vertiefende Vorlesung im Bereich Informatik III und Nebenfach Bioinformatik(2V)
-
Termine:
-
Vorlesung: Do, 15.00h - 17.00h, Raum H3/SFS.
Inhalt:
Das menschliche Genom wird durch ca. 3 Milliarden Basenpaare beschrieben.
Offenbar sind formale Beschreibungen lebender Objekte in der Biologie immer
noch erheblich komplexer als solche in der Informatik. Objekte in dieser
Größenordnung können nur mit Programmen verarbeitet werden.
Die biochemischen Mechanismen sind aus informatischer Sicht zwar kompliziert
aber doch in vielen Fällen formal spezifizierbar und dadurch in unseren
Modellen abbildbar. Umgekehrt erlauben verschiedene biochemische Strukturen
die Abbildung informatischer Konzepte, so dass Berechnungen im Reagenzglas
durchführbar sind. Ein wichtiges Buch zu diesem Thema ist hier [PRS98].
In der Vorlesung werden solche Methoden vorgestellt.
In Ähnlicher Weise stellen wir auch formale Modellbildungen aus
den Bereichen Proteinfaltung und Phylogenie vor. Schließlich gehen
wir auf die schon klassisch gewordenen und in der modernen Bildverarbeitung
oft eingesetzten Methoden des Abbildens von Wachstumsmechanismen in Formale
Text-, Bild- und 3-D-Daten ein: die Lindenmayer-Systeme. Wir benutzen hier
unter anderem [Fer94,RS80].
Literaturhinweise:
-
[Fer94]Henning Fernau, Iterierte Funktionen, Sprachen und Fraktale, B.I.
Wissenschaftsverlag, Mannheim, Wien, Zürich, 1994
-
[PRS98]Gheorghe Puaun, Grzegorz Rozenberg, and Arto Salomaa, DNA Computing:
New Computing Paradigms, Texts in Theoretical Computer Science. An EATCS
Series. Springer, 1998
-
[RS80] Grzegorz Rozenberg and Arto Salomaa, The Mathematical Theory of
{L} Systems, Academic Press, New York, 1980
-
Kryptologie
-
Veranstalter:
-
Form:
-
Vertiefende Vorlesung im Bereich Informatik III (2V)
-
Termine:
-
Vorlesung: Di, 08.00h - 10.00h, Raum H1/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.
Die Vorlesung wird zunächst einen Einblick in die klassischen Zwei-Weg
Kryptosysteme vermitteln und dabei die Grundlagen der Kryptographie und
Kryptanalyse legen.
Anschliessend wenden wir uns kurz der Theorie fehlertoleranter effizienter
Kodes zu, ohne die eine brauchbare Übertragung digitaler Daten nicht
realisierbar ist.
Im Hauptteil der Vorlesung werden moderne Kryptosysteme mit öffentlichen
Schlüsseln dargestellt, Verfahren für digitale Unterschriften
behandelt und weitere krytographische Anwendungen diskutiert. Dabei gehen
wir insbesondere auf die diesen Verfahren zugrunde liegenden Ergebnisse
der Komplexitätstheorie, der Kombinatorik und der Theorie der Pseudorandomisierung
ein.
Zur Vorlesung wird ein Skript erstellt.
Literatur:
-
S. Roman, Introduction to Coding and Information Theory, Springer 1996
-
F. Bauer, Kryptologie, Methoden und Maximen, Springer 1991
-
A. Salomaa, Public-Key Cryptography, Springer 1990
-
O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudorandomness,
Springer 1999
-
Speicherung und Komprimierung Multimedialer Daten
-
Veranstalter:
-
Liskiewicz
-
Form:
-
Vertiefende
Vorlesung im Bereich Theoretische Informatik, 7. + 8. Semester, sowie im
Nebenfach Medieninformatik (2V + 2 Ü)
-
Termine:
-
Mo. 10.00h-12.00h, Raum H1/SFS.
-
Übung: (optional)
-
Di. 10.00h-11.00h, Raum H1/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.
-
Seminare:
-
Datenbanken und XML
Veranstalter:
Buntrock,
Linnemann,
Kempa
-
Form:
-
Hauptseminar (2S)
-
Termin:
-
Mo, 16.00h-18.00h, IFIS Seminarraum, Osterweide 8
-
Beginn:
-
22. Oktober 2001, 16 c.t.
Achtung: Am 22.10.2001 um 16 h
c.t. beginnt im IfIs, Osterweide 8, Raum 16, das Seminar mit einer
Vergabe der noch offenen Themen!
-
Themen:
-
Dieses Seminar beschäftigt sich mit aktuellen Forschungsthemen der
Datenbankwelt. Den Schwerpunkt bildet dabei neben grundlegenden Entwicklungen
die Modellierung von strukturierten und multimedialen Dokumenten, wie sie
z.B. im WWW vorkommt. Es sind folgende Themen zu vergeben, deren Sortierung
nicht der Vortragsreihenfolge entspricht:
-
Type-Checking OQL Queries in the ODMG Type Systems
-
Information Gathering in the World Wide Web: The W3QL Query Language and
the W3QS System (bereits in Bearbeitung)
-
Quilt: An XML Query Language for heterogeneous Data Sources(bereits
in Bearbeitung)
-
WebOQL: Restructering Documents, Databases, and Webs
-
Efficiently Publishing Relational Data as XML Documents (bereits
in Bearbeitung)
-
Efficient Evaluation of XML Middle-ware Queries
-
Efficient Filtering of XML Documents for Selective Dissemination of Information
-
Unambiguous Regular Expressions and SGML Document Grammars
-
XML und Verschlüsselung (bereits in Bearbeitung)
-
XML Data Binding
-
Praktika:
-
Effizientes Problem lösen und programmieren
-
Veranstalter:
-
Liskiewicz,
Siebert
-
Form:
-
Termin:
-
Do, 17.00h - 20.00h, Raum H3 + H4(Rechnerpool)/SFS.
-
Anmeldung: bis 1.10.2001
-
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.
-
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, H3/SFS
-
Inhalt:
-
Die Mitglieder und Studenten der Arbeitsgruppe Theoretische
-
Informatik tragen über aktuelle Forschungsresultate vor.