Quels sont les algorithmes significatifs pour l’humanité au cours des dernières décennies? [fermé]

Quels algorithmes les plus importants au monde ont le plus contribué à l’humanité au cours des dernières décennies?

Je pensais que c'était une bonne connaissance générale pour un développeur.

Mise à jour:
Si possible, conservez la réponse à un algorithme de programmation spécifique .
Je voudrais obtenir une liste des plus importants, un seul algorithme par réponse.
S'il vous plaît envisager d'indiquer pourquoi l'algorithme est significatif et important ...

Le chiffrement à clé publique / privée est extrêmement important. Le commerce sur Internet ne serait nulle part aussi omniprésent sans cela.

Algorithme de Dijkstra

L'algorithme existe dans chaque routeur du monde pour identifier le meilleur itinéraire entre deux nœuds d'un réseau.

Transformée de Fourier rapide (FFT)

La FFT est une méthode extrêmement importante et largement utilisée pour extraire des informations utiles à partir de signaux échantillonnés .

Une transformée de Fourier rapide (FFT) est un algorithme efficace pour calculer la transformée de Fourier discrète (DFT) et son inverse.

Classement

PageRank est un algorithme d'analyse des liens, nommé d'après Larry Page, utilisé par le moteur de recherche Internet de Google. Il attribue une pondération numérique à chaque élément d'un ensemble de documents comportant des hyperliens, tels que le World Wide Web, dans le but de "mesurer" sa valeur relative. importance dans l'ensemble.

Algorithmes de compression de données

En informatique et en théorie de l'information, la compression de données ou le codage de source est le processus de codage de l'information utilisant moins de bits (ou d'autres unités portant de l'information) qu'une représentation non codée n'en utiliserait par le biais de schémas de codage spécifiques.

Smith-Waterman (et Needleman-Wunsch)

C'est peut-être trop exagéré, alors veuillez commenter.

Smith-Waterman: l'algorithme d'alignement de séquence

Je pense que l'un de ces exemples est constitué par les algorithmes de Smith-Waterman et de Needleman-Wunsch et leurs approximations. Ils font tous essentiellement la même chose: ils alignent deux chaînes ou plus (séquences) . Il y a une signification en biologie. Lorsque les séquences d'ADN ou de protéines sont alignées, des régions de similarité structurelle, fonctionnelle et évolutive sont révélées.

BLAST en tant que descendant de Smith-Waterman

Une heuristique qui se rapproche de Smith-Waterman est BLAST. Il permet de rechercher des séquences de grandes bases de données pour la similarité biologique. La popularité de BLAST est vraiment formidable - il s'agit très probablement de l'algorithme le plus utilisé en biologie. Les domaines plus récents de la bioinformatique et de la génomique ont des approximations plus récentes et plus précises des algorithmes de Smith-Waterman / Needleman-Wunsch qui sont plus précises que BLAST.

Assemblée du génome en tant que descendant de Smith-Waterman

Des approximations à haut débit de Smith-Waterman et Needleman-Wunsch, plus rapides que BLAST, sont utilisées pour assembler les génomes à partir de séquences séquentielles - où le produit du séquenceur est une quantité énorme d'ADN lu (des milliards) à partir de parties arbitraires du génome qui sont très court (50 à 100 nucléotides). Cette approche a été utilisée pour mener à bien le projet du génome humain. Tout le séquençage moderne se fait de cette façon.

Alignement de séquences multiples une extension de Smith-Waterman

Il existe de nombreux algorithmes d'alignement de séquences multiples - ils se rapprochent d'une version à séquences multiples du Smith-Waterman / Needleman-Wunsch. Plusieurs séquences sont alignées simultanément en tant que groupe. Il s'agit d'un problème beaucoup plus complexe que son homologue par paires, mais les solutions fournissent beaucoup plus d'informations sur la fonction biologique, la structure et l'historique de l'évolution des séquences associées.

Siam a cité comme suit les algorithmes les plus importants du 20ème siècle:

1946: L'algorithme Metropolis pour Monte Carlo . Grâce à l'utilisation de processus aléatoires, cet algorithme offre un moyen efficace de trébucher vers des réponses à des problèmes trop compliqués à résoudre avec précision.

