Theoretische Informatik

Fakultät

Ingenieurwissenschaften und Informatik

Version

Version 6.0 vom 25.02.2023

Modulkennung

11B0416

Modulname (englisch)

Introduction to the Theory of Computation

Studiengänge mit diesem Modul
  • Informatik - Medieninformatik (B.Sc.)
  • Informatik - Technische Informatik (B.Sc.)
  • Lehramt an berufsbildenden Schulen - Teilstudiengang Informationstechnik (M.Ed.)
Niveaustufe

3

Kurzbeschreibung

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.

Lehrinhalte
  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
Lernergebnisse / Kompetenzziele

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.

Lehr-/Lernmethoden

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.

Empfohlene Vorkenntnisse

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

Modulpromotor

Morisse, Karsten

Lehrende
  • Morisse, Karsten
  • Kleuker, Stephan
Leistungspunkte

5

Lehr-/Lernkonzept
Workload Dozentengebunden
Std. WorkloadLehrtyp
60Vorlesungen
Workload Dozentenungebunden
Std. WorkloadLehrtyp
45Veranstaltungsvor-/-nachbereitung
15Prüfungsvorbereitung
30Literaturstudium
Literatur

* 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

Prüfungsleistung
  • Mündliche Prüfung
  • Klausur 2-stündig
  • Portfolio Prüfung
Bemerkung zur Prüfungsform

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%)

Dauer

1 Semester

Angebotsfrequenz

Wintersemester und Sommersemester

Lehrsprache

Deutsch