Loading
     

Modulbeschreibung - Detailansicht

Wichtigste Meldungen anzeigenMeldungsfenster schließen
Moduldetails
Einführung in die Theoretische Informatik
Fakultät für Informatik
TUINFIN
8
1
6
IN0011
Zuordnungen zu SPO-Versionen
Lehrveranstaltungen und Prüfungsveranstaltungen
Beschreibungen
11W
Export
Allgemeine Daten (Modulhandbuch)
Bachelor
Einsemestrig
Sommersemester
Deutsch
Arbeitsaufwand (Work Load)
240
90
150
Studien- und Prüfungsleistungen
Prüfungsart: Klausur
Die Prüfungsleistung wird in Form einer 180-minütigen Klausur erbracht. Wissensfragen überprüfen die Vertrautheit mit Konzepten der Theoretischen Informatik, Konstruktionsaufgaben überprüfen die Fähigkeit, mit bekannten Algorithmen konkrete Probleme zu lösen oder kleine neue Algorithmen zu entwickeln, und Beweisaufgaben überprüfen die Fähigkeit, Aussagen über die Konzepte der Vorlesung logisch herzuleiten.
N
J
Beschreibung
IN0015 Diskrete Strukturen, MA0901 Lineare Algebra für Informatik, MA0902 Analysis für Informatik
Nach der erfolgreichen Teilnahme an diesem Modul verstehen die Teilnehmer die wesentlichen Konzepte der Theoretischen Informatik auf einem grundlegenden, aber wissenschaftlichen Niveau. Teilnehmer wissen, was reguläre Ausdrücke, kontextfreie Grammatiken, die Chomsky Hierarchy, endliche Automaten und Turingmaschinen sind. Sie können gegebene formale Sprachen mit dem passenden Beschreibungsmittel definieren und sie können zeigen, falls sich eine gegebene Sprache nicht mit einem bestimmten Beschreibungsmittel definieren lässt. Sie können beweisen, dass bestimmte Beschreibungsmittel äquivalent sind und können verschiedene Beschreibungen algorithmisch ineinander transformieren. Sie können die grundlegenden Konzepte der Komplexitätstheorie erklären und können Entscheidungsprobleme unter gegebenen Komplexitätsschranken algorithmisch aufeinander reduzieren.
Formale Sprachen, Grammatiken, Chomsky Hierarchy.

Reguläre Sprachen: DFA, NFA mit und ohne ε-Transitionen, reguläre Ausdrücke und Übersetzungen dazwischen; Systeme von Gleichungen zwischen Sprachen; Abschluss unter Booleschen Operationen; Ardens Lemma; Pumping Lemma; Entscheidungsprobleme; Minimierung; Satz von Myhill-Nerode.

CFLs: PDAs und Übersetzungen zw. CFGs und PDAs; Beweis, dass DPDAs schwächer als PDAs sind; Abschlusseigenschaften; CYK Algorithmus; Pumping Lemma; Chomsky und Greibach Normalformen.

Kontextsensitive Sprachen und LBAs.

Berechenbarkeit: Berechenbarkeit, Entscheidbarkeit, Halb-Entscheidbarkeit, rekursive Aufzählbarkeit und ihre Beziehungen; Existenz nichtberechenbarer Funktionen; Turing Maschinen, akzeptierte Sprachen und Typ-0 Sprachen; Äquivalenz von Turing Maschinen, While-Programmen und Goto-Programmen; Primitive und µ-rekursive Funktionen; Reduktionen zwischen Problemen; das Halteproblem; universelle Turing Maschinen; Satz von Rice und Satz von Rice-Shapiro; Unentscheidbarkeit des Postschen Korrespondenzproblems und wichtiger Probleme auf CFGs.

Komplexitätstheorie: Zeit und Platzkomplexitätsklassen; Polynomialzeitreduktionen; die Klassen P und NP; NP-Vollständigkeit; Satz von Cook; wichtige NP-vollständige Probleme und Reduktionen zwischen ihnen.

Alle Beweise werden behandelt.
In der Vorlesung werden die Inhalte vorgestellt und im Dialog mit den Studenten erläutert. In den begleitenden Übungen werden mit Hilfe von Aufgaben die angestrebten Lernergebnisse an konkreten Beispielen eingeübt, entweder individuell oder in Kleingruppen, und mit Hilfe des Tutors.
Folienpräsentation, Tafelanschrieb, Animationen, Vorlesungsaufzeichnung, Übungsblätter, online Diskussionsforum.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation
Dexter Kozen. Automata and Computability
Katrin Erk, Lutz Priese. Theoretische Informatik. Eine umfassende Einführung.
Uwe Schöning. Theoretische Informatik kurzgefasst.
Modulverantwortliche*r
Tobias Nipkow, Prof. Ph.D. (nipkow@tum.de)