### Status fertig### ### PO 2024 ### ### Studiengang und Semester 3I, 3BaIP ### Modulbezeichnung Theoretische Informatik ### Englische Modulbezeichnung Theory of Computation ### Modulkuerzel THIN ### ### Art Pflichtfach ### ECTS-Punkte 5 ### Studentische Arbeitsbelastung 60,90 ### Voraussetzungen (laut Prüfungsordnung) BI: Einführung in die Informatik, Programmieren 1, Mathematik 1 BIPV: Einführung in die Informatik, Grundlagen der Programmierung 1, Mathematik 1 ### Empfohlene Voraussetzungen Mathematik 2 ### Pruefungsform und -dauer Klausur 1,5 h oder mündliche Prüfung ### Lehrmethoden und Lernmethoden Vorlesung, Praktikum, Studentische Arbeit, Seminar ### Modulverantwortlicher J. Mäkiö ### Qualifikationsziele Nach Abschluss dieses Moduls sollen die Studierenden in der Lage sein: * zu erklären, warum Eingabeinstanzen kodiert werden müssen und was dabei zu beachten ist, * die wichtigsten mathematischen Grundbegriffe zu erläutern, darunter Mengen, Tupel, Relationen, Funktionen und Graphen, * die Modelle DEA, NEA und reguläre Ausdrücke sicher zu erklären und ihren Zusammenhang zu erläutern, * einen NEA, DEA oder regulären Ausdruck für eine reguläre Sprache zu konstruieren, * die Sprache eines DEA, NEA oder regulären Ausdrucks zu bestimmen, * einen NEA in einen DEA zu transformieren und den zugehörigen Algorithmus zu erläutern, * einen DEA zu minimieren und den entsprechenden Algorithmus zu erklären, * das Pumping-Lemma und dessen Beweisidee zu beschreiben, * das Pumping-Lemma anzuwenden, * Kellerautomaten zu erläutern und für eine kontextfreie Grammatik zu konstruieren, * die Sprache einer kontextfreien Grammatik zu beschreiben, * die Äquivalenz von kontextfreien Grammatiken und Kellerautomaten zu erläutern, * die Chomsky-Hierarchie der Sprachen zu erkennen und anhand von Beispielen zu erklären, * die Chomsky-Normalform zu erläutern und das Verfahren anzugeben sowie anzuwenden, * das Pumping-Lemma für kontextfreie Grammatiken zu beschreiben und anzuwenden, * die Abschlusseigenschaften von kontextfreien Grammatiken nennen und anwenden, * den Zusammenhang zwischen Turing-Maschinen und Berechenbarkeit zu erläutern, * den Unterschied zwischen "(un)entscheidbarer", "erkennbarer" und "aufzählbarer" Sprache zu erklären, * die elementaren Komplexitätsklassen zu erläutern und anhand von Beispielen zu erklären. Das Modul vermittelt grundlegende Kenntnisse im Bereich der theoretischen Informatik. Die Studierenden lernen die Grundbegriffe, Konzepte und Methoden von endlichen Automaten, Grammatiken, Komplexität und Berechenbarkeit kennen sowie die Beziehung zwischen theoretischen Maschinenmodellen und realen Computern. ### Lehrinhalte Stichworte sind: Endliche Automaten, Kellerautomaten, reguläre Ausdrücke, Automaten Transformationen und Minimierung, reguläre und nicht-reguläre Sprachen, Chomsky-Hierarchie, Grammatiken und kontextfreie Sprachen, Berechenbarkeitsmodelle, Churchsche These, Unentscheidbarkeit und Turing-Reduzierbarkeit, Komplexitätsklassen, das P=NP-Problem, polynomielle Reduzierbarkeit, NP-Vollständigkeit. ### Literatur - Hopcroft, J.E., Motwani, R., Ullman, J.D.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie - Hedtstück, U.: Einführung in die Theoretische Informatik, Oldenburger Wissenschaftsverlag, 2007. - Hoffmann, D.: Theoretische Informatik, Hanser Verlag, 2015. ### Titel der Lehrveranstaltung Theoretische Informatik ### Dozent J. Mäkiö ### SWS 2 ### Titel der Lehrveranstaltung Übung Theoretische Informatik ### Dozent J. Mäkiö ### WiMi N. N. ### SWS 1 ### Parallelitaet 4 ### ### Titel der Lehrveranstaltung Praktikum Theoretische Informatik ### Dozent J. Mäkiö ### WiMi N. N. ### SWS 1 ### Parallelitaet 4 ###