Kurs 1659

Grundlagen der Theoretischen Informatik

Betreuung: Prof. Dr. André Schulz

ECTS: 10 (SWS: 4 , Übungen: 2 SWS)

Arbeitsaufwand: 300 Stunden

Häufigkeit: jedes Semester

Dauer Modul: ein Semester

Veranstaltungs-Email-Adresse: Kurs.1659@fernuni-hagen.de

Inhalte:

Im ersten Kursteil wird mit Hilfe formaler Sprachen der Begriff der Berechenbarkeit entwickelt. Zunächst werden verschiedene Berechnungsmodelle vorgestellt, welche sich an der Chomsky-Hierarchie orientieren. Besonderes Augenmerk erfahren die regulären, kontextfreien und entscheidbaren Sprachen. Als Modelle werden der endliche Automat, der Kellerautomat und die Turingmaschine vorgestellt. Zudem wird auf das Konzept zur Beschreibung von Sprachen über Grammatiken vorgestellt. Dies führt zur Formulierung und Diskussion der Churchschen These.

Der zweite Kursteil widmet sich zuerst den nichtentscheidbaren Problemen. Hier werden wichtige Probleme, wie das Halteproblem, vorgestellt und wichtige Konsequenzen (Satz von Rice, Rekursionstheorem, Postsches Korrespondenzproblem) erläutert. Auch wird auf die Entscheidbarkeit von logischen Theorien eingegangen. In diesem Zusammenhang werden auch die Gödelschen Unvollständigkeitssätze diskutiert. Anschließend wird eine Einführung in die Komplexitätstheorie gegeben. In diesem Zusammenhang werden die Komplexitätsmaße Zeit und Speicherplatz eingeführt. Mit einer eingehenden Behandlung des P-vs-NP-Problems und der NP-Vollständigkeitstheorie schließt dieser Teil.

Qualifikationsziele:

Nach Bearbeiten des Kurses 01659 können die Studierenden mit den wesentlichen Grundbegriffen (Berechenbarkeit, Entscheidbarkeit, Aufzählbarkeit) umgehen. Sie können mit formalen Sprachen arbeiten und diese wichtigen Klassen zuordnen (regulär, kontextfrei, entscheidbar). Sie kennen zudem Berechnungs - und Beschreibungsmodelle dieser Sprachklassen und können mit Komplexitätsmaßen umgehen, Probleme Komplexitätsklassen zuordnen und bei schwierigen Problemen einschätzen, ob sie NP - vollständig sind. Sie lernen, wie man zeigen kann, dass Probleme nicht berechenbar sind.

Moodle:

Der Kurs ist so angelegt, dass er aus der Moodle Lernumgebung zu benutzen ist. Dort sind alle wichtigen Informationen und Dokumente zusammenhängend aufgeführt, und im Nachrichtenforum können kurzfristige Ankündigungen abgerufen werden.

Forum:

Für den Kurs haben wir ein Forum eingerichtet, welches im Gegensatz zu einem reinen Diskussionsforum als Frage und Antwort Forum organisiert ist. Alle Teilnehmenden sind aufgerufen nicht nur Fragen in dieses Forum zu stellen, sondern sich auch aktiv bei der Beantwortung von Fragen einzubringen. Die Nutzung des Forums erfordert eine Anmeldung. Sie müssen sich nicht mit ihrem Klarnamen anmelden (dürfen das aber).

Das Forum ist über Moodle zu erreichen.

Lesen Sie sich bitte auf den Webseiten des Forums die Richtlinien in den FAQs durch. Wer sich erfolgreich in die Betreuung des Forums einbringt, erhält Privilegien für die Moderation des Forums.

Inhaltliche Voraussetzung:

Elementare Begriffe und Methoden der Mathematik, wie sie in den einführenden Mathematikkursen des Studiengangs verwendet werden.

Detaillierter Zeitaufwand

Das Modul besteht aus 7 Kurseinheiten. Bearbeitungszeit je Kurseinheit (inkl. Übungs- und Einsendeaufgaben): 28 Stunden (insgesamt 196 Stunden).

Hinzu kommen 104 Stunden für Studientage und Prüfungsvorbereitung.

Lehr- und Betreuungsformen:

  • Kursmaterial
  • Lehrvideos
  • Einsendeaufgaben mit Korrektur und/oder Musterlösung
  • internetgestütztes Diskussionsforum
  • Studientag/e
  • fachmentorielle Betreuung (Regional- und Studienzentren)
  • Betreuung und Beratung durch Lehrende

Anmerkung:

Das Modul wurde zum Wintersemester 2018/19 grundlegend überarbeitet. Bezüglich der Prüfungsmodalitäten beachten Sie bitte die Prüfungsinformationen.

Verwendung des Moduls:

  • B.Sc. Informatik
  • B.Sc. Mathematik
  • M.Sc. Mathematik

Prüfung:

B.Sc. Informatik:

  • Prüfungsformen: Prüfung
  • Art der Prüfungsleistung: bestandene benotete Prüfungsklausur
  • Stellenwert der Note: 1/12
  • Voraussetzung: Leistungsnachweis zu einem Modul aus dem Pflichtbereich

B.Sc. Mathematik:

  • Prüfungsformen: Benotete Prüfung
  • Art der Prüfungsleistung: bestandene benotete mündliche Modulprüfung
  • Stellenwert der Note: 1/13
  • Voraussetzung: keine

M.Sc. Mathematik:

  • Prüfungsformen: Unbenoteter Leistungsnachweis oder Benotete Prüfung
  • Art der Prüfungsleistung: bestandene Kursabschlussklausur oder bestandene benotete mündliche Modulprüfung
  • Stellenwert der Note: 1/6
  • Voraussetzungen: keine
Christoph Doppelbauer | 16.01.2019