Diese Seite stammt aus altem Bestand.
Lehrveranstaltungen im WS 00/01
-
Grundstudium:
-
Hauptstudium:
-
Grundstudium:
-
Effiziente Algorithmen
-
Veranstalter:
-
Zeugmann, Jakoby
-
Form:
-
Proseminar (2S)
-
Termine:
-
Mi, 13.00h - 15.00h, Raum H3/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
Die Vorbesprechung und die Vergabe der Vorträge findet in der ersten
Veranstaltung im WS 00/01 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
-
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
-
Boolsche Funktionen und Schaltkreise
-
Veranstalter:
-
Zeugmann, Bläser
-
Form:
-
Proseminar (2S)
-
Termin:
-
Mi, 15.00h-17.00h, Raum R1/21.
Inhalt:
Schaltkreise sind die elementaren Bausteine der heutigen digitalen
Rechner. Aus komplexitätstheoretischer Sicht bilden Sie ein wichtiges
Modell, um die parallele Komplexität von Berechnungsproblemen zu untersuchen.
Ein Boolescher Schaltkreis besteht aus Gattern (z.B. für die logischen
Operationen Und, Oder und Negation), die azyklisch miteinander verbunden
sind. Ein Boolescher Schaltkreis berechnet eine Boolesche Funktion, also
eine Funktion, die 0-1-Vektoren auf 0-1-Vektoren abbildet. Das Proseminar
behandelt exemplarisch grundlegende Aspekte von Booleschen Funktionen und
Schaltkreisen.
-
Hauptstudium:
-
Pflichtvorlesungen:
-
Algorithmen, Komplexitätstheorie und Formale Sprachen
-
Veranstalter:
-
Vorlesung: Reischuk,
Buntrock,
Schindelhauer
-
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:
-
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:
-
Komplexe Datenstrukturen
-
Veranstalter:
-
Jakoby
-
Form:
-
Vertiefende Vorlesung im Bereich Informatik III (2V)
-
Termine:
-
Mo. 14.00h-16.00h, Raum H1/SFS.
-
Inhalt:
Der Entwurf und die Analyse komplexer Datenstrukturen sowie ihr Einsatz
in effizienten Algorithmen steht im Mittelpunkt dieser Veranstaltung. Für
viele einfache Problemstellungen, wie z.B. in der Datenverwaltung zeigt
es sich, dass eine direkte, einfache Umsetzung in einem Programm weniger
effizient ist, als die Verwendung ausgefeilter Methoden. So kann bei der
Implementierung eines Wörterbuches die Verwendung von perfekten Hashfunktionen
zu einem schnellen Datenzugriff auf der einen Seite und einer Minimierung
des Speicherbedarfs auf der anderen Seite führen, wohingegen eine
naheliegende Implementation entweder sehr speicheraufwendig ist oder nur
einen zeitaufwendigen Zugriff auf gespeicherte Daten zulässt. Diese
Veranstaltung ist richtet sich an Studenten des Hauptstudiums, die sich
neue Programmier-Techniken aneignen wollen die über das Grundstudium
hinausgehen. Spezielle Kenntnisse aus der Mathematik oder der Theoretischen
Informatik werden nicht vorausgesetzt.
-
Skript:
Das Skript
Literatur:
-
Knuth, The Art of Computer Programming, Vol. 1-3, Add. Wesley
-
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
-
Logik und Rekurionstheorie
Veranstalter:
-
Form:
-
Vertiefende Vorlesung im Bereich Informatik III (2V)
-
Termine:
-
Vorlesung: Mi, 14.00h - 16.00h, Raum H1/SFS.
Inhalt:
Diese Vorlesung dient zur Vertiefung der theoretischen Grundlagen.
Der Inhalt kann als Prüfungsstoff im theoretischen Teil der Diplomprüfung
eingebracht werden.
-
Die Logik ist eine Disziplin, die ursprünglich von den Philosophen,
dann mehr von den Mathematikern nd heute am meisten von den Informatikern
betrieben wird.
-
Nach einem kurzen einführenden Kapitel mit einer historischen Übersicht
und verschiedenen Beispielen eginnen wir mit einer überblicksartigen
Wiederholung der Aussagenlogik. Im ersten zentralen Teil der orlesung wenden
wir uns der Prädikatenlogik zu. Hier lernen wir den Sequenzenkalkül
aus dem Buch von Ebbinghaus, Flum und Thomas kennen. Einen Höhepunkt
wird sicher der wichtige Satz über die unvollständigkeit der
Arithmetik von Gödel bieten. Dieser Satz hat auch erhebliche erkenntnistheoretische
Bedeutung und signalisiert gewisse Grenzen für eine künstliche
Intelligenz.
-
Hieran anknüpfend werden wir die Bedeutung des Gödelschen Satzes
für die Informatik untersuchen und die rekursionstheoretischen Grundlagen
studieren. Damit ist ein für sich selbst interessanter Einblick in
die eleganten Themen der Rekursionstheorie verbunden, dies ist der zweite
zentrale Gegenstand der Vorlesung.
Ausgehend vom Sequenzenkalkül werden wir Ausflüge in die
Themen "automatisches Beweisen" und "Ableitungskalküle für nicht-klassische
Logiken" unternehmen. Diese Themen haben auch erhebliche Relevanz für
die Logikprogrammierung. Hierzu liest demnächst Herr Zeugmann eine
vertiefende orlesung, die mit ihren praktischen Komponenten zu dieser Vorlesung
eine hervorragende Ergänzung darstellen wird.
Literaturhinweise:
-
Heinz-Dieter Ebbinghaus/Jörg Flum/Wolfgang Thomas: Einführung
in
die Mathematische Logik, 3. Auflage, BI Wissenschaftsverlag, 1992.
-
Piergiorgio Odifreddi: Classical Recursion Theory. Studies in Logic and
the Foundations of Mathematics. North Holland, 1989.
-
Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability.
McGraw Hill, 1967. Erneut aufgelegt bei MIT Press, Cambridge 1987.
-
Uwe Schöning: Logik für Informatiker. 4. Auflage, Spektrum Akademischer
Verlag, 1995
-
Raymond~M. Smullyan: Gödel's Incompleteness Theorems. Oxford
Logic Guides. Oxford University Press, New York, 1992.
-
Raymond~M. Smullyan: Diagonalization and Self-Reference. Oxford Logic Guides.
Oxford University Press, New York, 1994.
-
Kryptologie
-
Veranstalter:
-
Form:
-
Vertiefende Vorlesung im Bereich Informatik III (2V)
-
Termine:
-
Vorlesung: Do, 14.00h - 16.00h, Raum R1/21.
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
-
Seminare:
-
Intelligente Sprach- und Textbearbeitung
-
Veranstalter:
-
Buntrock,
-
Form:
-
Hauptseminar (S)
-
Termin:
-
Vorlesung: Di, 14.00h-16.00h, Raum H3/SFS.
Inhalt:
-
Die Generierung von Texten entwickelt sich von der reinen Layoutgestaltung
hin zur intelligenten Speicherung von Wissen. Hierbei steht die Absicht
im Vordergrund, die so gespeicherten Dokumente mit verschiedensten Werkzeugen
weiter zu verarbeiten. Unter diesen Werkzeugen finden wir intelligente
Information-Retrieval-Systeme und damit im Zusammenhang stehend auch Tools
zur aktiven Entscheidungshilfe (z.B. im medizinischen Bereich) in Produktions-
oder Behandlungsprozessen.
-
So kann man darauf aus sein, die Informationen so abzuspeichern, daß
wir sie in speziell genormten Fachsprachen (z.B. im medizinischen Bereich)
ausgeben können. Eine konkrete Anwendung wäre hier, aus einer
kundenspezifischen Zusammenstellung eines Produktes (z.B. Kfz) die Erstellung
einer passenden Betriebsanleitung zu automatisieren.
Die Themenstellung des Seminars umfaßt
Erkennen verschiedener Begriffe
trotz unterschiedlicher Wortbildungen und -beugungen (Morphologie).
Vorstellung von Begriffsystemen
vornehmlich aus der Medizin (etwa zur Modellierung der Anatomie)
Techniken zur Speicherung
von "Wissen". Hier sollen Hypertexttechniken und speziell grammatikbasierte
Systeme (XML und SGML) vorgestellt werden.
Auf unserer Web-Seite gibt es detailierte Informationen zu den einzelnen
Problemkreisen und Vortragsthemen.
Interessenten können auch gerne schon vorher ihr Interesse an
einem Vortrag bei dem Veranstalter bekunden.
Die Einstiegsseite:
http://www.medinf.mu-luebeck.de/SeminarWS9900.html
-
Sicherheit
-
Veranstalter:
-
Reischuk,Liskiewicz
-
Form:
-
Hauptseminar (2S)
-
Termin:
-
Do, 12.00h-14.00h, Raum H3/SFS
Anmeldung und Themenvergabe bei Herrn Liskiewicz
1. Sitzung: 19.10.00, 12 Uhr
Inhalt:
Es werden folgende Themen behandelt:
Rechnersicherheit
Gefährliche Software: Viren,
Trojanische Pferde,Würmer
Systemsicherheit - Protokolle
Secure Email: Key-Management, PGP,
Finanzanwendungen: Smart Cards, Electronic Cash
Watermarking, Fingerprinting
Netzsicherheit
Firewalls
Internet-Privacy
Als Grundlage dient die folgende Literatur, sowie
weitere aktuelle Publikationen:
-
S. Fischer, A. Steinacker, R. Bertram, R.
Steinmetz, Open Security, Springer 1998
-
B. Preneel, V. Rijmen (Eds.), State of the Art in
Applied Cryptology, LNCS 1528, Springer
1997
-
A. Menezes, P. Oorschot, S. Vanstone,
Handbook of Applied Cryptography, CRC
Press 1997
-
Abrams, Jajodia, Podel, Information Security
(Eds), IEEE CS 1995
-
S. Shaffer, A. Simon, Network Security, AP
Professional, 1994
-
R. Farrow, Unix System Security, Addison
Wesley 1991
-
W. Cheswick, S. Bellowin, Firewalls and
Internet Security, Adison Wesley-ATT 1994
-
J. Dittman, Digitale Wasserzeichen, Springer 2000
-
P. Denning (Ed.) Computers under Attack,
Addision Wesley 1990
-
Algorithmen für Probleme der Molekularbiologie
-
Veranstalter:
-
Reischuk, Bläser
-
Form:
-
Hauptseminar (2S)
-
Termin:
-
Fr, 14.00h-16.00h, Raum H1/SFS.
Inhalt:
Ein grosser Teil der Funktionalität von DNA und Proteinen ist
einzig durch die Abfolge der Basen in den Molekülen festgelegt. Aus
dreidimensionalen Molekülen werden so eindimensionale lineare Ketten.
Es stellt sich also das Problem der Analyse und Verarbeitung von Zeichenketten
(z.B. über dem Alphabet G, A, T, C), einem klassischen Gebiet der
Informatik.
Viele der mittlerweile sehr komplexen Aufgabenstellungen in der Molekularbiologie,
die ohne Rechnereinsatz nicht mehr zu lösen sind, lassen sich daher
sehr gut abstrakt modellieren. Eine effiziente Lösung dieser Probleme
verlangt in vielen Fällen anspruchsvolle algorithmische und komplexitätstheoretische
Methoden.
In diesem Seminar werden exemplarisch einige wichtige algorithmische
Problem in der Molekularbiologie behandelt und Algorithmen zur Ihrer Lösung
oder Approximation einer Lösung erarbeitet.
Mögliche Themen sind u.a.: Pattern Matching, Sequence Alignment,
DNA fragment assembly, physikalische Kartierung, phylogenetische Bäume,
DNA Computing.
-
Praktika:
-
Effizientes Problem lösen und programmieren
-
Veranstalter:
-
Reischuk, Liskiewicz
-
Form:
-
Termin:
-
Mo, 17.00h - 20.00h, Raum H4(Rechnerpool)/SFS.
-
Anmeldung: bis 1.10.2000
-
-
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.
-
Parallelverarbeitung
-
Veranstalter:
-
Reischuk,
Liskiewicz,
Schindelhauer
-
Form:
-
Termin:
-
Mi, 15.00h - 18.00h, Raum H3/SFS.
-
Inhalt:
Auf dem Lübecker Hochleistungs-Parallelrechner sollen praktische
Aspekte der Parallverarbeitung mit Cache-cohärentem Shared Memory
eingehender untersucht werden. Die folgenden Thematiken können unter
Berücksichtigung der Interessen der Teilnehmer behandelt werden:
Algorithmische Entwurfsmethoden:
Dekompositionstechniken
Datenpartitionierung
Präfix-Operationen, List-Ranking, Pointer-Jumping
Programmierung:
Programmiermodelle
Programmiersprachen: paralleles Fortran, C,
Parallelisierende Compiler
Effiziente Shared Memory Implementierungen
Konkrete Problemstellungen:
Matrix-Multiplikation
Paralleles Sortieren
Kombinatorische Optimierungsprobleme
Leistungsmessungen:
Überwachungstools
Standard Benchmarks
Entwurf eigener Benchmarks für Kommunikationsbandbreiten
Literatur:
-
M. Snir et al., MPI - The Complete Reference Vol 1, MIT Press 1998
-
J. Gropp, E. Lusk, A. Skjellum, Using MPI, MIT Press 1997
-
G. Wilson, Practical Parallel Programming, MIT Press 1995
-
H. Stone, High-Performance Computer Architecture, Adison Wesley 1990
-
T. Bräunl, Parallele Programmierung, Vieweg 1993
-
J. JaJa, An Introduction to Parallel Algorithms, Adison Wesley 1992
-
Kumar, Grama, Gupta, Karypis, Introduction to Parallel Computing, Benjamin/Cummings
1994
-
G. Almasi, A. Gottlieb, Highly Parallel Computing, Benjamin/Cummings, 1989
-
-
Oberseminar Theoretische Informatik
-
Veranstalter:
-
Reischuk, Zeugmann
-
Form:
-
Oberseminar (3S)
-
Termin:
-
Inhalt:
-
Die Mitglieder und Studenten der Arbeitsgruppe Theoretische
-
Informatik tragen über aktuelle Forschungsresultate vor.