ALGORITHME

Ce sujet est traité dans les articles suivants :

1.  ALGORITHMIQUE

Écrit par : Philippe COLLARD, Philippe FLAJOLET

…  l'évaluation et l'optimisation des méthodes de calcul en mathématiques et en informatique. Un *algorithme consiste en la spécification d'un schéma de calcul, sous forme d'une suite d'opérations élémentaires obéissant à un enchaînement déterminé. Le terme d'algorithme tire lui-même son origine du nom du mathématicien persan Al… Lire la suite

2.  ALGORITHMIQUE MUSIQUE

Écrit par : Alain FÉRON

… *Un algorithme est « une suite finie de règles à appliquer dans un ordre déterminé à un nombre fini de données pour arriver, sans indétermination, en un nombre fini d'étapes, à un certain résultat et cela indépendamment des données » (Michel Philippot). En mathématiques, l'algorithme d'Euclide (recherche du plus grand commun diviseur de deux nombres… Lire la suite

3.  AUTO-ORGANISATION

Écrit par : Henri ATLAN

Dans le chapitre "Sophistication infinie"  : … productrice de nouveau, d'où sortirait une capacité infinie de signifier ce nouveau en l'interprétant. *Du point de vue de la théorie de la complexité des algorithmes, une telle capacité d'interprétation pourrait être assignée à une classe particulière d'algorithmes formellement définis comme capables de générer des objets infinis avec une… Lire la suite

4.  BIOLOGIE - La bio-informatique

Écrit par : Bernard CAUDRON

Dans le chapitre "Les logiciels d'analyse"  : … de grande taille, l'ordinateur et les programmes d'aide à la résolution deviennent incontournables. *Pour ce faire, les informaticiens ont développé des méthodes plus rapidement convergentes que les essais successifs : ce sont les algorithmes d'assemblage. Pour savoir si deux fragments se recoupent, il faut les comparer pour établir un degré de… Lire la suite

5.  CALCUL, mathématique

Écrit par : Philippe FLAJOLET

Dans le chapitre "Calcul numérique"  : … médiéval de l'arithmétique, d'après un système importé de l'Inde (nos chiffres dits arabes). *On parlera par la suite d'algorithme pour désigner toute description d'un procédé de calcul systématique. Très tôt, on calcule aussi des longueurs, des aires, des volumes. Archimède, au iii^e siècle av. J.-C., s'illustre… Lire la suite

6.  COMPLEXITÉ, mathématique

Écrit par : Jean-Paul DELAHAYE

…  se perdent dans une boucle et ne se terminent jamais (indécidabilité de l'arrêt d'un programme). *Ces preuves d'impossibilité sont importantes et une fine répartition entre ce qui est algorithmiquement faisable et ce qui ne l'est pas, est maintenant disponible. Ce domaine a ouvert la voie dans la décennie 1970 à une analyse d'un niveau plus fin,… Lire la suite

7.  CRYPTOLOGIE

Écrit par : Jacques STERN

Dans le chapitre "Les mécanismes mis en œuvre"  : … (mod n) et correspondant à b fois le produit de a par lui-même. *Le chiffrement R.S.A. réalise l'exponentiation m^e (mod  n), où m est un message (supposé codé par un entier inférieur à n) et où e est un entier fixé appelé l'exposant R.S.A. Le couple… Lire la suite

8.  HILBERT DAVID (1862-1943)

Écrit par : Rüdiger INHETVEEN, Jean-Michel KANTOR, Christian THIEL

Dans le chapitre "Problème 10 : résolubilité des équations diophantiennes"  : … fut la résolution du problème de Fermat par Wiles (1994). Hilbert ne proposait que de chercher un *algorithme (nous emploierons ce terme, qui n'est pas celui qu'emploie Hilbert, en admettant son sens intuitif) permettant de déterminer en un nombre fini d'opérations si une équation diophantienne a des solutions (entières). La théorie des fonctions… Lire la suite

9.  INTELLIGENCE

Écrit par : Jean-François RICHARD

Dans le chapitre "La solution de problèmes"  : … définie, lorsqu'on joue au bridge ou aux échecs. On peut alors distinguer plusieurs cas possibles : *– il existe pour la classe de problèmes définie une procédure de solution constituée d'une suite finie d'étapes qui permet d'atteindre avec certitude la situation terminale : c'est ce qu'on appelle un algorithme. Pour résoudre le problème, il suffit… Lire la suite

10.  ISLAM (La civilisation islamique) - Les mathématiques et les autres sciences

Écrit par : Georges C. ANAWATI, Roshdi RASHED,  Universalis

