# Le club des professionnels en informatique > Actualits >  Le Top 32 des algorithmes les plus importants au monde, lesquels comprenez-vous et utilisez-vous ?

## Katleen Erna

*Le Top 32 des algorithmes les plus importants au monde, lesquels comprenez-vous et utilisez-vous ?*

Un blogueur amricain a post un billet dans lequel il explique avoir essay avec ses collgues de rpertorier les algorithmes les plus importants au monde. Aprs un gros brainstorming, ces passionns ont tabli une liste de 32 entres. 

Leur critre ? Qu'il s'agisse d'algorithmes trs largement utiliss en informatique et en mathmatique.

Voici leur liste :




> *A* search algorithm* 
> Graph search algorithm that finds a path from a given initial node to a given goal node. It employs a heuristic estimate that ranks each node by an estimate of the best route that goes through that node. It visits the nodes in order of this heuristic estimate. The A* algorithm is therefore an example of best-first search.
> 
> *Beam Search* 
> Beam search is a search algorithm that is an optimization of best-first search. Like best-first search, it uses a heuristic function to evaluate the promise of each node it examines. Beam search, however, only unfolds the first m most promising nodes at each depth, where m is a fixed number, the beam width.
> 
> *Binary search* 
> Technique for finding a particular value in a linear array, by ruling out half of the data at each step.
> 
> ...


Source : http://www.risc.jku.at/people/ckouts...lgorithms.html   The Most Important Algorithms

 ::fleche::  Parmi ces algorithmes, lesquels connaissez-vous et lesquels utilisez-vous ?

 ::fleche::  Comprenez-vous tous ces algorithmes ?

 ::fleche::  Si vous aviez particip au brainstorming original, auriez-vous ajout une autre entre  cette liste ? Pourquoi ?

----------


## Shaoran

H ben ! Il m'en reste pas mal  dcouvrir  ::lol:: 

Je connais et matrise l'A*,Dijkstra, la mthode du Simplex , le tri -  fusion et que j'exploite essentiellement en cours et parfois dans des projets personnelles, ainsi que l'algorithme Union - Find et le calcul de Flot maximum que j'avais vu dans un bouquin ^^ (sans compter celui d'Euclide que j'ai appris au lyce).

