Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0574.68004
Lucchesi, Cláudio I.; Simon, Imre; Simon, Istvan; Simon, Janos; Kowaltowski, Tomasz
Theoretical aspects of computation. (Aspectos teóricos da computação). (Portuguese)
[B] Projeto Euclides, 8. Rio de Janeiro: Instituto de Matemática Pura e Aplicada, CNPq. XII, 292 p. (1979).

The book is divided into four parts, one on each of four main topics important in the theory of computation. The stated goal is to show mathematicians (and computer scientists) some of the open problems in the area, but the book is well enough written that it could well serve as a general introduction to and orientation in the field. \par Part A, on computer programming, discusses procedures and algorithms, computing languages, and the ideas of iteration and recursion. Examples are mostly drawn from elementary number theory. \par Part B, concerned with the complexity of algorithms, begins with deterministic and non-deterministic Turing machines, Church's thesis, and the idea of measuring complexity in terms of the amount of "time" required for it to run on a Turing machine. It continues with a brief discussion of undecidability. Efficiency of algorithms is studied by comparing the use of Strassen's algorithm for the finding of matrix products with the use of the classical algorithm. Then it contrasts the degree of complexity for checking the solution of a problem with that of finding such a solution. Then the question is opened whether NP is the same as P, including a proof of Cook's theorem that the set of satisfiable (not tautologously false) formulas of propositional calculus is NP-m-complete. (A corollary and an exercise remove the proof's restriction to formulas in disjunctive normal form.) It concludes with a brief discussion of several other NP-m-complete problems due to Karp. \par Part C introduces the theory of graphs. The treatment is mostly conventional, but with such appropriate special additions as a discussion of how to represent graphs on the computer, plus some graph algorithms written in the simple structured language the author's developed in part A (designed - successfully - for clarity of exposition). Chapter headings include, i.a., forests and trees; matching and coverings; vertex colorings and Brooks's theorem; Ramsey's theorem and applications; digraphs. The last chapter, especially contains some topics beyond "the usual". (Part C as a whole might make a viable text for a semester course in graphs for advanced undergraduates.) \par Part D, after essential preliminaries on relations, functions and monoids (presented very clearly and briefly, hence necessarily abstractly), takes up finite automata, featuring important theorems due to Kleene and to Schützenberger. \par Each of the all together fourteen chapters is supplied with very nice bibliographical notes, as well as with copious interesting exercises "of various degrees of difficulty", some quite challenging. The book cannot be read rapidly, but any time spent working through it slowly and carefully would be rewarding.
[B.L.McAllister]

MSC 2000:: *68-01 Textbooks (computer science)
68-02 Research monographs (computer science)
68N01 General
68Q45 Formal languages
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory in connection with computer science
68Q70 Algebraic theory of automata
68Q05 Models of computation
68W99 None of the above, but in this section

Keywords: theory of computation; open problems; computer programming; procedures; algorithms; computing languages; complexity of algorithms; Turing machines; undecidability; Efficiency of algorithms; graph algorithms; finite automata

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

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]