Technische Universität Ilmenau

Automaten und Komplexität - 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 Fachnummer 100535 - allgemeine Informationen
Fachnummer100535
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer2241 (Automaten und Logik)
Fachverantwortliche(r)Prof. Dr. Dietrich Kuske
SpracheDeutsch
TurnusSommersemester
Vorkenntnisse

Umgang mit mengentheoretischen Begriffen und Notationen (z.B. erworben in "Mathematik 1")

Lernergebnisse

Die Studierenden

  • kennen die Stufen 0, 2 und 3 der Chomsky-Hierarchie, ihre automatentheoretischen Charakterisierungen und können die Umwandlungen ausführen,
  • sind in der Lage, Nachweise der Nicht-Regularität zu führen,
  • sind mit Abschluss- und algorithmischen Eigenschaften der regulären und kontextfreien Sprachen vertraut.

Die Studierenden

  • kennen die Klassen der semi-entscheidbaren und der entscheidbaren Probleme mit wesentlichen Beispielen,
  • sind in der Lage, die Church-Turing These zu formulieren, ihre Bedeutung darzustellen und Argumente zu ihrer Begründung anzugeben.

Die Studierenden

  • kennen die Komplexiätsklassen P und NP und einige NP-vollständige Probleme,
  • können erläutern, warum die NP-schweren Probleme nicht effizient lösbar sind.
Inhalt
  • reguläre Sprachen: deterministische und nichtdeterministische endliche Automaten, reguläre Ausdrücke, effektiver Abschluss unter Booleschen Operationen, Verkettung und Iteration, Entscheidbarkeit von Leerheit, Inklusion und Äquivalenz, Pumping-Lemma
  • kontextfreie Sprachen: Kellerautomaten, Parsing, effektiver Abschluss unter positiven Booleschen Operationen, Verkettung und Iteration, Entscheidbarkeit der Leerheit, Pumping-Lemma, Nichtabschluss unter Schnitt
  • semi-entscheidbare Sprachen: Turing-Maschine
  • Berechenbarkeit: Church-Turing These, Unentscheidbarkeit des Halteproblems und der Universalität von kontextfreien Sprachen
  • Komplexitätstheorie: die Klassen P und NP, NP-Vollständigkeit, 3-SAT, graphentheoretische Probleme
Medienformen

Tafel, Übungsblätter

Literatur

Schöning "Theoretische Informatik kurzgefasst"

Lehrevaluation
Spezifik im Studiengang Bachelor Ingenieurinformatik 2013
FachnameAutomaten und Komplexität
Prüfungsnummer2200619
Leistungspunkte3
Präsenzstudium (h)34
Selbststudium (h)56
VerpflichtungPflicht
Abschlussschriftliche Prüfungsleistung, 90 Minuten
Details zum Abschluss
max. Teilnehmerzahl
Spezifik im Studiengang polyvalenter Bachelor Polyvalenter Bachelor mit Lehramtsoption für berufsbildende Schulen - Metalltechnik 2013 (IN), polyvalenter Bachelor Polyvalenter Bachelor mit Lehramtsoption für berufsbildende Schulen - Elektrotechnik 2013 (IN)
FachnameAutomaten und Komplexität
Prüfungsnummer2200371
Leistungspunkte3
Präsenzstudium (h)34
Selbststudium (h)56
VerpflichtungPflicht
Abschlusskeiner
Details zum Abschluss
max. Teilnehmerzahl

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