This page was taken from an older version of this website.
- Grundstudium:
- Einführung in die Informatik IV
- Veranstalter:
- Vorlesung: Reischuk
- Übung: Schindelhauer
- Form:
- Vorlesung und Übung (4V+3Ü)
- Termine:
- Vorlesung: Mi und Fr, 8h - 10h, Hörsaal H1, Turm
- Übung:
- Gruppe 1: Mo, 10h - 12h, Raum H1/SFS, Do, 14h - 15h, Raum H3/SFS
Gruppe 2: Mo, 16h - 18h, Raum H1/SFS, Do, 11h - 12h, Raum H2/SFS
- Gruppe 3: Mo, 16h - 18h, Raum H2/SFS, Do, 14h - 15h, Raum H3/SFS
- 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, Chomsky 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
- Proseminar "Effiziente Schaltkreise und VLSI-Algorithmen"
- Veranstalter:
- Jakoby
- Form:
- Proseminar (2S) (empfohlen ab 3. Semester)
- Termin:
- Do, 15h - 17h, Raum H3/SFS.
- Inhalt:
- Schaltkreise bestehen aus der Kombination einer kleinen Menge von Basisfunktionen,
die binäre Informationen verarbeiten. Sie bilden das Fundament jedes
Rechners. Zur Implementierung einer gewünschten Funktionalität
gibt es immer mehrere Entwurfsmöglichkeiten.
- Als Maße für die Effizienz eines Schaltkreises werden dessen
Tiefe und Größe untersucht: Die Tiefe, definert durch den längsten
Weg, ist ein Maß für die Berechnungsdauer der gewünschten
Funktionen. Die Größe korreliert mit dem Flächenverbrauch
im Layout.
- Durch die zunehmende Integration im Chip-Design haben sich die Entwurfsmethoden
drastisch verändert. Sogenannte VLSI-Algorithmen (very large scale
integrated circuits) positionieren die Bausteine eines Schaltkreises
auf den Knotenpunkten eines Gitters. Daher ist der klassische Schaltkreisentwurf
nicht ohne weiteres übertragbar.
- Das Proseminar behandelt exemplarisch grundlegende Aspekte von Schaltkreisen
Boolescher Funktionen und des VLSI-Entwurfs. Des weiteren werden Techniken
vorgestellt, die Schranken im Schaltkreisentwurf (die Unmöglichkeit
besonders effizienter Schaltkreisrealisation), beweisen.
- Weitere Informationen und Anmeldungen:
- bei der Vorbesprechung: (in der ersten Vorlesungswoche) Donnerstag,
15.4.1999, 15.00 Uhr, H3/SFS
- persönlich bei Andreas Jakoby (SFS Raum 4)
- oder per e-mail: jakoby@tcs.mu-luebeck.de
- Literatur:
- Ingo Wegener, Effiziente Algorithmen für grundlegende Funktionen,
B.G. Teubner, 1989
- Ingo Wegener, The Complexity of Boolean Functions, Wiley-Teubner
Series in Computer Science, 1987
- Jeffrey D. Ullman, Computational Aspects of VLSI, Computer Science
Press, 1983
- Hauptstudium:
- Pflichtvorlesungen:
- Parallele und Verteilte Systeme, Logik
- Veranstalter:
- Vorlesung: Reischuk,
Liskiewicz
- Übung: Genther
- Form:
- Pflichtvorlesung und Wahlpflichtübung (4V+2Ü)
- Termine:
- Vorlesung: Mi, 15h - 17h und Fr, 14h - 16h, Raum H1/SFS.
- Übung: Di, 17h - 19h, Raum H2/SFS.
- Inhalt:
- Logische Kalküle, Temporale Logiken, Petri-Netze, Synchronisationsprobleme
und logisches Schliessen in Verteilten Systemen, parallele Programmier-
und Maschinenmodelle, Verifikation paralleler Programme, Entwurf paralleler
Algorithmen, Beschleunigung und Effizienz, Parallele Komplexitätsklassen
- Auswahl Lehrbücher
- [B93] M. Ben-Ari, Mathematical Logic for Computer
Science, Prentice Hall 1993
- [MP92] Z. Manna, A. Pnueli, The Temporal Logic of Reactive and Concurrent
Systems - Specification, Springer 1992
- [L96] Lynch, Distributed Algorithms, Morgan
Kaufmann 1996
- [AG89] Almasi, Gottlieb, Highly Parallel Computing, Benjamin/Cummings
1989
- [S90] Stone, High-Performance Computer Architecture,
Add. Wesley 1990
- [J92] JaJa, An Introduction to Parallel
Algorithms, Add. Wesley 1992
- Wahlpflichtvorlesungen:
- Kryptologie
- Veranstalter:
- Reischuk
- Form:
- Vertiefende Vorlesung (2V)
- Termine:
- Vorlesung: Mo, 12h - 14h, Raum H1/SFS.
- Inhalt:
- Die Kryptologie beschäftigt sich mit der Frage, wie man Information
verschlüsseln, digital authentisieren und über unsichere Kanäle
übertragen kann.
- Mit dem Problem der Verschlüsselung hat sich die Menschheit schon
lange vor der Erfindung von Computern beschäftigt. Die moderne Kryptologie
besitzt mehrere Aspekte:
- 1.) Information zu messen, Gegenstand der Informationstheorie, die
vor etwa 50 Jahren von Shannon begründet wurde basierend auf mathematischer
Wahrscheinlichkeitsrechnung, während algorithmische Ansätze von
Solomonoff und Kolmogorov entwickelt wurden,
- 2.) fehlertolerante effiziente Kodes zu entwickeln, Gegenstand der
Kodierungstheorie,
- 3.) Verschlüsselungssverfahren zu konstruieren, die selbst bei
Einsatz von Hochleistungsrechnern nicht mit akzeptablem Aufwand gebrochen
werden können (algorithmische Komplexität) bzw.
- 4.) für ein gegebenes kryptografisches Protokoll mit Hilfe von
zahlentheoretischen, algebraischen oder kombinatorischen Methoden Algorithmen
zu entwickeln, die in der Lage sind, derartig chiffrierte Nachrichten zu
entschlüsseln.
- 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.
- Einführende Literatur
- [G68] R. Gallager, Information Theory
and Reliable Communication, J. Wiley 1968
- [L82] J. van Lint, Introduction to Coding
Theory, Springer 1982
- [W83] Heise, Quattrocchi, Informations- und
Codierungstheorie, Springer 1983
- [H87] R. Hamming, Information und Codierung,
VCH Weinheim 1987
- [W88] D. Welsh, Codes and Cryptography, Oxford
Univ. Press, 1988
- [KPS97] Klimant, Piotraschke, Schönfeld, Informations- und Kodierungstheorie,
Teubner 1997
- [R97] S. Roman, Introduction to Coding
and Information Theory, Springer 1997
- [H97] G. Hotz, Algorithmische Informationstheorie,
Teubner 1997
- [K81] A. Konheim, Cryptografie - a Primer,
J. Wiley 1981
- [S90] A. Salomaa, Public-Key Cryptography,
Springer 1990
- [B94] A. Beutelspacher, Kryptologie,
Vieweg 1994
- [BS95] A. Beutelspacher, J. Schwenk, K. Wolfenstetter,
Moderne Verfahren der Kryptographie, Vieweg 1995
- [B97] F. Bauer, Entzifferte Geheimnisse,
Springer 1997
- Parallele Algorithmen
- Veranstalter:
- Jakoby
- Form:
- Vertiefende Vorlesung (2V)
- Termine:
- Vorlesung: Fr, 8h - 10h, Raum H2/SFS.
- Skript
-
Inhaltsverzeichnis,
Kapitel Sortieren
Kapitel Routing
- 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 verlangen angepaßte
Algorithmen. Hierzu werden Modelle für solche Architekturen eingeführt
und verglichen.
- Eine effiziente parallele Umsetzung von Problemen ist oft nicht möglich.
Ursachen und Folgen werden mit Methoden der Komplexitätstheorie diskutiert.
- Literatur:
- Michel J. Quinn, Algorithmenbau und Parallelcomputer
- Alan Gibbons, Wojciech Rytter, Efficient Parallel Algorithms
- Alan Gibbons, Paul Spirakis, Lectures on parallel computation
- Seminar:
- Kombinatorische Optimierung
- Veranstalter:
- Reischuk
, Liskiewicz
- Form:
- Hauptseminar (S)
- Termine:
- Do, 8h - 10h, Raum 18/SFS.
- Inhalt:
- Kombinatorische Optimierungsprobleme treten in der Praxis in vielfältigster
Form auf. Lösungsverfahren, die optimale oder nahezu optimale Lösungen
effizient finden, sind daher von grosser Bedeutung. Ausgehend von dem linearen
Programmierungsproblem und dessen klassischer Lösung, dem Simplex-Algorithmus,
behandeln wir die Ellipsoid-Methode sowie Karmarkars-Algorithmus. Für
NP-vollständige Probleme wird die Frage behandelt, mit welcher Güte
sich diese approximieren lassen.
- Anmeldung und Literaturvergabe: Bei den Veranstaltern bis zum
12. April '99.
-
- Oberseminar:
- Oberseminar Theoretische Informatik
- Veranstalter:
- Reischuk
- Form:
- Oberseminar (3S)
- Termin:
- Do, 11h - 14h, Raum 18/SFS. (Auch in der vorlesungsfreien Zeit)
- Inhalt:
- Die Mitglieder und Studenten der Arbeitsgruppe Theoretische Informatik
- tragen über aktuelle Forschungsresultate vor.
