Module Import 04IN1018 - Fundamentals of Theoretical Computer Science

Status: Published
Workload8 ECTS = 240 hrs
Credits, Weight8 ECTS, (n.s.)
Language of Instruction German
Semester (n.s.)
Duration1 Sem.
M/E Mandatory
Courses
Course No. Type Name MA/EL Workload Credits Contact Hours Selfstudy Group Size
04IN1018-1 Lecture Fundamentals of Theoretical Computer Science (n.s.) 6 ECTS = 180 hrs - 4 hrs/week = 60 hrs 120 hrs (n.s.)
04IN1018-2 Exercise Fundamentals of Theoretical Computer Science (n.s.) 3 ECTS = 90 hrs - 2 hrs/week = 30 hrs 60 hrs (n.s.)
Learning Outcomes

Die Studierenden verfügen über ein Verständnis für die Grundlagenfragen der Informatik, kennen Automaten und formale Sprachen sowie deren Zusammenhänge, kennen Verfahren zur Beurteilung der Berechenbarkeit und Entscheidbarkeit, kennen Komplexitätsmaße und Methoden zur Bewältigung von Komplexität und können mathematische Methoden zur Klärung von Grundlagenfragen der Informatik anwenden.

Content

(not specified)

04IN1018-1 - Fundamentals of Theoretical Computer Science
  1. Reguläre Sprachen - endliche Automaten, determiniert und indeterminiert
  2. Kontextfreie Sprachen - indeterminierte Push-Down-Automaten
  3. Kontextsensitive = beschränkte Sprachen - indeterminierte Linear Beschränkte Automaten
  4. Rekursiv aufzählbare Sprachen - determinierte und indeterminierte Turing Maschinen
  5. Unentscheidbarkeit des Halteproblems und verwandter Probleme
  6. Komplexität und NP-Vollständigkeit von SAT und verwandter Probleme
Teaching Methods

(not specified)

Prerequisites
  • Grundkenntnisse der diskreten Mathematik (Mengen, Relationen, Abbildungen)
  • Grundlegende Beweistechniken
  • Grundlagen der Logik
Examination Methods

Klausur
Voraussetzung für die Vergabe von Leistungspunkten: regelmäßige und qualifizierte Teilnahme;
Stellenwert für die Note in der Endnote BEd: 4,44% entsprechend den LP (8:180)

Credit Requirements

(not specified)

References

(not specified)

04IN1018-1 - Fundamentals of Theoretical Computer Science

K. Erk, L. Priese. Theoretische Informatik, Springer Verlag, 2000

J. Hopcroft, R. Motwani, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson Studium, 3.Aktualisierte Auflage, 2011

Uwe Schöning: Theoretische Informatik - Kurzgefasst, Spektrum Hochschultaschenbücher, Spektrum Akademischer Verlag, 2008

Responsible / Organizational Unit
Sofronie-Stokkermans, Viorica / Institute for Computer Science
Additional Information

(not specified)

Last change
Apr 24, 2018 by Frey, Johannes
Last Change Module
Jun 11, 2013 by Frey, Johannes