Modulbeschreibung

Automaten und Sprachen

Kurzzeichen:
M_AutoSpr
Unterrichtssprache:
Deutsch
ECTS-Credits:
4
Leitidee:
  • Grundlagen zur Verarbeitung formaler Sprachen.
  • Fähigkeit, formale Spezifikationen (z.B. in BNF) zu erstellen und zu verstehen.
  • Beherrschung verschiedener Berechenbarkeitsbegriffe.
  • Grundlagen der Komplexitätstheorie.
Modulverantwortung:
Prof. Dr. Müller Andreas
Standort (angeboten):
Rapperswil-Jona
Modultyp:
Wahlpflicht-Modul für Informatik Retro STD_14_UG(Empfohlenes Semester: 2)Kategorie:Mathematik (I-m)
Wahlpflicht-Modul für Informatik STD_05(Empfohlenes Semester: 2)Kategorie:Mathematik (I-m)
Wahlpflicht-Modul für Informatik STD_11(Empfohlenes Semester: 2)Kategorie:Mathematik (I-m)
Wahlpflicht-Modul für Informatik STD_14(Empfohlenes Semester: 2)Kategorien:Informatik (I_Inf), Rahmenausbildung (Kat_RA)
Wahlpflicht-Modul für Informatik STD_21(Empfohlenes Semester: 2)Kategorien:Informatik (I_Inf), Rahmenausbildung (Kat_RA)
Wahlpflicht-Modul für Informatik STD_23(Empfohlenes Semester: 2)Kategorien:Informatik (I_Inf), Rahmenausbildung (Kat_RA)
Modulbewertung:
Note von 1 - 6

Leistungsnachweise und deren Gewichtung

Modulschlussprüfung:
Schriftliche Prüfung, 120 Minuten

Inhalte

Modul- und Lerninhalt:
  1. Reguläre Sprachen
    (Reguläre Ausdrücke, deterministische und nicht-deterministische endliche Automaten, Äquivalenz von regulären Sprachen und endlichen Automaten, Pumping-Lemma für reguläre Sprachen)
  2. Kontextfreie Sprachen
    (Kontextfreie Grammatiken, deterministische und nicht-deterministische Keller-Automaten, Äquivalenz von regulären Sprachen und Keller-Automaten, Pumping-Lemma für kontextfreie Sprachen)
  3. Berechnungstheorie
    (Turing-Maschinen, Halteproblem, Satz von Rice)
  4. Komplexitätstheorie
    (Die Klassen P und NP, NP-vollständige Probleme)