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