*** Status offen *** *** PO 2024 *** ------------------------------------------------------------------ --- --- Vorlage für Modulbeschreibungen --- --- Version: 1.1 --- --- Allgemeine Hinweise: --- --- - Kommentare beginnen mit --- und werden komplett ignoriert --- --- - Wichtige Schlüsselwörter beginnen mit *** und dürfen nicht --- verändert oder gelöscht werden!!! --- --- - Die Eingaben müssen immer in den leeren Zeilen nach *** erfolgen. --- --- - Für einen Zeilenumbruch muss eine Leerzeile eingegeben werden. --- --- - Aktuelle Modulhandbücher: --- BaI : http://oow.hs-el.de/studium/pdf_bm/mh/mh_b_informatik_emd.pdf --- BaE : http://oow.hs-el.de/studium/pdf_bm/mh/mh_b_elektrotechnik_automatisierungstechnik_emd.pdf --- BaMT: http://oow.hs-el.de/studium/pdf_bm/mh/mh_b_medientechnik_emd.pdf --- MaII: http://oow.hs-el.de/studium/pdf_bm/mh/mh_m_industrial_informatics_emd.pdf --- ------------------------------------------------------------------ *** Studiengang und Semester --- für Studiengang nur Kürzel verwenden: E, EP, EE, I, MT oder II --- Semester wird davor geschrieben, auch Semesterbereiche möglich --- Wenn das Modul in mehreren Studiengängen verwendet wird, werden diese --- durch Komma getrennt aufgeführt. --- --- Beispiel: 2I, 2-3E, 5MT 3I, 3BaIP *** Modulbezeichnung --- Name laut Modulliste verwenden Theoretische Informatik *** Englische Modulbezeichnung Theoretical Computer Science *** Modulkuerzel THIN *** *** Art --- nur Alternativen: Pflichtfach, Wahlpflichtfach --- --- Beispiele: --- Pflichtfach --- Wahlpflichtfach --- Pflichtfach Vertiefung Technische Informatik Pflichtfach *** ECTS-Punkte --- nur Zahl angeben --- Beispiele: --- 5 --- 7,5 5 *** Studentische Arbeitsbelastung --- Angabe als x Stunden Kontaktzeit und y Stunden Selbststudium --- Format: x, y 60,90 *** Voraussetzungen (laut Prüfungsordnung) --- nur Modulbezeichnungen aufführen, z.B. Java 1 Grundlagen Informatik Java 1 Mathematik 1 Mathmematik 2 *** Empfohlene Voraussetzungen --- zusätzliche Module, die nicht in Prüfungsordnung als Voraussetzung stehen --- nur Modulbezeichnungen aufführen, z.B. Java 1 BI: Mathematik 1, Programmieren 1 BIPV: Mathematik 1, Grundlagen der Programmierung 1 *** Pruefungsform und -dauer --- Alternativen: --- Klausur 1,5 h --- Klausur 1,5h oder mündliche Prüfung --- Mündliche Prüfung --- Erstellung und Dokumentation von Rechnerprogrammen Klausur 1,5 h oder mündliche Prüfung *** Lehrmethoden und Lernmethoden --- Alternativen: Vorlesung, Praktikum, Seminar, Studentische Arbeit --- Falls Modul aus mehreren Veranstaltungen besteht, werden diese durch --- Komma getrennt aufgeführt. Vorlesung, Praktikum, Studentische Arbeit, Seminar *** Modulverantwortlicher --- Vorname abgekürzt, keine Titel --- Beispiel: F. Rump J. Mäkiö *** Qualifikationsziele --- Fließtext eingeben --- siehe Vorgaben in der Dokumentation 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 Chosky-Hierarchie der Sprachen kennen und anhand von Beispielen erläutern können die Chomsky-Normalform erklären sowei das Verfahren anzugeben und anwenden zu 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 --- Fließtext eingeben 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 --- max. drei Angaben --- Format: Heun, V.: Grundlegende Algorithmen, Vieweg, 2000. --- Mehrere Literaturangaben durch Leerzeilen trennen! 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. ------------------------------------------------------------------ --- --- Hier beginnt die Aufzählung der einzelnen Lehrveranstaltungen --- des Moduls (z.B. Vorlesung und Praktikum). --- --- Falls mehrere Lehrveranstaltungen vorgesehen sind, bitte die --- entsprechenden Bereiche auskommentieren. --- ------------------------------------------------------------------ *** Titel der Lehrveranstaltung --- Beispiel: Praktikum Informationssysteme Theoretische Informatik *** Dozent --- Vorname abgekürzt, keine Titel --- Beispiel: F. Rump J. Mäkiö *** SWS --- Zahl angeben 2 *** Titel der Lehrveranstaltung --- Beispiel: Praktikum Informationssysteme Übung Theoretische Informatik *** Dozent --- Vorname abgekürzt, keine Titel --- Beispiel: F. Rump J. Mäkiö *** WiMi N. N. *** SWS --- Zahl angeben 1 *** Parallelitaet 4 *** *** Titel der Lehrveranstaltung Praktikum Theoretische Informatik *** Dozent J. Mäkiö *** WiMi N. N. *** SWS 1 *** Parallelitaet 4 *** ------------------------------------------------------------------ --- --- Ausfüllen der Modul-Kompetenz-Matrix nicht vergessen! --- ------------------------------------------------------------------