Général

15 des algorithmes les plus importants qui ont aidé à définir les mathématiques, l'informatique et la physique

15 des algorithmes les plus importants qui ont aidé à définir les mathématiques, l'informatique et la physique



We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Algorithmes sont utilisés par nous tous en permanence avec ou sans notre connaissance directe. Ils ont des applications dans de nombreuses disciplines différentes, de math et la physique à, bien sûr, l'informatique.

Il s'avère algorithmes ont une longue et illustre histoire qui remonte à l’ancienne période mésopotamienne. Mais lequel de ces processus de calcul complexes pourrait être considéré comme l'un des plus importants?

Ce sont 15 des candidats les plus probables.

CONNEXES: COMMENT LES ALGORITHMES FONCTIONNENT LE MONDE DANS lequel NOUS VIVONS

Une brève histoire des algorithmes

Les algorithmes sont des ensembles d'instructions prédéfinis et autonomes conçus pour exécuter diverses fonctions, et ils existent depuis plus longtemps que vous ne le pensez. De l'ancienne Babylone à nos jours, les algorithmes sont une caractéristique importante de notre société depuis des millénaires.

Les tout premiers exemples étaient des algorithmes simples utilisés par les anciens pour suivre, entre autres, leurs céréales et leur bétail. Dans leur sillage, et avec l'avènement d'un système numérique formalisé, d'autres sauts technologiques et conceptuels ont été réalisés, dont l'invention de l'abaque, de l'algèbre et du concept de variables.

Les penseurs grecs anciens comme Euclide, Archimède et Ératosthène utilisaient les premiers algorithmes pour faire des choses comme déterminer le plus grand diviseur commun de différents nombres, approximer Pi et calculer des nombres premiers.

Au fil du temps, de telles prouesses donneront lieu à des symboles et des règles impliqués dans la formulation des systèmes d'évaluation.

On pense que le terme «algorithme» lui-même a ses origines avec l'astronome et mathématicien persan du IXe siècle, Muhammad ibn Mūsā al-Khwārizmī. Cet homme est largement considéré comme la personne qui a introduit pour la première fois le positionnement décimal dans le système numérique du monde occidental.

Son nom de famille, latinisé comme Algorithme, deviendrait synonyme d'instructions pour effectuer des calculs pour exécuter des tâches.

On lui attribue également le développement du tout premier système de résolution d'équations linéaires et quadratiques. Les formes d'algorithmes originales, quoique rudimentaires, appelées algorismes, étaient considérés comme des règles pour effectuer des calculs arithmétiques avec des chiffres hindous-arabes.

Le prochain plus grand bond en avant dans l'histoire des algorithmes est survenu dans les années 1800 avec le travail du grand George Boole. Beaucoup d'autres font avancer les algorithmes aux XIXe et XXe siècles, notamment Giuseppe Peano et Ada Lovelace, pour n'en citer que quelques-uns.

Mais les algorithmes bénéficieraient d'une mise à jour majeure avec les travaux d'Emil Post et d'Alan Turing dans les années 1930, ce qui donnerait finalement naissance à l'ordinateur moderne. Rien ne serait plus pareil.

Quels sont les algorithmes les plus importants?

Et donc, sans plus tarder, voici quelques exemples des algorithmes les plus importants de tous les temps. La liste comprend des exemples anciens ainsi que certains des algorithmes informatiques et des algorithmes de programmation les plus révolutionnaires de l'histoire.

La liste d'algorithmes suivante est loin d'être exhaustive et ne présente aucun ordre particulier.

1. Les algorithmes babyloniens sont les plus anciens jamais trouvés

Créateur: Inconnue

Quand il a été créé: vers 1600 avant JC

Son impact / implications sur le monde: Le premier algorithme connu au monde

Bien qu'il existe des preuves d'algorithmes de multiplication précoces en Égypte (vers 2000-1700 avant JC), il est largement admis que l'algorithme écrit le plus ancien a été trouvé sur un ensemble de tablettes d'argile babyloniennes datant d'environ 1800-1600 avant JC.

Leur vraie signification n'a été révélée qu'autour 1972, lorsque l'informaticien et mathématicien Donald E. Knuth a publié les premières traductions en anglais de diverses tablettes mathématiques cunéiformes.

Voici quelques extraits de son 1972 manuscrit expliquant ces premiers algorithmes: -

"Les calculs décrits dans les tablettes babyloniennes ne sont pas simplement des solutions à des problèmes individuels spécifiques; ce sont en fait des procédures générales pour résoudre toute une classe de problèmes." - Pages 672 à 673 de "Ancient Babylonian Algorithms".

