Theoretische Informatik

Verständliche Einführung in die theoretische Informatik mit anschaulichen Beispielen und vielen Informationen zur historischen Entwicklung des Faches

Die theoretische Informatik behandelt die mathematischen Grundlagen des Faches Informatik und ist daher in ihrer Darstellung und Entwicklung tief verwurzelt in der Mathematik. Aus genau diesem Grund gilt sie unter vielen Studierenden als ein besonders herausforderndes Fach und genießt den zweifelhaften Ruf, unverständlich und wenig praxisrelevant zu sein – eben "zu theoretisch".
Das vorliegende Buch versucht nicht nur, die wesentlichen Grundlagen anschaulich und verständlich darzustellen, sondern geht darüber hinaus auch auf die geschichtliche Entwicklung des Faches ein.
In den ersten Kapiteln werden die mathematischen Grundlagen aus Mengenlehre und Logik behandelt und auch auf die dabei auftretenden Schwierigkeiten (Russelsche Antinomie, Gödelscher Unvollständigkeitssatz, Halteproblem). Insbesondere die Arbeiten von Turing sind für die theoretische Informatik grundlegend. All dies wird anschaulich mit Beispielen erklärt und die historische Entwicklung aufgezeigt.
Es folgen Kapitel über formale Sprachen, Automatentheorie, Berechenbarkeitstheorie und Komplexitätstheorie, welche den üblichen Inhalt einer Einführungsvorlesung in diesem Fach abdecken. Durchgängig werden formale Konzepte durch Beispiele veranschaulicht, wichtige Definitionen und Sätze in Kästen hervorgehoben und der Stoff durch Einschübe über historische Entwicklung und die beteiligten Wissenschaftler aufgelockert, was mir gut gefallen hat. Am Ende jedes Kapitels gibt es eine Reihe von Übungsaufgaben, deren Lösungen über einen Code von der Website des Autors abrufbar sind.
Für diejenigen, die von knappen, formalen Darstellungen der theoretischen Informatik abgeschreckt werden, bietet dieses Buch eine gute Alternative mit Erklärungen, anschaulichen Beispielen und interessanten Informationen zu den Pionieren der theoretischen Informatik.