Technische Universität Ilmenau

Berechenbarkeit und Komplexitätstheorie - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu unseren Studiengängen. Rechtlich verbindliche Angaben zum Verlauf des Studiums entnehmen Sie bitte dem jeweiligen Studienplan (Anlage zur Studienordnung). Bitte beachten Sie diesen rechtlichen Hinweis. Angaben zum Raum und Zeitpunkt der einzelnen Lehrveranstaltungen entnehmen Sie bitte dem aktuellen Vorlesungsverzeichnis.

Fachinformationen zu Berechenbarkeit und Komplexitätstheorie im Studiengang Bachelor Informatik 2010
ACHTUNG: wird nicht mehr angeboten!
Fachnummer5346
Prüfungsnummer2200082
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2241 (Automaten und Logik)
Fachverantwortliche(r)Prof. Dr. Dietrich Kuske
TurnusWintersemester
SpracheDeutsch
Leistungspunkte4
Präsenzstudium (h)34
Selbststudium (h)86
VerpflichtungPflicht
Abschlussmündliche Prüfungsleistung, 20 Minuten
Details zum Abschluss
max. Teilnehmerzahl
Vorkenntnisse

Fach "Algorithmen und Datenstrukturen", "Grundlagen und diskrete Strukturen" und "Automaten und Formale Sprachen"

Lernergebnisse

Fachkompetenz: Die Studierenden kennen die grundlegenden Begriffe und Sachverhalte der Berechbarkeitstheorie und der NP-Vollständigkeitstheorie sowie weitere Grundkonzepte der Komplexitätstheorie sowie die zentrale Bedeutung des P-NP-Problems. Sie kennen wesentliche Vertreter der wichtigen Komplexitätsklassen.

Methodenkompetenz: Die Studierenden können Simulationen beschreiben, Reduktionen (Berechbarkeitstheorie und NP-Vollständigkeitsbeweise) durchführen und analysieren, sie können Probleme in Komplexitätsklassen einsortieren.

Inhalt
  • Berechnungsmodelle (Turingmaschine, Registermaschine)
  • Simulation zwischen Modellen
  • Formalisierung des Berechenbarkeitsbegriffs, Church-Turing-These
  • Halteproblem
  • Nicht berechenbare Funktionen, nicht entscheidbare Probleme
  • Reduktion
  • Unentscheidbarkeit semantischer Fragen (Satz von Rice)
  • Postsches Korrespondenzproblem, Unentscheidbarkeit bei Grammatiken und logischen Systemen
  • Die Klassen P und NP
  • NP-Vollständigkeit
  • Satz von Cook/Levin
  • P-NP-Problem
  • Reduktionen, NP-Vollständigkeitsbeweise
  • Grundlegende NP-vollständige Probleme
Medienformen

Vorlesung: Folien, Folienkopien (Online)

Übung: Übungsblätter (Online)

Literatur
  • Schöning "Theoretische Informatik kurzgefasst"
  • Asteroth, Baier "Theoretische Informatik"
  • Wegener "Theoretische Informatik"
  • Hopcroft, Motwani, Ullman "Einführung in die Automatentheorie, Formale Sprachen und Komplexität
Lehrevaluation

Pflichtevaluation:

Freiwillige Evaluation:

WS 2010/11 (Vorlesung, Übung)

WS 2011/12 (Vorlesung, Übung)

WS 2012/13 (Vorlesung)

WS 2013/14 (Vorlesung)

Hospitation:

Informationen und Handreichungen zur Pflege von Modul- und Fachbeschreibungen durch den Modul- oder Fachverantwortlichen finden Sie auf den Infoseiten zum Modulkatalog.