Aprs je connais certains grand nom comme la transform de fourier utilis en rseaux il me semble (les sales souvenirs de matlab  utiliser a en cours sans savoir ce que c'est) et le RSA. Mais quand mme il y en a un paquet que je connais pas  ::calim2:: 

En revanche la programmation dynamique n'est pas un algorithme je vois pas ce que a fait dans cette liste, c'est une branche d'algorithme pas un algorithme proprement dit =/

----------


## Lordsephiroth

Ca rappelle pas mal de trucs vu en cours cette liste. Je pensais pas un jour tomber  nouveau sur ces termes que j'avais considr comme " oublier le lendemain de l'examen" (remarque... comme la plupart des choses que j'ai apprises  ::ccool:: ).

Y a quand mme quelques trucs marrants, genre : 




> In computational algebraic geometry and computational commutative algebra, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial ideal into a Grbner basis with respect to some monomial order. One can view it as a generalization of the Euclidean algorithm for univariate gcd computation and of Gaussian elimination for linear systems


Un seul mot  rpondre  a : WTF ?  ::mouarf::  ::mouarf::

----------


## bombseb

Dommage que a ne soit pas en franais, a a l'air intressant...

----------


## Floral

La plupart des algorithmes de compression sans lesquels mon 56k de l'poque serait encore entrain de m'envoyer des trucs.

----------


## amaury pouly

Bonjour,
cette liste me parait assez bizarre de par le statut des lments qui la composent. D'une part on a de vrais algorithmes (Dijkstra, drivation discrte, Karatsuba) et d'autres part on a des mthodes tellement gnrales que cela a peu de sens (programmation dynamique, compression).
On peut remarquer par ailleurs que la dernire entre (Viterbi) rentre dans la catgories de la programmation dynamique.
Bon j'arrte l de faire mon rabat-joie  ::aie:: 

Je connais bien la programmation dynamique, Karatsuba, Dijkstra, Ford-Fulkerson, le tri fusion et d'autres. Je connais la plupart au moins de noms mais a s'arrte l pour certains  ::roll::

----------


## befalimpertinent

Liste trs complte mais je suis surpris de ne pas trouver l'algorithme MinMax que je pensais trs utilis pour grer l'I.A dans les petits jeux simples. (Ou alors il s'appelle diffremment en anglais)

----------


## Bryce de Mouris

Effectivement on retrouve pas mal d'algorithmes vus en cours, personnellement je trouvais a trs intressant. Ca colle parfaitement  l'idologie du "partisan du moindre effort" de l'informatique. Des algos puissants, cls en mains et qui ont fait leurs preuves !

+1 pour le MinMax, trs utile dans les jeux  2 joueurs tour par tour (dmineur, chec, morpion...).

----------


## zoonel

tiens je vois pas les algos pour gnrer les nombres alatoires, ou alors ils considrent que c'est repris dans le tas, pourtant il y a bien un "data compression" .

----------


## TNT89

*Discrete differentiation*
C'est pas un algorithme!
 ::aie::

----------


## fezvez

Trs jolie liste, j'y retrouve plein de classiques.

J'mets les mmes objections que certains, mais il est vrai que a ressemble plus  la liste des "meilleures techniques pour calculer des choses rapidement"

Sinon, je connais de nom pas mal de trucs. Mais je dois avouer avoir dcouvert ces "algorithmes" en parcourant la liste : 

Buchberger's algorithm 
LLL algorithm 
Q-learning 
Quadratic sieve 
Schnhage-Strassen algorithm  (Je suis all faire un tour sur Wikipedia, c'est trs puissant!)
Strukturtensor

----------


## gael

Pour qu'il y ait un top, il faut qu'il y ait un ordre... rien de trs rigoureux, enfin a peut tre intressant. 

Peut-tre est-ce un problme de traduction mais je ne vois rien sur les rduction/dcomposition de matrice (LU, ...)

----------


## tomlev

Y a pas le Quicksort dans leur liste ??  :8O: 

C'est quand mme un des algos les plus connus et les plus utiliss au monde, certainement beaucoup plus que certains qui sont mentionns et que quasiment personne ne connait... Srieusement, combien de personnes ont dj entendu parler de "Karatsuba multiplication", et combien connaissent le Quicksort ? A mon avis y a pas photo...

----------


## freelibre

Tout  apprendre on se rend toujours compte avec votre flux Twitter qu'on a beaucoup  apprendre !!

En tout cas bonne continuation.

----------


## pseudocode

C'est assez disparate comme liste. "Binary search" et "LLL" c'est quand meme pas du mme niveau.  ::aie::

----------


## Nebulix

Gradient descent est un *trs mauvais* algorithme de minimisation ! ::aie:: 
Je doute que quiconque l'utilise vraiment.
Nelder-Mead ou Levenberg-Marquart sont bien meilleurs.

----------


## HAL-9000

*Expectation-maximization algorithm (EM-Training)*

Combien de fois j'ai pu utiliser ce dernier...  ::mouarf::

----------


## ToTo13

C'est absolument pas crdible, ni exhaustif !!!
Si on en croit leurs critres, il manque deux algorithmes incontournable d'imagerie :
 - Bresenham => utilis dans TOUTES les cartes graphiques. Donc plus utilis que a tu meurs.
 - Z-Buffer => utilis dans TOUTES les cartes graphiques.

----------


## wjhoo

tres jolie,
il me reste pas mal d'algorithme a voir.
 ::mouarf::

----------


## Invit

> Y a pas le Quicksort dans leur liste ?? 
> 
> C'est quand mme un des algos les plus connus et les plus utiliss au monde, certainement beaucoup plus que certains qui sont mentionns et que quasiment personne ne connait... Srieusement, combien de personnes ont dj entendu parler de "Karatsuba multiplication", et combien connaissent le Quicksort ? A mon avis y a pas photo...


Tout  fait d'accord !
QuickSort, recherche dichotomique, B-Trees sont  l'origine de tout le gnie logiciel associ aux bases de donnes. Mme s'il est possible qu'ils figurent ici sous un nom diffrent. Cette liste copie colle me semble srieusement inexhaustive. Son origine acadmique est douteuse dans une spcialit o les universits ne comptent que pour la moiti de la science. Le march les a souvent contredit notamment en France.

Pour ma part, j'entretiens une relation trs erotique avec la FFT que j'implmente ou exploite depuis 1991. A l'poque, l'algorithme tait vendu en dur avec la machine pour des sommes astronomiques !   
On ne parle de Fourrier (un franais) que pour l'analyse alors que cet algo est omniprsent dans la compression destructive de signal (mpeg 1,2,4, 1 layer 3,...) sous sa forme primitive la DCT (transforme en cosinus discrte) 

Des millions de DCT sont effectues chaque seconde en regardant le TNT par exemple - tant pour l'image que pour le son

----------


## BrunoIRM

Salut,

On retrouve les tartes  la crme du calcul numrique (FFT, Euclide, drive discrte, Newton ...).

Les poids lourds de la crypto et du codage (RSA, Hash-coding, ...)

Je rejoins l'avis de grand nombre d'entre-vous : certains "algo" prsents ne sont pas des algo mais plutt des domaines d'application (data compression, programmation dynamique, ...)

On aurait pu ajouter par exemple l'algorithme de code correcteur d'erreur de Reed-Salomon qui est particulirement utilis dans la lecture des CD Audio (le fait de lire sans erreur un CD ray au tampon Jex  :;): )

Dans dans le domaine plus calculatoire : les algo diffrences finie : euler, RK2/4, ...

Et bien sr Quicksort, le grand absent.

Mais bon, difficile de juger de l'intrt d'une telle liste au vu de la grande varit des domaines d'applications....

En tous cas, de sacrs souvenirs sur les bancs des facs  :;): 

B.

----------


## tomlev

> recherche dichotomique


Celui l il y est : Binary Search

----------


## damien.charpentier

> Y a pas le Quicksort dans leur liste ?? 
> 
> C'est quand mme un des algos les plus connus et les plus utiliss au monde, certainement beaucoup plus que certains qui sont mentionns et que quasiment personne ne connait... Srieusement, combien de personnes ont dj entendu parler de "Karatsuba multiplication", et combien connaissent le Quicksort ? A mon avis y a pas photo...


Peut-tre parce qu'il ressemble de loin au merge sort?  ::aie::  

Je n'ai pas vu d'algorithmes de recherche de texte dans la liste.

----------


## pvincent

Manifestement, le calcul numrique n'est pas leur point fort. 
La mthode de Gauss-Jordan est de nos jours considre comme avant tout pdagogique (la Netlib est base sur la dcomposition LU ou la SVD)
On sait que la diffrentiation discrte est source d'instabilits et on prfre le plus souvent transformer les quations diffrentielles en quation intgrales. Il est d'ailleurs surprenant de voir que les mthodes d'lments finis (FEM) si souvent utilises en modlisation ne sont pas dans cette liste.

----------


## PPGodOfLove

Je connais RSA (en bonne partie) et l'algorithme d'Euclide, sinon j'ignorais l'existence de quasiment tous les autres XD

----------


## cinemania

Il est vrai qu'on y trouve de tout et n'importe quoi et surtout des trucs qui ne sont pas ou peu utiliss, mme dans les domaines d'o ils dcoulent.
Ensuite c'est clair qu'ils ont visiblement confondu Algorithmes et Methodologie ou Modlisation, car effectivement Dynamic Programming n'a rien  faire dans cette liste vraiment trs light.

Mais pire, il n'y a pas de classement dans le sens du plus utilis au moins utilis, Djisktra est probablement le plus utilis sans que personne ne le sache vraiment, car il est  la base d'OSPF sans quoi vous pourriez dire adieu  internet, car plus de routage... 
D'ailleurs, il reste la rfrence en rseau, nettement plus que A* mme s'il est aussi trs utilis, puisqu'internet ce n'est jamais qu'un vaste Graphe  ::): 
Diffie-Hellman est utilis certes, mais pas tant que cela au regard des grands absents que sont Quick Sort ou d'autres algorithmes de tri rapides comme Heap Sort.

En ralit, leurs choix ne sont fonds sur rien si ce n'est peut-tre le nombre d'occurrences sur le net et notamment des algorithmes pas utiliss car mauvais mais qui justement ont fait normment couler d'encre...

En plus leur liste ne peut reflter que leur sensibilit  eux, dans la mesure o la sensibilit Europenne est toute autre,  et certains algorithmes notamment en dveloppement sont fortement utiliss aux usa et pas ici, et inversement, pour des raisons diverses et varies toutes meilleures les unes que les autres.

Il aurait t plus critique et cohrent de faire une liste par domaine d'application quitte  rduire le nombre d'algorithme par domaine, comme un top 10 de chaque, cette approche aurait t nettement plus crdible, et moins fourre tout, car l comme je le disais, on se demande vraiment sur quels faits, ou mmes quelles statistiques tangibles ils se fondent pour avancer leurs choix.

----------


## popo

Tout  fait d'accord avec la majorit.
On se demande d'o ils tiennent cette liste.

----------


## 3logy

> Il aurait t plus critique et cohrent de faire une liste par domaine d'application quitte  rduire le nombre d'algorithme par domaine, comme un top 10 de chaque, cette approche aurait t nettement plus crdible, et moins fourre tout, car l comme je le disais, on se demande vraiment sur quels faits, ou mmes qu'elles statistiques tangibles ils se fondent pour avancer leurs choix.


 ::ccool::  T'aurais une idee si un ranking pareil existe?

----------


## pvincent

Bien qu'il ne soit pas parfait (voir http://en.wikipedia.org/wiki/Numerical_Recipes) le livre "Numerical Recipes" (http://www.nr.com) donne une bonne base de dpart pour se lancer dans le calcul numrique. Ce qui ne gache rien, il est librement accessible sur le Net.

De toute faon, il est clair qu'aucun algorithme n'est universel et que la configuration des donnes joue un rle important dans l'efficacit d'un mthode particulire (lire le chapitre sur le tri dans Numerical Recipes).

----------


## danbo52

Bon, sans reprendre toutes les dmos des matheux gniaux, est-ce que par exemple, la transforme de Laplace est en soi un algorithme (dans le raisonnement).
Ceci me semble bizarre.
Ce type de classification veut tout et rien dire.
Peut-tre aurait-il t intressant pour les protagonistes de dfinir des branches d'utilisation et de dire quels sont les algorithmes les plus utiliss, du genre:
Mcanique, on a a , a et a
Physique.....
Chimie....
Informatique...
ou comme disent certains internautes ici, classer par pertinence en fonction d'un process, ex:
Pour les mini-maxi, on classe du plus pertinent au moins pertinent en comprenant bien ce que pertinent veut dire.

Bon, j'ai pas que a  faire, faut que j'aille faire une rduction de matrice pour un problme d'optimisation volumtrique de chargement de container avec des objets de formes bizarres (en gros,, j'ai des objets tordus, combien et comment je les mets dans mon container, pour optimiser les cots...)