1947: Méthode simplex pour la programmation linéaire . Une solution élégante à un problème commun de planification et de prise de décision.

1950: méthode d'itération de sous-espace de Krylov . Une technique pour résoudre rapidement les équations linéaires qui abondent dans le calcul scientifique.

1951: L'approche décompositive des calculs matriciels . Une suite de techniques pour l'algèbre linéaire numérique.

1957: Le compilateur d'optimisation Fortran . Transforme le code de haut niveau en un code lisible par ordinateur efficace.

1959: Algorithme QR pour calculer des valeurs propres . Une autre opération cruciale de la matrice rendue rapide et pratique.

1962: Algorithmes Quicksort pour le tri . Pour le traitement efficace de grandes bases de données.

1965: Transformation de Fourier rapide . Peut-être l’algorithme le plus répandu aujourd’hui, il décompose les formes d’ondes (comme le son) en composantes périodiques.

1977: Détection de relation entière . Une méthode rapide pour repérer des équations simples satisfaites par des collections de nombres apparemment sans rapport.

1987: Méthode multipolaire rapide . Une avancée dans la gestion de la complexité des calculs à n corps, appliquée à des problèmes allant de la mécanique céleste au repliement des protéines.

Personnellement, je remplacerais la détection de relation entier par PageRank .

PageRank, aimez-le ou détestez-le, mais cela affecte les décisions et les actions de millions de personnes dans le monde entier googlant quotidiennement.

Si je devais énumérer les 3 algorithmes les plus importants utilisés actuellement dans les ordinateurs, je dirais:

1. Recherche binaire
2. Tri rapide
3. Algorithme de Dijkstra

L' algorithme de recherche binaire est utilisé en permanence pour réduire un élément dans une liste triée, la plupart des recherches d'index utilisent quelque chose le long de ces lignes à un moment donné. Cet algorithme fournit une recherche dans une liste ordonnée en o (log n) time.

L’ algorithme Quicksort a finalement réussi à trier jusqu’à O (n log n) cas moyen et à O (n ^ 2) cas pire. Le tri est l’une des tâches de données les plus courantes sur un ordinateur et l’une des plus coûteuses; l’amélioration du tri moyen des cas représentait un progrès considérable en termes d’efficacité.

L'algorithme de Dijkstra, comme on l'a dit, produit le chemin le plus court entre les points d'un graphique. Ceci est largement utilisé pour toutes sortes d'applications de routage, le plus souvent en ce qui concerne Internet lui-même, garantissant que le chemin le plus rapide à travers le réseau enchevêtré de routeurs interconnectés est utilisé.

Théorème de Bayes

C'est probablement elle qui a le plus contribué à maintenir à un niveau gérable le nombre de spams qui font perdre du temps dans ma boîte de réception.

Bien sûr, je suis il a été utilisé dans de nombreuses autres applications intéressantes, mais la suppression de SPAM est mon préféré.

TimSort

C'est l'algorithme de tri utilisé à présent dans Python , Java 7 et Android

Fondamentalement:

• O (N log N) dans le pire des cas (ne dégénère pas)
• O (N) pour une liste presque triée (en fait N-1exactement sur la liste déjà triée)

Et la beauté de ça? C'est stable ! Et donc adapté au tri multipasse selon différents critères.

À propos, si quelqu'un a une implémentation C ++ optimisée sous la main ...

Tous les algorithmes utilisés pour résoudre le problème de visibilité dans l'animation par ordinateur 3D me semblent essentiels.

Algorithme du peintre

L'algorithme du peintre, également appelé remplissage prioritaire, est l'une des solutions les plus simples au problème de visibilité en infographie 3D. Lors de la projection d'une scène 3D sur un plan 2D, il est nécessaire à un moment donné de déterminer quels polygones sont visibles et ceux qui sont masqués.

Z-buffering

En infographie, la mise en tampon z consiste à gérer les coordonnées de profondeur d'image dans des graphiques tridimensionnels (3-D), généralement effectuées de manière matérielle, parfois sous forme de logiciel. C'est une solution au problème de visibilité, qui consiste à décider quels éléments d'une scène rendue sont visibles et lesquels sont cachés. L'algorithme du peintre est une autre solution courante qui, bien que moins efficace, peut également gérer des éléments de scène non opaques. La mise en mémoire tampon Z est également appelée mémoire de profondeur.

Détermination de la surface cachée

En infographie 3D, la détermination de la surface cachée (aussi appelée élimination de la surface cachée, élimination d’occlusion (OC) ou détermination de la surface visible) est le processus utilisé pour déterminer quelles surfaces et parties de surface ne sont pas visibles d’un certain point de vue. Un algorithme de détermination de la surface cachée est une solution au problème de visibilité, qui était l’un des premiers problèmes majeurs dans le domaine de l’infographie 3D. Le processus de détermination de la surface cachée est parfois appelé masquage, et un tel algorithme est parfois appelé masqueur L’analogue pour le rendu de ligne est l’élimination de ligne cachée.

Quel que soit ce dont vous avez besoin pour résoudre votre problème actuel.

Soundex est un algorithme phonétique permettant d'indexer des noms par son.

Algorithme de Viterbi

Utilisé à l'origine pour décoder les codes convolutionnels corrigeant les erreurs, il est maintenant utilisé pour résoudre un large éventail de problèmes de reconnaissance (allant de la reconnaissance vocale à la bioinformatique). Vous pouvez le trouver dans plusieurs périphériques de communication et de stockage.

MP3

Bien que ce soit un terme plus général qu’un algorithme spécifique, je mentionnerais MP3 comme agrégation des différents algorithmes et techniques qui fonctionnent en coopération pour générer ce format audio avec pertes.

Cela a sûrement été très significatif à "l'ère numérique".

Intégration numérique Runge-Kutta . Sans cela, de nombreuses simulations ne seraient pas possibles. Pas de programme spatial, pas d'énergie nucléaire, pas de balistique, pas de simulation sportive, pas de gilet pare-balles, pas de simulation d'essais de collision, pas de simulation de mouvement de fluide, pas de simulation d'interactions chimiques, pas de bâtiments résistants aux tremblements de terre ... la liste est longue.

Algorithme de tri.

Tri rapide

Tri par insertion

Facile à mettre en œuvre, très rapide sur les petites listes et utilisé dans les implémentations Fusion / Tri rapide pour les accélérer. Il est stable et fonctionne dans O (n) sur des listes triées (quand elles sont triées par ordre croissant).

Gauss-Jordan en calcul matriciel

Filtre de Kalman

Il est fortement utilisé en navigation, suivi de cible (pour presque tous les capteurs: radar, sonar, FLIR, ladar). Un manuel montre une application dans un contrôleur de lecteur de disque. Les systèmes de contrôle robotiques utilisent fréquemment des filtres de Kalman.

Langue parlée et écrite.

Ils constituent actuellement l’un des algorithmes les plus efficaces pour transférer des connaissances d’une chose à une autre. Sans langage, la société civile ne pourrait pas exister et l'information ne pourrait pas être transmise.

La structure de données de tas et ses algorithmes associés pour la construction et la maintenance de tas.

Et montrez du respect pour le tri rapide. Même si ce n’est pas toujours le choix, c’est l’un des algorithmes fondamentaux du développement historique de l’informatique et un excellent moyen de comprendre la récursivité et l’analyse algorithmique. C'est beau et oui, j'adore.

Algorithmes d'indexation tels que B-tree, B + -tree, index de hachage, index d'arborescence binaire, etc. Pour indexer une énorme quantité de données.

MapReduce comme moyen de diviser, de conquérir et de paralléliser le traitement de grands ensembles de données.

Algorithme de force brute!

Beaucoup de gens sous-estiment cet algorithme de force brute. En fait, il est principalement utilisé pour résoudre des problèmes sans motif. Je l'aime beaucoup!

Tri à bulles!

Le genre de bulle n'est pas aussi mauvais que Bogosort . C'est pourquoi je vote pour le genre Bubble.