|
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 2013/2014 | 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. 2009w | Pflichtmodule | Berechenbarkeit und Formale Sprachen)
Studien-/Prüfungsleistungen:
Berechenbarkeit und Formale Sprachen (Vorlesung mit Übungen) (Prüfungsnummer: 30101)
- Prüfungsleistung, Klausur, Dauer (in Minuten): 90, benotet
- Anteil an der Berechnung der Modulnote: 100.0 %
- Erstablegung: WS 2013/2014, 1. Wdh.: SS 2014
- Termin: 28.03.2014, 11:00 Uhr, Ort: s. Aushang
Termin: 21.07.2014, 10:30 Uhr, Ort: H 7 TechF
Termin: 03.02.2015, 13:00 Uhr, Ort: H 11
Termin: 27.07.2015, 08:00 Uhr, Ort: K 1 TechF
Übungen zu Berechenbarkeit und Formale Sprachen (Prüfungsnummer: 30102)
- Studienleistung, Übungsleistung, unbenotet
- weitere Erläuterungen:
Zum erfolgreichen Absolvieren der Übungsleistung werden gefordert:
- Erstablegung: WS 2013/2014, 1. Wdh.: WS 2014/2015
|
|
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|