2. Studiensemester

0 Pflicht-Präsenz(en)

Einsendeaufgabe(n)

Pflichtchat(s)

Allgemein

Lerngebiet:
Informatik: Theoretische Informatik
Niveaustufe:
Bachelor
Studiensemester:
2
Kreditpunkte:
5 cp
Status:
Pflichtmodul
Häufigkeit des Angebotes:
Nur einmal im Jahr
Lehrsprache:
Deutsch
Lehrende:
Dipl.-Inform. Andreas Wilkens

Teilnahmevoraussetzungen

Obligatorische:
Grundlagen der Mathematik, Informatik, Programmieren

Modulinhalte

Das Studienmodul gibt eine Einführung in einige grundlegenden Modelle und Methoden der Theoretischen Informatik. Anhand von Automatenmodellen und von diesen analysierbaren formalen Sprachen werden die grundsätzlichen Fähigkeiten und Beschränkungen von Computern und Softwaresystemen untersucht. Dabei stehen insbesondere die Beziehungen zwischen den Automatenmodellen als analysierende Konzepte und den beschreibenden bzw. generierenden Konzepten für formale Sprachen im Vordergrund. Darüber hinaus wird die Frage diskutiert und beantwortet, ob gewisse Probleme überhaupt durch einen Computer oder ein Softwaresystem lösbar sind oder sich einer algorithmischen Berechnung verschließen.

Lerneinheiten

    • Formale Sprachen (Arbeitsaufwand ca. 10h) Arbeitsau
      • Alphabete, Wörter und Sprachen
      • Zusammenhang mit Programmiersprachen
    • Endliche Automaten (Arbeitsaufwand ca. 25h) Arbeitsau
      • Deterministische endliche Automaten
      • Nichtdeterministische endliche Automaten
    • Reguläre Sprachen (Arbeitsaufwand ca. 25h) Arbeitsau
      • Reguläre Sprachen und Operationen
      • Reguläre Ausdrücke
      • Eigenschaften regulärer Sprachen
    • Kontextfreie Sprachen(Arbeitsaufwand ca. 30h) Arbeitsau
      • Kontextfreie Grammatiken
      • Kellerautomaten
      • Eigenschaften kontextfreier Sprachen
    • Turingmaschinen und Berechenbarkeit (Arbeitsaufwand ca. 30h)
      • Deterministische Turingmaschinen
      • Intuitiver Algorithmusbegriff
      • Turing-Berechenbarkeit
    • Entscheidbarkeit (Arbeitsaufwand ca. 20h)
      • Entscheidbare Probleme
      • Das Halteproblem

Präsenz

Pflichtpräsenzen:
0 von 3
Zeitaufwand:
Inhalte:
Zusammenfassung und Wiederholung ausgewählter Abschnitte aus dem Studienmodul, Klärung inhaltlicher Fragen, Besprechung von Übungsaufgaben, Klausurvorbereitung
Art:
fakultativ
Teilnahme:
erfordert physische Anwesenheit

Prüfung

Einsendeaufgaben:

Erfolgreiche Bearbeitung von drei Einsendeaufgaben. D.h. mindestens 50% der maximal ereichbaren Punkte pro Einsendeaufgabe.

Leistungsnachweise:
keine
Prüfungsform:
Klausur (120 Minuten)

Literatur

  • Introduction to the Theory of Computation
    Sipser, M
    Boston 2006
    2rd Edition. Thomson Course Technology
    ISBN 0-619-21764-2
  • Introduction to Automata Theory, Languages, and Computation
    Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D
    Addison-Wesley 2001
    Second Edition

Hinweise

Medien-/Lernform

Multimedial aufbereitetes Online-Studienmodul zum Selbststudium mit zeitlich parallel laufender Online-Betreuung (E-Mail, Chat, Einsendeaufgaben u. a.) sowie Präsenzphasen

Hinweise

Verantwortliche

Prof. Dr. Friedhelm Seutter (Ostfalia Hochschule Wolfenbüttel)