Hochschule Darmstadt - Fb Informatik

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

Theoretical Computer Science

Belegnummern:30.7410 [PVL 30.7411]
Sprache:deutsch
Zuordnung:Bachelor 2014 - 4. Semester
Bachelor dual KESS 2014 - 6. Semester
Bachelor dual KITS 2014 - 6. Semester
Bachelor dual KoSI 2014 - 6. Semester
Bachelor KMI 2014 - 4. Semester
Lehrform:V+Ü = Vorlesung+Übung
SWS:4+2
CP:7.5
Prüfung:Klausur
Anmeldung zur Prüfung:explizit und unabhängig von der Belegung
PVL (z.B. Praktikum):unbenotet (Lösen von 50 % der Übungsaufgaben)
Häufigkeit des Angebots:jedes Semester (zuletzt im WS 2019/2020)
Erforderliche Vorkenntnisse:Grundlegende Kenntnisse auf Bachelorniveau in Mathematik und Programmierung
Lernziele:Die Studierenden sollen
  • ein Verständnis für grundlegende Konzepte, Begriffe und Zusammenhänge aus den Teilgebieten Automatentheorie, formale Sprachen, Berechnungstheorie und P/NP-Theorie entwickeln.
  • ein Verständnis für grundlegende Beweismethoden entwickeln.
  • die Fähigkeit heraus bilden, 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.
  • ein Verständnis von deterministischen und nichtdeterministischen Maschinenmodellen und die algorithmische Lösbarkeit/Nichtlösbarkeit von Problemen sowie die inhärente Komplexität von Problemen entwickeln.
Lehrinhalte:
  • Grundbegriffe: Wörter, Alphabete, Relationen, Operationen über Relationen
  • Formale Sprachen: Das Wortproblem, Bezug zu allgemeinen Entscheidungsproblemen
  • Formale Sprachen und Automatentheorie: deterministische und nichtdeterministische endliche Automaten, Anwendung endlicher Automaten, Äquivalenz deterministischer und nichtdeterministischer endlicher Automaten, Minimierungsalgorithmus, endliche Automaten mit Worttransitionen, reguläre Sprachen und das Wortproblem, deterministische und nichtdeterministische Kellerautomaten
  • Formale Sprachen und Grammatiken: Chomsky Hierarchie, rechtslineare Grammatiken, reguläre Ausdrücke inkl. Anwendung in Skriptsprachen, Zusammenhang zu endlichen Automaten, Abschlusseigenschaften regulärer Sprachen, kontextsensitive Grammatiken und das Wortproblem, kontextfreie Grammatiken und das Wortproblem (Chomsky-Normalform, CYK-Algorithmus), Anwendungen kontextfreier Sprachen (Syntax von Programmiersprachen, XML-basierte Sprachen und Document Type Definitions), kontextfreie Sprachen und Kellerautomaten
  • Berechenbarkeitstheorie: deterministische Turingmaschinen, akzeptierte und entscheidbare Sprache, Turing-Reduzierbarkeit, universelle Turingmaschine, Unentscheidbarkeit (Halteproblem, PCP), weitere Berechnungsmodelle, Churchsche These, berechenbare Funktionen (Zuordnung zu den Begriffen akzeptierte und entscheidbare Sprache, Algorithmusbegriff, Satz von Rice)
  • Komplexitätstheorie: Mehrband-Turingmaschinen, nichtdeterministische Turingmaschinen, Äquivalenz von deterministischen und nichtdeterministischen Turingmaschinen, Zeit- und Speicherplatzkomplexität, Komplexitätsklassen, das P=NP? Problem, polynomielle Reduzierbarkeit, NP-Vollständigkeit, NP-vollständige Entscheidungs- und NP-schwere Optimierungsprobleme (SAT, Clique, Färbbarkeit von Graphen)
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.
Arbeitsformen / Hilfsmittel:Vorlesungsskript, Übungsaufgaben
Modulverantwortung:Steffen Lange
Freigabe ab:WS 2014/2015
Angebot im WS 19/20:Braun / Schaffrath

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