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