Studienreihe Informatik: Grundbegriffe der Theoretischen Informatik

More about the book

In diesem Lehrbuch werden die grundlegenden Begriffe der Theoretischen Informatik, wie Berechenbarkeit, Entscheidbarkeit, rekursive Funktionen, Regelsprachen, Turingmaschinen und Komplexität, anhand der Programmiersprache PASCAL motiviert und einheitlich dargestellt. Ein zentrales Konzept ist die Äquivalenz verschiedener Ansätze zur Theorie der Berechenbarkeit, einschließlich Programme, rekursive Funktionen, Regelsprachen und Turingmaschinen. Die ersten sieben Kapitel behandeln qualitative Aspekte der Berechenbarkeit, während Kapitel 8 sich mit quantitativen Aspekten beschäftigt. Die Komplexität, also der Zeit- und Speicheraufwand für Berechnungen, hängt sowohl vom Berechnungsmodell als auch vom zu lösenden Problem ab, wobei bestimmte Schranken nicht unterschritten werden können. Aufgrund der Breite der Theoretischen Informatik sind einige Einschränkungen bei der Stoffauswahl notwendig. So wird Semantik informell behandelt, Parallelität nur ansatzweise betrachtet und Automatentheorie nur am Rande erwähnt. Ziel war es, ein umfassendes Bild der Theoretischen Informatik zu bieten und ein Fundament für weitergehende Studien zu legen. Das Buch setzt Grundkenntnisse aus Anfängervorlesungen über Analysis und Lineare Algebra voraus, und im Anhang werden die mathematischen Grundlagen knapp zusammengefasst, um den Leser mit der Terminologie vertraut zu machen.