Theoretische Informatik (ThI)
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.
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.