Theoretische Informatik (TI)

Inhalte

Grundlagen

  • Mengen, Relationen, Graphen, Polynome
  • Zahlensysteme, Zahlendarstellung, Numerische Aspekte
  • Codierung, Informationstheorie.

Logik und Boolesche Algebra

  • Aussagenlogik
  • Prädikatenlogik
  • Boolesche Algebra, Schaltnetze und Schaltwerke.

Reguläre (Typ-3) Sprachen

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

Modellierung sequentieller und paralleler (Ausgabe-) Prozesse

  • Endliche Maschinen, Berechnungen
  • Automatennetze, Petri-Netze.

Kontextfreie (Typ-2) Sprachen

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

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

  • Grammatiken, Monotonie, Normalform, Turingautomaten, Einführung in die Begriffe : Berechenbarkeit, Entscheidbarkeit und Komplexität.

Termine

Ort und Zeit der Veranstaltung sind dem Veranstaltungsplan zu entnehmen.

Lernziele

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

Prüfungsleistungen

Wichtige Informationen für Studierende, die sich im September 2020 im PSSO angemeldet haben:
(1) Nur Studierende, die sich in PSSO angemeldet haben, dürfen an der Online-Klausur teilnehmen.
(2) Die Online-Klausur wird am 29.10.2020 um 11:00 Uhr stattfinden. Sie dauert 45 Minuten.
(3) Hilfsmittel und Gruppenarbeit sind generell nicht erlaubt und strengstens untersagt.
(4) Die Online-Klausur befindet sich in einem separaten ILIAS-System der TH Köln. Sie müssen sich aus technischen Gründen dort möglichst bald anmelden und vorab dem Klausur-Kurs (s. u.) beitreten, um dann an der Klausur teilnehmen zu können.
(5) Bitte melden Sie sich zunächst mit Ihrer CampusID unter folgendem Link an: https://f10.eassessment.th-koeln.de
(6) Sie sehen dort den Reiter "Prüfungen". Dort wählen Sie "Anmeldung zur Prüfung" aus.
(7) Unsere TI-Prüfung ist am 9. Prüfungstag. Daher öffnen Sie bitte den Ordner "Prüfungstag 9".
(8) Dort finden Sie den Kurs "Theoretische Informatik", dem Sie beitreten müssen, um an der Online-Klausur teilzunehmen.
(9) Am Prüfungstag wird die Klausur kurz vor der angegebenen Startzeit in diesem Kurs sichtbar und aktivierbar sein. Auch dazu müssen Sie sich vorher erneut in diesem ILIAS-System anmelden.

WICHTIG:
Bitte registrieren Sie sich in diesem Kurs "Theoretische Informatik" bis spätestens Montag, den 26.10.2020, 23:59 Uhr.
Dann findet ein Abgleich mit den Daten im PSSO statt. Falls Sie nicht via PSSO für die TI-Prüfung angemeldet sind, ist eine Klausurteilnahme für Sie nicht möglich.

Probeklausur
Damit Sie das Handling und den Umgang mit Online-Klausuren üben können, stellen wir eine Probeklausur zu Verfügung. Diese ist kürzer als die richtige Klausur. Sie dauert nur 20 Minuten, zeigt aber die gleichen Features und Fragetypen wie die reale Klausur. Die Teilnahme ist freiwillig und liefert keinen Beitrag zum Ergebnis der eigentlichen Online-Klausur (also z. B. keine Bonus-Punkte o. ä.).

Die Probeklausur findet am Montag, den 19.10.2020 um 14.00 Uhr statt.
Bitte treten Sie dann dazu dem folgenden Kurs im Prüfungsbereich bei:
PROBE Remote Prüfungen → Informatik BA → Theoretische Informatik (ITM, WI und TI).
Dort finden Sie dann die Probeklausur "TI - Probe Remote Prüfung".

Gewichtung

Der Aufwand für dieses Fach beträgt 4 SWS. Die Aufteilung ist 2 SWS Vorlesung, 2 SWS Übung.

Teilnahmevoraussetzungen

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

Literatur und Material

  • Brill, M. ( 2005 ): Mathematik für Informatiker. Carl Hanser Verlag, München.
  • Dean, N. ( 2003 ): Diskrete Mathematik. Pearson Studium. München.
  • Hedtstück, U. ( 2004 ): Einführung in die Theoretische Informatik. Oldenbourg, München.
  • Hopcroft, J. E. et al. (2003): Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium, München.
  • Kelch, R. ( 2003 ): Rechnergrundlagen. Vom Rechenwerk zum Universalrechner. Fachbuchverlag Leipzig im Carl Hanser Verlag.
  • Kelch, R. ( 2003 ): Rechnergrundlagen. Von der Binärlogik zum Schaltwerk. Fachbuchverlag Leipzig im Carl Hanser Verlag.
  • Kelly, J. ( 2003 ): Logik.Pearson Studium, München.
  • Meinel, C., Mundhenk, M. ( 2002 ): Mathematische Grundlagen der Informatik. B. G. Teubner, Stuttgart.
  • Schöning, U. ( 2002 ): Ideen der Informatik. Oldenbourg, München.
  • Vossen, G., Witt K. (2006): Grundkurs Theoretische Informatik Vieweg & Sohn, Braunschweig.

Modulbeschreibung

Weitere Informationen finden Sie im Modulhandbuch.

Ansprechpartner

Bei Fragen wenden Sie sich bitte an: