NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 20/08/2018

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique           Brèves de Maths    

            

LOGIQUE

 

Débutants

Logique

Intelligence artificielle

 

Glossaire

Algorithme

 

 

INDEX

 

 

Logique

Introduction

Algorithme débutant

Algorithmes

Programmation

Algorithmes TOP 15

Robots

Sommaire de cette page

>>> Algorithmes Babyloniens

>>> Algorithme d'Euclide

>>> Crible d'Ératosthène

>>> Algèbre de Boole

>>> Programmation avec Ada Lovelace

>>> Transformée de Fourier rapide

>>> Algorithme de classement de Google

>>> Méthode Monte Carlo

>>> Algorithme de SIMPLEX

>>> Méthode de résolution des espaces de Krylov

>>> Filtre de Kalman

>>> Algorithme QR

>>> Compilateur Fortran optimisé

>>> Algorithme de tri QUICKSORT

>>> Algorithmes de compression

 

 

 

 

 

ALGORITHMES – TOP 15

Les plus importants de l'histoire

 

Algorithme, procédure, recette … sorte de mode d'emploi très précis qui permet de produire un résultat attendu à chaque fois qu'il est utilisé, même si les données de départ sont différentes.

Un algorithme permet de résoudre un problème répétitif, récurrent.

C'est une suite d'opérations très précises (instructions) qui permet de résoudre un problème ou d'obtenir un résultat.

Quels sont les algorithmes les plus importants qui ont marqué l'histoire? Ou, du moins, les grandes avancées en procédures informatiques. Classement selon Christopher McFadden – 2018

 

Anglais:

Algorithms can be found in many fields of science such as physics, math, and computing. They have a long history with some being more influential than others. On rencontre les algorithmes dans de nombreux domaines des sciences comme la physique, les maths et l'informatique. Avec une longue histoire, certains furent plus déterminants que d'autres.

Voir Anglais – Le bagage minimum

Voir Les trois algorithmes les plus célèbres aujourd'hui

 

 

 

 

Algorithmes Babyloniens – 1600 av. J.-C.

Sans doute les algorithmes les plus vieux du monde, découverts inscrits sur des tablettes d'argile.

Ces algorithmes indiquent comment effectuer les opérations courantes  tout en utilisant leur système de numération particulier:  sexagésimal flottant.

Ils montrent également comment résoudre de nombreux cas d'équations algébriques en procédant pas à pas par une suite précise d'instructions.

Knuth explique: les Babyloniens fonctionnaient avec un "langage machine" et non un "langage symbolique" comme le nôtre aujourd'hui.

 

C'est Donald E. Knuth (mathématicien et informaticien à l'Université de Stanford) qui publie en 1972 les premières traductions de ces tablettes et met en évidence l'aspect algorithmique des calculs.

 

 

Algorithme d'Euclide – 300 av. J.-C.

L’un des premiers algorithmes en théorie des nombres qui n'ai jamais été créés, l’algorithme d’Euclide s’utilise encore jusqu’à aujourd’hui.

Il permet de trouver les plus grands diviseurs communs de deux nombres ou entiers positifs (PGCD).

 

Euclide (v-325 à -275) est un mathématicien grec, père de la géométrie, auteur du manuscrit Les éléments dans lequel figure cet algorithme.

 

Algorithme d'Euclide: suite de divisions itératives dont les résultats sont réinjectés dans la division suivante.

 

 

Crible d'Ératosthène – 200 av. J.-C.

Le crible d’Ératosthène permet de trouver tous les nombres premiers à partir de 1 jusqu'au nombre que vous voulez.

Toujours efficace pour de petits nombres, il est supplanté aujourd'hui par d'autres méthodes plus sophistiquées.

 

Ératosthène (-276 à -194), connu pour avoir calculé la longueur du méridien terrestre.

 

