auptstudiumsgrundlagenveranstaltung zur Theoretischen Informatik im SoSe 2003
------------------------------------------------------------------------
18.111 Automaten und KomplexitŠt (AUK) 
------------------------------------------------------------------------
ĘĘ Manfred Kudlek 
4st. Mo 10 - 12 B-201, Mi 10 - 12 B-201
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.
Inhalt:
Formale Sprachen (Normalformen von Grammatiken, Entscheidbarkeitsprobleme), Abschlusseigenschaften, Allgemeine Sprachfamilien, Ersetzungssysteme (algebraisch, parallel), Automaten (endlich, stochastisch), KomplexitŠtstheorie (Zeit, Platz,VollstŠndigkeit), Parallele Maschinen (PRAM, Zellularautomaten), Kryptographie (Grundlagen), sequentielle und parallele Algorithmen, Analyse und Design von Algorithmen 
Stell. im Studienplan:
Hauptstudium, Vertiefungsgebiete A6, Th1, Th2, Th3, Th4; Schwerpunkte BV, ES, IM, INE, OSE, RNT, SEM, SV, VIS, WV
Voraussetzungen:
Grundstudium
Vorgehen:
Vorlesungen mit gelegentlichen †bungen
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
Eignung:
Geeignet fźr Bioinformatikstudierende. Bedingt geeignet fźr Lehramtsstudierende, Nebenfachstudierende, Wirtschaftsinformatikstudierende.
Stichworte:
Formale Systeme und Grammatiken, Kryptographie, Modelle von Automaten, KomplexitŠtstheori