Theoretical computer science. An extensive introduction (Q4955544)

Das Lehrbuch bietet eine ausführliche und sorgfältig geschriebene Übersicht über die klassischen Themen der theoretischen Informatik. Anschauliche Motivationen, präzise Definitionen und vollständige Beweise erlauben die Verwendung als Grundlage für eine Vorlesung aber auch zum Selbststudium. Die verwendete Terminologie unterscheidet sich teilweise von anderen deutschsprachigen Lehrbüchern, was die ergänzende Verwendung des Buches leider etwas erschwert. Die inhaltliche Auswahl folgt im Wesentlichen den klassischen Werken der theoretischen Informatik, auch sind viele Formulierungen und Beweise dort entnommen. Als Ausnahme ist ein Kapitel über Nicht-Standard-Berechnungsmodelle zu nennen. Nach einführenden Kapiteln über mathematische und aussagenlogischen Grundlagen werden in Teil 1 des Buches Formale Sprachen und korrespondierende Automatentypen ausführlich behandelt. Teil II widmet sich der Berechenbarkeitstheorie unter Berücksichtigung verschiedener Typen von Registermaschinen, rekursiver Funktionen sowie alternativer Berechnungsmodelle (Verschiedene Ein- und Zwei-Register-Maschinen, Wang-Maschinen, Tag-Systeme, Rödding-Netze). Ein relativ kurzes Kapitel beschäftigt sich mit Komplexität, hier insbesonders mit einer Sammlung NP-vollständiger Probleme.