Crible d'Ératosthène: écrire la suite des nombres à partir de 2 et supprimez tous les multiples de 2. Le nombre 3 reste en tête: supprimez tous ses multiples. Le nombre 5 reste en tête: supprimez tous ses multiples. Etc.

Les nombres de tête: 2, 3, 5 … sont premiers.

 

 

Algèbre de BOOLE – 1847

 

L’algèbre de Boole est la base de la conception de toutes les logiques modernes que ce soit pour les circuits des ordinateurs (matériel- harware) ou pour l'informatique (logiciel- software) 

 

Il n'y aurait pas d’ordinateurs ou de systèmes informatiques sans la découverte de la logique booléenne.

 

George Boole (1815-1864) est un logicien, mathématicien et philosophe britannique.

 

Algèbre de Boole: calcul logique à partir de 0 et de 1 (ou vrai, faux; ou encore, le courant passe ou non; la mémoire est excitée ou pas; etc.).

La fonction ET, par exemple, produit un "vrai" en sortie, seulement si les toutes les entrées sont "vraies". Codé en binaire, cela donne: 1 ET 1 = 1, mais 0 ET 1 = 0.

 

Programmation avec ADA LOVELACE – 1840

L’algorithme développé par Ada Lovelace est reconnu comme étant le premier programme informatique destiné à être implémenté sur une machine.

En 1953, on a découvert un code informatique écrit par elle, permettant le calcul des nombres de Bernoulli.

Ce programme est considéré aujourd’hui comme étant le premier exemple de code informatique enregistré.

 

Ada Lovelace (1815-1852), mathématicienne britannique, fille de lord Byron le poète. En duo avec Babbage qui conçoit une machine à calculer, elle en écrit le programme.

 

Extrait du programme d'Ada Lovelace

Document complet >>>

 

 

Transformée de Fourier rapide – 1802

Algorithme qui transforme un signal temporel (qui est fonction du temps) en données fréquentielles (son spectre de fréquences).

Principe: on part du constat que tout signal, même complexe, peut être reconstitué par sommation de signaux plus simples à fréquences pures.

Son emploi révolutionna le domaine du traitement du signal. L'algorithme y est connu sous le nom de FFT (Fast Fourier Transform).

 

Joseph Fourier (1768-1830) est un mathématicien et physicien français surtout connu pour sa théorie analytique de la chaleur.

 

En fait c'est Carl Gauss en 1802 qui initie ce type de procédé pour calculer l'orbite des astéroïdes.

En 1822, Joseph Fourier élabore la théorie. La version moderne, utilisée en traitement du signal, date de 1965, et elle est due à James Cooley et John Tukey.

 

http://villemin.gerard.free.fr/Wwwgvmm/Analyse/Fourier_fichiers/image033.jpg

 

 

Algorithme de classement de Google – 1996

 

Le PageRank est sans aucun doute l’algorithme le plus utilisé dans le monde.

C'est lui que vous sollicitez lorsque vous introduisez des mots dans le moteur de recherche Google.

L'importance accordée à une page donnée est fonction de ses liens à d'autres pages, dans les deux sens.

 

 

Algorithme crée par Larry Page avec la contribution de Sergey Brin, tous deux étudiants à l'université de Standford. Notez qu'astucieusement l'algorithme porte le nom de son auteur principal: Page rank (to rank veut dire: classer, hiérarchiser).

 

Voir GAFAM

 

Méthode Monte Carlo – 1946

 

La méthode Monte-Carlo est assez déroutante: elle consiste à approcher la solution à un problème par essais successifs conduits à partir de données aléatoires.

Elle est utilisée pour résoudre des problèmes extraordinairement complexes. Où le hasard répété un grand nombre de fois conduit au déterminisme.

Domaine d'application: intégration, optimisation, génération de données sous contrainte de loi de probabilité, etc.

 

 

John von Neumann, Stanislaw Ulam, and Nick Metropolis ont utilisé cette méthode à Los Alamos pour la simulation stochastique (aléatoire) dans le cadre de l'optimisation de la bombe atomique.

 

 

