|
Berechenbarkeit und Formale Sprachen (BFS)7.5 ECTS (englische Bezeichnung: Theory of Computation and Formal Languages)
Modulverantwortliche/r: Rolf Wanka Lehrende:
Rolf Wanka
Startsemester: |
WS 2022/2023 | Dauer: |
1 Semester | Turnus: |
jährlich (WS) |
Präsenzzeit: |
90 Std. | Eigenstudium: |
135 Std. | Sprache: |
Deutsch |
Lehrveranstaltungen:
Inhalt:
- Registermaschinen und Turingmaschinen als Modelle des Berechenbaren, die Churchsche These und unentscheidbare Probleme
NP-Vollständigkeit und das P-NP-Problem
Endliche Automaten
Grammatiken und die Chomsky-Hierarchie
Kontextfreie Grammatiken und Kontextfreie Sprachen
Kellerautomaten
Lernziele und Kompetenzen:
Die Studierenden
erwerben fundierte Kenntnisse über die Grenzen der Berechenbaren, insbesondere lernen sie, wie man beweist, dass bestimmte Aufgaben unlösbar sind bzw. dass sie vermutlich nicht schnell gelöst werden können;
lernen die wesentlichen Techniken kennen, mit denen man Programmiersprachen beschreiben und syntaktisch korrekte Programme erkennen kann;
erwerben fundierte Kenntnisse in den Beweis- und Analyse-Methoden der algorithmisch orientierten Theoretischen Informatik
Literatur:
Studien-/Prüfungsleistungen:
Berechenbarkeit und Formale Sprachen (Vorlesung mit Übungen) (Prüfungsnummer: 30101)
(englischer Titel: Theory of Computation and Formal Languages)
- Prüfungsleistung, Klausur, Dauer (in Minuten): 90, benotet
- Anteil an der Berechnung der Modulnote: 100.0 %
- Erstablegung: WS 2022/2023, 1. Wdh.: SS 2023
- Termin: 08.08.2022
Übungen zu Berechenbarkeit und Formale Sprachen (Prüfungsnummer: 30102)
(englischer Titel: Theory of Computation and Formal Languages (Exercises))
- Studienleistung, Übungsleistung, unbenotet
- weitere Erläuterungen:
Zum erfolgreichen Absolvieren der Übungsleistung werden gefordert:
- Erstablegung: WS 2022/2023, 1. Wdh.: WS 2023/2024
|
|
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|