PTI06100 – Theoretical Computer Science

Module
Theoretical Computer Science
Theoretische Informatik
Module number
PTI06100
Version: 1
Faculty
Physikalische Technik / Informatik
Level
Bachelor
Duration
1 Semester
Semester
Summer semester
Module supervisor
Lecturer(s)

FG Informatik
Tina.Geweniger(at)fh-zwickau.de
Lecturer in: "Theoretische Informatik"

Dr. Martin Hünniger
Martin.Huenniger(at)fh-zwickau.de
Lecturer in: "Theoretische Informatik"

Course language(s)

German
in "Theoretische Informatik"

ECTS credits

6.00 credits

Workload

180 hours

Courses

4.00 SCH (3.00 SCH Vorlesung | 1.00 SCH Seminar)

Self-study time

120.00 hours
60.00 hours Self-study - Theoretische Informatik
60.00 hours Vor-/Nachbereitung - Theoretische Informatik

Pre-examination(s)

Attestation
in "Theoretische Informatik"

Examination(s)

schriftliche Prüfungsleistung
Module examination | Examination time: 90 min | Weighting: 100%
in "Theoretische Informatik"

Media type
No information
Instruction content/structure
  • Formale Sprachen
  • Grammatiken (Chomsky-Hierarchie)
  • Berechnungsmodelle: endliche Automaten, Kellerautomaten,Turingmaschinen
  • Berechenbarkeit, Entscheidbarkeit, Halteprobleme
  • Einführung in die Komplexitätstheorie
Qualification objectives

Die Studierenden verstehen die theoretischen Grundlagen der praktischen und der angewandten Informatik. Sie kennen wichtige Klassen formaler Sprachen als Grundlage von Programmier- und Beschreibungssprachen und deren Zusammenhang mit verschiedenen Maschinenmodellen. Sie können die verschiedenen Sprachklassen und Maschinenmodelle zur Repräsentation und Lösung praktischer Aufgabenstellungen anwenden.

Sie kennen die Grenzen der algorithmischen Lösbarkeit von Problemen.

Sie kennen wichtige Komplexitätsklassen und können die Komplexität praktischer Probleme einschätzen.

Special admission requirements

keine

Recommended prerequisites

Beherrschen einer Programmiersprache (z. B. aus PTI600/PTI602 - Programmierung 1)
sowie Inhalte entsprechend der Module:
PTI620 - Diskrete Mathematik und Logik
PTI621 - Algorithmen und Datenstrukturen

Continuation options
No information
Literature
  • Schöning: Theoretische Informatik - kurzgefasst, Spektrum 2008
  • Hopcroft; Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Oldenbourg 2000
  • Vossen, Witt: Grundkurs Theoretische Informatik, Vieweg & Sohn 2006
  • Socher: Theoretische Grundlagen der Informatik, Hanser 2007
Notes
No information