t.BA.IT.THIN.19HS (Theoretische Informatik) 
Modul: Theoretische Informatik
Diese Information wurde generiert am: 25.04.2024
Nr.
t.BA.IT.THIN.19HS
Bezeichnung
Theoretische Informatik
Veranstalter
T CAI
Credits
4

Beschreibung

Version: 3.0 gültig ab 01.02.2022
 

Kurzbeschrieb

 Grundbegriffe sowie Konzepte der theoretischen Informatik, Modelle zur Beurteilung der Leistungsfähigkeit aktueller und zukünftiger Computersysteme:
Formale Sprachen, Automatentheorie, Berechenbarkeit und Komplexität

Modulverantwortung

 Olaf Stern, strf

Lernziele (Kompetenzen)
Ziel Kompetenzen Taxonomiestufen
(1) Sie können die wichtigsten formalen Sprachen/Grammatiken und die entsprechenden Automatentypen erläutern und deren Zusammenhänge darlegen. Sie können Automaten für gegebene Sprachen entwerfen, die diese erkennen bzw. definieren (und umgekehrt). F, M K2, K3
(2) Sie können die wichtigen Ansätzen zur Formalisierung der Konzepte der Berechenbarkeit und des Algorithmus veranschaulichen und die Äquivalenz der verschiedenen Ansätze erkennen. Sie können die Konzepte der entscheidbaren und semi-entscheidbaren Probleme darlegen und erklären in welchem Verhältnis diese zueinander stehen. F, M K2
(3) Sie können die wichtigsten Komplexitätsklassen - insbesondere P und NP - und einfache Notationen dazu (O- und Omega-Notation) erklären. Sie verstehen die Frage ob P=NP ist und können ihre Bedeutung diskutieren. Sie können die Methode der polynomialen Reduktion an einfachen Beispielen anwenden. F, M K2, K3

Modulinhalte

 Motivation der theoretischen Informatik:
  • Formale Berechnungsmodelle
  • Grundlegende Prinzipien erkennen, unabhängig von Hard- und Software
  • Grenzen der automatischen Berechnungen

(1) Formale Sprachen / Automatentheorie:
  • Grundlegende Definitionen der Formalen Sprachen
  • Reguläre Sprachen, endlicher Automat (DEA, NEA, e-NEA)
  • Kontextfreie Sprachen, Kellerautomaten
  • (Rekursive Sprachen), Turingmaschine (TM)
  • Chomsky-Hierarchie

(2) Berechenbarkeit und Algorithmus-Begriff:
  • Berechenbare Funktionen Church'sche These
  • Äquivalenz von TM und Computer
  • Berechenbarkeit und Programmier-Sprachen: GOTO-, While- und Loop-Programme.
  • Algorithmus-Begriff
  • Primitive Rekursion
  • Nicht-Entscheidbarkeit und Entscheidbarkeit: Diagonalisierungssprache Ld, Satz von Rice, Fleissige Bieber
  • Semi-entscheidbare Probleme: Halteproblem, Game-of-Life, (Collatz-Zahlen ?)
  • Reduktion

(3) Komplexitätstheorie
  • Komplexität von Algorithmen
  • O-Notation (Omega-Notation)
  • polynomiale Funktionen und exponentielle Funktionen
  • Klasse P, Klasse NP
  • NP-vollständig, NP-schwierig
  • Polynomialzeit-Reduktion

Lehrmittel/Materialien

 - Ausführlicher Foliensatz, Ergänzungsunterlagen, Aufgabenserien mit Musterlösungen
- John E. Hopcroft, Rajeev Motwani, und Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Berechenbarkeit bzw. Introduction to Automata Theory, Languages, and Computation, Pearson Studium, Addison-Wesley Verlag, (auch als Taschenbuch und e-Book verfügbar), 2011 / 2013

Ergänzende Literatur

 - Hans-Joachim Böckenhauer, Juraj Hromkovic: Formale Sprachen, Springer Verlag, 2013
- Juray Hromkovic: Theoretische Informatik, Teubner Verlag, 3. Auflage, 2007
- Uwe Schöning: Theoretische Informatik - kurz gefasst, Spektrum Akademischer Verlag, 5. Auflage, 2008

Zulassungs-voraussetzungen 

 keine

Unterrichtssprache

 (X) Deutsch ( ) Englisch

Teil des Internationalen Profils

 ( ) Ja (X) Nein

Modulausprägung

 Typ 2a
  Details siehe unter: T_CL_Modulauspraegungen_SM2025

Leistungsnachweise
Bezeichnung Art Form Umfang Bewertung Gewichtung
Leistungsnachweise während Studiensemester Aufgabenserien schriftlich ca. 9 Serien Punkte => Note 20%
Semesterendprüfung Klausur schrifltich 90 Min. Note 80%

Bemerkungen

  

Rechtsgrundlage

 Die Modulbeschreibung ist neben Rahmenprüfungsordnung und Studienordnung Teil der Rechtsgrundlage. Sie ist verbindlich. Eine in der ersten Unterrichtswoche des Semesters schriftlich festgehaltene und kommunizierte Modulvereinbarung kann die Modulbeschreibung präzisieren. Die Modulvereinbarung ersetzt nicht die Modulbeschreibung.

Hinweis

Kurs: Theoretische Informatik - Vorlesung
Nr.
t.BA.IT.THIN.19HS.V
Bezeichnung
Theoretische Informatik - Vorlesung

Hinweis

  • Für das Stichdatum 01.08.2099 ist kein Modulbeschreibungstext im System verfügbar.