Diese kompakte Einfhrung in die Theoretische Informatik stellt die wichtigsten Modelle fr zentrale Probleme der Informatik vor. Dabei werden u.a. folgende Fragestellungen behandelt:

Welche Probleme sind algorithmisch lsbar? (Theorie der Berechenbarkeit und Entscheidbarkeit)

Wie schwierig ist es algorithmische Probleme zu lsen? (Theorie der Berechnungskomplexitt, NP-Theorie)

Wie sind informationsverarbeitende Systeme prinzipiell aufgebaut? (Theorie der endlichen Automaten)

Welche Strukturen besitzen Programmiersprachen? (Theorie der formalen Sprachen)

In der Erarbeitung dieser Themen wird der Abstraktionsproze von den realen Gegenstnden der Informatik zu den in der Theoretischen Infromatik etabliertern Modellen, wie z.B. Random-Access-Maschinen, Turingmaschinen und endlichen Automaten, nachvollzogen und umgekehrt verdeutlicht, was diese Modelle aufgrund der ber sie gewonnenen Erkenntnisse fr die Praxis leisten knnen.

Der vorliegende Text stellt reichhaltiges Material fr die Gestaltung einer einsemestrigen vierstndigen Vorlesung bereit. Viele Beispiele und Aufgaben erleichtern das Verstndnis und ermglichen die Aneignung des Stoffes auch im Selbststudium. Zum Testen selbstgeschriebener Programme kann ein Compiler vom Server des Autors heruntergeladen werden.

Die kompakte Einführung stellt Modelle für zentrale Probleme der Informatik vor. Dabei werden u.a. folgende Fragestellungen behandelt: Welche Probleme sind algorithmisch lösbar? (Theorie der Berechenbarkeit und Entscheidbarkeit). Wie schwierig ist es algorithmische Probleme zu lösen? (Theorie der Berechnungskomplexität, NP-Theorie). Wie sind informationsverarbeitende Systeme prinzipiell aufgebaut? (Theorie der endlichen Automaten). Welche Strukturen besitzen Programmiersprachen? (Theorie der formalen Sprachen). Viele Beispiele und Aufgaben erleichtern das Verständnis und ermöglichen die Aneignung des Stoffes auch im Selbststudium.