Algorithmes de base déployés

Pour démontrer l’importance des algorithmes (par exemple pour les étudiants et les professeurs qui ne pratiquent pas la théorie ou qui viennent même de domaines totalement différents), il est parfois utile de disposer d’une liste d’exemples où des algorithmes centraux ont été déployés dans les secteurs commercial, gouvernemental, etc. ou logiciel / matériel largement utilisé.

Je recherche de tels exemples qui répondent aux critères suivants:

1. Le logiciel / matériel utilisant l'algorithme devrait être largement utilisé maintenant.

2. L'exemple devrait être spécifique. Veuillez donner une référence à un système spécifique et à un algorithme spécifique.
   Par exemple, dans "l'algorithme X est utile pour le traitement d'image", le terme "traitement d'image" n'est pas assez spécifique; dans "La recherche Google utilise des algorithmes graphiques", le terme "algorithmes graphiques" n'est pas suffisamment spécifique.

3. L'algorithme doit être enseigné dans des programmes de premier cycle ou de doctorat typiques. classes d'algorithmes ou de structures de données. Idéalement, l'algorithme est traité dans des manuels d'algorithmes typiques. Par exemple, "le système X connu utilise l'algorithme Y peu connu" n'est pas bon.

Mise à jour:

Merci encore pour les bonnes réponses et les liens! Certaines personnes font remarquer qu'il est difficile de satisfaire aux critères, car les algorithmes centraux sont tellement omniprésents qu'il est difficile d'indiquer une utilisation spécifique. Je vois la difficulté. Mais je pense que cela vaut la peine de proposer des exemples spécifiques car, selon mon expérience, je disais aux gens: "Regardez, les algorithmes sont importants parce qu'ils sont un peu partout !" ne marche pas.

Les algorithmes qui sont le moteur principal d’un système sont, à mon avis, plus faciles à trouver dans les cours autres que les algorithmes, pour la même raison, les théorèmes ayant des applications immédiates sont plus faciles à trouver dans les mathématiques appliquées que dans les cours de mathématiques pures. Il est rare qu'un problème pratique ait la structure exacte du problème abstrait dans une conférence. Pour argumenter, je ne vois aucune raison pour que le matériel de cours d'algorithmes à la mode tel que la multiplication de Strassen, le test de primalité AKS ou l'algorithme de Moser-Tardos soit pertinent pour les problèmes pratiques de bas niveau liés à la mise en oeuvre d'une base de données vidéo, d'un compilateur d'optimisation, d'un système d'exploitation , un système de contrôle de congestion de réseau ou tout autre système. La valeur de ces cours est d’apprendre qu’il existe des moyens complexes d’exploiter la structure d’un problème pour trouver des solutions efficaces. Les algorithmes avancés sont également des endroits où l'on rencontre des algorithmes simples dont l'analyse est non triviale. Pour cette raison, je ne rejeterais pas les algorithmes aléatoires simples ou le PageRank.

Je pense que vous pouvez choisir n’importe quel gros logiciel et y trouver des algorithmes de base et avancés. En guise d’étude de cas, j’ai fait cela pour le noyau Linux et ai montré quelques exemples de Chromium.

Structures de données de base et algorithmes dans le noyau Linux

Les liens sont vers le code source sur github .

1. Liste de liens , liste doublement chaînée , liste chaînée verrouillage sans .

2. B + Arbres avec des commentaires vous indiquant ce que vous ne pouvez pas trouver dans les manuels.

   Une implémentation relativement simple de B + Tree. Je l’ai écrit comme un exercice d’apprentissage pour comprendre le fonctionnement de B + Trees. S'est avéré utile aussi.

   ...

   Une astuce a été utilisée qui ne se trouve pas couramment dans les manuels scolaires. Les valeurs les plus basses sont à droite, pas à gauche. Tous les emplacements utilisés dans un nœud sont à gauche, tous les emplacements inutilisés contiennent des valeurs NUL. La plupart des opérations bouclent simplement une fois sur tous les slots et se terminent sur le premier NUL.

3. Listes de tri prioritaires utilisées pour les mutex , les pilotes , etc.

4. Les arbres rouge-noir sont utilisés pour la planification, la gestion de la mémoire virtuelle, le suivi des descripteurs de fichiers et des entrées de répertoire, etc.
5. Arbres à intervalles

6. Les arbres Radix sont utilisés pour la gestion de la mémoire , les recherches liées à NFS et les fonctionnalités liées au réseau.

   Une utilisation courante de l’arbre de base est de stocker des pointeurs pour structurer des pages;

7. Priorité tas , qui est littéralement une implémentation de manuel, utilisée dans le système de groupe de contrôle .

   Segment de priorité prioritaire de taille statique contenant uniquement des pointeurs, basé sur CLR, chapitre 7

8. Les fonctions de hachage , avec une référence à Knuth et à un papier.

   Knuth recommande les nombres premiers approximativement selon le nombre d'or par rapport au nombre entier maximum pouvant être représenté par un mot machine pour le hachage multiplicatif. Chuck Lever a vérifié l'efficacité de cette technique:

   http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

   Ces nombres premiers sont choisis pour être binaires, c'est-à-dire que leurs opérations peuvent utiliser des décalages et des ajouts au lieu de multiplications pour des machines où les multiplications sont lentes.

9. Certaines parties du code, telles que ce pilote , implémentent leur propre fonction de hachage.

   fonction de hachage utilisant un algorithme Rotating Hash

   Knuth, D. L'art de la programmation informatique, volume 3: le tri et la recherche, chapitre 6.4. Addison Wesley, 1973

10. Tables de hachage utilisées pour implémenter les inodes , les contrôles d'intégrité du système de fichiers, etc.

11. Les tableaux de bits , utilisés pour traiter les drapeaux, les interruptions, etc., sont décrits dans Knuth Vol. 4

12. Sémaphores et verrous

13. La recherche binaire est utilisée pour la gestion des interruptions , la recherche de cache de registre , etc.

14. Recherche binaire avec arbres B

15. Profondeur première recherche et variante utilisée dans la configuration du répertoire .

    Effectue une première marche modifiée de l’arborescence de l’espace de noms en commençant (et se terminant) au nœud spécifié par start_handle. La fonction de rappel est appelée chaque fois qu'un noeud correspondant au paramètre type est trouvé. Si la fonction de rappel renvoie une valeur autre que zéro, la recherche est immédiatement terminée et cette valeur est renvoyée à l'appelant.

16. La largeur de la première recherche est utilisée pour vérifier l'exactitude du verrouillage au moment de l'exécution.

17. Le tri par fusion sur les listes chaînées est utilisé pour la récupération de place , la gestion du système de fichiers , etc.

18. Le tri à bulles est étonnamment implémenté aussi, dans une bibliothèque de pilotes.

19. Correspondance de chaîne Knuth-Morris-Pratt ,

    Implémente un algorithme de correspondance de chaîne linéaire dans le temps en raison de Knuth, Morris et Pratt [1]. Leur algorithme évite le calcul explicite de la fonction de transition DELTA. Son temps de correspondance est O (n), pour n longueur (texte), en utilisant simplement une fonction auxiliaire PI [1..m], pour m longueur (motif), précalculé à partir du motif du temps O (m). Le tableau PI permet à la fonction de transition DELTA d'être calculée efficacement "à la volée" selon les besoins. Pour résumer, pour tout état "q" = 0,1, ..., m et tout caractère "a" dans SIGMA, la valeur PI ["q"] contient les informations indépendantes de "a" et est nécessaire pour calculer DELTA ("q", "a") 2. Puisque le tableau PI n'a que m entrées, alors que DELTA a O entrées (m | SIGMA |), nous économisons un facteur de | SIGMA | dans le temps de prétraitement en calculant PI plutôt que DELTA.

    [1] Cormen, Leiserson, Rivest, Introduction de Stein aux algorithmes, 2e édition, MIT Press.

    [2] Voir la théorie de l'automatisation finie

20. Correspondance des motifs de Boyer-Moore avec des références et recommandations pour savoir quand préférer l'alternative.

    Implémente l'algorithme de correspondance de chaîne de Boyer-Moore:

    [1] Algorithme de recherche rapide de chaînes, RS Boyer et Moore. Communications de l'Association for Computing Machinery, 20 (10), 1977, p. 762-772. http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

    [2] Manuel d'algorithmes de correspondance de chaîne exacte, Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf.

    Remarque: Boyer-Moore (BM) effectuant des recherches d'appariement de droite à gauche, il est encore possible qu'une correspondance puisse être étalée sur plusieurs blocs. Dans ce cas, cet algorithme ne détectera aucune coïncidence.

    Si vous souhaitez vous assurer que cela ne se produira jamais, utilisez plutôt la mise en œuvre Knuth-Pratt-Morris (KMP). En conclusion, choisissez l'algorithme de recherche de chaîne approprié en fonction de votre configuration.

    Supposons que vous utilisiez l'infrastructure de recherche de texte pour le filtrage, NIDS ou
    tout autre objectif similaire axé sur la sécurité, puis optez pour KMP. Sinon, si vous vous souciez vraiment des performances, supposons que vous classifiez les paquets pour appliquer les stratégies de qualité de service (QoS), et que vous ne craignez pas les correspondances possibles réparties sur plusieurs fragments, puis choisissez BM.

Structures de données et algorithmes dans le navigateur Web Chrome

Les liens sont vers le code source sur le code Google . Je ne vais en énumérer que quelques-uns. Je suggérerais d'utiliser la fonction de recherche pour rechercher votre algorithme ou structure de données préféré.

1. Arbres splay .

   L'arbre est également paramétré par une politique d'allocation (Allocator). La stratégie est utilisée pour allouer des listes dans le magasin gratuit C ou dans la zone. voir zone.h.

2. Les diagrammes de Voronoï sont utilisés dans une démo.
3. Tabulation basée sur l'algorithme de Bresenham .

1. Arbres binaires
2. Arbres rouge-noir

   Conclusion de Julian Walker

   Les arbres noirs et rouges sont des bêtes intéressantes. On pense qu'ils sont plus simples que les arbres AVL (leur concurrent direct), et à première vue, cela semble être le cas, car l'insertion est un jeu d'enfant. Cependant, quand on commence à jouer avec l'algorithme de suppression, les arbres noirs et rouges deviennent très délicats. Cependant, le contrepoids à cette complexité supplémentaire réside dans le fait que l’insertion et la suppression peuvent être mises en œuvre à l’aide d’un algorithme descendant unique. Ce n'est pas le cas avec les arbres AVL, où seul l'algorithme d'insertion peut être écrit de haut en bas. La suppression d'une arborescence de AVL nécessite un algorithme ascendant.

   ...

   Les arbres noirs et rouges sont populaires, comme la plupart des structures de données avec un nom fantaisiste. Par exemple, en Java et C ++, les structures de carte de bibliothèque sont généralement implémentées avec un arbre noir rouge. Les arbres noirs et rouges ont également une vitesse comparable à celle des arbres AVL. Bien que l'équilibre ne soit pas aussi bon, le travail nécessaire pour le maintenir est généralement meilleur dans un arbre noir rouge. Il y a quelques idées fausses qui circulent, mais pour l'essentiel, le battage médiatique sur les arbres noirs et rouges est exact.

3. Arbres AVL
4. La correspondance de chaîne Rabin-Karp est utilisée pour la compression.
5. Calcule les suffixes d'un automate .
6. Filtre Bloom implémenté par Apple Inc.
7. Algorithme de Bresenham .

Bibliothèques de langages de programmation

Je pense qu'ils valent la peine d'être considérés. Les concepteurs de langages de programmation ont estimé que certains ingénieurs avaient intérêt à consacrer du temps et des efforts à la mise en œuvre de ces structures de données et de ces algorithmes afin que d'autres n'en aient pas besoin. L’existence de bibliothèques est une des raisons pour lesquelles nous pouvons trouver des structures de données de base réimplémentées dans un logiciel écrit en C mais moins pour les applications Java.

1. La STL C ++ comprend des listes, des piles, des files d'attente, des cartes, des vecteurs et des algorithmes pour le tri, la recherche et la manipulation de segments de mémoire .
2. L'API Java est très étendue et couvre beaucoup plus.
3. La bibliothèque Boost C ++ inclut des algorithmes tels que Boyer-Moore et Knuth-Morris-Pratt.

Algorithmes d'allocation et d'ordonnancement

Je trouve cela intéressant parce que même si elles s'appellent des heuristiques, la politique que vous utilisez dicte le type d'algorithme et la structure de données nécessaires. Vous devez donc connaître les piles et les files d'attente.

1. Le moins récemment utilisé peut être mis en œuvre de plusieurs manières. Une implémentation basée sur des listes dans le noyau Linux.
2. Les autres possibilités sont le premier entré, le premier sorti, le moins fréquemment utilisé et le round robin.
3. Une variante de FIFO a été utilisée par le système VAX / VMS.
4. L'algorithme Clock de Richard Carr est utilisé pour le remplacement du cadre de page sous Linux.
5. Le processeur Intel i860 a utilisé une stratégie de remplacement aléatoire.
6. Le cache de remplacement adaptatif est utilisé dans certains contrôleurs de stockage IBM et dans PostgreSQL, bien que brièvement, en raison de problèmes de brevets .
7. L' algorithme d'allocation de mémoire Buddy , qui est décrit par Knuth dans TAOCP Vol. 1 est utilisé dans le noyau Linux et l'allocateur simultané jemalloc utilisé par FreeBSD et dans Facebook .

Utilitaires de base dans les systèmes * nix

1. grep et awk implémentent tous les deux la construction Thompson-McNaughton-Yamada d'ADN à partir d'expressions régulières, qui surpassent apparemment l'implémentation de Perl .
2. tsort implémente le tri topologique.
3. fgrep implémente l' algorithme de correspondance de chaînes Aho-Corasick.
4. GNU grep , implémente l'algorithme de Boyer-Moore selon l'auteur Mike Haertel.
5. crypt (1) sur Unix a implémenté une variante de l'algorithme de chiffrement sur la machine Enigma.
6. Le diff Unix implémenté par Doug McIllroy, basé sur un prototype co-écrit avec James Hunt, fonctionne mieux que l’algorithme de programmation dynamique standard utilisé pour calculer les distances de Levenshtein. La version Linux calcule la distance d'édition la plus courte.

Algorithmes Cryptographiques

Cela pourrait être une très longue liste. Les algorithmes cryptographiques sont implémentés dans tous les logiciels pouvant effectuer des communications ou des transactions sécurisées.

1. Les arbres Merkle , en particulier la variante Tiger Tree Hash, ont été utilisés dans des applications entre homologues telles que GTK Gnutella et LimeWire .
2. MD5 est utilisé pour fournir une somme de contrôle pour les packages logiciels et pour les contrôles d'intégrité sur les systèmes * nix ( implémentation Linux ). Il est également pris en charge sous Windows et OS X.
3. OpenSSL implémente de nombreux algorithmes cryptographiques, notamment AES, Blowfish, DES, SHA-1, SHA-2, RSA, DES, etc.

Compilateurs

1. L'analyse LALR est implémentée par yacc et bison.
2. Les algorithmes Dominator sont utilisés dans la plupart des compilateurs d'optimisation basés sur la forme SSA.
3. lex et flex compilent les expressions régulières dans les NFA.

Compression et traitement d'image

1. Les algorithmes de Lempel-Ziv pour le format d'image GIF sont implémentés dans des programmes de manipulation d'images, à partir de l'utilitaire * nix converti en programmes complexes.
2. Le codage de longueur d'exécution est utilisé pour générer des fichiers PCX (utilisés par le programme Paintbrush d'origine), des fichiers BMP compressés et des fichiers TIFF.
3. La compression par ondelettes étant la base de JPEG 2000, tous les appareils photo numériques générant des fichiers JPEG 2000 implémenteront cet algorithme.
4. La correction d'erreur Reed-Solomon est implémentée dans le noyau Linux , les lecteurs de CD, les lecteurs de codes à barres et a été combinée à la convolution pour la transmission d'images à partir de Voyager.

Apprentissage par clause axée sur les conflits

Depuis l'an 2000, la durée d'exécution des solveurs SAT sur des points de repère industriels (généralement issus du secteur du matériel, bien que d'autres sources soient également utilisées) a diminué chaque année de manière presque exponentielle. Une partie très importante de ce développement concerne l’ algorithme d’ apprentissage par clause axé sur les conflits , qui associe l’algorithme booléen de contrainte dans l’article original de Davis Logemann et Loveland à la technique d’apprentissage par clause issue de la programmation par contraintes et de la recherche en intelligence artificielle. Pour la modélisation industrielle spécifique, la SAT est considérée comme un problème facile ( voir la présente discussion).). Pour moi, il s’agit de l’une des plus grandes réussites de la période récente, car elle combine des avancées algorithmiques étalées sur plusieurs années, des idées ingénieuses en matière d’ingénierie, une évaluation expérimentale et un effort collectif concerté pour résoudre le problème. L' article de CACM par Malik et Zhang est une bonne lecture. Cet algorithme est enseigné dans de nombreuses universités (j'ai assisté à quatre où c'était le cas) mais généralement dans un cours de logique ou de méthodes formelles.

Les applications des solveurs SAT sont nombreuses. IBM, Intel et de nombreuses autres entreprises ont leurs propres implémentations de solveur SAT. Le gestionnaire de paquets dans OpenSUSE utilise également un solveur SAT.

PageRank est l'un des algorithmes les plus connus. Développé par le cofondateur de Google, Larry Page, et ses co-auteurs, ce logiciel a été à la base du moteur de recherche original de Google et est largement réputé pour l’avoir aidé à obtenir de meilleurs résultats de recherche que leurs concurrents de l’époque.

Nous imaginons un "surfeur aléatoire" commençant sur une page Web et cliquant de manière répétée sur un lien aléatoire pour l'emmener sur une nouvelle page. La question est: "Quelle fraction du temps le surfeur passera-t-il sur chaque page?" Plus le surfeur passe de temps sur une page, plus la page est considérée comme importante.

$M$

$M^k \pi_0$$k$$\pi_0$$M$

Je mentionnerais le logiciel CPLEX (ou similaire), largement utilisé, de la méthode / algorithme Simplex pour résoudre les problèmes de programmation linéaire. C'est l'algorithme (?) Le plus utilisé dans la recherche économique et opérationnelle.

"Si l'on prenait des statistiques sur le problème mathématique qui utilise le plus de temps informatique dans le monde, alors (sans compter les problèmes de manipulation de base de données tels que le tri et la recherche), la réponse serait probablement une programmation linéaire. " (L. Lovász, Un nouveau algorithme de programmation linéaire - meilleur ou pire que la méthode simplex? Math. Intelligencer 2 (3) (1979/80) 141-146.)

L'algorithme Simplex a également une grande influence en théorie; voir, par exemple, la conjecture de Hirsch (polynomiale) .

Je suppose qu'un étudiant typique de premier cycle ou de doctorat class in algorithmics traite de l'algorithme Simplex (y compris les algorithmes de base de l'algèbre linéaire comme Gauss Elimination Method).

(D'autres algorithmes réussis, y compris Quicksort pour le tri, sont répertoriés dans Algorithmes du livre .)

Si je comprends bien, le national de jumelage des résidents n’a été pendant longtemps qu’une application directe de l’ algorithme de Gale-Shapley au problème du mariage stable. Depuis, il a été légèrement mis à jour pour traiter certains détails supplémentaires tels que les assignations de conjoint (ou "problème à deux corps"), etc ...

Si vous incluez également un programme de niveau doctorat, de nombreux programmes (parmi la plupart?) De troisième cycle comprennent un cours sur la théorie du codage. Si vous suivez un cours de théorie des codes, vous allez certainement aborder le code de Reed-Solomon qui fait partie intégrante du fonctionnement des disques compacts et le codage Huffman utilisé dans les formats de fichier JPEG, MP3 et ZIP. En fonction de l'orientation du cours, vous pouvez également couvrir Lempel-Ziv, utilisé au format GIF. Personnellement, j'ai eu Lempel-Ziv dans un cours d'algorithme de premier cycle, mais je pense que cela pourrait être atypique.

GNU grep est un outil de ligne de commande permettant de rechercher dans un ou plusieurs fichiers d’entrée des lignes contenant une correspondance avec un motif spécifié. Il est bien connu que grep est très rapide! Voici une citation de son auteur Mike Haertel (prise d' ici ):

GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the
final letter of the target string, and uses a lookup table to tell it how far
ahead it can skip in the input whenever it finds a non-matching character.

Plus généralement, le prix Kanellakis est décerné par l'ACM pour précisément ces découvertes théoriques qui ont eu un impact majeur dans la pratique.

le prix de 2012 concerne le hachage tenant compte des localités , qui est devenu une méthode de choix pour la réduction de la dimensionnalité dans l'exploration de données en cas de problèmes de voisinage (et est relativement facile à enseigner - du moins pour l'algorithme lui-même)

le $\varepsilon$ fraction près de la "masse" totale de tous les éléments (la masse est le premier ou le second moment de le vecteur de fréquence). Cela suffit pour trouver des éléments "tendances", ce dont vous avez besoin dans de nombreuses applications.

Voici quelques exemples d'utilisations industrielles de ces structures de données:

• Le système Google de Sawzall pour l'analyse de données non structurées utilise le compte croquis pour mettre en œuvre une fonction «éléments les plus populaires»
• Le système de "base de données de flux" Gigascope d' AT & T pour la surveillance du trafic réseau implémente le schéma CountMin.
• Le système de surveillance continue de Sprint (CMON) implémente CountMin.

Voici également un site qui collecte des informations sur les applications de CountMin.

En ce qui concerne l'enseignement, je sais que les techniques de dessin de base sont enseignées à Princeton dans des cours de mathématiques discrets de premier cycle. On m'a appris le sketch CountMin lors de mon premier cours d'algorithmes. Quoi qu'il en soit, l'analyse de CountMin est plus simple que celle de presque tous les autres algorithmes randomisés: il s'agit d'une application simple de l'indépendance par paire et de l'inégalité de Markov. Si ce n'est pas le matériel standard dans la plupart des cours d'algorithmes, je pense que c'est pour des raisons historiques.

Au cours de la dernière décennie, des algorithmes ont été utilisés pour augmenter le nombre (et la qualité, je pense?) Des greffes de rein par le biais de divers programmes de jumelage de donneurs. J'ai eu du mal à trouver les dernières nouvelles à ce sujet, mais voici au moins quelques indications:

• En 2007, l’Alliance for Paired Donation utilisait un algorithme d’ Abraham, de Blum et de Sandholm. . Ils l'utilisent peut-être encore, mais je n'ai pas pu le savoir en effectuant une recherche en ligne. Bien que cet algorithme ne soit presque certainement pas traité dans les cours "standard", il combine plusieurs idées fondamentales enseignées dans ces cours afin de fournir un algorithme assez bon pour un problème généralement NP-complet (une variante de Cycle Cover )

• Le registre national des reins utilise également certains algorithmes standard, notamment CPLEX (à un moment donné). Cela a conduit à une chaîne de transplantations réellement exécutée reliant 60 personnes .

C’est l’un de mes exemples préférés, non seulement du succès des algorithmes, mais aussi de l’importance de l’étude des algorithmes pour les problèmes NP-complets. Ils peuvent littéralement sauver des vies et l’ont déjà fait!

L'algorithme de Viterbi, qui est encore largement utilisé dans la reconnaissance vocale et de nombreuses autres applications: http://en.wikipedia.org/wiki/Viterbi_algorithm L'algorithme lui-même est une programmation dynamique de base.

From Wikipedia: "L’algorithme de Viterbi a été proposé par Andrew Viterbi en 1967 en tant qu’algorithme de décodage pour les codes convolutifs sur des liaisons de communication numériques bruyantes. [1] L’algorithme a trouvé une application universelle dans le décodage des codes convolutifs utilisés à la fois dans les réseaux numériques cellulaires numériques CDMA et GSM. modems d'accès distant, satellites, communications en espace lointain et réseaux locaux sans fil 802.11. Il est également couramment utilisé aujourd'hui pour la reconnaissance vocale, la synthèse vocale, la recherche de mots clés, la linguistique computationnelle et la bioinformatique, par exemple dans la synthèse vocale reconnaissance), le signal acoustique est traité comme la séquence d'événements observée et une chaîne de texte est considérée comme la "cause cachée" du signal acoustique. L'algorithme de Viterbi recherche la chaîne de texte la plus probable en fonction du signal acoustique. "

1. A * est utilisé dans de nombreux appareils de navigation personnels (également appelés unités GPS)
2. A * est très bien défini et a été mis en œuvre assez simplement.
3. A * n'est pas tout à fait trivial, mais il ne faut pas de doctorat pour le comprendre.

Découvrez le projet BonnTools for Chip Design de Jens Vygen. http://www.or.uni-bonn.de/~vygen/projects.html J'ai entendu des exposés à ce sujet et j'ai également examiné certains de leurs documents. Ils utilisent l’arrondissement aléatoire de style Raghavan-Thompson ainsi que la méthode de mise à jour multiplicative du poids pour la résolution de LP à flux de production multiples à grande échelle. Cependant, comme dans tout grand projet, ils doivent aussi faire de l'ingénierie, mais la méthodologie repose beaucoup sur des algorithmes bien connus.

C'est drôle que j'ai vu cette question aujourd'hui et que, par coïncidence, j'ai cliqué sur ce lien pour consulter les nombreuses utilisations de la transformation de Fourier .

Je suis plutôt surpris de voir que, avec tous les algorithmes sophistiqués ci-dessus, personne ne mentionne la vénérable famille d'algorithmes de compression Lempel-Ziv (inventée en 1977/78).

1. Ceux-ci sont utilisés partout - du texte à l'image pour le traitement en continu. Il est fort possible que LZ * soit l’un des algorithmes les plus utilisés.
2. La compression du dictionnaire constituait une avancée considérable dans la théorie de la compression et un changement radical par rapport à l'approche de Shannon-Fano.
3. Les algorithmes de la famille sont plutôt simples et faciles à comprendre.

Mise à jour

Apparemment, cela a déjà été mentionné brièvement.

La décomposition en valeurs singulières (SVD) est étroitement liée à l' analyse factorielle statistique ou à l' analyse en composantes principales et est compréhensible dans une classe d'algèbre linéaire ou de statistiques de premier cycle et possède de nombreuses propriétés théoriques importantes. il joue également un rôle dans les algorithmes de compression d'images. il a joué un rôle clé dans les entrées gagnantes du concours Netflix d'un million de dollars (l'un des plus grands concours de datamining au monde) et est désormais implémenté sur leur site pour prédire le nombre d'utilisateurs. il est également connu pour être étroitement lié aux réseaux de neurones auto-organisateurs de Hebbian, qui trouvent leur origine dans la théorie biologique.

il existe également un lien avec la descente de gradient qui est largement utilisée dans les réseaux de neurones artificiels et d’ apprentissage automatique , ainsi qu’en tant que technique d’optimisation très universellement appliquée, la méthode de Newton étant une forme 2D de base. il existe un algorithme de descente de gradient pour obtenir le SVD.

La recherche d'un chemin eulérien est à la base de l'assemblage du génome - une tâche couramment effectuée lorsque l'on travaille avec des génomes complets (en bioinformatique, en médecine, en criminalistique, en écologie).

MISE À JOUR Oubliée celle évidente: UPS, FedEx et USPS doivent résoudre chaque soir de grandes instances de problème lié au vendeur itinérant. Cela leur permet d'économiser beaucoup de temps et d'argent pour envoyer les chauffeurs sur un itinéraire optimal.

UPDATE2 Le minimum de vertex de retour est utilisé pour la résolution des blocages dans de nombreux systèmes d'exploitation.

J'aime ce système qui permet de sauver un maximum de vies au Royaume-Uni grâce aux greffes de rein, basé sur des algorithmes d'appariement maximum: don de rein apparié et altruiste . Ils mettent en correspondance des personnes ayant besoin d'un rein et dont un ami / un parent ne correspondant pas est disposé à faire un don, avec d'autres personnes se trouvant dans la même situation, de manière maximale. Puis le jour du don, tous les donneurs font un don en même temps, suivi d'un transport rapide des reins à travers le pays jusqu'aux destinataires.

Ce livre relativement nouveau mérite d'être considéré comme une réponse complète / détaillée à la question sous une forme pratique, étendue / collectée, et qui pourrait être utilisé comme matériel supplémentaire pour une classe d'algorithmes. [certains d’entre eux ont déjà été mentionnés; le fort chevauchement est remarquable.]

• Neuf algorithmes qui ont changé l'avenir: les idées ingénieuses qui animent les ordinateurs d' aujourd'hui par MacCormick

  • indexation des moteurs de recherche
  • Classement
  • cryptographie à clé publique
  • codes de correction d'erreur
  • la reconnaissance de formes
  • compression de données
  • bases de données
  • signatures numériques
  • théorie de la calculabilité

• Une autre référence quelque peu similaire mais plus théorique, Le meilleur du 20ème siècle: Nom de l' éditeur - Top 10 Algorithms Cipra / SIAM.

  • Méthode de Monte Carlo
  • algorithme simplex
  • Krylov sous-espace itération
  • calcul matriciel de décomposition
  • Compilateur Fortran
  • Algorithme de matrice QR
  • tri rapide
  • FFT
  • détection de relation entière
  • algorithme multipolaire rapide

La recherche de chaînes Knuth-Morris-Pratt est largement utilisée, spécifique et enseignée dans les étudiants de premier cycle et de deuxième cycle.

En pensant à des algorithmes très basiques

1. Les générateurs de nombres aléatoires se trouvent partout et spécifiquement dans tous les jeux.
2. Les bases de données sont composées de nombreux algorithmes, notamment B +, hachages, files d'attente prioritaires, expressions régulières, cryptographie, tri, etc. Un de mes amis a déclaré que les SGBD se situaient au sommet de la chaîne alimentaire.
3. Le tri est utilisé partout, par exemple dans Excel. Il est effectivement utilisé à tout moment dans la vie réelle, mais en général, les humains utilisent des algorithmes ad hoc.
4. Les bits de parité sont utilisés tout autour
5. Le codage Huffman est un logiciel de compression et de transmission
6. Les piles (LIFO) sont utilisées partout. Dans les langages de programmation, dans les processeurs, etc ...

C'est bien de montrer qu'ils apparaissent dans la vie réelle:

A. De nombreux groupes utilisent une sorte d’algorithme d’arbre de couverture pour communiquer en divisant les listes téléphoniques de manière hiérarchique entre les personnes B. Les voitures situées à une intersection utilisent généralement un algorithme alternatif (de manière volontaire) C. La plupart des lieux, comme des banques et des hôpital, organisent leurs clients dans un algorithme FIFO

Un problème algorithmique fascinant se pose dans les applications médicales du scanner. En tomographie informatisée (CT), le corps est exposé aux rayons X sous différents angles. Les émetteurs de rayons X se trouvent à une extrémité du scanner et les capteurs à l’autre extrémité. À partir d'une telle série de numérisations, une image est reconstruite pour que le médecin puisse l'examiner!

L' algorithme de rétroprojection filtré est la base de la reconstruction d'une image à partir d'un ensemble de numérisations. Cet algorithme est en fait une forme de problème d’approximation dans lequel le "signal" est échantillonné en dessous du taux de Nyquist. Cet algorithme est utilisé "en coulisse" dans tous les hôpitaux et la rétroprojection filtrée de base utilise des mathématiques de premier cycle telles que les transformations de Fourier pour réaliser le théorème de la tranche de Fourier .

Un exemple de FFT

Une fois, j'ai aidé à porter un algorithme FFT dans une autre langue système.

L'algorithme était utilisé pour déterminer les coupures de lignes dans la livraison coaxiale de la télévision par câble / Internet / téléphone. En gros, un technicien demande à ce qu'un signal soit envoyé à la boîte du client, tout en obtenant un affichage en temps réel des statistiques relatives à un client spécifique, telles que la qualité de service, le dB, ... Le technicien peut utiliser les données et un graphique pour déterminer à quelques pas de distance entre la maison et le pôle où il existait une rupture partielle (ou de multiples ruptures, comme on me l'avait dit).

Comme mentionné ci-dessus, la FFT est largement utilisée, mais c’est l’une des plus flagrantes et évidentes (en termes de pourquoi et de comment) que j’ai vu dans la pratique.

Désolé j'ai dû garder un haut niveau.

L'algorithme de ligne de Bresenham est l'algorithme le plus utile que j'ai rencontré. Facile à comprendre, je l’ai utilisé pour de nombreuses applications allant du dessin de ligne à un répartiteur complexe pour le moteur de diffusion 3D au rendu complexe de polygones, ainsi que pour des utilisations complexes en animation et en redimensionnement.

Planification d'itinéraire personnalisable (Daniel Delling, Andrew V. Goldberg, Thomas Pajor et Renato F. Werneck) http://research.microsoft.com/apps/pubs/default.aspx?id=145688

pouvoirs de Bing Maps: http://www.bing.com/blogs/site_blogs/b/maps/archive/2012/01/05/bing-maps-new-routing-engine.aspx

Wikipedia possède une collection décente d'algorithmes / applications classés plus ou moins dans une liste . Microsoft fournit les articles les plus cités, mais sans aucune explication explicite du domaine de l'informatique ni de l'application. Il existe également une liste chronologique de différentes conférences CS _http: //jeffhuang.com/best_paper_awards.html_ compilée par le professeur Huang.

Le regroupement spectral est un algorithme de regroupement élégant, connu sous le nom d' algorithme de coupes normalisées introduit par Jianbo Shi et Jitendra Malik pour la segmentation d'images. Il a également été bien développé dans les applications de clustering de données, constituant une bonne intersection entre les deux communautés.

Deux autres exemples de prédilection personnels bien ancrés dans l’informatique, mais que les théoriciens de l’abstraction ont peut-être facilement laissés de côté. Ils ont connu d’énormes progrès / transformations et ont eu un impact pratique / appliqué considérable à massif dans la vie quotidienne au cours des dernières décennies. déjà une génération entière a grandi sans connaître le monde sans eux. essentiellement la catégorie de la modélisation et de la simulation .

• algorithmes de simulation de physique . principalement en utilisant les lois de Newtons mais en utilisant d’autres lois (comme la dynamique des fluides). utilisé dans une grande variété d'applications allant des applications d'ingénierie aux jeux vidéo, et parfois aux films. Ceci est également responsable de l'amélioration significative de la sécurité, de l'efficacité ou de la fiabilité des voitures et des avions, par exemple, en soumettant les conceptions virtuelles / de test à des contraintes simulées. un important domaine de recherche connexe en cours de la bioinformatique avec des implications énormes en biologie, par exemple conception de médicaments, prévention des maladies, etc.: repliement des protéines / prévision de la structure . Notez également que cette année, le prix Nobel de chimie a été attribué à Karplus, Levitt, Warshel pour la simulation de la chimie . les algorithmes de simulation de physique sont fortement impliqués dans la sûreté / les essais d'armes nucléairespar exemple dans les laboratoires de Los Alamos.

• Raytracing / algorithmes CGI . Ce sujet de recherche a commencé il y a à peine quelques décennies [un ami a obtenu son diplôme de maîtrise en algorithmes de gravure de rayons en écriture CS], mais il est devenu très utilisé dans les jeux et l'industrie du cinéma, atteignant des niveaux extraordinaires de vraisemblance qui est à l'origine de nombreuses effets spéciaux dans les films. ces industries ont littéralement investi des milliards de dollars et misent sur ces algorithmes, et des grandes entreprises entières les exploitent, par exemple Pixar . Cette technique est maintenant tellement répandue qu’elle est utilisée couramment, même dans les films "typiques". par exemple récemment The Great Gatsby s’appuie beaucoup sur les effets CGI pour dessiner des environnements convaincants ou stylisés, retoucher le film / les personnages, etc.

Rosetta Code répertorie les algorithmes appliqués par tâche de programmation (692) et par langage de programmation (518) avec Semantic MediaWiki.

Peut-être que tous les principaux algorithmes / préférés d'intérêt pour ce public ont été mentionnés à ce stade. cependant, quelques autres méritent d'être mentionnés pour leur exhaustivité. & une analyse de ce qui est considéré comme un algorithme significatif est pertinente ici.

Dans les domaines de la CS & IT, il semble y avoir un phénomène observé il y a longtemps dans l'IA appelé "déplacer les poteaux de but" . Il s’agit d’un phénomène psychologique dans lequel le domaine progresse relativement rapidement mais où les gens s’adaptent rapidement à la «nouvelle normalité» et prennent des avancées réelles, voire révolutionnaires, comme banales ou non, rétrospectivement, après avoir accompli, c’est-à-dire minimisées ou minimisées. Cette question rend bien compte de la façon dont les algorithmes passent de la recherche et développement au "déploiement". citant l'auteur de la question dans des commentaires ultérieurs:

En fait, une fraction négligeable de tout le code écrit est la mise en œuvre de tout ce qui est intéressant d'un point de vue algorithmique.

mais ceci est problématique et constitue fondamentalement une redéfinition du mot "algorithme" centrée sur le TCS. vraisemblablement les algorithmes intéressants sont avancés. cela signifie-t-il que si un problème est réduit à un algorithme avancé, ce n'est plus "intéressant"? et "avancé" est clairement une cible en mouvement. il existe donc un moyen de définir les "algorithmes" de manière étroite ou large . il semble que la définition du TCS change en fonction du contexte, mais il convient de noter que même dans le TCS, il existe une tendance à la définition large, par exemple dans ce qu'on appelle "l'objectif algorithmique" .

Parfois, les algorithmes les plus répandus sont aussi les plus négligés! Internet et WWW constituent un vaste environnement / quasi-écologie pour les algorithmes. encore relativement jeune et âgé d’environ 2 décennies (inventé en 1991), il a connu une croissance massive et exponentielle en peu de temps. La croissance du site WWW a probablement même dépassé la célèbre loi exponentielle Moores.

Internet / WWW sont supportés par de nombreux algorithmes sophistiqués. Internet possède des algorithmes de routage complexes intégrés dans les routeurs (alimentant à nouveau des entreprises de plusieurs milliards de dollars, telles que Cisco). une théorie avancée y est applicable, par exemple dans les algorithmes de routage . ces algorithmes ont fait l’objet de recherches émergentes, avancées / à la pointe de la technologie il y a plusieurs décennies, mais ils sont maintenant tellement ajustés et bien compris que c’est un peu invisible.

il ne faut pas oublier de si tôt qu'il y a plusieurs décennies, des chercheurs renommés n'étaient même pas certains du fonctionnement ou de l'impossibilité du monde de l'internet (comme le montrent les premières recherches sur la commutation de paquets, un nouveau modèle de conception radicalement différent de celui qui existait auparavant), et Il y a quelques années encore, on craignait que le système échoue à un moment donné et commence à échouer en raison de pics de volume énormes.

il utilise également une détection / correction d'erreur sophistiquée . Internet est probablement le plus grand système, le plus tolérant aux pannes jamais construit par les humains, toujours en croissance.

Ensuite, il existe des arguments solides en faveur de l’avancée des algorithmes qui alimentent le WWW. Les serveurs HTTP et Web sont hautement optimisés et utilisent également des protocoles de sécurité / cryptage avancés (HTTPS). la logique de rendu d'une page Web est devenue extrêmement avancée en HTML5 et CSS3 , avec le Javascript langage de programmation .

Le CSS relativement nouveau repose sur divers principes similaires à ceux de la programmation orientée objet, tels que la réutilisabilité et l'héritage. en parlant de composition, TeX est un système de composition scientifique important, complexe en interne (pas si différent d’un langage de programmation) inventé par Knuth et qui peut maintenant être rendu sur des pages Web (et est utilisé dans des centaines de milliers d’articles scientifiques ou plus).

Un autre domaine relativement nouveau d’algorithmes reposant sur l’Internet et qui reposent toujours sur l’ intelligence collective . Le logiciel stackexchange lui-même est un exemple de système sophistiqué d’intelligence collective. les réseaux sociaux présentent également les caractéristiques clés de l'intelligence collective et des fonctionnalités sont ajoutées en permanence pour augmenter cette intelligence (par exemple, les "Likes" de Facebook ne datent que de quelques années). le domaine des systèmes de notation repose sur des algorithmes de filtrage collaboratif et continue d'évoluer en fonction de nouvelles recherches et applications.

Bref, tous les succès révolutionnaires transformant l'expérience humaine quotidienne vont bien au-delà des «objectifs de terrain». comme l'indique le titre de la question, tous les principaux algorithmes sont déployés . maintenant si omniprésent et invisible qu’il ressemble à l’expression «informatique», «une partie de la plomberie».

Un algorithme (matériel) étonnamment réussi est la réinitialisation à la mise sous tension.

Sans un système dans lequel un ordinateur est dans un état connu lors de la mise sous tension, rien d'autre ne se passe bien .

La réinitialisation à la mise sous tension explique pourquoi tout fonctionne avec un processeur, qu’il soit considéré intégré ou non.

La prochaine fois que vous rencontrerez des difficultés pour les programmeurs et les informaticiens, soulevez votre verre de soda à la réinitialisation à la mise sous tension.