ALGORITHME

ALGORITHME DE TRANSFORMÉE DE FOURIER RAPIDE (J. W. Cooley et J. W. Tukey)

  • Écrit par 
  • Bernard PIRE
  •  • 352 mots

of Computation de la Société américaine de mathématiques (A.M.S), de l’« Algorithme de transformée de Fourier rapide » par les mathématiciens américains James William Cooley (né en 1926) et John Wilder Tuckey (1915-2000) révolutionne l’automatisation des calculs physico-mathématiques liés à l’étude de systèmes dont l’évolution est prédite par […] Lire la suite☛ http://www.universalis.fr/encyclopedie/algorithme-de-transformee-de-fourier-rapide/#i_90925

ALGORITHMIQUE

  • Écrit par 
  • Philippe COLLARD, 
  • Philippe FLAJOLET
  •  • 6 831 mots
  •  • 5 médias

L'objet de l'algorithmique est la conception, 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é […] Lire la suite☛ http://www.universalis.fr/encyclopedie/algorithmique/#i_90925

ALGORITHMIQUE MUSIQUE

  • Écrit par 
  • Alain FÉRON
  •  • 392 mots
  •  • 1 média

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☛ http://www.universalis.fr/encyclopedie/musique-algorithmique/#i_90925

APPRENTISSAGE PROFOND ou DEEP LEARNING

  • Écrit par 
  • Jean-Gabriel GANASCIA
  •  • 2 649 mots
  •  • 1 média

Dans le chapitre « Le perceptron »  : […] En 1957, un psychologue américain, Frank Rosenblatt (1928-1971), met au point un algorithme d’apprentissage pour des réseaux de neurones formels à deux couches qu’il appelle des « perceptrons », car ils reproduisent selon lui les capacités de perception des rétines […] Lire la suite☛ http://www.universalis.fr/encyclopedie/apprentissage-profond-deep-learning/#i_90925

AUTO-ORGANISATION

  • Écrit par 
  • Henri ATLAN
  •  • 6 239 mots
  •  • 1 média

Dans le chapitre « Sophistication infinie »  : […] 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 sophistication infinie […] Lire la suite☛ http://www.universalis.fr/encyclopedie/auto-organisation/#i_90925

BIOLOGIE - La bio-informatique

  • Écrit par 
  • Bernard CAUDRON
  •  • 5 440 mots
  •  • 3 médias

Dans le chapitre « Analyse des séquences  »  : […] sous une forme codée adaptée aux comparaisons qu'il va effectuer. L'algorithme utilisé est fondé sur la recherche de mots dans un texte, comme en linguistique, agrémenté d'une évaluation de score. Une étude de la probabilité de trouver une séquence de taille donnée dans une banque de taille connue permet de pondérer ce score et de donner en […] Lire la suite☛ http://www.universalis.fr/encyclopedie/biologie-la-bio-informatique/#i_90925

CALCUL, mathématique

  • Écrit par 
  • Philippe FLAJOLET
  •  • 1 782 mots

Dans le chapitre « Calcul numérique »  : […] Un traité célèbre du mathématicien persan du ixe siècle al-Khwārizmı̄ a servi de base à l'enseignement 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/calcul-mathematique/#i_90925

COMPLEXITÉ, mathématique

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 1 627 mots

long et complexe soit-il – qui, chargé d'analyser d'autres programmes, repère ceux qui 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/complexite-mathematique/#i_90925

CRYPTOLOGIE

  • Écrit par 
  • Jacques STERN
  •  • 5 755 mots
  •  • 2 médias

Dans le chapitre « Les mécanismes mis en œuvre »  : […] notée ab (mod n) et correspondant à b fois le produit de a par lui-même. Le chiffrement R.S.A. réalise l'exponentiation me (mod  n),m est un message (supposé codé par un entier inférieur à n) et où e est un […] Lire la suite☛ http://www.universalis.fr/encyclopedie/cryptologie/#i_90925

HILBERT DAVID (1862-1943)

  • Écrit par 
  • Rüdiger INHETVEEN, 
  • Jean-Michel KANTOR, 
  • Christian THIEL
  •  • 14 855 mots
  •  • 1 média

Dans le chapitre « Problème 10 : résolubilité des équations diophantiennes »  : […] le coup de tonnerre que 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/david-hilbert/#i_90925

IMAGERIE PAR RÉSONANCE MAGNÉTIQUE DE DIFFUSION (IRMD)

  • Écrit par 
  • Jean-Gaël BARBARA
  •  • 2 860 mots
  •  • 2 médias

Dans le chapitre « Validation des données d’IRM de diffusion »  : […] au sens épistémologique classique, qui devient, avec des techniques comme l’IRMd et ses algorithmes d’analyse sophistiqués, en elle-même un certain type d’objet scientifique probabiliste, à l’intérieur d’un paradigme de la complexité qui se généralise dans les sciences. En réalité, on peut dire que l’objet et l’objet-hypothèse deviennent […] Lire la suite☛ http://www.universalis.fr/encyclopedie/imagerie-par-resonance-magnetique-de-diffusion/#i_90925

INDE (Arts et culture) - Les mathématiques

  • Écrit par 
  • Agathe KELLER
  •  • 5 548 mots
  •  • 4 médias

virtuoses de résolution d’équations indéterminées du second degré. Plus largement, les mathématiciens y ont exploré l’univers des algorithmes, que ce soit en termes de rapidité, d’élégance ou de preuve. Et, finalement, depuis la fin du xixe siècle, des mathématiciens du sous-continent indien participent de manière reconnue au développement des […] Lire la suite☛ http://www.universalis.fr/encyclopedie/inde/#i_90925

INTELLIGENCE

  • Écrit par 
  • Jean-François RICHARD
  •  • 6 577 mots

Dans le chapitre « La solution de problèmes »  : […] – 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 d'identifier la classe à laquelle appartient le problème et d'appliquer la procédure correspondant à […] Lire la suite☛ http://www.universalis.fr/encyclopedie/intelligence/#i_90925

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

  • Écrit par 
  • Georges C. ANAWATI, 
  • Roshdi RASHED
  • , Universalis
  •  • 22 471 mots
  •  • 1 média

Dans le chapitre « L'analyse numérique »  : […] 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 de ces techniques […] Lire la suite☛ http://www.universalis.fr/encyclopedie/islam-la-civilisation-islamique-les-mathematiques-et-les-autres-sciences/#i_90925

KHOT SUBHASH (1978-    )

  • Écrit par 
  • Bernard PIRE
  •  • 649 mots

1992, qui affirme que tout problème de décision appartenant à la classe NP a une preuve qui peut être vérifiée par un algorithme contenant des tirages aléatoires. Autrement dit, il suffit de lire un nombre constant de bits choisis au hasard suivant une distribution adéquate d’une solution d’un problème NP pour décider si cette solution est valide […] Lire la suite☛ http://www.universalis.fr/encyclopedie/subhash-khot/#i_90925

KLEENE STEPHEN COLE (1909-1994)

  • Écrit par 
  • Pierre GOUJON
  •  • 370 mots

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☛ http://www.universalis.fr/encyclopedie/stephen-cole-kleene/#i_90925

KOLMOGOROV THÉORIE DE LA COMPLEXITÉ DE

  • Écrit par 
  • Jean-Paul DELAHAYE
  •  • 561 mots

travaux viennent d'établir que 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/theorie-de-la-complexite-de-kolmogorov/#i_90925

LOGICIELS

  • Écrit par 
  • Jacques PRINTZ
  •  • 6 533 mots

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☛ http://www.universalis.fr/encyclopedie/logiciels/#i_90925

MÉSOPOTAMIE - Les mathématiques

  • Écrit par 
  • Christine PROUST
  •  • 3 607 mots
  •  • 7 médias

Dans le chapitre « L’époque paléo-babylonienne »  : […] n’ont du reste pas de rapport du tout avec le réel. Certains portent sur des algorithmes de calcul numérique qui exploitent les ressources de la base 60, riche en diviseurs. Le plus courant de ces algorithmes est celui qui permettait de factoriser des nombres pour calculer des inverses, des racines carrées ou des racines […] Lire la suite☛ http://www.universalis.fr/encyclopedie/mesopotamie-les-mathematiques/#i_90925

