Modulbeschreibung
Automaten und Sprachen
Kurzzeichen:
M_AutoSpr
Durchführungszeitraum:
FS/15-FS/25
ECTS-Punkte:
4
Lernziele:
- 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.
Verantwortliche Person:
Müller Andreas
Standort (angeboten):
Rapperswil-Jona
Zusätzlich vorausgesetzte Kenntnisse:
keine
Skriptablage:
Modultyp:
Standard-Modul für Informatik STD_05(Empfohlenes Semester: 2)
Standard-Modul für Informatik STD_11(Empfohlenes Semester: 2)
Standard-Modul für Informatik STD_14(Empfohlenes Semester: 2)
Standard-Modul für Informatik STD_21(Empfohlenes Semester: 2)
Standard-Modul für Informatik STD_23(Empfohlenes Semester: 2)
Standard-Modul für Informatik Retro STD_14_UG(Empfohlenes Semester: 2)
ECTS-Punkte pro Kategorie
Mathematik / 4 Punkte
Mathematik / 4 Punkte
Mathematik / 4 Punkte
Modulbewertung
Bewertungsart:
Note von 1 - 6
Leistungsbewertung
Während der Prüfungssession:
Schriftliche Prüfung, 120 Minuten
Kurse in diesem Modul
Automaten und Sprachen
Kurzzeichen:
AutoSpr
Lernziele:
Plan und Lerninhalt:
- 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) - Kontextfreie Sprachen
(Kontextfreie Grammatiken, deterministische und nicht-deterministische Keller-Automaten, Äquivalenz von regulären Sprachen und Keller-Automaten, Pumping-Lemma für kontextfreie Sprachen) - Berechnungstheorie
(Turing-Maschinen, Halteproblem, Satz von Rice) - Komplexitätstheorie
(Die Klassen P und NP, NP-vollständige Probleme)
Unterrichtssprache:
Deutsch
Bibliographie:
Kursart:
(Durchführung gemäss Stundenplan)
Vorlesung mit 3 Lektionen pro Woche
- Max. Teilnehmer: 36
- Harte Grenze: ja
Uebung mit 1 Lektionen pro Woche
- Max. Teilnehmer: 18
- Harte Grenze: ja
Übergangsregelungen:
Theoretische Grundlagen der Informatik (mUk_ThGlI / I) (nicht durchgeführt)