Les comprimés semblent également avoir été une forme précoce de manuel d'instructions: -

«Notez également la terminaison stéréotypée« Ceci est la procédure », qui se trouve généralement à la fin de chaque section sur une table. Ainsi, les procédures babyloniennes sont de véritables algorithmes, et nous pouvons féliciter les Babyloniens d'avoir développé une manière agréable d'expliquer un algorithme par exemple alors que l'algorithme lui-même était en cours de définition .... "- Pages 672 à 673 de" Ancient Babylonian Algorithms ".

2. L'algorithme d'Euclid est toujours utilisé aujourd'hui

Créateur: Euclide

Quand il a été créé: 300 avant JC

Son impact / implications sur le monde: L'algorithme d'Euclid est l'un des premiers algorithmes jamais créés et, avec quelques modifications, est encore utilisé par les ordinateurs aujourd'hui.

L'algorithme euclidien est une procédure utilisée pour trouver le plus grand diviseur commun (GCD) de deux entiers positifs. Il a été décrit pour la première fois par Euclide dans son manuscrit Éléments écrit autour 300 avant JC.

C'est un calcul très efficace qui est encore utilisé aujourd'hui par les ordinateurs sous une forme ou une autre.

L'algorithme d'Euclid nécessite la division et le calcul successifs des restes jusqu'à ce que le résultat soit atteint. Il est mieux décrit en utilisant un exemple:

Quel est le GCD de 56 et 12?

Étape 1 - Divisez le plus grand par le plus petit nombre: -

56/12 = 4 (reste 8)

Étape 2 - Divisez le diviseur par le reste de l'étape précédente: -

12/8 = 1 (reste 4)

Étape 3 - Continuez l'étape 2 jusqu'à ce qu'il ne reste plus de reste (dans ce cas, il s'agit d'un processus simple en 3 étapes): -

8/4 = 2 (pas de reste)

Dans ce cas, le GCD est de 4.

Cet algorithme est largement utilisé pour réduire les fractions communes à leurs termes les plus bas et dans les applications mathématiques avancées telles que la recherche de solutions entières aux équations linéaires.

3. Le tamis d'Eratosthène est un algorithme ancien et simple

Créateur: Ératosthène

Quand il a été créé: 200 avant JC

Son impact / implications sur le monde: Le tamis d'Eratosthène est largement accepté comme l'un des algorithmes les plus anciens de tous les temps. Il vous permet de trouver tous les nombres premiers dans une table de nombres donnés (autant que vous souhaitez en inclure).

Pour l'exécuter, vous trouvez tous les nombres supérieurs à 2, puis biffez ceux qui sont divisibles par 2. Ensuite, vous faites de même pour les nombres non barrés supérieurs à 3, ainsi de suite À l'infini jusqu'à ce que tous les nombres composites (non premiers) soient barrés.

4. L'algèbre booléenne (binaire) a été le fondement de l'ère de l'information

Créateur: George Boole

Quand il a été créé: 1847

Son impact / implications sur le monde: Cet algorithme est largement reconnu comme le fondement du codage informatique moderne. Il est encore utilisé aujourd'hui, en particulier dans les circuits informatiques.

Vous connaissez peut-être le terme booléen issu des mathématiques, de la logique et du codage informatique.

L'algèbre booléenne est une branche de l'algèbre dans laquelle une variable ne peut jamais être vraie ou fausse - des valeurs dites de vérité (généralement binaires 1 ou 0). Il a d'abord été inventé par George Boole dans son 1845 travail Une enquête sur les lois de la pensée.

L'algèbre booléenne est largement reconnue comme étant le fondement de l'ère de l'information.

5. L'algorithme d'Ada Lovelace a été le premier programme informatique

Créateur: Ada Lovelace

Quand il a été créé: 1842

Son impact / implications sur le monde: Cet algorithme est largement reconnu comme le premier programme informatique.

Ada Lovelace a passé la meilleure partie de l'année à traduire une des conférences de Charles Babbage (qui avait été transcrite en français par un ingénieur italien) en anglais. Au cours de ce processus, elle a consciencieusement ajouté des notes explicatives supplémentaires.

Ses notes ont été étiquetées A - G, ce dernier décrivant un algorithme pour un «moteur analytique» pour calculer les nombres de Bernoulli. La note G est maintenant largement acceptée comme étant le premier exemple enregistré de code informatique, ce qui en fait le tout premier programmeur informatique.

Le moteur n'a jamais été construit, et donc, son algorithme n'a jamais été testé de son vivant. Son travail a été redécouvert en 1953 quand ses notes ont été republiées.

