DE | EN

Studieren. Wissen. Machen.

Hochschule der Medien

Veranstaltungsbeschreibung

113200a Theoretische Informatik

Zuletzt geändert:11.05.2018 / 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 Schmitz
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
Inhaltliche Verbindung zu anderen Lehrveranstaltungen im Modul: Setzt inhaltliche Vorkenntnisse entsprechend der Lehrveranstaltungen "Diskrete Mathematik" und "Software-Entwicklung 1" voraus und ist Basiswissen für die Lehrveranstaltung "Software Engineering".
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.
Akzeptieren

Diese Website verwendet Cookies. Durch die Nutzung dieser Website erklären Sie sich damit einverstanden, dass Cookies gesetzt werden. Mehr erfahren