This page was taken from an older version of this website.
- Grundstudium:
- Proseminar "Datenstrukturen und
Algorithmen"
- Veranstalter:
- Genther, Weis, Reischuk
- Form:
- Proseminar (2S) (empfohlen ab 3. Semester)
- Vorbesprechung:
- In der ersten Semesterwoche im WS
1997/98. Informationen jederzeit bei den
Veranstaltern.
- Termin:
- Do, 10h-12h, Raum H1/SFS.
- Inhalt:
- Algorithmen und Datenstrukturen bilden das zentrale
Thema der Informatik. Datenstrukturen organisieren
Informationen so, daß effiziente Algorithmen
möglich werden.
Das Proseminar behandelt exemplarisch einige
grundlegende Aspekte. Dazu gehören beispielsweise -
um nur einige zu nennen - Sortieren, Suchen und
Hashing auf Bäumen, Graphen oder Heaps und
randomisierte Verfahren. Ebenso werden die Kosten der
Algorithmen in Bezug auf Laufzeit und Speicherplatz
analysiert.
Die Vorbesprechung und die Vergabe der Vortraege
findet in der ersten Veranstaltung im WS 97/98
statt. Interessierte Studierende werden gebeten, sich
bereits vor Beginn des Semesters bei den Veranstaltern
anzumelden. In die geplanten Vortragsthemen kann bei
dieser Gelegenheit Einblick genommen werden.
- Literatur:
- Ausgewählte Kapitel zu den Themen: Grundlagen von
Algorithmen und Datenstrukturen, Sortieren, Suchen,
Bäume, Graphen aus
- A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data
Structures and Algorithms, Addison-Wesley, 1983
(korrigierte Auflage 1987).
- S. Baase, Computer Algorithms, Addison-Wesley,
1988 (zweite, korrigierte Auflage 1993).
- T.Ottmann, P.Widmayer: Algorithmen und
Datenstrukturen, BI 1993.
- Hauptstudium:
- Algorithmen und Komplexitätstheorie/Formale
Sprachen und Automaten
- Veranstalter:
- Vorlesung: Buntrock
Übung: Jakoby, Weis
- Form:
- Pflichtvorlesung und Wahlpflichtübung (4V+2Ü)
- Termine:
-
- Vorlesung: Mo, 10.15h-11.45h und Do,
12.30h-14.00h, Raum 3, Gebäude 21.
- Übung: Mi, 10h-12h, Raum H1/SFS.
- Inhalt:
- Die Veranstaltung führt in die im Titel genannten
Gebiete der Theoretischen Informatik ein. Ein
Hauptaugenmerk wird dabei sein, Problemklassen zu
finden, die uns in verschiedensten Berechnungs- oder
Beschreibungsmodellen begegnen. Solche Klassen haben
eine besondere Bedeutung. Hierzu zählen die
aus dem Grundstudium bereits bekannten Klassen P und
NP sowie CFL und CSL.
- Effiziente Algorithmen
- Veranstalter:
- Schindelhauer, Reischuk
- Form:
- Vertiefende Vorlesung (2V)
- Termine:
-
- Vorlesung: Mo, 14h-16h, Raum H2/SFS.
- Inhalt:
- Der Entwurf und die Analyse effizienter Algorithmen
steht im Mittelpunkt dieser Veranstaltung. Selbst für
einfache Problemstellungen, wie z.B. das Suchen eines
Wortes in einen Text oder Multiplikation zweier
Zahlen, zeigt sich, daß eine direkte, einfache
Umsetzung in ein Programm weniger effizient ist, als
die Verwendung ausgefeilter Methoden. Zu diesem Zweck
werden verschiedene algorithmische Techniken
vorgestellt, wie z.B. dynamische Programmierung,
branch and bound, Einsatz von Datenstrukturen,
diskrete Fourier-Transformation, Monte-Carlo-,
Las-Vegas-Algorithmen, Derandomisierung.
Dabei werden Problemstellungen aus den Bereichen
- Arithmetik
- Kombinatorik
- Graphtheorie
- Zahlentheorie
- Pattern Matching
betrachtet.
Diese Veranstaltung ist konzipiert für Studenten
des Hauptstudiums, die sich neue Programmier-Techniken
aneignen wollen. Spezielle, über das Grundstudium
hinausgehende, Kenntnisse aus der Mathematik oder der
Theoretischen Informatik werden nicht vorausgesetzt.
- Literatur:
-
- Knuth, The Art of Computer Programming, Vol.1-2,
1968, 1969.
- Aho, Hopcroft, Ullman, The Design and Analysis of
Computer Algorithms, Addison-Wesley, 1974.
- Purdom, Brown, The Analysis of Algorithms,
Holt, Rinehart, Winston, 1984.
- Cormen, Leiserson, Rivest, Introduction to
Algorithms, MIT Press, 1990.
- Sedgewick, Algorithms, Addison-Wesley, 1991.
- Kozen, The Design and Analyses of Algorithms,
Springer, 1991.
- Einführung in die Informationstheorie,
Kodierung und Kryptologie
- Veranstalter:
- Reischuk
- Form:
- Vertiefende Vorlesung (2V)
- Termine:
-
- Vorlesung: Fr, 14h-16h, Raum H1/SFS.
- Inhalt:
- Gegenstand der Informationstheorie ist die Frage, wie
man Information messen und übertragen kann. Eng
verknüpft damit sind Probleme einer effizienten
und sicheren Kodierung, Thema der Kodierungstheorie
und Kryptologie, mit dem sich die Menschheit schon
lange vor der Erfindung von Computern beschäftigt
hat. Vor 50 Jahren wurde von Shannon basierend auf
mathematischer Wahrscheinlichkeitstheorie die moderne
Informationstheorie begründet. Algorithmische
Ansätze sind von Solomonoff und Kolmogorov
entwickelt worden. Durch neue Ergebnisse der
Komplexitätstheorie einerseits und konkrete
Sicherheitsbedürfnisse in globalen Netzen
andererseits hat die Kryptologie in den letzten Jahren
eine stürmische Aufwärtsentwicklung
erlebt. Dieser Aufgabenbereich entwickelt sich zu
einem der Schwerpunkte im Tätigkeitsspektrum von
Informatikern und Mathematikern mit einer Verschiebung
vom militärischen zum kommerziellen Bereich.
Die Vorlesung gibt einen ersten Überblick
über die historische Entwicklung und die
wichigsten Methoden und Ergebnisse in diesem Themenfeld.
- Literatur:
- Einführende Literatur:
- G. Hotz, Algorithmische Informationstheorie,
Teubner 1997.
- S. Roman, Introduction to Coding and Information
Theory, Springer 1997.
- Heise, Quattrocchi, Informations- und
Codierungstheorie, Springer 1983.
- T. Beth, Hess, Wirl, Kryptografie, Teubner 1983.
- A. Beutelspacher, Kryptologie, Vieweg 1991.
- A. Konheim, Cryptografie - a Primer, J. Wiley
1981.
Weiterführende Literatur:
- R. Gallager, Information Theory and Reliable
Communication, 1968.
- N. Abramson, Information Theory and Coding, 1963.
- Csizar, Körner, Information Theory, Academic
Press 1981.
- W. Peterson, E. Weldon, Error Correcting Codes,
1972.
- E. Berlekamp, Algebraic Coding Theory, 1968.
- A. Salomaa, Public-Key Cryptography, Springer
1990.
- G. Brassard, Modern Cyryptology, Springer, 1988.
- D. Kahn, The Codebreakers, 1967.
- C. Meyer, Matyas, A New Dimension in Computer
Data Security - Cryptografie, J. Wiley 1982.
- D. Denning, Cryptographie and Data Security,
Add. Wesley, 1982.
- S. Shaffer, A. Simon, Network Security, Academic
Press 1994.
- M. Li, P. Vitanyi, An Introduction. to Kolmogorov
Complexity and its Applications, Springer 1993.
- Praktische Semesterarbeit "Kryptographische
Protokolle/Didaktik-Software"
- Veranstalter:
- Reischuk, Schindelhauer
- Form:
- Praktische Semesterarbeit
- Termine:
- Mi, 17h-19h, Raum H1/SFS.
- Inhalt:
- Folgende Themenstellungen stehen u.a. zur Wahl
- Kryptographische Protokolle
- sichere Kartenspiele im Internet
- digitale Signatursysteme
- Benutzerschnittstellen für Kryptographiesysteme
- Didaktik-Software
- Visualisierung effizienter Datenstrukturen
- Interaktiver Debugger für formale Sprachen
- graphisch-interaktive Programmierung und
Simulation elementarer Maschinenmodelle wie
z.B.
- Endliche Automaten
- Turing-Maschinen
- Zähler-Automaten
- Keller-Automaten
- Literatur:
-
- Rüdiger Reischuk, Einführung in die
Komplexitätstheorie, Teubner 1990.
- Beutelspacher, Kryptographie, Vieweg, 1994.
- Ingo Wegener, Theoretische Informatik, Teubner, 1992.
- Aho, Sethi, Ullman, Compilerbau, Addison-Wesley, 1988.
- Hauptseminar "Parallele
Algorithmen"
- Veranstalter:
- Jakoby, Reischuk
- Form:
- Hauptseminar (2S)
- Termine:
- Mi, 15h-17h, Raum H1/SFS.
- Inhalt:
- In diesem Hauptseminar soll auf die verschiedenen
Fragestellungen eingegangen werden, die sich im Rahmen
der Entwicklung effizienter paralleler Algorithmen
ergeben. Hierzu zählen unter anderen Probleme der
Rechnerkommunikation, wie
- Broadcasting, oder
- Prozeß-Synchronisation
oder der, den Algorithmen zugrundeliegenden
Rechnermodellen, wie
- Netzwerke,
- Shared Memory Architekturen oder
- Schaltkreise.
Im Rahmen des Seminars soll mit Hilfe aktueller
Veröffentlichungen derartige Fragestellungen und
Lösungsansätze für diese Probleme
vorgestellt werden. Desweiteren sollen effiziente
parallele Algorithmen aus verschiedenen Bereichen
diskutiert werden, wie beispielsweise:
- Graphenalgorithem oder
- Algorithmen im Rahmen des Patternmatching.
- Literatur:
-
- A. Gibbons, W. Rytter, Efficient Parallel
Algorithms
- A. Gibbons, P. Spirakis, Lectures on parallel
computation
- T. Cormen, C. Leiserson, R. Rivest, Introduction
to Algorithms
- Oberseminar Theoretische Informatik
- Veranstalter:
- Reischuk, Buntrock
- Form:
- Oberseminar (3S)
- Termin:
- Di, 16h-19h, Raum 18/SFS.
