×

zbMATH — the first resource for mathematics

Basic course of theoretical computer science. (Grundkurs Theoretische Informatik.) (German) Zbl 0758.68012
Stuttgart etc.: Verlag Teubner. 219 p. (1992).
Zwischen einer Einführung in die Mengenlehre und einem Anhang über Aussagen- und Prädikatenlogik sind die Standard-Elemente der Automatentheorie, der Theorien der formalen Sprachen und der (Turing-) Berechenbarkeit und schließlich der Komplexitätstheorie (bis zum Speed-up-Theorem und der \(P=NP\)-Problematik) suggestiv und übersichtlich dargestellt.
Leider bietet dieses Lehrbuch keine Übungsaufgaben. An theoretischen Beispielen mangelt es nicht, aber der Praxisbezug bleibt bis auf wenige Andeutungen ausdrücklich dem Erfindungsreichtum des Lesers überlassen; so müssen sich endliche Automaten und reguläre Sprachen wieder einmal gegenseitig rechtfertigen, und daß es nur “sehr wenige” reguläre Sprachen gibt, wird einfach daraus gefolgert, daß es nur abzählbar viele reguläre Ausdrücke gibt, während die Menge aller Sprachen überabzählbar ist.
Reviewer: M.Armbrust (Köln)
MSC:
68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
03-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations
68Q99 Theory of computing
PDF BibTeX XML Cite