Theoretische Informatik 2
Prof. Dr. Florian Niebling
- Kreditpunkte
- 5
- Studiensemester
- 2
- Sprache
- deutsch
- Kürzel
- TI2
- Voraussetzungen nach Prüfungsordnung
- keine
- Prüfung
Einzelleistung: Schriftliche Prüfung Bewertung durch Prof. Dr. Florian Niebling
Empfohlene Voraussetzungen
Einfache Kenntnisse der naiven Mengenlehre, wie sie in der Schule vermittelt und bei der mathematischen Begriffsbildung verwendet werden.
Lehrform/SWS
4 SWS: Vorlesung 2 SWS; Übung 2 SWS
Arbeitsaufwand
Gesamtaufwand 150h, davon
- 36h Vorlesung
- 36h Übung
- 78h Selbstlernphase
Angestrebte Lernergebnisse
siehe Theoretische Informatik 1.
Inhalt
- Reguläre (Typ-3) Sprachen: Endliche Automaten, Reguläre Ausdrücke; Typ3-Grammatiken, Zustandsübergangsdiagramme; Chomsky-Hierarchie
- Modellierung sequentieller und paralleler (Ausgabe-) Prozesse: Endliche Maschinen / Automaten; Automatennetze, Petri-Netze, Zelluläre Automaten
- Kontextfreie (Typ-2) Sprachen: Kontextfreie Grammatiken, Chomsky-Normalform; Kellerautomaten; Anwendungen (Ableitungs- und Syntaxbäume, Syntax von Programmiersprachen, Backus-Naur-Form)
- Kontextsensitive (Typ-1) und rekursiv aufzählende (Typ-0) Sprachen: Grammatiken, Turingautomaten, Einführung in die Begriffe: Berechenbarkeit, Entscheidbarkeit und Komplexität
Literatur
- Hoffmann, D. (2011): Theoretische Informatik, 2. Auflage
- Vossen, G., Witt K. (2004): Grundlagen der Theoretischen Informatik mit Anwendungen. 3. Aufl. Vieweg & Sohn, Braunschweig.
- Hedtstück, U. ( 2004 ): Einführung in die Theoretische Informatik. Oldenbourg, München.
- Asteroth, A., Baier, C. (2002) Theoretische Informatik. Pearson Studium München
- Hopcroft, J. E. et al. (2002): Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium, München.
- Schöning, U. (1997): Theoretische Informatik - kurzgefaßt. 3. Aufl. Spektrum Akademischer Verlag, Heidelberg.