Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithmique algébrique par Daouda Niang Diatta Résumé Ce chapitre est un chap

Algorithmique algébrique par Daouda Niang Diatta Résumé Ce chapitre est un chapitre d'introduction : faire des opérations exactes sur un ordinateur, en précision inﬁnie, ne peut se faire sans précaution. Les limites imposées par la machine, principalement la taille de la mémoire disponible et la vitesse d'exécution des programmes, se font rapidement sentir. On ne peut donc aborder l'algorithmique algébrique sans avoir au moins un minimum de repères informatiques, notamment la notion de complexité des algorithmes. C'est le sujet que nous allons brièvement développer ici. 1 Calcul formel : quelques généralités Le calcul formel a commencé à se développer vers les années 1970, lorsque les ordinateurs devinrent assez puissants pour envisager des calculs polynomiaux, des dérivations itérées de grosses fonctions ou bien des calculs de primitives pratiquement inaccessibles à la main. Ce genre de calcul est évidemment purement mécanique et il semble naturel qu'un ordinateur puisse réaliser ce travail automatiquement. On obtenait alors la valeur formelle d'une fonction dérivée ou d'une primitive et non pas simplement une valeur approchée en un point particulier. On pouvait donc manipuler des formules avec un ordinateur ! Avec la puissance accrue des machines et le développement de nouveaux algorithmes, de nombreux systèmes formels seront développés depuis, capable de mener des calculs de plus en plus gros sur des objets de plus en plus abstraits. 1.1 Calcul formel et calcul numérique La première caractéristique de tels systèmes est de pouvoir faire tout calcul exactement et donc d'appréhender les objets pour ce qu'ils sont : ainsi le rationnel 1 / 3 ne peut être en aucun cas remplacé dans un système formel par un nombre décimal du genre 0,333333 qui est un autre rationnel qui ne lui est pas égal ! On doit impérativement faire travailler la machine en précision inﬁnie. Tout calcul sera exécuté sans aucun recours à des calculs approchés. Ceci présente avantage et inconvénient. D'une part, il n'y a aucune erreur dans l'évaluation d'une formule, et en cela, on est débarrassé du problème auquel on est constamment confronté en analyse numérique, les erreurs d'approximation et incertitudes numériques. Mais d'un autre coté, il faut être prêt à gérer des nombres de plus en plus gros, qui prendront pour être stockés de plus en plus de place mémoire, et sur lesquels les opérations seront de plus en plus longues à être exécutées. Prenons un exemple simple pour illustrer les divers problèmes qui se posent en calcul numérique et formel. Si nous cherchons la valeur du polynôme x7 ¡ 5x + 1 en 1 71000. Un bon système numérique nous donne 1, ce qui est manifestement faux mais reste cependant un nombre simple, facile à manipuler et proche du résultat exact. Quant à un système formel, il calcule la valeur exacte qui est une fraction dont le numérateur aussi bien que le dénominateur ont 5916 chiﬀres chacun en base 10. L'exactitude autant que la rapidité ont donc chacun un prix ! On peut résumer les deux approches dans le tableau ci-dessous 1 Calcul numérique Calcul formel approximation en virgule ﬂottante des nombres nombres exactement représentés erreur d'approximation résultats exacts calculs rapides calculs lents encombrement mémoire réduit grosse capacité mémoire requise En fait, de plus en plus, ces deux philosophies tendent à se compléter l'une l'autre plutôt qu'à s'opposer : des parties particulièrement instables peuvent être traitées formellement, le calcul numérique reprenant la main pour accélérer les calculs posant moins de problème. Le souci du mathématicien qui veut réaliser des calculs formellement sera de proposer des algo- rithmes aussi rapides que possible en faisant attention à la taille des résultats générés au cours du calcul, de façon à minimiser simultanément l'encombrement en mémoire et la durée des calculs, les deux contraintes étant liées par le fait que plus les données deviennent grosses plus leur manipu- lation prend de temps. Evidemment ces soucis n'existent pas en calcul numérique : toute opération en virgule ﬂottante prend le même temps de calcul, que les nombres soient petits ou gros, et le stockage du résultat nécessite toujours le même nombre d'octets. Cette problématique, particulière au calcul formel, reviendra constamment tout au long de ce cours. 1.2 Quelques points délicats Deux remarques vont surprendre celui qui découvre pour la première fois un système de calcul formel : la place des nombres réels et les les diﬃcultés de manipulation et de présentation des résultats. La place des nombres réels : ils sont omniprésents dans presque toutes les mathématiques et leurs applications; cependant il n'y a pas plus insaisissable qu'un nombre réel. Les seuls réels immédiatement codable, i.e inscriptibles en mémoire d'ordinateur, sont les décimaux. Comment faire dans le cadre du calcul formel, lorsque l'on prétend dire des choses exactes ? En réalité, le problème est diﬃcile. Une classe de nombres réels que l'on appelle nombres algébriques, peut être manipulée relativement simplement. Déﬁnition 1. (Nombres algébriques) Un nombre 2 C est dit algébrique, s'il existe un polynôme non nul P 2 Z[X] tel que P( ) = 0. Un nombre non algébrique est dit transcendant. Remarque. L'ensemble des nombres algébriques est un sous-corps de C, contenant Q mais ne contenant pas R. On le note souvent Q ¯ car c'est le plus petit corps algébriquement clos contenant Q. L'ensemble des nombres algébriques est dénombrable, donc négligeable, puisque les polynômes non nuls à coeﬃcients entiers sont dénombrables et que chacun d'eux possède un nombre ﬁni de zéros. Toutefois la quasi-totalité des nombres réels sont transcendants; aussi pour un système de calcul formel leurs existence est-elle fantomatique ! Comment alors manipuler des nombres transcendants tels que p ou e ? 2 Il faudra pour chacun d'eux fournir au système des relations caractéristiques en nombre suﬃsant qui permettront à la machine de manipuler le nombre. Evidemment, ceci ne peut se faire qu'au cas par cas. Par exemple la constante e est la valeur en 1 de la fonction exponentielle, laquelle est déﬁnie comme la solution de l'équation diﬀérentielle Y 0 = Y avec Y (0) = 1 ! Quant à π, le fait que eiπ = ¡1 est fondamental et permet, via la formule de Moivre, de donner la valeur exacte des fonctions trigonométriques en les multiples rationnels de π. Les diﬃcultés de manipulation et de présentation des résultats. Donnons un exemple : Nous sommes tous heureux de voir la machine réaliser la simpliﬁcation suivante : 2x7 ¡ 187x6 + 1473x5 ¡ 292x4 + 553x3 + 765x2 ¡ 299x + 85 x6 ¡ 85x5 + 14x4 ¡ 27x3 + 47x2 + 17x ¡ 5 = 2x ¡ 17 Cependant, on a aussi : x1000 ¡ 1 x ¡ 1 = x999 + x998 + ::: + 1 et nous voudrions bien ne pas voir aﬃcher le résultat de droite qui, cette fois-ci ne nous paraît pas du tout être une simpliﬁcation. Ce phénomène est général et a des répercussions pas seulement sur la lisibilité des résultats mais aussi sur l'eﬃcacité des calculs car tout le monde comprend bien qu'il est préférable de faire des calculs sur la fraction de gauche du second exemple que de manipuler un polynôme qui possède 1000 monômes. Ces problèmes sont délicats : en quoi une expression est elle plus simple qu'une autre aux yeux d'un utilisateur ? En quoi est-elle plus facilement manipulable ? Ces questions tiennent autant des mathématiques que de l'intelligence artiﬁcielle, et nous concentrant sur l'aspect algébrique des choses, nous ne l'aborderons pas, bien qu'elles soit importantes dans la conception des systèmes formels. 2 Complexité des calculs Pour un concepteur d'algorithme, une tâche capitale est de pouvoir a priori évaluer le temps que prendra son algorithme pour fournir le résultat escompté sur une machine donnée. Il faut prendre conscience du fait que de nombreux formules n'ont qu'une valeur théorique et ne débouchent sur aucun calcul pratique car leur exécution demanderait beaucoup trop de temps. Prenons l'exemple banal d'un calcul de déterminant d'une matrice 25×25 de nombres entiers, A =(ai;j)16i;j625, qui est donc une matrice de taille très modeste. La déﬁnition même du déterminant nous indique une méthode pour faire le calcul : det (A) = X σ2S25 sgn(σ)a1;σ(1):::a25;σ(25) où S25 désigne le groupe des permutations de l'ensemble f1; :::; 25g. Un rapide calcul nous fait sentir à quel point la programmation d'une telle formule serait absurde pour calculer det(A) : il y'a dans cette somme 25! ≈1; 55:1025 produits. Imaginons, cas le plus simple, que les coeﬃcients ai;j sont des entiers à un seul chiﬀre, de sorte que les produits de 25 facteurs intervenant dans notre formule soit le plus simple possible; et supposons enﬁn que notre ordinateur soit à même de calculer 10 milliards de ces produits par seconde. Combien faudra-t-il de temps pour obtenir det(A) ? Un rapide calcul nous le dit : environ 49 000 000 années ! ... 3 Il est donc indispensable d'évaluer le temps que nécessitera un algorithme pour fournir le résultat avant même de le programmer. Sinon on risque fort de perdre de nombreuses heures de travail en programmation inutile, ou à attendre un résultat qui ne viendra jamais de notre vivant!... uploads/s3/ chapitre-1 13 .pdf