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, 12:15 - 13:45, H5)
  • Ü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, 18:15 - 19:45, H4; Wed, 10:15 - 11:45, 00.131-128; Hinweis: Am Mittwoch, den 17.07.19 findet die LV im Raum 11.150, Martensstr. 3, statt!)

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:

Die Studierenden definieren und erklären grundlegenden Begriffe der theoretischen Informatik (z.B. kontextfreie/entscheidbare Sprache, primitiv rekursive Funktion etc.). Sie führen Beispiele an und geben die Begriffe in eigenen Worten wieder. Sie geben grundlegenden Konstruktionen und Beweisverfahren wieder (z.B. Minimierung von Automaten, Unentscheidbarkeit des Halteproblems, Reduktionsbeweise für NP-Vollständigkeit u.v.a.m.) und können diese Verfahren auf vorgelegte Probleme anwenden. Die Studierenden analysieren ein vorgelegtes (Entscheidung- oder Berechnungs-)Problem und können es in der Chomsky-Hierarchie einordnen und inbesondere seine Entscheidbarkeit feststellen. Sie können die Komplexität eines Problemes analysieren und seine Komplexität in den Klassen P, NP bzw. NP-Vollständig einordnen.

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 2019, 1. Wdh.: WS 2019/2020

1. Prüfer:

Stefan Milius

Termin: 17.09.2019, 10:00 Uhr, Ort: H5/H6 TechFak
Termin: 20.10.2020, 12:30 Uhr, Ort: H 11
Termin: 24.03.2021, 11:00 Uhr, Ort: H 8 TechF