6. La transformation de Fourier rapide décompose les signaux en fréquences

Créateur: Carl Gauss, Joseph Fourier, James Cooley et John Tukey

Quand il a été créé: 1802, 1822, 1965

Son impact / implications sur le monde: Cet algorithme est utilisé pour décomposer un signal en fréquences qui le composent - un peu comme un accord musical peut être exprimé en fréquences, ou hauteurs, de chaque note qu'il contient.

L'algorithme de transformée de Fourier rapide (FTT) peut retracer ses origines jusqu'à Carl Gauss, qui l'a d'abord créé pour calculer les trajectoires des astéroïdes. La formule a ensuite été développée par Joseph Fourier en 1822.

Mais la forme la plus moderne et la plus largement utilisée de l'algorithme a été créée et publiée par James Cooley et John Tukey dans 1965. Cette version est l'algorithme le plus poussé en mathématiques appliquées et a révolutionné le traitement du signal.

"FFT s'appuie sur une stratégie de division et de conquête pour réduire une corvée ostensiblement O (N2) à un O (N log N) batifoler. Mais contrairement à Quicksort, la mise en œuvre est (à première vue) non intuitive et moins que simple. lui-même a donné à l'informatique une impulsion pour étudier la complexité inhérente aux problèmes informatiques et aux algorithmes. " - Barry A. Cipra.

7. L'algorithme de classement de Google (PageRank) pourrait être l'algorithme le plus utilisé

Créateur: Larry Page (principalement) et Sergey Brin

Quand il a été créé: 1996

Son impact / implications sur le monde: Le PageRank est sans doute l'algorithme le plus utilisé au monde aujourd'hui. C'est, bien sûr, le fondement du classement des pages sur le moteur de recherche de Google.

Il est intéressant de noter que le PageRank porte le nom de Larry Page plutôt que de signifier littéralement «pages Web de rang o». Ce n'est pas le seul algorithme que Google utilise de nos jours pour classer les pages sur ses résultats de recherche, mais c'est le plus ancien et le plus connu d'entre eux.

Le PageRank a été conçu par Larry Page et Sergey Brin alors qu'ils étudiaient à l'Université de Stanford dans le cadre de leur projet de recherche sur un nouveau type de moteur de recherche.

Le principe principal était de classer les pages en fonction de leur importance relative ou de leur popularité. De manière générale, les pages qui apparaissent plus haut dans la hiérarchie ont plus de liens arrière ou de liens vers elles.

L'algorithme de PageRank est donné par la formule suivante:

PR (A) = (1-d) + d (PR (T1) / C (T1) + ... + PR (Tn) / C (Tn))

où:

  • PR (A) est le PageRank de la page A,
  • PR (Ti) est le PageRank des pages Ti qui renvoient à la page A,
  • C (Ti) est le nombre de liens sortants sur la page Ti et;
  • d est un facteur d'amortissement qui peut être réglé entre 0 et 1.

Nous pouvons voir que cet algorithme ne classe pas les sites Web dans leur ensemble, mais classe chaque page individuellement. Il peut également être assimilé à un «schéma pyramidal dans lequel une page particulière est classée de manière récursive en fonction des autres pages qui y renvoient.

Le PageRank est tombé en disgrâce ces dernières années, mais il est toujours utilisé dans le cadre d'une suite générale d'autres algorithmes chez Google.

8. La méthode de Monte Carlo (Metropolis Algorithm) a été utilisée à Los Alamos

Créateur: John von Neumann, Stan Ulam et Nick Metropolis

Quand il a été créé: 1946

Son impact / implications sur le monde: Il a été utilisé comme mot de code Los Alamos pour les simulations stochastiques appliquées pour construire de meilleures bombes atomiques après la Seconde Guerre mondiale.

La méthode de Monte Carlo est définie comme suit: "Monte Carlo est l'art d'approximer une espérance par la moyenne d'échantillon d'une fonction de variables aléatoires simulées."

Cet algorithme important est utilisé pour approcher des solutions à des problèmes numériques d'une complexité ingérable en imitant un processus aléatoire. Il repose sur un échantillonnage aléatoire répété pour obtenir un résultat - en fait, en utilisant le hasard pour résoudre des problèmes qui pourraient être déterministes en principe.

L'algorithme est largement utilisé dans les problèmes physiques et mathématiques et est plus utile lorsqu'il est difficile ou impossible d'utiliser d'autres approches.

Les méthodes de Monte Carlo sont principalement utilisées dans trois classes de problèmes: l'optimisation, l'intégration numérique et la génération de tirages à partir d'une distribution de probabilité.