----------


## Tellen

> Bon, j'ai pas que a  faire, faut que j'aille faire une rduction de matrice pour un problme d'optimisation volumtrique de chargement de container avec des objets de formes bizarres (en gros,, j'ai des objets tordus, combien et comment je les mets dans mon container, pour optimiser les cots...)
> 
> Bonne crbralisation  tous.


En fait tu joues  Tetris 3D ?  ::aie::   ::lol::

----------


## danbo52

> En fait tu joues  Tetris 3D ?


euh! pas aujourd'hui, c'est du vrai de vrai c'que j'ai  faire !

"Il n'y a pas que des imbciles dans la sphre intellectuelle, il y a aussi des jambons, du bal musette et des gens honntes!"

----------


## Tonioyo

En fait il s'agit des algorithmes mathmatiques appliqus  l'informatique et pas des algorithmes au sens large. Je trouve aussi dommage qu'il n'y ait pas de classement.

----------


## Tellen

> euh! pas aujourd'hui, c'est du vrai de vrai c'que j'ai  faire !


Je me doute bien c'etait juste une plaisanterie car la description de ce que tu faisais m'a fait penser  Tetris.

----------


## Rams7s

> En fait tu joues  Tetris 3D ?


 ::ccool:: 

C'est plus rigolo de le dire comme a que de dire le problme des sacs  dos. Je te volerai ta phrase  l'occasion  ::D:

