Logo der HdM
Veranstaltungsbeschreibung

113200a Theoretische Informatik

Zuletzt geändert:23.06.2017 / Ihler
EDV-Nr:113200a
Studiengänge: Medieninformatik (Bachelor, 7 Semester), Prüfungsleistung im Modul Theoretische Informatik in Semester 2
Häufigkeit: immer
Dozent: Prof. Dr. Roland SchmitzDetails zum Dozenten
Sprache: Deutsch
Art: V
Umfang: 2 SWS
ECTS-Punkte: 3
Workload: Vorlesung:
15 Termine zu je 2 SWS = 22,5 Zeitstunden
Vor- und Nachbereitung, Übungsaufgaben und Wissenslücken:
15 Termine zu je 3 SWS = 34 Zeitstunden
Selbständiges Erarbeiten von Stoff :
4 Termine zu je 4 Zeitstunden = 16 Zeitstunden
Prüfungsvorbereitung:
2 Tage zu je 8 Zeitstunden = 16 Zeitstunden
Gesamter Zeitaufwand (Workload)= 88,5 Zeitstunden
Prüfungsform:
Beschreibung: Grammatiken
  • Definition und Beispiele
  • Chomsky - Hierarchie
  • Reguläre Grammatiken
  • Kontextfreie Grammatiken
  • Kontextsensitive Grammatiken
Automatentheorie
  • Deterministische Endliche Automaten
    • Definition und Beispiele
    • Reguläre Sprachen
    • Minimalautomaten
  • Nichtdeterministische Automaten
  • Satz von Rabin/Scott
  • Kellerautomaten
  • Turing-Maschinen
    • Definition und Beispiele
    • Church'sche These
    • Halteproblem

Anwendung und Vertiefung des Vorlesungsstoffes durch Bearbeitung von Übungsaufgaben.
Literatur: Die Vorlesung folgt in großen Teilen dem Buch
  • Ulrich Hedtstück, Einführung in die Theoretische Informatik: Formale Sprachen und Automatentheorie, 4. Auflage, Oldenbourg Wissenschaftsverlag, 2007
und folgenden Kapiteln aus dem Buch
  • Uwe Schöning, Ideen der Informatik: Grundlegende Modelle und Konzepte der Theoretischen Informatik, 3. Auflage, Oldenbourg Wissenschaftsverlag, 2008:
    • Kapitel 2: Graphen
    • Kapitel 3: Formale Sprachen, Grammatiken und Automaten
    • Kapitel 4: Berechenbarkeit und deren Grenzen.
Beweise und viele Details finden sich z.B. in

  • Uwe Schöning, Theoretische Informatik – kurzgefaßt, 3. Auflage, Spektrum Akademischer Verlag, 1997.


Weitere Literatur finden Sie in der HdM-Bibliothek.
Internet: Zum Experimentieren mit Grammatiken und Automaten sollte ein Tool wie z.B. JFLAP verwendet werden.
© Hochschule der Medien 2017 | Impressum | Hinweise zum Datenschutz Login