### 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 dem Studium dieses Moduls sollen Studierenden in der Lage sein zu erklären, warum Eingabeinstanzen kodieren werden müsses, und was dabei zu beacten ist erklären, was sind Entscheidungsprobleme die wichtigsten mathematischen Grundbegriffe: Menge, Tupel Relation, Funktion und Graph sicher zu benutzen die Modelle DEA, NEA und regulärer Ausdruck sowei deren Zusammenhang erklären können für eine reguläre Sprache einen NEA, DEA oder regulären Ausdruck konstruieren können aus einem DEA, NEA oder regulären Ausdruck seine Sprache bestimmen einen NEA zum DEA überführen können und den entsprechenden Algorithmus erläutern können einen DEA zu minimieren und den entsprechenden Algorithmus erläutern können das Pumpinglemma und seine Beweisidee beschreiben können das Pumpinglemma anwenden können, um die nichtregularität eine Sprache nachweisen zu können Kellerautomaten erklären und für eine kontextfreie Grammatik konstruieren können die Sprache eine kontextfreien Grammatik beschreiben können die äquivalenz von kontextfreien Grammatiken und Kellerautomaten erklären können die Chomsky-Hierarchie der Sprachen kennen und anhand von Beispielen erläutern können die Chomsky-Normalform erklären sowie das Verfahren anzugeben und anwenden können, um eine kontextfreie Grammatik in Chomsky-Normalform umwandeln das Pumpinglemma für kontextfreie Grammatiken zu beschreiben und anzuwenden die Abschlusseigenschaften von kontextfreien Grammatiken nennen und anwenden zu können den Zusammenhang zwischen Turingmaschinen und Berechenbarkeit erläutern können den Unterschied zwischen "(un-)entscheidbare", "erkennbare" und "aufzählbare" Sprache erläutern können die lementare komplexitätsklassen erläutern und anhand von Beispielen erläutern können Das Modul vermittelt die grundlegenden Kenntnisse auf dem Gebiet der theoretischen Informatik. Die Studierenden erlernen die grundlegenden Begriffe, Konzepte und Methoden endlicher Automaten, Grammatiken, Komplexität und Berechenbarkeit sowie den Zusammenhang zwischen theoretischen Maschinenmodellen und realen Rechnern. ### 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 ###