MÉTHODE

  • Écrit par 
  • Jean LARGEAULT
  •  • 9 008 mots

Dans le chapitre « Qu'est-ce que la méthode ? »  : […] à 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. Quand […] Lire la suite☛ http://www.universalis.fr/encyclopedie/methode/#i_90925

METROPOLIS ALGORITHME DE

  • Écrit par 
  • Bernard PIRE
  •  • 361 mots

Inventé en 1953 par Nicholas Metropolis et ses collaborateurs (dont Edward Teller, le « père » de la bombe H) du laboratoire de Los Alamos au Nouveau-Mexique, l'algorithme de Metropolis était d'abord destiné à faire calculer par des ordinateurs les équations d'états de mélanges de molécules en interactions. Il s'est depuis lors révélé bien adapté […] Lire la suite☛ http://www.universalis.fr/encyclopedie/algorithme-de-metropolis/#i_90925

MEYER YVES (1939-    )

  • Écrit par 
  • Stéphane JAFFARD
  •  • 1 232 mots
  •  • 1 média

Dans le chapitre « La théorie des ondelettes »  : […] utilisées auparavant en traitement du signal et de l'image, et ouvre la voie aux algorithmes de décomposition rapides. L'imposant ouvrage en trois volumes Ondelettes et opérateurs qu'Yves Meyer publie en 1990 aura un profond impact sur la communauté scientifique. Ainsi, David Donoho, professeur à Stanford, percevra l’immense […] Lire la suite☛ http://www.universalis.fr/encyclopedie/yves-meyer/#i_90925

MOTEURS DE RECHERCHE

  • Écrit par 
  • Brigitte SIMONNOT
  •  • 4 127 mots
  •  • 2 médias

Dans le chapitre « Le classement des résultats »  : […] moteur a sa propre recette qui mélange un grand nombre de critères exprimés dans des algorithmes. L'importance d'un mot pour décrire une page peut être déterminée à partir de sa position dans la page (par exemple, un mot présent dans le titre de la page aura plus de poids que les autres) ou sa fréquence d'apparition. Google a aussi mis en place un […] Lire la suite☛ http://www.universalis.fr/encyclopedie/moteurs-de-recherche/#i_90925

NEUROSCIENCES COGNITIVES

  • Écrit par 
  • Michèle FABRE-THORPE, 
  • Simon THORPE
  •  • 4 856 mots
  •  • 2 médias

Dans le chapitre « L'imagerie du fonctionnement cérébral »  : […] cérébrale enregistrée sur la moitié des essais sera utilisée pour déterminer le meilleur « classifieur » – un algorithme mathématique – qui associe une activation cérébrale spécifique à la présentation d'un objet donné. Les activations cérébrales enregistrées sur l'autre moitié des essais seront soumises à cet algorithme pour déterminer à quel […] Lire la suite☛ http://www.universalis.fr/encyclopedie/neurosciences-cognitives/#i_90925

NOTATION MATHÉMATIQUE

  • Écrit par 
  • Hans FREUDENTHAL
  •  • 10 386 mots
  •  • 3 médias

Dans le chapitre « Les lettres »  : […] Un algorithme vraiment algébrique s'est développé assez tôt dans la théorie des équations. On invente des symboles pour l'inconnue et ses puissances, puis on forme des sommes algébriques avec ces symboles et des numéraux. Cela commence déjà avec Diophante. Les Indiens employaient des noms de couleurs pour des inconnues diverses. Les termes utilisés […] Lire la suite☛ http://www.universalis.fr/encyclopedie/notation-mathematique/#i_90925

NUMÉRIQUE CALCUL

  • Écrit par 
  • Jean-Louis OVAERT
  •  • 5 699 mots