Dans le chapitre "L'analyse numérique"  : … aux mathématiques hellénistiques, les mathématiques arabes offrent un nombre bien plus important d'*algorithmes numériques. L'algèbre, en effet, n'a pas seulement fourni les moyens théoriques indispensables à ce développement – ne fût-ce que l'étude des expressions polynomiales et les règles combinatoires – mais aussi un vaste domaine d'application… Lire la suite

11.  KLEENE STEPHEN COLE (1909-1994)

Écrit par : Pierre GOUJON

… *Mathématicien américain né à Hartford (Connecticut). Diplômé de l'Amherst College, Stephen C. Kleene entre, en 1930, à l'université de Princeton. Il est docteur de la même université en 1934. Dès cette époque, il partage son temps entre l'enseignement (université du Wisconsin) et la recherche. Il est successivement membre du Conseil national de la… Lire la suite

12.  KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE

Écrit par : Jean-Paul DELAHAYE

… ce n'est pas le cas et que la notion abstraite conduit à des applications à l'utilité incontestable.* La méthode suivie repose sur l'utilisation des algorithmes de compression de données qui sont devenus centraux pour nombre d'applications informatiques en même temps qu'ils sont devenus efficaces. On peut les voir comme des outils de recherche de… Lire la suite

13.  LOGICIELS

Écrit par : Jacques PRINTZ

Dans le chapitre "Place des logiciels dans la société"  : … plus profonde avec la nature des phénomènes physiques que nous souhaitons mettre à notre service, et avec* l'expression mathématique de ces phénomènes : les algorithmes. Sans algorithmes, pas de traitement d'images, pas de radar, pas de compression de données, pas de téléphones mobiles, pas de G.P.S. (Global Positioning System, « système de… Lire la suite

14.  LOGIQUE MATHÉMATIQUE

Écrit par : Daniel ANDLER, Roger MARTIN

Dans le chapitre "Effectivité, décidabilité"  : … La notion de méthode effective de calcul, ou encore d'*algorithme, accompagne les mathématiques depuis les origines. Soit (Pi)i∈I une famille de problèmes formulés en termes mathématiques, telle que, pour chaque i de I, le problème Pi admette une réponse Ri… Lire la suite

15.  MÉTHODE

Écrit par : Jean LARGEAULT

Dans le chapitre "Qu'est-ce que la méthode ?"  : … de même forme à partir de propriétés communes. Dans l'acception la plus stricte, une méthode est un *algorithme défini préalablement aux questions d'une classe donnée, et qui, à toute question de la classe, fournit, au bout d'un nombre fini d'étapes, une solution soit par une réponse affirmative ou négative, soit par le calcul d'une valeur numérique… Lire la suite

16.  NOTATION MATHÉMATIQUE

Écrit par : Hans FREUDENTHAL

Dans le chapitre "L'arithmétique élémentaire"  : … n'était pas seulement l'écriture des nombres, mais aussi la méthode de calcul écrit, appelé *algorithme par les Européens du Moyen Âge d'après le nom de Muḥammad b. Mūsā al-Khwarīzmī, auteur d'un livre où cette méthode fut exposée. Tant que les calculs arithmétiques se faisaient sur l'abaque, l'existence d'une écriture rationnelle des… Lire la suite

17.  NUMÉRIQUE CALCUL

Écrit par : Jean-Louis OVAERT

Dans le chapitre "Méthode des tangentes (ou de Newton)"  : … des racines carrées d'un nombre entier par des nombres rationnels. À cet effet, on utilise l'*algorithme d'Euclide de divisions successives. Héron d'Alexandrie part d'une autre idée. Pour approcher a, il écrit a sous la… Lire la suite

18.  ONDELETTES

Écrit par : Alexandre GROSSMANN, Bruno TORRESANI

Dans le chapitre "3. Des algorithmes rapides"  : … succès rencontré par les méthodes fondées sur la transformation de Fourier tient dans l'existence *d'algorithmes rapides de calcul qui lui sont associés (la fameuse F.F.T. [Fast Fourier Transform]). Or il s'est avéré que les transformations en ondelettes discrètes, pour peu que l'ondelette soit convenablement choisie, sont naturellement associées… Lire la suite

19.  PENSÉE

Écrit par : Pascal ENGEL

Dans le chapitre "Pensée, machines et fonctionnalisme"  : … d'intelligence artificielle, parce que, comme l'a remarqué D. Dennett, les limitations qui peuvent peser sur un* algorithme ne sont pas nécessairement des limitations de mécanismes particuliers utilisant cet algorithme. Or, c'est à sa capacité de reproduire certains des mécanismes de pensée « intelligents » qu'on mesure les succès de l'intelligence… Lire la suite

20.  PHYSIQUE - Physique et informatique

Écrit par : Claude ROIESNEL

Dans le chapitre " Les algorithmes "  : … Schématiquement, le choix d'un *algorithme dépend non seulement de la géométrie, parallèle ou non, du problème, mais aussi de ses propriétés statistiques. La méthode la plus fréquemment utilisée pour étudier les systèmes en équilibre statistique est la méthode de Monte-Carlo. Pour décrire les processus cinétiques, hors d'équilibre ou non, on… Lire la suite

21.  POST EMIL LEON (1897-1954)

Écrit par : Bernard JAULIN

… *Mathématicien américain né à Augustów (Pologne) et mort à New York. Arrivé aux États-Unis en 1904, Emil Post obtint son Ph.D. à l'université Columbia de New York en 1920. Il était membre de l'American Mathematical Society depuis 1918 et de l'Association for Symbolic Logic dès sa fondation en 1935. Sa thèse de doctorat, publiée en 1921, porte sur le… Lire la suite

22.  PROGRAMMATION

Écrit par : Jean-François MONIN

Dans le chapitre "Structures de contrôle et structures de données, systèmes de types"  : … se trouve dans la structuration des données à manipuler. L'algorithmique (science de la conception *d'algorithmes) repose pour une bonne part sur la définition de structures de données efficaces et adaptées au problème ciblé. Les données élémentaires sont représentées par des mots mémoire de taille fixe : cela inclut les entiers (bornés), les… Lire la suite

