|
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 2018/2019 | 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:
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan: Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:
- Informatik (Bachelor of Science): 3. Semester
(Po-Vers. 2007 | TechFak | Informatik (Bachelor of Science) | Pflichtmodule | Berechenbarkeit und Formale Sprachen)
- Informatik (Bachelor of Science): 4. Semester
(Po-Vers. 2009s | TechFak | Informatik (Bachelor of Science) | weitere Pflichtmodule | Berechenbarkeit und Formale Sprachen)
- Informatik (Bachelor of Science): 3. Semester
(Po-Vers. 2009w | TechFak | Informatik (Bachelor of Science) | weitere Pflichtmodule | Berechenbarkeit und Formale Sprachen)
- Mathematik (Bachelor of Science): 3. Semester
(Po-Vers. 2007 | NatFak | Mathematik (Bachelor of Science) | alte Prüfungsordnungen | Bachelorprüfung | Nebenfach Informatik | Wahlbereich 2 | Berechenbarkeit und Formale Sprachen)
- Mathematik (Bachelor of Science): 3. Semester
(Po-Vers. 2009 | NatFak | Mathematik (Bachelor of Science) | Nebenfach Informatik | Module im 2. und 3. Studienjahr | Wahlbereich 2 | Berechenbarkeit und Formale Sprachen)
- Mathematik (Bachelor of Science)
(Po-Vers. 2015w | NatFak | Mathematik (Bachelor of Science) | Module des Nebenfachs | Nebenfach Informatik | Vertiefungsmodule | Berechenbarkeit und Formale Sprachen)
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 2018/2019, 1. Wdh.: SS 2019
- Termin: 11.04.2019, 14:00 Uhr, Ort: Tentoria
Termin: 05.08.2019, 11:00 Uhr, Ort: H 8 TechF
Termin: 17.08.2020, 11:00 Uhr, Ort: H 11
Ü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 2018/2019, 1. Wdh.: WS 2019/2020
|
|
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|