Einführung in die Theoretische Informatik

Bachelorstudieng?nge mit Hauptfach Informatik:?Informatik, 伟德国际_伟德国际1946$娱乐app游戏izinische Informatik, Wirtschaftsinformatik (Vertiefung Informatik)
Alle Bachelorstudieng?nge mit Nebenfach Informatik (u.a. Mathematik, Physik, Geographie, Betriebswirtschaftlehre, Wirtschaftsmathematik)

Anmeldung ab M?rz im Digicampus.
?

?bersicht

Veranstaltungsart: Vorlesung + ?bung (Bachelor)

Credits: 4V + 2?, 8 LP

Turnus: Jedes Sommersemester

Empfohlenes Semester:
2. Fachsemester

Prüfung:?Klausur (120 Minuten)

Sprache: Deutsch

Ziel der Vorlesung ist eine Einführung in formale Sprachen und Automaten. Themenauswahl:

Endliche Autaten und regul?re Sprachen
- DFA, NFA, regul?re Ausdrücke, Pumping-Lemma, Abschlusseigenschaften, Nerode-Automat
Kellerautomaten und kontextfreie Sprachen
- CFG (Normalformen, Syntaxbaum, Pumping-Lemma, Ein- und Mehrdeutigkeit), PDA (Odgens Lemma), Abschlusseigenschaften, deterministisch kontextfreie Sprachen
Turingmaschinen und Berechenbarkeit
- Churchsche These, Turingmaschinen (nichtdeterministisch, Mehrband), Random Access Machines, mu-rekursive Funktionen, (Semi-)Entscheidbarkeit, Wortproblem, Halteproblem, Leerheitsproblem, Satz von Rice, Postsches Korrespondenzproblem, Reduktion
Chomsky-Hierarchie
- Uneingeschr?nkte Grammatiken, Kontextsensitive Sprachen, Linear beschr?nkte Turingmaschinen

伟德国际_伟德国际1946$娱乐app游戏