Einführung in die Theoretische Informatik,

-

intermediate

Ziel des Moduls ist es eine Einführung in die theoretische Informatik und ihre typischen und grundlegenden mathematischen Denk- und Argumentationsweisen zu bieten.

Inhalt (Die Reihenfolge der Themen und die Gewichtung sind dem Dozenten überlassen)

A Formale Sprachen
• Repetition: Sprachen und Entscheidungsprobleme, Grammatiken, Chomsky-Hierarchie
• Endliche Automaten und reguläre Sprachen (DFA, NFA, Minimale DFA) Pumping-Lemma, Satz von Myhill-Nerode
• Reguläre Ausdrücke
• Kontextfreie Sprachen

B Berechnungstheorie
• Berechungsmodelle (Turing-Maschinen, rekursive Funktionen, loop-, while- und goto-Programme)
• Church-Turing-These
• Entscheidbarkeit und rekursive Aufzählbarkeit
• Universelle Turing-Maschinen
• Unentscheidbarkeit
• Reduktion
• Satz von Rice

C Komplexität
• Komplexitätsklassen
• Polynomiale Reduktion
• P- und NP-Probleme

Formale Sprachen Die Studierenden können mit Grammatiken einfache Sprachen beschreiben, verstehen die Chomsky-Hierarchie und können Sprachen einordnen. Sie kennen die Abschlusseigenschaften der regulären Sprachen. Sie können einen einfachen regulären Ausdruck in einen minimalen, deterministischen Automaten überführen. Sie sind in der Lage in einfachen Fällen mit Hilfe des Pumping-Lemmas oder des Satzes von Myhill-Nerode nachzuweisen, dass eine Sprache nicht regulär ist. Sie können eine kontextfreie Grammatik auf Chomsky-Normalform bringen und den Cocke-Younger-Kasami-Algorithmus anwenden. Berechnungstheorie Die Studierenden kennen wichtige Berechnungsmodelle und können die Church-Turing-These erklären. Sie kennen die Begriffe Entscheidbarkeit und rekursive Aufzählbarkeit und verstehen das Konzept der Universellen Turing-Maschinen. Sie können erklären, was eine unentscheidbare Sprache ist und kennen Beispiele. Die Studierenden verstehen die Idee der Reduktion und sind in der Lage einfache Reduktionen selbst durchzuführen. Sie können den Inhalt des Satzes von Rice erklären. Komplexität Die Studierenden können erklären, was eine Komplexitätsklasse ist und einfache Beispiele einordnen. Sie verstehen die Bedeutung der Klassen P und NP, kennen einige wichtige Beispiele und verstehen die polynomiale Reduktion.

Erfahrungsnote