|
Berechenbarkeit und Formale Sprachen (BFS)7.5 ECTS (Prüfungsordnungsmodul: Berechenbarkeit und Formale Sprachen)
Modulverantwortliche/r: Rolf Wanka Lehrende:
Rolf Wanka
Startsemester: |
WS 2011/2012 | Dauer: |
1 Semester |
Präsenzzeit: |
90 Std. | Eigenstudium: |
135 Std. |
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:
Weitere Informationen:
www: http://www12.informatik.uni-erlangen.de/edu/BFS/WS1112/
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
- Informatik (Bachelor of Science): 3. Semester
(Po-Vers. 2009w | Pflichtmodule | Berechenbarkeit und Formale Sprachen)
Dieses Modul ist daneben auch in den Studienfächern "Mathematik (Bachelor of Science)" verwendbar. Details
Studien-/Prüfungsleistungen:
- schriftlich, Dauer (in Minuten): 90, benotet
- weitere Erläuterungen:
Auf Basis der Bewertung der während des Semesters bearbeiteten Übungsaufgaben können bis zu 10 % Klausur-Bonuspunkte erworben werden, die zu dem Ergebnis der Klausur hinzugerechent werden, falls die Klausur auch ohne Bonuspunkte bereits bestanden ist.
- Erstablegung: WS 2011/2012, 1. Wdh.: SS 2012
- Leistungsschein, benotet
- weitere Erläuterungen:
Im Rahmen der Übungen sind Übungsaufgaben zu bearbeiten, die korrigiert und bewertet werden. Kriterium für die Vergabe des Scheins: 50 % der Punkte aus den Übungsaufgaben plus Vorrechnen. Bei erfolgreicher Übungsteilnahme werden außerdem auf der Basis des Übungsergebnisses Bonuspunkte für die Klausur vergeben.
- Erstablegung: WS 2011/2012, 1. Wdh.: SS 2012
|
|
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|