Einführung in die Theoretische Informatik
Introduction to Theory of Computation

Modul IN0011

Dieses Modul wird durch Fakultät für Informatik bereitgestellt.

Diese Modulbeschreibung enthält neben den eigentlichen Beschreibungen der Inhalte, Lernergebnisse, Lehr- und Lernmethoden und Prüfungsformen auch Verweise auf die aktuellen Lehrveranstaltungen und Termine für die Modulprüfung in den jeweiligen Abschnitten.

Basisdaten

IN0011 ist ein Semestermodul in Deutsch auf Bachelor-Niveau das im Sommersemester angeboten wird.

GesamtaufwandPräsenzveranstaltungenUmfang (ECTS)
240 h 90 h 8 CP

Inhalte, Lernergebnisse und Voraussetzungen

Inhalt

Es werden folgende grundlegende Konzepte der Theoretischen Informatik behandelt: Formale Sprachen und ihre Einordnung in die Chomsky-Hierarchie. Elementare Automatentheorie und der Bezug zu Formalen Sprachen. Der algorithmische Begriff der Entscheidbarkeit. Grundlagen der Komplexitätstheorie auf der Basis eines passenden Maschinenmodells.

Lernergebnisse

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 uns 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 in einander transformieren. Sie können die grundlegenden Konzepten der Komplexitätstheorie erklären und können Entscheidungsprobleme unter gegebenen Komplexitätsschranken algorithmisch auf einander reduzieren.

Voraussetzungen

IN0015 Diskrete Strukturen, MA0901 Lineare Algebra für Informatik, MA0902 Analysis für Informatik

Lehrveranstaltungen, Lern- und Lehrmethoden und Literaturhinweise

Lehrveranstaltungen und Termine

ArtSWSTitelDozent(en)Termine
VO 4 Einführung in die Theoretische Informatik (IN0011) Montag, 09:00–11:00
Donnerstag, 14:00–16:00
Donnerstag, 16:00–17:00
UE 2 Tutorübungen zu Einführung in die Theoretische Informatik (IN0011) Termine in Gruppen

Lern- und Lehrmethoden

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.

Medienformen

Folienpräsentation, Tafelanschrieb, Animationen, Vorlesungsaufzeichnung, Übungsblätter, online Diskussionsforum.

Literatur

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.

Modulprüfung

Beschreibung der Prüfungs- und Studienleistungen

Prüfungsart: Klausur Die Prüfungsleistung wird in Form einer 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.

Wiederholbarkeit

Eine Wiederholungsmöglichkeit wird am Semesterende angeboten.

Kondensierte Materie

Wenn Atome sich zusammen tun, wird es interessant: Grundlagenforschung an Festkörperelementen, Nanostrukturen und neuen Materialien mit überraschenden Eigenschaften treffen auf innovative Anwendungen.

Kern-, Teilchen-, Astrophysik

Ziel der Forschung ist das Verständnis unserer Welt auf subatomarem Niveau, von den Atomkernen im Zentrum der Atome bis hin zu den elementarsten Bausteinen unserer Welt.

Biophysik

Biologische Systeme, vom Protein bis hin zu lebenden Zellen und deren Verbänden, gehorchen physikalischen Prinzipien. Unser Forschungsbereich Biophysik ist deutschlandweit einer der größten Zusammenschlüsse in diesem Bereich.