Website
Modulhandbuch

Modul CS2000-KP08, CS2000

Theoretische Informatik (TI)

Dauer:
1 Semester
Angebotsturnus:
Jedes Wintersemester
Leistungspunkte:
8
Studiengang, Fachgebiet und Fachsemester:
  • Bachelor Medieninformatik 2020 (Pflicht), Informatik, 3. Fachsemester
  • Bachelor Informatik 2019 (Pflicht), Grundlagen der Informatik, 3. Fachsemester
  • Bachelor Robotik und Autonome Systeme 2020 (Wahlpflicht), Informatik, 5. oder 6. Fachsemester
  • Bachelor Medizinische Informatik 2019 (Pflicht), Informatik, 3. Fachsemester
  • Bachelor Informatik 2016 (Pflicht), Grundlagen der Informatik, 3. Fachsemester
  • Bachelor Robotik und Autonome Systeme 2016 (Wahlpflicht), Informatik, 5. oder 6. Fachsemester
  • Bachelor IT-Sicherheit 2016 (Pflicht), Informatik, 3. Fachsemester
  • Bachelor Medizinische Ingenieurwissenschaft 2011 (Wahlpflicht), Informatik, 5. Fachsemester
  • Bachelor Medizinische Informatik 2014 (Pflicht), Informatik, 3. Fachsemester
  • Bachelor Informatik 2014 (Pflicht), Grundlagen der Informatik, 3. Fachsemester
  • Bachelor Medieninformatik 2014 (Pflicht), Informatik, 3. Fachsemester
  • Bachelor Medizinische Informatik 2011 (Pflicht), Informatik, 3. Fachsemester
  • Bachelor Informatik 2012 (Pflicht), Grundlagen der Informatik, 3. Fachsemester
Lehrveranstaltungen:
  • CS2000-Ü: Theoretische Informatik (Übung, 2 SWS)
  • CS2000-V: Theoretische Informatik (Vorlesung, 4 SWS)
Workload:
  • 90 Stunden Präsenzstudium
  • 135 Stunden Selbststudium und Aufgabenbearbeitung
  • 15 Stunden Prüfungsvorbereitung
Lehrinhalte:
  • Formalisierung von Problemen mittels Sprachen
  • formale Grammatiken
  • reguläre Sprachen, endliche Automaten
  • kontextfreie Sprachen, Kellerautomaten
  • sequentielle Berechnungsmodelle: Turing-Maschinen, Registermaschinen
  • sequentielle Komplexitätsklassen
  • Simulation, Reduktion, Vollständigkeit
  • Erfüllbarkeitsproblem, NP-Vollständigkeit
  • (Un-)Entscheidbarkeit und Aufzählbarkeit
  • Halteproblem und Church-Turing These
Qualifikationsziele/Kompetenzen:
  • Studierenden können die theoretischen Grundlagen der Syntax und der operationalen Semantik von Programmiersprachen selbst darstellen
  • Sie können Formalisierungen ineinander umwandeln, indem sie Sätze der Theoretischen Informatik anwenden
  • Sie können algorithmische Probleme nach ihrer Komplexität klassifizieren
  • Sie können algorithmische Probleme modellieren und mit geeigneten Werkzeugen lösen
  • Sie können die Möglichkeiten und Grenzen der Informatik beurteilen
Vergabe von Leistungspunkten und Benotung durch:
  • Klausur sowie Studienleistungen
Voraussetzung für:
Setzt voraus:
Modulverantwortlicher:
Lehrende:
Literatur:
  • J. Hopcroft, R. Motwani, J. Ullman: Introduction to Automata Theory, Languages and Computation - Addison Wesley, 2001
Sprache:
  • Wird nur auf Deutsch angeboten
Letzte Änderung:
17.7.2019