L’évolution des algorithmes

Encadré par : Mme Alaoui Réalisé par : Boughaleb Hasnae

Mme Ravier

Année: 2005-2006 Etablissement: Collège Jean de la Fontaine

Ce document vous parlera des algorithmes, de leur créateur et surtout de leur évolution.

L’histoire des sciences occidentales a longtemps occulté ce qu’elle devait à la science arabe et, désormais, celle-ci apparaît comme un chaînon indispensable dans l’histoire universelle des sciences. Les savants des pays d’Islam ont d’abord étudié et assimilé, des apports nouveaux aux disciplines pratiquées dans les civilisations antérieures (surtout grecque, mésopotamienne et indienne) en ayant recours à la science expérimentale et en défrichant des domaines et des techniques qui ne se constitueront que bien plus tard en Europe. Le Moyen age de l’Occident est contemporain de l’âge d’or de la civilisation de l’Islam. Une langue commune, l’arabe, la prospérité de l’empire a favorisé le commerce international, l’encouragement des califes et des princes, la liberté de pensée et la tolérance, sont des facteurs qui ont permis de faire progresser le patrimoine scientifique commun.

Lorsque l’on pense à l’apport des savants arabes au développement scientifique de l’Europe, deux domaines viennent immédiatement à l’esprit : les mathématiques et l’astronomie. La civilisation arabo-musulmane nous a légué le système de numérotation utilisé dans le monde entier et a transmis le chiffre zéro inventé par les mathématiciens indiens. Les mathématiciens arabes ont inventé l’algèbre et furent les premiers à imaginer les différents procédés permettant la résolution des équations. En ce qui concerne l’astronomie, il suffit de constater que la nomenclature des termes employés est particulièrement riche en appellations venant de l’Islam. Par ailleurs les astronomes arabes ont mis au point un grand nombre d’instruments leur permettant d’accomplir des mesures à partir de leurs observations du ciel, le plus connu étant l’astrolabe ; mais il en existe d’autres tout aussi sophistiqués. La civilisation de l’Islam s’est emparée de toutes les branches du savoir intellectuel et technique. Elle a accompli des découvertes prodigieuses dans différents domaines de la science qu’il s’agisse de la mesure du temps (horlogeries variées) et du repérage dans l’espace (navigation et création de cartes géographiques) ou de la mise au point de dispositifs mécaniques et optiques. Il convient aussi de ne pas oublier la chimie qui s’applique à comprendre la composition et le comportement de la matière, ni bien sûr la médecine et l’architecture qui concernent la santé et le bien-être des hommes.

Al Khawarizmi, (v. 780-v. 850), mathématicien arabe, dont les travaux sur l'algèbre, l'arithmétique et les tables d'astronomie ont considérablement fait progresser la pensée mathématique.

Le mot algorithme n’est pas dérivé d’un mot latin ou grec, mais d’une contraction et d’une dérivation du nom du mathématicien arabe al-Khuwarizmi, auteur d’un ouvrage décrivant des méthodes de calcules algébriques, son nom donna au moyen age algorisme qui devint algorithme avec lady Ada Lovelace fille de *lord Byron et assistante de *Charles Babbage.

*Byron, lord (1788-1824), écrivain romantique anglais, auteur notamment du Chevalier Harold

*Babbage, Charles (1792-1871), mathématicien et théoricien de l’organisation industrielle britannique, dont les travaux sur la mécanisation du calcul sont à l’origine de l’ordinateur.

Khawarizmi fut bibliothécaire à la cour du Calife Alde Allah al-Ma'mun et astronome à l'observatoire de Bagdad. Il fut le premier à utiliser à des fins mathématiques l'expression al jabr, dont est dérivé le mot français algèbre. La version latine (par le traducteur italien Gérard de Crémone) du traité d'algèbre d'al-Khuwarizmi fut à l'origine de la connaissance mathématique en Europe médiévale. Ses travaux sur les algorithmes, permirent d'introduire la méthode de calcul utilisant les chiffres arabes et la notation décimale.

