Internal Preview! The data shown below is not valid for students! Please refer to the official Module Descriptions at the Examination Office.
Grundzüge der Theoretischen Informatik TI

General

study semester
3
standard study semester
6
cycle
jedes Wintersemester
duration
1 Semester
SWS
6
ECTS
9
teaching language
Englisch

People

responsible
Prof. Dr. Raimund Seidel
lectures
Prof. Dr. Raimund Seidel
Prof. Dr. Bernd Finkbeiner
Prof. Dr. Kurt Mehlhorn
Prof. Dr. Markus Bläser

Assessment & Grades

entrance requirements

Programmierung 1 und 2 und Mathematik für Informatiker 1 und 2 oder vergleichbare Veranstaltungen der Mathematik sind empfohlen.

assessment / exams

Erfolgreiche Bearbeitung der Übungsaufgaben berechtigt zur Klausurteilnahme.

grade

Wird aus Leistungen in Klausuren, Übungen und praktischen Aufgaben ermittelt. Die genauen Modalitäten werden vom Modulverantwortlichen bekannt gegeben.

Workload

course type /weekly hours
  4 SWS Vorlesung
+ 2 SWS Übung
= 6 SWS
total workload
   90 h Präsenzstudium
+ 180 h Eigenstudum
= 270 h (= 9 ECTS)

Aims / Competences to be developed

Die Studierenden kennen verschiedene Rechenmodelle und ihre relativen Stärken und Mächtigkeiten.

Sie können für ausgewählte Probleme zeigen, ob diese in bestimmten Rechenmodellen lösbar sind oder nicht.

Sie verstehen den formalen Begriff der Berechenbarkeit wie auch der Nicht-Berechenbarkeit.

Sie können Probleme aufeinander reduzieren.

Sie sind vertraut mit den Grundzügen der Ressourcenbeschränkung (Zeit, Platz) für Berechnungen und der sich daraus ergebenden Komplexitätstheorie.

Content

Die Sprachen der Chomsky Hierarchie und ihre verschiedenen Definitionen über Grammatiken und Automaten; Abschlusseigenschaften; Klassifikation von bestimmten Sprachen („Pumping lemmas“);

Determinismus und Nicht-Determinismus;

Turing Maschinen und äquivalente Modelle von allgemeiner Berechenbarkeit (z.B. μ-rekursive Funktionen, Random Access Machines) Reduzierbarkeit, Entscheidbarkeit, Nicht-Entscheidbarkeit;

Die Komplexitätsmaße Zeit und Platz; die Komplexitätsklassen P und NP;

Grundzüge der Theorie der NP-Vollständigkeit

Literature & Reading

Bekanntgabe jeweils vor Beginn der Vorlesung auf der Vorlesungsseite im Internet.

Additional Information

Dieses Modul ist inhaltsgleich mit dem englischsprachigen Modul Introduction to Theoretical Computer Science.

Curriculum

This module is part of the following study programmes:

Informatik BSc: Grundlagen der Informatik
study semester: 3 / standard study semester: 6
Cybersicherheit BSc: Grundlagen der Informatik
study semester: 3 / standard study semester: 6
Medieninformatik BSc: Grundlagen der Informatik
study semester: 4 / standard study semester: 6
Lehramtsstudienfach Informatik: Grundmodule
study semester: / standard study semester: 3-5
Data Science and Artificial Intelligence BSc: Grundlagen der Informatik
study semester: 3 / standard study semester: 6
Eingebettete Systeme BSc: Wahlpflichtbereich Informatik
study semester: / standard study semester: