Hinweis

Die Angaben zu dem unten angeführten Modul können unter Umständen nicht mehr aktuell sein.
Bitte beachten Sie deshalb die Informationen in den jeweiligen Modulhandbüchern des entsprechenden Studienganges
(https://www.th-koeln.de/studium/alle-studiengaenge-auf-einen-blick_76.php?faculty_de%5B%5D=Informatik+und+Ingenieurwissenschaften).

Modul: Theoretische Informatik (TI)Sommersemester 2026

Hinweis: Wegen der 'Corona-Krise' muss derzeit in der Gestaltung von Lehrveranstaltungen und Prüfungen von den Richtlinien, die in unseren Modulhandbüchern festgelegt sind, teilweise abgewichen werden. Beachten Sie bitte insbesondere die Hinweise Ihrer Dozentinnen und Dozenten in den einzelnen Lehrveranstaltungen, Sie werden dort über die jeweiligen Veränderungen informiert.

Akkreditierungsdatum: 23.05.17
Letzte Änderung: 06.07.19

Lehrveranstaltung(en):

Semester:
2. Sem.

Modulverantwortliche(r):
Prof. Dr. Stefan Karsch

Lehrende(r):
Prof. Dr. Stefan Karsch

Sprache:
deutsch

Studiengang/Zuordnung - Curriculum/Semester:

Bachelor: IT-Management (Grundlagen, 2. Sem.)
Bachelor: Wirtschaftsinformatik (Grundlagen, 2. Sem.)

Semesterwochenstunden:
Gesamt: 4 SWS (Vorlesung: 2 SWS, Praktikum: 0 SWS, Übung: 2 SWS, Seminar: 0 SWS)
Zusatz: kein

Gruppengröße Praktikum:

Lehrform:

Arbeitsaufwand:
Gesamt: 150h (Vorlesung: 30h, Praktikum: 0h, Übung: 30h, Seminar: 0h, Selbststudium: 90h)
Zusatz: kein

Credits:
5 CP
Zusatz: kein

Voraussetzungen:

Einfache Kenntnisse der naiven Mengenlehre, wie sie in der Schule vermittelt und bei der mathematischen Begriffsbildung verwendet werden.

Lernziele/Kompetenzen:

Grundsätzliches Ziel des Kurses ist eine Einführung in die Begriffe, Methoden, Modelle und Arbeitsweise der Theoretischen Informatik anhand der ausgewählten Teilgebiete.
Die Studierenden erwerben fundierte Kenntnisse der grundlegenden Themengebiete und eine wesentliche Basis und Vorbereitung für Veranstaltungen in höheren Semestern des Studiums.
Die gestellten Übungsaufgaben sollen selbstständig gelöst werden und in den Übungsstunden vorgeführt und der Lösungsweg den Kommilitonen hierbei erklärt werden.

Inhalt:

Grundlagen

Mengen, Relationen, Graphen
Zahlensysteme, Zahlendarstellung, Numerische Aspekte
Codierung, Textdarstellung, Alphabete, Wörter

Logik und Boolesche Algebra

Aussagenlogik
Prädikatenlogik
Boolesche Algebra

Reguläre (Typ-3) Sprachen

Endliche Automaten
Reguläre Ausdrücke
Typ3-Grammatiken, Syntaxdiagramme
Chomsky-Hierarchie

Kontextfreie (Typ-2) Sprachen

Kontextfreie Grammatiken, Chomsky- und Greibach-Normalformen
Anwendungen (Ableitungs- und Syntaxbäume, Syntax von Programmiersprachen, Backus-Naur-Form)

Kontextsensitive (Typ-1) und rekursiv aufzählende (Typ-0) Sprachen

Grammatiken, Monotonie, Normalform

Berechenbarkeit, Entscheidbarkeit und Komplexität

Berechenbarkeit intuitiv
Programmier- und Spezifikations-Modelle
Church'sche These
WHILE- und GOTO-Programme, Kleene-Normalform
Turing-Maschinen, Turing-Berechenbarkeit
Entscheidbarkeit, rekursive Aufzählbarkeit
Komplexität (Einf.)

Leistungen:

Klausur (schriftliche Prüfung, 90 Min.)

Medienformen:

Vorlesung im Hörsaal (PowerPoint und Beamer)

Vorlesungsunterlagen: Foliensammlung
Beispiele

Übungen zur Vertiefung des vermittelten Stoffs

Übungsaufgaben
Beispiellösungen

Literatur:

Vorlesungsunterlagen: Foliensammlung, Übungsaufgaben, Beispiellösungen

Brill, Manfred: Mathematik für Informatiker. Carl Hanser Verlag, München, 2005.
Erk, Katrin; Priese, Lutz: Theoretische Informatik – Eine umfassende Einführung. Springer, Heidelberg, 2008.
Hedtstück, Ulrich: Einführung in die Theoretische Informatik. Oldenbourg, München, 2012.
Hoffmann, Dirk W.: Theoretische Informatik. Carl Hanser Verlag, 2016.
Hopcroft, J. E.; Motwani, R.; Ullmann, J. D.: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit. Pearson Studium, 2011.
Kelch, Rainer: Rechnergrundlagen - Von der Binärlogik zum Schaltwerk. Carl Hanser Verlag, 2002.
Kelch, Rainer: Rechnergrundlagen - Vom Rechenwerk zum Universalrechner. Carl Hanser Verlag, 2003.
Kelly, John: Logik - im Klartext. Pearson Studium, München, 2003.
Meinel, C., Mundhenk, M.: Mathematische Grundlagen der Informatik. Springer, Berlin; Vieweg+Teubner, Stuttgart, 2015.
Schöning, Uwe: Ideen der Informatik. Oldenbourg, München, 2008.
Vossen, G.; Witt K.-U.: Grundkurs Theoretische Informatik. Vieweg+Teubner, Braunschweig, 2016.

Näheres wird in der Veranstaltung bekannt gegeben bzw. siehe Homepage (www.ktds-koln.de)

Schwerpunkte:

Sonstige Informationen: