Berechenbarkeit und Formale Sprachen (BFS)7.5 ECTS
(englische Bezeichnung: Theory of Computation and Formal Languages)
(Prüfungsordnungsmodul: Berechenbarkeit und Formale Sprachen)

Lectures:

• • Berechenbarkeit und Formale Sprachen
    (Vorlesung, 4 SWS, Rolf Wanka, Mon, 14:15 - 15:45, H9; Fri, 10:15 - 11: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:

1. Informatik (Bachelor of Science): 3. Semester
   (Po-Vers. 2009w | Pflichtmodule | Berechenbarkeit und Formale Sprachen)

Studien-/Prüfungsleistungen:

Berechenbarkeit und Formale Sprachen (Klausur)_ (Prüfungsnummer: 30101)

Prüfungsleistung, Klausur, Dauer (in Minuten): 90, benotet

Anteil an der Berechnung der Modulnote: 100.0 %

Erstablegung: WS 2012/2013, 1. Wdh.: SS 2013, 2. Wdh.: keine Wiederholung

1. Prüfer:

Rolf Wanka

Termin: 03.08.2013, 10:00 Uhr, Ort: H 13
Termin: 28.03.2014, 11:00 Uhr, Ort: s. Aushang
Termin: 21.07.2014, 10:30 Uhr, Ort: H 7 TechF

Berechenbarkeit und Formale Sprachen (Übungsschein)_ (Prüfungsnummer: 30102)

Studienleistung, Studienleistung, unbenotet

weitere Erläuterungen:
Der Leistungsschein wird vergeben auf:

• Mindestens 50% der Übungspunkte

• Mind. einmal vorrechnen in der Übungsgruppe

Erstablegung: WS 2012/2013, 1. Wdh.: WS 2013/2014, 2. Wdh.: keine Wiederholung

1. Prüfer:

Rolf Wanka