2. Studiensemester

0 Pflicht-Präsenz(en)

Einsendeaufgabe(n)

Pflichtchat(s)

2. Studiensemester

0 Pflicht-Präsenz(en)

8 Einsendeaufgaben

0 Pflichtchats

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:: Es werden Übungsaufgaben angeboten, die die Studierenden möglichst selbstständig lösen sollten. Darüber hinaus wird eine Einsendeaufgabe gegen Ende des Semesters geben, die erfolgreich bearbeitet werden muss (d.h. 50% der erreichbaren Punkte). Die Lösungen der Aufgaben werden in Online-Konferenzen besprochen. Wenn nötig, werden hierzu zusätzliche Termine mit Studierenden vereinbart.
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)