Theoretische Informatik für Wirtschaftsinformatik und Lehramtsstudierende (ThInfWiL)5 ECTS
(englische Bezeichnung: Theory of Informatics for Business Informatics and Student Teachers)
(Prüfungsordnungsmodul: Theoretische Informatik für Wirtschaftsinformatik und Lehramt)

Lectures:

• • Theoretische Informatik für Wirtschaftsinformatik und Lehramt
    (Vorlesung, 2 SWS, Stefan Milius, Wed, 8:15 - 9:45, H4)
  • Übung zu Theoretische Informatik für Wirtschaftsinformatik und Lehramt
    (Übung, 2 SWS, Tadeusz Litak)
  • Intensivübung zu Theoretische Informatik für Wirtschaftsinformatik und Lehramt (optional)
    (Übung, 2 SWS, Stefan Milius, Wed, 12:15 - 13:45, EL 4.14)

Inhalt:

Grundlegende Begriffe und Kernergebnisse der Automatentheorie, Berechenbarkeitstheorie und Komplexitätstheorie werden überblickhaft behandelt:

• endliche Automaten und reguläre Grammatiken und Sprachen

• Kellerautomaten, kontextfreue Grammatiken und Sprachen

• Turingmaschinen und berechenbare Funktionen

• Primitiv rekursive und mü-rekursive Funktionen

• LOOP- und WHILE-Berechenbarkeit

• Entscheidbare Sprachen und Unentscheidbarkeit

• Chomsky-Hierarchie

• Komplexitätsklassen P und NP

• NP-Vollständigkeit

Lernziele und Kompetenzen:

Fachkompetenz

Wissen

Die Studierenden geben elementare Definitionen und Fakten zu formalen Sprachen und entsprechenden Maschinenmodellen und Grammatiken wieder.

Verstehen

Die Studierenden

• erklären grundlegende Konzepte der Begriffe der Automaten- und Berechenbarkeits- und Komplexitätstheorie.

• beschreiben Beispiele dieser Konzepte.

• erläutern grundlegende Konstruktionen, Algorithmen und wesentliche Resultate und entsprechende Beweise (z.B. Unentscheibarkeit des Halteproblems).

Anwenden

Die Studierenden

• führen Konstruktionen auf vorgelegten Maschinen und Grammatiken und Sprachen durch (z.B. Automatenminiierung, Potenzmengen-Konstruktion, Chomsky-Normierung, CYK-Algorithmus).

• wenden grundlegende Beweisverfahren der theoretischen Informatik an (z.B. Induktionsbeweise, Pumping-Lemma, Reduktionen).

Analysieren

Die Studierenden

• analysieren formale Sprachen und ermitteln ihre Zugehörigkeit zu den Klassen der Chomsky-Hierarchie.

• untersuchen die Entscheidbarkeit von vorgelegten formalen Sprachen.

• analysieren die Komplexität eine Entscheidungsproblem und klassifizieren es als Problem in P, NP bzw. NP-vollständig.
  

Lern- bzw. Methodenkompetenz

Die Studierenden

• beherrschen das grundsätzliche Konzept des Beweises als hauptsächliche Methode des Erkenntnisgewinns in der theoretischen Informatik. Sie überblicken abstrakte Begriffsarchitekturen.

• vollziehen mathematische Argumentationen nach, erklären diese, führen diese selbst und legen sie schriftlich nieder.

Sozialkompetenz

Die Studierenden lösen Probleme in kollaborativer Gruppenarbeit und präsentieren erarbeitete Lösungen.

Literatur:

• U. Schöning: Theoretische Informatik - kurz gefasst, 5. Aufl., Spektrum 2008.

• J.E. Hopcroft, R. Motwani und J.D. Ullman: Introduction to Automata Theory, Languages, and Computation, 2. Aufl., Addison Wesley, 2001.

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Digitale Geistes- und Sozialwissenschaften (Bachelor of Arts (2 Fächer))
   (Po-Vers. 2018w | PhilFak | Digitale Geistes- und Sozialwissenschaften (Bachelor of Arts (2 Fächer)) | Module der Grundlagen- und Orientierungsprüfung Digitale Geistes- und Sozialwissenschaft | Theoretische Informatik für Wirtschaftsinformatik und Lehramt)

Studien-/Prüfungsleistungen:

Theoretische Informatik für Wirtschaftsinformatik und Lehramt (Prüfungsnummer: 34501)

Prüfungsleistung, Klausur, Dauer (in Minuten): 90, benotet, 5 ECTS

Anteil an der Berechnung der Modulnote: 100.0 %

Erstablegung: SS 2020, 1. Wdh.: WS 2020/2021

1. Prüfer:

Stefan Milius

Termin: 20.10.2020, 12:30 Uhr, Ort: H 11
Termin: 24.03.2021, 11:00 Uhr, Ort: H 8 TechF
Termin: 05.10.2021, 12:00 Uhr, Ort: BASPH
Termin: 06.04.2022, 11:00 Uhr, Ort: H 9 TechF