HEINZ
NIXDORF
INSTITUT
Universität-GH Paderborn
Theoretische Informatik
AG Meyer auf der Heide
Seminar Dateikomprimierung und Codierung, WS 95/96
Artur Czumaj, Miroslaw Kutylowski
Schedule und Ausarbeitungen
Anmeldung:
per email bei Artur Czumaj
(artur@uni-paderborn.de) bis Ende Oktober.
Hier kann man Artur eine email schicken.
Vorbesprechung:
Mitwoch, 25.10.95, um 17.30 Uhr, C2
Sprechstunden: nach Vereinbarung und zusätzlich wie folgt:
-
Miroslaw Kutylowski
Freitag: 9-11 Uhr, F1.219
zusätzlich direkt nach Vorlesungen in Campus zu erreichen:
Mittwoch, 17.30, C2
Freitag, 15.30, C2
Voraussetzungen:
Vordiplom
Scheinerwerb:
Ausarbeitung und Seminarvortrag
Prüfungsgebiet:
H II, ThI
Parallelveranstaltungen:
Vorlesung Informationstheorie, Codierungen und Kryptographie von M. Kutylowski
Termine:
- Vorbesprechung am Mitwoch, 25.10.95, um 17.30 Uhr, C2
- Anmeldung zum Seminar bis Ende Oktober
- Seminarvorträge im Januar
(ca. 5-6 Treffen, insgesamt 10-12 Vorträge)
Raum:
im F1 Gebäude an der Fürstenallee
Inhaltsübersicht:
- Compaction :
deterministische und randomisierte Algorithmen, untere Schranken
2 Seminarvorträge
- Codierung für Verschicken durch unzuverlässige Netze
1 Seminarvortrag
- Expander-Codierung
2 Seminarvorträge
- Parallele Dateikomprimierung
1 Seminarvortrag
- Berechnung von Superstrings
1 Seminarvorträge
- Mustererkennung für komprimierte Texte
1 Seminarvortrag
- Bildkomprimierung
2 Seminarvorträge
- Deterministic coin tossing und online-Komprimierung
1 Seminarvortrag
Literatur:
D. A. Lelewer und D. S. Hirschberg,
"Data compression",
Computing Surveys 19(3), 1987, 261-296.
M. Sipser und D. A. Spielman,
"Expander codes",
Proc. 35th IEEE Symposium on Foundations of Computer Science (FOCS),
1994, 566-576.
D. A. Spielman,
"Linear-time encodable and decodable eroor-correcting codes",
Proc. 27th ACM Symposium on Theory of Computing (STOC), 1995, 388-397.
L. M. Stauffer und D. S. Hirschberg,
"Parallel text compression",
Technical Report 91-44, University of California, Irvine, January 1993.
Revised.
M. Farach und M. Thorup,
"String matching in Lempel-Ziv compressed strings",
Proc. 27th ACM Symposium on Theory of Computing (STOC), 1995, 703-712.
A. Amir, G. Benson, und M. Farach,
"Let sleeping files lie: Pattern matching in Z-compressed files",
Proc. 5th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1994.
A. Blum, T. Jiang, M. Li, J. Tromp, und M. Yannakakis,
"Linear approximation of shortest superstrings",
Journal of Association for Computing Machinery 41(4), 1994, 630-647.
T. Jiang und M. Li,
"Shortest common superstrings",
Manuscript, 1995.
S. Chaudhuri,
"Sensitive functions and approximate problems",
Proc. 34th IEEE Symposium on Foundations of Computer Science (FOCS),
1993.
P. D. MacKenzie,
"Load balancing requires Omega(log^* n) expected time",
Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 1992.
Weitere Informationen (Termine,...) werden durch email verschickt,
Ausarbeitungen werden durch WWW unter dieser
Adresse zugänglich gemacht.
Ins Netz gesetzt von: Artur Czumaj