C144 – Theoretische Informatik

Modul
Theoretische Informatik
Theoretical Computer Science
Modulnummer
C144
Version: 2
Fakultät
FIM-INF: Informatikstudiengänge - Fakultät Informatik und Medien
Niveau
Master
Dauer
1 Semester
Turnus
Wintersemester
Modulverantwortliche

Prof. Dr. rer. nat. Sibylle Schwarz
sibylle.schwarz@htwk-leipzig.de
Dozierende

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

Prof. Dr. rer. nat. Johannes Waldmann
johannes.waldmann@htwk-leipzig.de
Dozentin/Dozent in: "Theoretische Informatik"
Sprache(n)

Deutsch
in "Theoretische Informatik"
ECTS-Leistungspunkte

5.00 ECTS-Punkte

Workload

150 Stunden

Lehrveranstaltungen

4.00 SWS (2.00 SWS Vorlesung | 2.00 SWS Übung)
Selbststudienzeit

94.00 Stunden
28.00 Stunden Vorbereitung Lehrveranstaltung - Theoretische Informatik
56.00 Stunden Bearbeitung Prüfungsvorleistung - Theoretische Informatik
10.00 Stunden Vorbereitung Prüfung - Theoretische Informatik
Prüfungsvorleistung(en)

Prüfungsvorleistung Beleg
in "Theoretische Informatik"

Prüfungsvorleistung Referat
in "Theoretische Informatik"
Prüfungsleistung(en)

Prüfung Klausurarbeit
Prüfungsdauer: 90 Minuten | Wichtung: 100%
in "Theoretische Informatik"
Lehr- und Lernformen
  • Vorlesung
  • Übung
  • Bearbeiten von Problemen und Lösungsfindung
  • Selbstudium anhand theoretischer und praktischer Übungsaufgaben
Medienform

keine Angabe
Lehrinhalte/Gliederung
-
  • 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
Qualifikationsziele

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.
Zulassungsvoraussetzung

Keine
Empfohlene Voraussetzungen
  • 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
Literaturhinweise
  • 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.
Aktuelle Lehrressourcen
-

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

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

Informatik | Master (20INM) Pflichtmodul
Link zu Kurs/Lernressourcen im OPAL/Moodle/etc.
Detailansicht schließen
© Modulux (Version 4.1)