Einführung in die Theoretische Informatik

Diese Einführung in die Theoretische Informatik für das Grundstudium stellt Modelle für zentrale Probleme der Informatik vor: die Leistungsfähigkeit von Maschinen und Algorithmen (Random-Access-Maschinen, Pascal, Turingmaschinen und partiell-rekursive Funktionen, Entscheidbarkeit und Aufzählbarkeit), die Effizienz von Berechnungen (Zeitkomplexität, P-NP-Theorie), Aufbau und Wirkungsweise informationsverarbeitender Systeme (endliche Automaten und deren Realisierung durch Schaltkreise, reguläre Mengen) und die Struktur von Programmiersprachen (regelbasierte Grammatiken, Chomsky-Hierarchie, kontextfreie Sprachen). Viele Beispiele und Aufgaben, z.T. in Pascal, erleichtern das Verständnis und ermöglichen die Aneignung des Stoffes auch im Selbststudium.