Westsächsische Hochschule Zwickau

PTI06680 – Theoretische Informatik

Modul

Theoretische Informatik
Theoretical Computer Science

Modulnummer

PTI06680
Version: 1

Fakultät

Physikalische Technik / Informatik

Niveau

Bachelor

Dauer

1 Semester

Turnus

Sommersemester

Modulverantwortliche/-r

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

Dozent/-in(nen)

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

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

Lehrsprache(n)

Deutsch
in "Theoretische Informatik"

ECTS-Credits

5.00 Credits

Workload

150 Stunden

Lehrveranstaltungen

4.00 SWS (4.00 SWS Vorlesung mit integr. Übung / seminaristische Vorlesung)

Selbststudienzeit

90.00 Stunden
40.00 Stunden Übungsaufgaben - Theoretische Informatik
30.00 Stunden Vor-/Nachbereitung - Theoretische Informatik
20.00 Stunden Selbststudium - Theoretische Informatik

Prüfungsvorleistung(en)

Testat
in "Theoretische Informatik"

Prüfungsleistung(en)

schriftliche Prüfungsleistung
Modulprüfung | Prüfungsdauer: 120 min | Wichtung: 100%
in "Theoretische Informatik"

Medienform

Keine Angabe

Lehrinhalte/Gliederung

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

Qualifikationsziele

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.

Besondere Zulassungsvoraussetzung

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

Empfohlene Voraussetzungen

Keine Angabe

Fortsetzungsmöglichkeiten

Keine Angabe

Literatur

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

Dirk Hoffmann: "Theoretische Informatik"

Rolf Socher: "Theoretische Grundlagen der Informatik"

Hinweise

Keine Angabe