Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1128.68037
Hollas, Boris
Basic course theoretical computer science with exercises and test questions. (Grundkurs Theoretische Informatik mit Aufgaben und Prüfungsfragen.) (German)
[B] Heidelberg: Elsevier/Spektrum Akademischer Verlag. xi, 211~p. EUR~20.00 (2007). ISBN 978-3-8274-1826-5/pbk

This is a rather succinct book on theoretical computer science, compared with other standard volumes about this topic. Yet it contains all the main contents usually taught during one-semester courses. It emphasises the impact of theory for practical applications. To cope with the difficulties students have with grasping formal proofs, the first chapter is devoted entirely to proof techniques, propositional logic and an introduction to graph theory already with applications like sorting, searching and even zero-knowledge protocols. The second chapter treats the different types of automata: finite, non-deterministic, push-down, Turing, as well as formal languages and grammars: Chomsky hierarchy, parsing, lexical analysis, regular expressions, with spam filters as an interesting application. Of course the pumping lemmas are discussed in detail. Computability and decidability is the topic of Chapter 3, which is clearly more formal than the former chapters. It is restricted to time complexity and does not mention, e.g., space complexity. Nevertheless, it contains on only 50 pages all the main material: halting problem, loop programs, reducibility, {\bf P} and {\bf NP} and, quite impressive, reducibility chains for SAT, 3SAT, CLIQUE, (directed) Hamilton path/cycle, KNAPSACK, PARTITION and (as exercise) integer linear programming, all with proofs. The most important feature of the book is the wealth of exercises. Each chapter also gives about twenty questions which are suitable for oral examinations, arranged in an order which might actually arise during an exam. The forth chapter (and 25\% of the book) contains the solutions to all of them. The range is from very easy to very difficult. (An example of an exercise rated ``very difficult'' is the proof of the uncomputability of the busy beaver function.) All in all the reader will get a compact, affordable volume containing all the core material, the exposition being supported by many well-chosen diagrams.
[Dieter Riebesehl (Lüneburg)]

MSC 2000:: *68Qxx Theory of computing
68-01 Textbooks (computer science)

Keywords: automata; formal languages; grammars; computability; decidability; complexity classes

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.
	Elementary number theory. Primes, congruences, and secrets.

Simple Search

Zentralblatt MATH Berlin [Germany]