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

Lehrveranstaltungen:

• • Berechenbarkeit und Formale Sprachen
    (Vorlesung, 4 SWS, Rolf Wanka, Do, 14:15 - 15:45, H9; Fr, 10:15 - 11:45, H8)
  • Übungen zu Berechenbarkeit und Formale Sprachen
    (Übung, Rolf Wanka et al.)

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

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Informatik (Bachelor of Science)
   (Po-Vers. 2022w | TechFak | Informatik (Bachelor of Science) | Gesamtkonto | Berechenbarkeit und Formale Sprachen)

Studien-/Prüfungsleistungen:

Berechenbarkeit und Formale Sprachen (Vorlesung mit Übungen) (Prüfungsnummer: 30101)

(englischer Titel: Theory of Computation and Formal Languages)

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

Anteil an der Berechnung der Modulnote: 100.0 %

Erstablegung: WS 2022/2023, 1. Wdh.: SS 2023

1. Prüfer:

Rolf Wanka

Termin: 08.08.2022

Übungen zu Berechenbarkeit und Formale Sprachen (Prüfungsnummer: 30102)

(englischer Titel: Theory of Computation and Formal Languages (Exercises))

Studienleistung, Übungsleistung, unbenotet

weitere Erläuterungen:
Zum erfolgreichen Absolvieren der Übungsleistung werden gefordert:

• Mindestens 50% der Übungspunkte

• Mind. einmal vorrechnen in der Übungsgruppe

Erstablegung: WS 2022/2023, 1. Wdh.: WS 2023/2024

1. Prüfer:

Rolf Wanka