Berechenbarkeit und Formale Sprachen (BFS)7.5 ECTS

Lehrveranstaltungen:

• • Berechenbarkeit und Formale Sprachen
    (Vorlesung, 4 SWS, Rolf Wanka, Mo, 10:15 - 11:45, H9; Fr, 08:15 - 09:45, H9)
  • Übungen zu Berechenbarkeit und Formale Sprachen
    (Übung)

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:

• I. Wegener. Theoretische Informatik. Teubner

• J. Hopcroft, J. Ullman. Introduction to Automata Theory, Languages and Computation

Weitere Informationen:

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:

1. Informatik (Bachelor of Science): 3. Semester
   (Po-Vers. 2007 | Pflichtmodule | Berechenbarkeit und Formale Sprachen)
2. Informatik (Bachelor of Science): 4. Semester
   (Po-Vers. 2009s | Pflichtmodule | Berechenbarkeit und Formale Sprachen)
3. Informatik (Bachelor of Science): 3. Semester
   (Po-Vers. 2009w | Pflichtmodule | Berechenbarkeit und Formale Sprachen)
4. Mathematik (Bachelor of Science)
   (Po-Vers. 2007 | Bachelorprüfung | Nebenfach Informatik | Wahlbereich 2 | Berechenbarkeit und Formale Sprachen)
5. 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

1. Prüfer:

Rolf Wanka

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

1. Prüfer:

Rolf Wanka