|
| Author(s) | Schöning, Uwe |
|---|---|
| Title | Theoretische Informatik kurz gefasst |
| Publisher | B.I. Wiss. Verl. |
| Year of publication | 1992 |
| Reviewed by | Mirela Stefanescu |
A short introduction to theoretical informatics for students in informatics and mathematics is very useful now, when there are so many books concerning special branches of informatics. First part of the book is devoted to studying automata theory and formal languages. Let us remind some topics in this part: gramatics, Chomsky hierarchy, word problem, syntactic trees, the Backus-Naur form, finite automata, nondeterministic automata, equivalences and minimal automata, context free languages (normal forms, CYK-algorithm, deterministic context-free languages, context sensitive and type 0-languages).
The second part studies the computability theory: Church conjecture, Turing computabiltity, LOOP-, WHILE -, and GOTO-computability, primitively recursive and mu-recursive functions, Ackerman function , reductibility and refinement problems, Post correspondences, Gödel theorem.
As a respectable course, this ends with the complexity theory: complexity classes and P-NP-problem, NP-completeness and some solved NP-completeness problems.
A short appendix on mathematical foundations (some definitions: algebraic operations, semigroups, equivalence relations, cardinals), some comments on references and a list of literature on this subject complete the book.
The book is a good modern introductions in informatics and it is nicely printed, such that it is necessary to any library for students and specialists in informatics.