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.

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

##### MSC:

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 |