Theoretical computer science. An extensive introduction

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) General topics in the theory of computing (68Q01) Formal languages and automata (68Q45)

Review text

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.

Recommendations

Cited in

(18)

This page was built for publication: Theoretical computer science. An extensive introduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4955544)