L’histoire de l’algèbre commence en Mésopotamie et en Égypte, plus de trois mille ans avant notre ère. En effet, les mathématiciens cherchent déjà, à cette époque, à résoudre des équations linéaires (de la forme ax = b) et des équations du second degré (de la forme ax² + bx = c), ainsi que les équations indéterminées (de la forme x² + y² = z²), qui relient plusieurs inconnues entre elles.

Vers 350 apr. J.-C., Diophante s’inspire des connaissances babyloniennes et égyptiennes pour rédiger son ouvrage Arithmetica, qu’on peut considérer comme le premier exposé méthodique d’algèbre. Il y introduit un grand nombre d’abréviations et de symboles, qui forment la base de l’algèbre

Par la suite, l’algèbre trouve un foyer d’accueil dans le monde islamique, où elle est considérée comme la « science de la réduction de l’arithmétique en une forme plus parfaite ». Au IXe siècle, le mathématicien arabe Al Khawarizmi élabore l’un des premiers traités d’algèbre, en rédigeant un exposé systématique de la théorie des équations, avec exemples et démonstrations à l’appui. Dans cet ouvrage, il emploie les termes d’al-djabr et d’al-muqabala : le premier, qui a donné « algèbre » en français, signifie « réparation » ou « remplissage », et définit l’opération de transposition dans une équation, opération qui consiste à ajouter un même nombre de chaque côté de l’égalité ou de l’inégalité. Le second terme, qui veut dire « mise en opposition » ou « balancement », caractérise l’opération consistant à réduire les termes semblables de chaque côté de l’égalité ou de l’inégalité, puis à simplifier l’équation en divisant par un même nombre les deux termes. Aujourd’hui, cette méthode est encore enseignée dans les écoles.

Les algorithmes ont été utilisés dès l’époque des Babyloniens, pour des calculs concernant le commerce et les impôts.

Souvent appliqué au domaine informatique, l’algorithme n’en est pas moins utilisable dans d’autres domaines : Si la boulangère n’a pas livré le pain, aller acheter une baguette à la boulangerie d’en face et ensuite faire la vaisselle est un algorithme décrivant le comportement que doit avoir une personne à qui est destiné le mot.

Un algorithme n’est forcément pas infaillible, il se peut que certains cas ne soit pas prévus. Dans notre exemple, que doit faire la personne si la boulangerie d’en face est fermée ?

Algorithme mathématique : méthode de résolution d’un problème suivant un enchaînement déterminé de règles opératoires.

Al-Khuwarizmi à qui l’on doit un traité d’algèbre (825) car dans le domaine des mathématiques, les algorithmes furent utilisés dès l’Antiquité pour traiter des problèmes d’arithmétique ou de géométrie. Le calcul du plus grand commun diviseur de deux nombres par la méthode d’*Euclide (300 av. J.-C.) en constitue un exemple célèbre. Plus tard, les algorithmes intervinrent dans les méthodes de résolution d’équations algébriques et d’équations.

*Euclide (mathématicien), (IIIe siècle av. J.-C.), mathématicien grec, auteur du plus célèbre ouvrage de l’histoire des mathématiques, les Éléments. Euclide se distingue également en théorie des nombres, démontrant notamment que l’ensemble des nombres premiers est infini. Il est aussi le premier à pratiquer la division avec le reste, appelée aujourd’hui division euclidienne.

Algorithme informatique : procédé de calcul mis en œuvre sur un ordinateur, et qui, répété autant de fois qu’il est nécessaire, permet d’obtenir le résultat cherché.

