Diese Website verwendet nur technisch notwendige Cookies. In der Datenschutzerklärung können Sie mehr dazu erfahren.

Zum Hauptinhalt springen
Logo, Startseite der Hochschule der Medien
Veranstaltungsbeschreibung

113200a Theoretische Informatik

Zuletzt geändert:10.10.2024 / Ihler
EDV-Nr:113200a
Studiengänge: Medieninformatik (Bachelor, 7 Semester), Prüfungsleistung im Modul Theoretische Informatik in Semester 2
Häufigkeit: unregelmäßig
Medieninformatik (Bachelor, 7 Semester), Prüfungsleistung im Modul Theoretische Informatik in Semester 3
Häufigkeit: immer
Dozent: Prof. Dr. Edmund Ihler
Link zur Veranstaltung / zum E-Learning-Kurs: https://learn.mi.hdm-stuttgart.de/ilias.php?baseClass=ilrepositorygui&ref_id=14339
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: 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


Grammatiken
  • Definition und Beispiele
  • Chomsky - Hierarchie
  • Reguläre Grammatiken
  • Kontextfreie Grammatiken
  • Kontextsensitive Grammatiken
Anwendung und Vertiefung des Vorlesungsstoffes durch Bearbeitung von Übungsaufgaben.
Literatur: Die Vorlesung folgt in großen Teilen
  • Roland Schmitz, Theoretische Informatik für Dummies, 1. Auflage, Oldenbourg WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim, 2019
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: