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

Klausur

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: Raphaela Butz, M.Sc., Anna Ottersbach, B.Sc.