23.  RAZBOROV ALEXANDER ALEXANDROVITCH (1963- )

Écrit par : Bernard PIRE

…  le nombre de pas et la quantité de mémoire nécessaires au calcul d'une fonction, sont nombreuses. *En 1985, encore étudiant, il parvient à établir un résultat marquant sur l'existence d'algorithmes polynomiaux en temps pour une tâche qui semble non polynomiale. La technique développée par Razborov pour analyser les performances d'un circuit… Lire la suite

24.  RÉSEAUX DE NEURONES FORMELS

Écrit par : Gérard DREYFUS

Dans le chapitre "L'apprentissage des réseaux de neurones formels"  : … du processus à commander. Les techniques d'apprentissage des réseaux de neurones formels sont des *algorithmes d'optimisation : ils cherchent à minimiser l'écart entre les réponses réelles du réseau et les réponses désirées, en modifiant les paramètres par étapes (appelées « itérations ») successives. La sortie du réseau de neurones s'adapte de… Lire la suite

25.  LA SCIENCE DU SECRET (J. Stern)

Écrit par : Bernard PIRE

…  les mathématiques donnent un cadre théorique adéquat à la nouvelle cryptologie. Par exemple, *le concept de complexité d'un algorithme donne une mesure du temps nécessaire à la réalisation d'un calcul par une machine idéale telle que celle inventée par Turing en 1936. L'analyse abstraite du souci quotidien des voyageurs de commerce (minimiser… Lire la suite

26.  SHOR PETER (1959- )

Écrit par : Bernard PIRE

…  dans le New Jersey. Après des travaux remarquables sur la théorie des graphes et la combinatoire, *Shor réussit en 1994 à construire explicitement un algorithme grâce auquel un ordinateur quantique pourrait résoudre un problème qui semble insoluble pour un ordinateur classique. Il développe ensuite un algorithme quantique capable de factoriser des… Lire la suite

27.  SONS - Bruit

Écrit par : Pierre BUGARD, Claude CARLES, Gérard MANGIANTE,  Universalis

Dans le chapitre "Le contrôle actif"  : … signal de référence et le signal d'erreur sont numérisés et traités par le contrôleur. Grâce à un *algorithme, les coefficients du filtre numérique du contrôleur sont recalculés en permanence de façon que la somme bruit + contre-bruit soit la plus faible possible Les algorithmes. L'algorithme le plus fréquent est celui des « moindres… Lire la suite

28.  STATISTIQUE

Écrit par : Georges MORLAT

Dans le chapitre "Méthodes de classification"  : … même chemin), de trouver, par sectionnement, toutes les classifications cohérentes entre elles. Les *algorithmes, qui permettent de déterminer une classification à partir des éléments caractérisant un ensemble d'objets (distance, indices de similarité, éventuellement indices multidimensionnels), se classent en algorithmes descendants (on divise… Lire la suite

29.  TARJAN ROBERT ENDRE (1948- )

Écrit par : Bernard PIRE

… *Mathématicien et théoricien de l'informatique américain, premier lauréat du prix Nevanlinna en 1982 pour ses travaux sur la conception d'algorithmes efficaces. Né le 30 avril 1948 à Pomona (Californie), Robert Endre Tarjan fait ses études au California Institute of Technology de Pasadena (Californie) et à l'université Stanford (Californie), où il… Lire la suite