----------


## niocnioc

trop bidon leur liste y a meme pas le nom de don knuth dedans...

 la limite ils auraient pu mettre des algos que tout le monde utilise sans s'en rendre compte, comme bresenham en informatique graphique ou tous les algos de la theorie des graphes comme djikstra, prim, kruskal & co sans lesquels on aurait pas internet.

----------


## amaury pouly

> trop bidon leur liste y a mme pas le nom de don knuth dedans...
> 
>  la limite ils auraient pu mettre des algos que tout le monde utilise sans s'en rendre compte, comme bresenham en informatique graphique ou tous les algos de la thorie des graphes comme djikstra, prim, kruskal & co sans lesquels on aurait pas internet.


Quelle critique constructive !

D'une faon gnrale je ne pense pas que parler des algorithmes les plus utiliss ait un sens puisque cela dpend de ce qu'on appelle "utilis". Certes Brensmann est utilis dans toutes les cartes graphiques mais c'est aussi parce que c'est un algorithme simple facilement implmentable en hardware. Certes Dijkstra est utilis dans les rseau mais c'est parce qu'il est simple et trivial  implmeter en distribu.

Je ne pense pas qu'un critre objectif soit pertinent pour un classement mais ce n'est pas non plus une raison pour y mettre n'importe quoi  ::aie::

----------


## geforce

Bonjour a tous, 
Quelqu'un aurai des liens simple et parasitique pour l'algorithme du Branch and bound ? (ou des exemple dj fait)
Merci
PS: idalement en fr.

----------

