Westsächsische Hochschule Zwickau

PTI06680 – Theoretical Computer Science

Module

Theoretical Computer Science
Theoretische Informatik

Module number

PTI06680
Version: 1

Faculty

Physikalische Technik / Informatik

Level

Bachelor

Duration

1 Semester

Semester

Summer semester

Module supervisor

Prof. Dr. Ralf Laue
ralf.laue(at)fh-zwickau.de

Lecturer(s)

Prof. Dr. Ralf Laue
ralf.laue(at)fh-zwickau.de
Lecturer in: "Theoretische Informatik"

Prof. Dr. Maren Hinrichs
Maren.Hinrichs(at)fh-zwickau.de
Lecturer in: "Theoretische Informatik"

Course language(s)

German
in "Theoretische Informatik"

ECTS credits

5.00 credits

Workload

150 hours

Courses

4.00 SCH (4.00 SCH Lecture with integrated exercise / seminar-lecture)

Self-study time

90.00 hours
40.00 hours Übungsaufgaben - Theoretische Informatik
30.00 hours Vor-/Nachbereitung - Theoretische Informatik
20.00 hours Self-study - Theoretische Informatik

Pre-examination(s)

Attestation
in "Theoretische Informatik"

Examination(s)

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

Media type

No information

Instruction content/structure

Formale Sprachen
Syntax und Semantik von Programmiersprachen
Sprachen und Grammatik, Syntaxdiagramme
Chomsky-Hierarchie
Erweiterte Backus-Naur-Form

Automaten
Endliche Automaten (EA)
EA und reguläre Sprachen, reguläre Ausdrücke
Kellerautomaten

Anwendungen der Automatentheorie
Codierungs- und Informationstheorie
Informationsgehalt einer Nachricht
Entropie, Redundanz, Fehlertoleranz
Huffman- und Fano-Code
Datenkomprimierung

Algorithmen und Berechenbarkeitstheorie
Definition des Begriffs „Algorithmus“
Loop-Programme, While-Programme, Goto-Programme
primitiv-rekursive Funktionen
Turing-Maschinen
Church'sche These
Halteprobleme
Entscheidbarkeit, Unentscheidbarkeit
Erfüllbarkeitsproblem für Boole’sche Ausdrücke

Komplexitätstheorie
O-Kalkül
P und NP
NP-Vollständigkeit

Qualification objectives

Die Studenten sind mit den grundlegenden Begriffen der theoretischen Informatik vertraut. Durch Erkennen der Zusammenhänge zwischen den theoretischen Konzepten und praktischen Anwendungen wird den Studenten die Wichtigkeit der Auseinandersetzung mit der theoretischen Informatik bewusst.

Die Studenten kennen wichtige Klassen formaler Sprachen und deren Zusammenhang mit verschiedenen Maschinenmodellen. Sie kennen die Grenzen der algorithmischen Lösbarkeit von Problemen, kennen wichtige Komplexitätsklassen und können die Komplexität praktischer Probleme einschätzen.

Sie kennen grundlegende Inhalte aus der Codierungs- und Informationstheorie und die Grundidee von Algorithmen zur fehlertoleranten und zur komprimierten Speicherung bzw. Übertragung von Informationen.

Special admission requirements

Kenntnisse der Inhalte der Module
Programmierung 1 und 2, Algorithmen und Datenstrukturen

Recommended prerequisites

No information

Continuation options

No information

Literature

Uwe Schöning: "Theoretische Informatik – kurz gefasst"

Dirk Hoffmann: "Theoretische Informatik"

Rolf Socher: "Theoretische Grundlagen der Informatik"

Notes

No information