| Veranstaltungs-Nr.: | 18.111 (SoSe 2006) |
| Titel: | Automaten und Komplexität (AUK) |
| Veranstalter: | Matthias Jantzen |
| Zeit / Ort: | 4 st. Mo. 10-12 B-201 Mi 10-12 B-201 |
| - |
| Inhalt: | Entscheidbarkeitsprobleme bei Formalen Sprachen.
Abschlusseigenschaften Formaler Sprachen.
Sequentielle und parallele Ersetzungssysteme.
Parallele Rechnermodelle (PRAM, Schaltkreise).
Massiv parallele Modelle (neuronale Netze, Zellularautomaten, Systolic Arrays)
Probabilistische Automaten (endliche, Turingmaschinen).
Netzwerktopologien.
Automaten für unendliche Objekte und logische Beschreibung davon,
Modell Checking, Komplexitätstheorie, Komplexitätsklassen,
Kryptographie. |
| Lernziel: | Vorlesung zur Vertiefung von Modellen, Begriffen und Methoden der Theoretischen Informatik aus dem Grundstudium (F1-F3), und Kennenlernen weiterer grundlegender Modelle, Begriffe und Methoden der Theoretischen Informatik. Gelegentliche Übungen. |
| Stell. im Studienplan: | Hauptstudium |
| Voraussetzungen: | Grundstudium |
| Vorgehen: | Vorlesungen mit gelegentlichen Übungen |
| Verwendbarkeit: | - |
| Literatur: | J.E. Hopcroft, J.D. Ullman: Introduction to Automata, Languages and Computation, Addison Wesley, 1979
A. Salomaa: Formal Languages, Academic Press, 1973
M. Jantzen: Theoretische Grundlagen der Programmierung, (Skript)
I. Wegener:Effiziente Algorithmen für Grundlegende Funktionen, Teubner, 1989
R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics, Addison Wesley, 1989
M. Aigner: Discrete Mathematik, Vieweg, 1993
J. Gruska: Foundations of Computing, ITP, 1997
A. Salomaa: Public Key Cryptography, Springer, 1990/1996
D.R. Stinson: Cryptography-Theory and Praxis, CRC-Press, 1995
R. Reischuk: Komplexitätstheorie: Teubner, 1999
|
| Periodizität: | jährlich zum SS |
| Sprache: | Deutsch |
| Eignung: | Geeignet für Bioinformatikstudierende. Bedingt geeignet für Lehramtsstudierende, Nebenfachstudierende, Wirtschaftsinformatikstudierende. |
| Stichworte: | Komplexitätstheorie, Formale Systeme und Grammatiken, Kryptographie, Modelle von Automaten |