Dans le chapitre « Comparaison des méthodes précédentes »  : […] Il faut en effet remarquer qu'un algorithme peut être plus rapidement convergent qu'un autre, tout en étant moins performant. Ainsi, la convergence d'un processus par trichotomie est d'ordre 1/3n, tandis que celle d'un processus par dichotomie est d'ordre 1/2n ; […] Lire la suite☛ http://www.universalis.fr/encyclopedie/calcul-numerique/#i_90925

ONDELETTES

  • Écrit par 
  • Alexandre GROSSMANN, 
  • Bruno TORRESANI
  •  • 5 718 mots

Dans le chapitre « 3. Des algorithmes rapides »  : […] 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 à des algorithmes […] Lire la suite☛ http://www.universalis.fr/encyclopedie/ondelettes/#i_90925

PENSÉE

  • Écrit par 
  • Pascal ENGEL
  •  • 8 283 mots
  •  • 1 média

Dans le chapitre « Pensée, machines et fonctionnalisme »  : […] 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 artificielle, et pas à sa […] Lire la suite☛ http://www.universalis.fr/encyclopedie/pensee/#i_90925

PHYSIQUE - Physique et informatique

  • Écrit par 
  • Claude ROIESNEL
  •  • 6 728 mots

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' […] Lire la suite☛ http://www.universalis.fr/encyclopedie/physique-physique-et-informatique/#i_90925

POST EMIL LEON (1897-1954)

  • Écrit par 
  • Bernard JAULIN
  •  • 622 mots

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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/emil-leon-post/#i_90925

PROGRAMMATION

  • Écrit par 
  • Jean-François MONIN
  •  • 7 826 mots

Dans le chapitre « Structures de contrôle et structures de données, systèmes de types »  : […] 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 caractères et les flottants (une […] Lire la suite☛ http://www.universalis.fr/encyclopedie/programmation/#i_90925

RAZBOROV ALEXANDER ALEXANDROVITCH (1963-    )

  • Écrit par 
  • Bernard PIRE
  •  • 247 mots

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 booléen – un […] Lire la suite☛ http://www.universalis.fr/encyclopedie/alexander-alexandrovitch-razborov/#i_90925

RÉSEAUX DE NEURONES

  • Écrit par 
  • Gérard DREYFUS
  •  • 5 123 mots
  •  • 9 médias

Dans le chapitre « L'apprentissage des réseaux de neurones formels »  : […] à 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 mieux en mieux […] Lire la suite☛ http://www.universalis.fr/encyclopedie/reseaux-de-neurones-formels/#i_90925

LA SCIENCE DU SECRET (J. Stern)

  • Écrit par 
  • Bernard PIRE
  •  • 1 301 mots

de chiffrement, 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/la-science-du-secret/#i_90925

SHOR PETER (1959-    )

  • Écrit par 
  • Bernard PIRE
  •  • 218 mots

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 nombres entiers, […] Lire la suite☛ http://www.universalis.fr/encyclopedie/peter-shor/#i_90925

SONS - Bruit

  • Écrit par 
  • Pierre BUGARD, 
  • Claude CARLES, 
  • Gérard MANGIANTE
  • , Universalis
  •  • 8 926 mots
  •  • 7 médias

Dans le chapitre « Qu'est-ce que le contrôle actif ? »  : […] pour créer un signal (le signal d'erreur), qui est envoyé vers le contrôleur. Le 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/sons-bruit/#i_90925

STATISTIQUE

  • Écrit par 
  • Georges MORLAT
  •  • 14 017 mots
  •  • 1 média

Dans le chapitre « Méthodes de classification »  : […] 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 progressivement l'ensemble de tous les objets ; les méthodes de segmentation en sont un exemple) et […] Lire la suite☛ http://www.universalis.fr/encyclopedie/statistique/#i_90925

TARJAN ROBERT ENDRE (1948-    )

  • Écrit par 
  • Bernard PIRE
  •  • 184 mots

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☛ http://www.universalis.fr/encyclopedie/robert-endre-tarjan/#i_90925


Affichage 

Algorithmes de calcul de p

tableau

Comparaison des approximations fournies par les trois algorithmes de calcul de p 

Crédits : Encyclopædia Universalis France

Afficher

Algorithmes de calcul de p
Crédits : Encyclopædia Universalis France

tableau