Algorithme de SIMPLEX – 1947

Il s’agit d’un algorithme de résolution des problèmes d’optimisation linéaire.

Un programme linéaire résume un problème particulier, comme l'optimisation de la production d'objets, sous la forme d'un système d'équations.

Ce genre de problème peut être résolu pour les plus simples par l'algèbre ou par représentation graphique. Pour les cas plus difficiles, on utilise la méthode de Monte-Carlo ou la méthode de Simplex ou d'autres méthodes plus récentes.

 

George Dantzig (1914-2005) est un mathématicien américain.

Preuve de sa capacité mathématique: À l'université de Berkeley, le professeur fait part de deux problèmes ouverts en statistiques. Croyant qu'il s'agissait d'un devoir, Dantzig les as résolu en quelques jours.

 

Exemple de programme linéaire à résoudre

Algorithme de Simplex

Il fonctionne par itérations successives qui sélectionnent les variables produisant les plus grandes avancées vers la solution minimale.

 

 

 

Méthode de résolution de systèmes linéaires imposants (sous-espaces de Krylov) – 1950

La résolution de systèmes linéaires très imposants nécessite des factorisations matricielles très coûteuses (en temps de calcul et mémoire).

On utilise alors des méthodes itératives qui génèrent des résidus de plus en plus petits qui font converger vers la solution du problème. La méthode fait appel aux puissances successives d'une matrice (sous-espace de Krylov)

Cette méthode, connue sous le nom GMRES (généralisation de la Méthode de Minimisation du Résidu), fait partie des méthodes les plus importantes pour la résolution des systèmes linéaires.

 

Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos ont développé cette méthode à l'Institut d'analyse numérique du Bureau national des Normes à Zurich.

 

Méthode (idée)

Résoudre: Ax = b

Idée: utiliser la méthode des sous-espaces de Krylov avec un système aménagé: M-1Ax = M-1b.

Intérêt: il n'est pas nécessaire de former explicitement la matrice M-1Ax. Il faut résoudre Mu = z lorsque nécessaire.

Impératif: il doit être facile de résoudre Mu = z pour un vecteur z arbitraire.

 

Sous-espace de Krylov (1931)

À partir d'une matrice A (n x n) et un vecteur b de dimension n, on forme le sous-espace vectoriel dit sous-espace de Krylov.

 

 

 

Filtre de Kalman – 1958 

Il s'agit de filtrer un signal en présence de bruit. Par exemple, le retour d'un écho radar ou d'un écho sonar ou d'un signal GPS. Le cerveau fait cela automatiquement lorsqu'il trie la parole de votre interlocuteur parmi tous les bruits de la cantine.

Il s'agit donc d'estimer une information (un signal) utile polluée par un bruit aléatoire, mais dont on estime la loi du comportement.

Autrement-dit: il s'agit de trouver l'aiguille dans la botte de foin, tout en connaissant les caractéristiques de l'aiguille et celles du foin (Utilisation d'un aimant?).

 

Rudolf E. Kalman (1930-2016) est un mathématicien et automaticien américain. Sa découverte sera utilisée par la Nasa pour le programme Apollo et la Navette spatiale.

 

Intérêt du filtre de Kalman

Dans une méthode d'estimation classique (par exemple, la méthode des moindres carrés), une simple erreur dans la modélisation du système entraine inévitablement une erreur au niveau de l'estimation.

La force du filtre de Kalman est d'intégrer un terme d'imprécision sur le modèle lui-même, ce qui lui permet de donner des estimations correctes malgré les erreurs de modélisation (pour peu que les erreurs restent raisonnables).

Source Ferdinand Piette

 

 

Algorithme QR – Années 1950

Algorithme qui permet de trouver les valeurs propres des matrices.

Pour connaitre les solutions d'un système d'équations, il faut connaitre les valeurs propres de la matrice qui le représente.