Un algorithme se présente comme une liste d’instructions de nature mathématique ou logique pouvant être programmées ; il peut se traduire schématiquement par un organigramme. Convenablement utilisés, les algorithmes informatiques offrent des performances bien supérieures aux méthodes de résolutions manuelles et peuvent être appliqués à des problèmes de taille importante. Ils sont également à la base de méthodes de traitement de l’information : tri en mémoire centrale d’ordinateur ou recherche rapide d’informations. Le traitement de données textuelles, la traduction des langages de programmation et le calcul formel représentent d’autres domaines faisant appel à des algorithmes adaptés et efficaces. Un algorithme informatique doit répondre à des règles opérationnelles : il doit être fini et se terminer après un nombre fini d’opérations, chaque instruction doit être définie sans ambiguïté, le fonctionnement de l’algorithme est déterministe (il donne les mêmes résultats pour les mêmes données) et toutes les opérations doivent pouvoir être effectuées par une personne en utilisant des moyens manuels (papier et crayon). Il n’existe pas de méthode pour découvrir un algorithme. Sa réalisation est un acte créatif.

Un ordinateur ne sait rien faire ; il peut être comparé à une marionnette sans ses fils. Pour qu’il puisse prendre vie, il doit mettre en œuvre des programmes. Pour créer ces programmes, appelés logiciels, il faut formaliser le problème, exprimer les actions à exécuter sous la forme d’algorithmes et les traduire dans un langage de programmation.

Soit l’énoncé suivant : « Tracer un octogone régulier.» On ne peut pas directement en déduire l’algorithme. Il faut réfléchir sur les caractéristiques de l’octogone régulier pour espérer pouvoir résoudre l’énoncé. Lorsqu’on aura découvert qu’un octogone est une figure plane, formée par une ligne fermée à huit angles et huit côtés égaux, on sera à même d’écrire l’algorithme du tracé. Il faut être conscient de la difficulté du problème pour mettre en œuvre les bons traitements.

En revanche, dans une problématique de gestion de stock, il faudra peut-être utiliser des bases de données, des instructions de tri et de calcul.

Algorithme génétique : méthode de programmation qui repose sur le principe de l’évolution pour effectuer la recherche d'une solution à un problème.

La recherche du minimum absolu d'une fonction mathématique est un exemple typique de l'emploi d'algorithme génétique. D'une manière plus générale, les problèmes intéressants se ramènent à chercher des solutions dans un espace de recherche de très grande taille, espace notamment rencontré lorsque le nombre de cas à explorer avant d’être sûr d'avoir trouvé la meilleure solution grandit de manière exponentielle avec la taille du problème. On dit que ce sont des problèmes difficiles.

Les algorithmes génétiques ont pour but de résoudre de tels problèmes par leur approche spécifique, différente des algorithmes d'optimisation les plus courants. Le fait de travailler sur une population implique un parallélisme implicite : ce sont plusieurs solutions qui sont explorées simultanément. De plus, il est possible d’arrêter à tout moment un tel algorithme, il propose toujours une solution, qui n’est pas forcément la meilleure, mais qui n’est pas trop mauvaise non plus. Enfin les algorithmes génétiques évitent un piège très souvent rencontré dans les algorithmes d’optimisation : ils ne s’arrêtent pas dans les extrema locaux, c'est-à-dire qu’ils essayent constamment de trouver de meilleures solutions, même s’ils semblent les avoir atteintes. En conséquence, les algorithmes génétiques sont très robustes, mais ils souffrent de ne pas être prévisibles, et donc leur efficacité ne peut pas être calculée à l’avance.

L’algorithme est une suite finie d'opérations élémentaires constituant un schéma de calcul ou de résolution d'un problème qui a été inventé par Al Khawarizmi.

Cette forme de calcul ne c’est pas arrêté à sa mort, elle a aidé les autres sciences (médecine, chimie, astronomie…) à se développer. De plus aujourd’hui il y a plusieurs autres algorithmes comme les algorithmes :

Et nous pouvons créer notre propre algorithme pour un problème que nous devons résoudre.