C144 – Theoretical Computer Science

Module
Theoretical Computer Science
Theoretische Informatik
Module number
C144
Version: 2
Faculty
FIM-INF: Informatikstudiengänge - Fakultät Informatik und Medien
Level
Master
Duration
1 Semester
Semester
Winter semester
Module supervisor

Prof. Dr. rer. nat. Sibylle Schwarz
sibylle.schwarz@htwk-leipzig.de
Lecturer(s)

Prof. Dr. rer. nat. Sibylle Schwarz
sibylle.schwarz@htwk-leipzig.de
Lecturer in: "Theoretische Informatik"

Prof. Dr. rer. nat. Johannes Waldmann
johannes.waldmann@htwk-leipzig.de
Lecturer in: "Theoretische Informatik"
Course language(s)

German
in "Theoretische Informatik"
ECTS credits

5.00 credits

Workload

150 hours

Courses

4.00 SCH (2.00 SCH Vorlesung | 2.00 SCH Übung)
Self-study time

94.00 hours
28.00 hours Examination preparation - Theoretische Informatik
56.00 hours Bearbeitung Prüfungsvorleistung - Theoretische Informatik
10.00 hours Course preparation - Theoretische Informatik
Pre-examination(s)

Prüfungsvorleistung Beleg
in "Theoretische Informatik"

Prüfungsvorleistung Referat
in "Theoretische Informatik"
Examination(s)

Prüfung Klausurarbeit
Examination time: 90 minutes | Weighting: 100%
in "Theoretische Informatik"
Form of teaching
  • Vorlesung
  • Übung
  • Bearbeiten von Problemen und Lösungsfindung
  • Selbstudium anhand theoretischer und praktischer Übungsaufgaben
Media type

keine Angabe
Instruction content/structure
-
  • Darstellung von Problemen als formale Sprachen
  • Berechenbarkeit:
    • Berechnungsmodelle und deren Grenzen
    • Turing-, GOTO-, LOOP-, WHILE-Berechenbarkeit
    • Primitive und partielle Rekursion
    • Äquivalenz von Berechnungsmodellen, Churchsche These
  • Entscheidbarkeit und Aufzählbarkeit:
    • Reduktionen, Halteprobleme, Postsches Korrespondenzproblem
    • Entscheidbarkeit von Logik-Problemen
  • Komplexitätstheorie:
    • Komplexitätsklassen P,NP, PSPACE, Reduktionen, Vollständigkeit
    • Zusammenhang zwischen Ausdrucksstärke von Berechnungsmodellen und Komplexität von Problemen
  • praktische Beispiele und Folgerungen
Qualification objectives

Nach erfolgreichem Abschluss des Moduls sind die Studierenden in der Lage, fundiert die prinzipiellen Möglichkeiten und Grenzen der verschiedenen Berechenbarkeitsmodelle einzuschätzen. Sie besitzen ein Grundverständnis grundlegender Komplexitätsklassen. Sie können die Komplexität ausgewählter Problembeispiele beurteilen und algorithmisch unlösbare oder schwer handhabbare Probleme als solche erkennen.
Special admission requirements

Keine
Recommended prerequisites
  • Formale Darstellung praktischer Probleme
  • Entwicklung von Lösungen in höheren Programmiersprachen
  • Auswahl geeigneter Algorithmen und Datenstrukturen
  • Methoden zur Bestimmung der Laufzeit von Algorithmen
  • klassische Aussagen- und Prädikatenlogik
  • Automaten, formale Sprachen, Chomsky-Hierarchie
Literature
  • J. E. Hopcroft, J. D. Ullman: „Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie“, Pearson Studium, 2006 oder aktuellere Ausgabe
  • I. Wegener: „Theoretische Informatik“, Teubner, 2005.
  • R. Socher: „Theoretische Grundlagen der Informatik“, Fachbuchverlag Leipzig, 2008.
Current teaching resources
-

Lehrmaterial und aktuelle Informationen: https://informatik.htwk-leipzig.de/schwarz
Notes
-

Prüfungsvorleistung: regelmäßiges erfolgreiches Lösen der Übungsaufgaben und 3 Kurzvorträge zu schriftlichen Übungsaufgaben
Applicability

Informatik | Master (20INM) Pflichtmodul
Link to course/learning resources in OPAL/Moodle/etc.
Close detail view
© Modulux (Version 4.1)