Hochschule Darmstadt - Fb Informatik

Drucken| Layout| Design| Schriftgröße English|
Modulbeschreibung
Modul:Theoretische Informatik

Theoretical Computer Science

Belegnummern:30.7332 [PVL 30.7333]
Sprache:deutsch
Zuordnung:Bachelor 2021 - 3. Semester
Bachelor dual KITS 2021 - 4. Semester
Bachelor dual KoSI 2021 - 4. Semester
Bachelor KMI 2021 - 3. Semester
Lehrform:V+Ü = Vorlesung+Übung
SWS:2+2
CP:5
Prüfung:Klausur
Anmeldung zur Prüfung:explizit und unabhängig von der Belegung
PVL (z.B. Praktikum):unbenotet (Abgabe von 50 % korrekt gelösten Übungsaufgaben.)
Häufigkeit des Angebots:jedes Semester (zuletzt im SS 2022)
Erforderliche Vorkenntnisse:Grundlegende Kenntnisse auf Grundlegende Kenntnisse auf Bachelorniveau in Mathematik, Algorithmen und Datenstrukturen sowie Programmierkenntnisse in Mathematik und Programmierung
Lernziele:Die Studierenden werden
  • ein Verständnis für grundlegende Konzepte, Begriffe und Zusammenhänge aus den Teilgebieten Automatentheorie und formale Sprachen entwickeln.
  • ein Verständnis für grundlegende Beweismethoden entwickeln. die Fähigkeit herausbilden, einfache Beweise selbständig zu führen.
  • Kenntnis von der Leistungsfähigkeit unterschiedlicher Beschreibungsmittel erhalten und die Fähigkeit entwickeln, die Beschreibungsmittel selbständig zu gebrauchen.
  • das Wissen um den Zusammenhang zwischen der Leistungsfähigkeit und der algorithmischen Beherrschbarkeit unterschiedlicher Beschreibungsmittel erhalten.
  • ein Verständnis nichtdeterministischer Maschinenmodelle und deren Bedeutung entwickeln.
Lehrinhalte:
  • Grundbegriffe: Wörter, Alphabete, Relationen, Operationen über Relationen
  • Formale Sprachen: Das Wortproblem, Bezug zu allgemeinen Entscheidungsproblemen, effiziente versus nicht-effiziente Lösungsalgorithmen für das Wortproblem
  • Formale Sprachen und Automatentheorie: deterministische und nichtdeterministische endliche Automaten, Anwendung endlicher Automaten, Äquivalenz deterministischer und nichtdeterministischer endlicher Automaten, Minimierungsalgorithmus, deterministische und nichtdeterministische Kellerautomaten
  • Formale Sprachen und Grammatiken: Chomsky Hierarchie, effizient aufzählbare Sprachen und das Wortproblem (Unentscheidbarkeit des Wortproblems), kontextsensitive Grammatiken und das Wortproblem (Beziehung zur Komplexitätsklasse NP), rechtslineare Grammatiken, Abschlusseigenschaften, reguläre Ausdrü;cke (inkl. Verwendung in Skriptsprachen), Abschlusseigenschaften, rechtslineare Sprachen und das Wortproblem (endliche Automaten), kontextsensitive Grammatiken und das Wortproblem, kontextfreie Grammatiken und das Wortproblem (Chomsky-Normalform, CYK-Algorithmus), Anwendungen kontextfreier Sprachen (Syntax von Programmiersprachen, XML-basierte Sprachen und Sprachen zur Beschreibung von Kommunikationsprotokollen), kontextfreie Sprachen und nichtdeterministische Kellerautomaten, deterministische Kellerautomaten
Literatur:
  • Hromkovic, J.: Theoretische Informatik, Teubner Verlag, Stuttgart, 2002.
  • Schöning, U.: Theoretische Informatik - kurz gefasst, Spektrum Akademischer Verlag, Heidelberg, 1997.
  • Wegener, I.: Theoretische Informatik - eine algorithmenorientierte Einführung, Teubner Verlag, Stuttgart, 1999
Modulverantwortung:Steffen Lange
Freigabe ab:WS 2022/2023

[Fachbereich Informatik] [Hochschule Darmstadt]
© 2008 - 2022 FBI OBS Team. Alle Rechte vorbehalten.