zbMATH — the first resource for mathematics

La reconnaissance des formes par algorithmes. (Pattern recognition by algorithms). (French) Zbl 0665.68065
√Čtudes et Recherches en Informatique. Paris etc.: Masson. 251 p. (1984).
How can we cope with the computational complexity of pattern recognition algorithms ? That is the question ! That is the main question the author tries to answer in his work.
The book is an excellent guide for beginners in pattern recognition. Due to the author’s pedagogical experience - being a distinguished professor at Universit√© Pierre et Marie Curie - the concepts and results are presented in a rigorous, clear, concise and attractive manner at a lecture notes level. Many examples illustrating important concepts and algorithms are provided. In most cases other works are referenced in order to bypass technical details and to focus on the main ideas. Therefore, I think that the book is especially of a great value for practitioners in pattern recognition.
The author outlines his book in six chapters. The first one recalls important concepts related to the theory of algorithms: computability, undecidability, computational complexity, exponential problems, NP- completeness, polynomial problems.
The second chapter deals with generalities concerning representation and interpretation such as: information, coding, properties of the representation and interpretation spaces.
The third chapter overviews signal processing techniques such as: filtering, sampling, data compression.
The last three chapters are dedicated to the study of three types of representation spaces: finite, n-ordinal, and euclidean.
Since 1984 when the book was published, many theoretical and technological advances have arisen. I mention here parallel computing and architectures only. Nevertheless, the book is actual because there are still a lot of intractable problems, i.e., exponential problems, in pattern recognition, and within the last section of the first chapter entitled “How to escape intractability” the author presents his ideas and strategies related to intractability.
Reviewer: F.Petrescu
68T10 Pattern recognition, speech recognition
68Q25 Analysis of algorithms and problem complexity
62C10 Bayesian problems; characterization of Bayes procedures
68W99 Algorithms in computer science
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q45 Formal languages and automata