Theoretische Informatik

Ingenieurwissenschaften und Informatik

Version 6.0 vom 25.02.2023

11B0416

Introduction to the Theory of Computation

• Informatik - Medieninformatik (B.Sc.)
• Informatik - Technische Informatik (B.Sc.)
• Lehramt an berufsbildenden Schulen - Teilstudiengang Informationstechnik (M.Ed.)

3

Die theoretische Informatik bildet sowohl hinsichtlich der Begrifflichkeiten als auch der Betrachtungen und Schlußweisen eine sehr wichtige Grundlage des Informatikstudiums und ist als Kernfach anzusehen.

1. Formale Sprachen und Chomsky-Hierarchie
2. Endliche Automaten und reguläre Ausdrücke
3. Kellerautomaten und kontextfreie Grammatiken
4. Turingmaschine
5. Berechenbarkeit
6. Komplexitätstheorie

Wissensverbreiterung
Die Studierenden kennt die wichtigsten Grundbegriffe und Modelle der theoretischen Informatik einschließlich ihrer Grenzen, kann sie praktischen Anwendungen zuordnen und sie bei deren Bewertung und Einschätzung verwenden.
Wissensvertiefung
Die Studierenden erkennen und verstehen die theoretischen Grundlagen der Informatik in praktischen Anwendungen.
Können - instrumentale Kompetenz
Die Studierenden können für eigenen Anwendungsfälle die theoretischen Modelle und Konzepte der Informatik richtig identifizieren und einsetzen. Sie können Modelle der theoretischen Informatik eigenständig entwerfen und im Rahmen einer Argumentation begründen.
Können - kommunikative Kompetenz
Studierende können Modelle der Theoretischen Informatik entwickeln, argumentieren und präsentieren.
Können - systemische Kompetenz
Die Studierenden können die theoretischen Konzepte in eigene Problemlösungen integrieren.

Die Veranstaltung wird als Vorlesung oder nach der Methode des Inverted Classroom durchgeführt, bei der die gemeinsame Veranstaltungszeit (Kontaktzeit) nach der individuellen Vorbereitung durch die Studierenden durch verschiedene Lehrformen als Übungen, Diskussionen und Arbeit in Kleingruppen durchgeführt werden.

Mathematik 1 (I); Mathematik 2 (I); Programmierung 1 (I)

Morisse, Karsten

• Morisse, Karsten
• Kleuker, Stephan

5

* Hopcroft, Motwani, Ulman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit, 3. Auflage, Pearson, 2011* Lewis, Papadimitriou: Elements of the Theory of Computation, Prentice-Hall, 2nd Ed., 1997* Schöning: Theoretische Informatik kurz gefaßt* Sipser: Introduction to the Theory of Computation, Thomson, 2013* Erk, Priese: Theoretische Informatik, Springer-Verlag, 2008* Hoffmann: Theoretische Informatik, Hanser-Verlag, 2015

• Mündliche Prüfung
• Klausur 2-stündig
• Portfolio Prüfung

Je nach Teilnehmerzahl entweder Klausur oder mündliche Prüfung. Alternativ bei Einsatz der ICM-MethodePortfolio-Prüfung bestehend aus:
1) Alternativ Klausur / mdl. Prüfung (Gewichtung 80%) und
2) semesterbegleitende Übungen (Gewichtung 20%)

1 Semester

Wintersemester und Sommersemester

Deutsch