9. La méthode simplex pour la programmation linéaire a été largement adoptée par l'industrie

Créateur: George Dantzig

Quand il a été créé: 1947

Son impact / implications sur le monde: La méthode simplex de programmation linéaire est l'un des algorithmes les plus réussis de tous les temps. Il a été largement utilisé dans le monde de l'industrie ou dans toute autre situation où la survie économique repose sur la capacité à maximiser l'efficacité dans le cadre d'un budget et / ou d'autres contraintes.

Conçu par George Dantzig en 1947, cet algorithme est devenu l'un des plus répandus de l'histoire, malgré le fait que la plupart des problèmes du monde réel sont très rarement de nature linéaire.

Il offre cependant une manière simple et élégante de trouver des solutions aux problèmes. Certains ont noté qu'il peut être affecté par des retards exponentiels mais qu'il est par ailleurs très efficace - il faut généralement 2m (où m est le nombre de contraintes d'égalité) à 3m itérations à compléter.

Il fonctionne en utilisant une stratégie systématique pour générer et valider des solutions de vertex candidates dans un programme linéaire. A chaque itération, l'algorithme choisit la variable qui apporte la plus grande modification vers la solution à coût minimum.

Cette variable remplace alors l'une de ses covariables, ce qui la limite le plus radicalement, déplaçant ainsi la méthode du simplexe vers une autre partie de l'ensemble de solutions et vers la solution finale.

10. Les méthodes d'itération du sous-espace de Krylov sont encore utilisées aujourd'hui

Créateur (s'il est connu):Magnus Hestenes, Eduard Stiefel et Cornelius Lanczos

Quand il a été créé (s'il est connu): 1950

Son impact / implications sur le monde: La méthode d'itération du sous-espace de Krylov est l'une des dix classes les plus importantes de méthodes numériques au monde.

Les méthodes d'itération du sous-espace de Krylov sont un ensemble d'algorithmes qui ont été développés à l'Institute for Numerical Analysis du National Bureau of Standards dans les années 1950. Ils abordent la tâche trompeusement simple de résoudre des équations de la forme Ax = b.

Bien sûr, ce n'est pas aussi simple que cela, le A est une énorme matrice n par n. Cela signifie donc que la réponse algébrique x = b / A n'est pas exactement un jeu d'enfant à calculer.

"Méthodes itératives - telles que la résolution d'équations de la forme Kxje + 1 = Kxje + b - Axi avec une matrice K plus simple et idéalement "proche" de A - conduit à l'étude des sous-espaces de Krylov. Nommé d'après le mathématicien russe Nikolai Krylov, les sous-espaces de Krylov sont enjambés par les puissances d'une matrice appliquée à un vecteur «reste» initial r0 = b - Hache0. "- Barry A. Cipra.

"Lanczos a trouvé un moyen astucieux de générer une base orthogonale pour un tel sous-espace lorsque la matrice est symétrique. Hestenes et Stiefel ont proposé une méthode encore plus astucieuse, connue sous le nom de méthode du gradient conjugué, pour les systèmes qui sont à la fois symétriques et définis positivement."

Ces algorithmes ont été continuellement modifiés au cours des 50 dernières années. Leurs itérations actuelles pour les systèmes non symétriques comprennent la méthode résiduelle minimale généralisée (GMRES) et la méthode stabilisée par gradient biconjugué (Bi-CGSTAB).

11. Kalman Filter est idéal pour prédire l'avenir, en quelque sorte

Créateur:Rudolf E. Kálmán

Quand il a été créé (s'il est connu): 1958-1961

Son impact / implications sur le monde: Le filtre de Kalman est un outil général et puissant pour combiner des informations en présence d'incertitude.

Le filtrage de Kalman, alias l'estimation quadratique linéaire (LQE), est un algorithme qui utilise une série de mesures, observées dans le temps et incluant un bruit statistique, pour produire une estimation de variables inconnues via une distribution de probabilité conjointe.

En d'autres termes, cela vous aide à faire une estimation éclairée de ce qu'un système va probablement faire ensuite, avec raison bien sûr. Les filtres Kalman sont parfaits pour les situations où les systèmes changent constamment.

Un autre grand avantage de cet algorithme est qu'il est léger en «mémoire». Seul le résultat de l'étape précédente est nécessaire pour progresser, ce qui le rend très rapide et parfaitement adapté à la résolution de problèmes en temps réel.

12. Les algorithmes QR pour le calcul des valeurs propres se sont révélés extrêmement utiles

Créateur: John G. F. Francis et par Vera N. Kublanovskaya indépendamment

Quand il a été créé: Fin des années 50

Son impact / implications sur le monde: L'algorithme QR simplifie grandement les calculs des valeurs propres (qui sont les nombres les plus importants associés aux matrices). Après son développement, le calcul de ces chiffres embêtants est devenu une tâche de routine plutôt qu'un processus formidable et à forte intensité de main-d'œuvre.

L'algorithme QR, alias l'algorithme des valeurs propres, est important en algèbre linéaire numérique. En plus de permettre le calcul rapide des valeurs propres, il facilite également le traitement des vecteurs propres dans une matrice donnée.

Sa fonction de base est d'effectuer une décomposition QR, d'écrire une matrice comme un produit d'une matrice orthogonale et d'une matrice triangulaire supérieure, et de multiplier les facteurs dans l'ordre inverse et d'itérer.

13. La formulation du compilateur d'optimisation Fortran pourrait être l'événement le plus important de l'histoire de la programmation

Créateur: John Backus (et l'équipe IBM)

Quand il a été créé: 1957

Son impact / implications sur le monde: Probablement l'algorithme / l'événement le plus important de la programmation informatique.

Fortran a été développé par John Backus et son équipe chez IBM à la fin des années 1950, permettant aux scientifiques, et à d'autres utilisateurs, de dire à un ordinateur ce qu'ils voulaient qu'il fasse sans qu'il soit nécessaire de «s'enliser» dans les minuties du code machine . Le compilateur d'optimisation de Fortran est modeste par rapport aux normes modernes avec «23 500 instructions en langage d'assemblage - le premier compilateur était néanmoins capable de calculs étonnamment sophistiqués». - Barry A. Cipra.

Backus reconnaîtrait son importance pour le monde plus tard, en 1998, lorsqu'il a rappelé l'histoire de Fortran I, II et III pour le Annales IEEE de l'histoire de l'informatique. Le compilateur, a déclaré Backus, "a produit un code d'une telle efficacité que sa sortie surprendrait les programmeurs qui l'ont étudié."

14. Quicksort est excellent pour aider à trier les choses

Créateur: Tony Hoare d'Elliott Brothers, Limited, Londres

Quand il a été créé: 1962

Son impact / implications sur le monde: Il a fourni un moyen de trier rapidement et efficacement les listes par ordre alphabétique et numérique.

Trier un certain nombre de choses par ordre alphabétique ou numérique a toujours été une tâche laborieuse et fastidieuse. Tony Hoare a réussi, en 1962, pour produire un algorithme pour effectuer cette tâche rapidement.

Son algorithme Quicksort utilisait une stratégie récursive pour «diviser et conquérir» pour parvenir rapidement à une solution. Il s'avérerait être deux à trois fois plus rapide que ses principaux concurrents fusionnent le tri et le tri en tas.

Cela fonctionne en choisissant un élément comme «pivot». Tous les autres sont ensuite triés en piles d'éléments «plus gros» et «plus petits» par rapport au pivot.

Ce processus est ensuite répété dans chaque pile.

"Bien qu'il soit possible de rester coincé en effectuant toutes les comparaisons N (N - 1) / 2 (surtout si vous utilisez comme pivot le premier élément d'une liste déjà triée!), Quicksort fonctionne en moyenne avec une efficacité O (N log N) . " - Barry A. Cipra.

La simplicité et l'élégance de cet algorithme lui ont valu de nombreux éloges à son époque et en ont fait le modèle de la complexité informatique à la fin des années 1990.

15. JPEG et d'autres algorithmes de compression de données sont incroyablement utiles

Créateur: Groupe conjoint d'experts photographiques, IBM, Mitsubishi Electric, AT&T, Canon Inc., Commission d'études 16 de l'UIT-T

Quand il a été créé: 1992

Son impact / implications sur le monde: Les algorithmes de compression de données, tels que JPEG, MP3, zip ou MPEG-2, sont largement utilisés dans le monde entier. La plupart sont devenus de facto standard pour leur application particulière. Ils ont rendu les systèmes informatiques moins chers et plus efficaces au fil du temps.

Il est difficile de distinguer un algorithme de compression de données particulier car sa valeur ou son importance dépend des applications des fichiers. Ils sont devenus si répandus aujourd'hui qu'ils sont utilisés chaque fois que vous téléchargez un fichier sur votre ordinateur, jouez de la musique ou des jeux vidéo, diffusez des vidéos, utilisez une base de données ou interagissez avec le cloud.


Voir la vidéo: TOUT COMPRENDRE À LIA - Dossier #33 - LEsprit Sorcier (Août 2022).