L'algorithme consiste à effectuer une factorisation QR, à multiplier les matrices dans l'autre sens et itérer (recommencer) le processus.

 

Note: Cet algorithme QR n'a rien à voir avec le QR code (Quick Response). Ici, il s'agit de matrices nommées Q et R. 

 

Invention: Heinz Rutishauser (Zurich)

Développement: John G. F. Francis et Vera N. Kublanovskaya, indépendamment.

 

Factorisation QR

Décomposition d'une matrice A en un produit: A = QR avec Q est une matrice orthogonale et R une matrice triangulaire haute.

 

QT Algorithme (idée)

Sous certaines conditions, la matrice Ak converge vers une matrice triangulaire et ses valeurs propres figurent sur la diagonale.

 

 

Compilateur Fortran optimisé – 1954

 

Un événement important dans le monde de l'informatique.

Un compilateur réalise l'interface entre un langage évolué (Ici, le Fortran) compréhensible par l'homme et le langage de base de l'ordinateur (assembleur), celui qui traduit les directives en instructions binaires, lesquelles pilotent les circuits électroniques.

 

 

Créateur: John Backus 1954 et l'équipe IBM qui la développé (1957).

Fortran est un mot-valise pour Formula Translator

 

Histoire personnelle

En fin des années 1960, le Fortran était en concurrence avec l'Algol. J'ai débuté l'informatique avec l'Algol.

 

Algorithme de tri QUICKSORT – 1962

Algorithme rapide de classement de listes par ordre alphabétique ou numérique.

Cet algorithme utilise une stratégie récursive: le programme est vu comme une fonction qui peut faire appel à elle-même (idée de poupées russes).

 

Auteur: Tony Hoare d'Elliott Brothers, Limited, Londres

 

Algorithme

Un élément de la liste est choisi comme pivot. Les autres éléments sont triés en piles de données plus grandes ou plus petites que le pivot. le procédé est répété dans chaque pile avec son propre pivot  (récursivité).

 

 

 

Algorithmes de compression – 1992

Les algorithmes de compression de données ont rendu les systèmes informatiques moins chers et plus efficaces au fil du temps.

Ils font gagner en occupation de place mémoire au prix d'une puissance calcul supplémentaire.

Ils ont contribué à faire des économies et surtout à assurer la faisabilité de certains projets comme la transmission des programmes de télévision.

 

Compression

Les algorithmes de compression sans perte (lossless) restituent fidèlement les données initiales. Essentiels pour l'archivage de données, par exemple.

Les algorithmes avec pertes (lossy) concernent plutôt les images, le son et la vidéo.

 

Formats de données avec compression

Sans perte: Zip, rar, PNG

Avec perte: JPEG, MP3, MPEG-2,  MPEG-4

 

 

 

Suite

*   AlgorithmesIntroduction

*    Affichage de l'heureExemple

*    AlgorithmeGlossaire

*    Mes premiers pas en programmation (en codage)

*    ProgrammationIndex

Top

*    Les trois algorithmes les plus célèbres aujourd'hui

*    Les 17 équations qui ont changé le monde

*    Les 7 problèmes de la fondation Clay et AUTRES …

Voir

*    Automate

*    Dualité

*    Énigmes et paradoxes

*    Grands Hommes

*    Histoire de l'informatique

*    Histoire des ordinateurs

*    Intelligence

*    Intelligence des animaux

*    Inventions

*    LogiqueIndex

*   Machine de Turing

*    Multimédia et informatiqueIndex

*    Outils de la logique

*    Puissance de calcul

*    Puzzles et énigmesIndex

*    Raisonnement

*    Réseaux neuronaux

*    Systèmes experts

*    Turing et le Bureau 47

Site

*    15 of the Most Important Algorithms That Helped Define Mathematics, Computing, and Physics – Christopher McFadden – 2018

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Logique/IAalgo15.htm