Mathématiques pour le calcul formel / Maurice Mignotte

Ce livre correspond à un cours donné par l'auteur en 1986-1987 à Strasbourg dans le cadre du DEA de mathématiques et s'addresse à des lecteurs qui possèdent un niveau équivalent à celui de la licence de mathématique (celui du DEUG devrait même suffire). Les notions utilisées implicitement sont assez limitées; ce sont les conventions de la théorie des ensembles, la donnée des entiers naturels, des rudiments de combinatoire, de l'analyse au niveau de la terminale des lycées ainsi qu'un peu d'algèbre: notions de groupe, d'anneau et des corps, quelques résultats élémentaires en algèbre linéaire. La première partie du cours (les deux premiers chapitres) porte sur des résultats élémentaires en arithmétique; par exemple l'algorithme d'Euclide, le théorème chinois, le théorème de Fermat, etc. La seconde et dernière partie (qui s'étend sur cinq chapitres), est construite pour mener à un algorithme de factorisation des polynômes à coefficients entiers. Ce long chemin commence par la présentation des résultats algébriques généraux sur des polynômes généraux sur un anneau. Ensuite, on étudie les polynômes à coefficients complexes (en particulier, on démontre un certain nombre d'inégalités sur les racines ou les facteurs d'un polynôme à coefficients complexes), réelles (le thème principal est la séparation des racines réelles d'un polynôme) et dans un corps fini (qu'il contient l'algorithme de Berlekamp de factorisation des polynômes à coefficients dans un corps fini). Au dernier chapitre, on donne donc des méthodes de factorisation des polynômes à coefficients entiers (l'effort essentiel porte sur l'algorithme de Lenstra-Lenstra-Lovász). Si la part consacrée aux algorithmes est relativement faible, par contre, les exercices qui figurent à la fin de chaque chapitre prennent une place importante. (Zentralblatt)

Index