|
Berechenbarkeit und Formale Sprachen (BFS)7.5 ECTS
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: Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:
- Informatik (Bachelor of Science): 3. Semester
(Po-Vers. 2007 | Pflichtmodule | Berechenbarkeit und Formale Sprachen)
- Informatik (Bachelor of Science): 4. Semester
(Po-Vers. 2009s | Pflichtmodule | Berechenbarkeit und Formale Sprachen)
- Informatik (Bachelor of Science): 3. Semester
(Po-Vers. 2009w | Pflichtmodule | Berechenbarkeit und Formale Sprachen)
- Mathematik (Bachelor of Science)
(Po-Vers. 2007 | Bachelorprüfung | Nebenfach Informatik | Wahlbereich 2 | Berechenbarkeit und Formale Sprachen)
- Mathematik (Bachelor of Science)
(Po-Vers. 2009 | Nebenfach Informatik | Module des 2. und 3. Studienjahrs | Wahlbereich 2 | Berechenbarkeit und Formale Sprachen)
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
- Termin: 03.08.2013, 10:00 Uhr, Ort: H 13
- 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 |
|
|