1. Startseite
  2. Veranstaltungen
  3. Vorlesungsverzeichnis
  4. Veranstaltung - Theoretische Informatik

Zurück zur Auswahl

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).

Theoretische Informatik (TI ITM WI V) Sommersemester 2026

Dozent/in:
Prof. Dr. Florian Niebling

Semester:
2

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.)

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)

 

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.

Medienformen:

Vorlesung im Hörsaal (PowerPoint und Beamer)

  • Vorlesungsunterlagen: Foliensammlung
  • Beispiele

Übungen zur Vertiefung des vermittelten Stoffs

  • Übungsaufgaben
  • Beispiellösungen

Modulzuordnung (laut Prüfungsordnung):

Im Curriculum der Studiengänge:

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