IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Expert éminent sénior
    Avatar de Katleen Erna
    Profil pro
    Inscrit en
    juillet 2009
    Messages
    1 547
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : juillet 2009
    Messages : 1 547
    Points : 75 992
    Points
    75 992
    Par défaut Le Top 32 des algorithmes les plus importants au monde, lesquels comprenez-vous et utilisez-vous ?
    Le Top 32 des algorithmes les plus importants au monde, lesquels comprenez-vous et utilisez-vous ?

    Un blogueur américain a posté un billet dans lequel il explique avoir essayé avec ses collègues de répertorier les algorithmes les plus importants au monde. Après un gros brainstorming, ces passionnés ont établi une liste de 32 entrées.

    Leur critère ? Qu'il s'agisse d'algorithmes très largement utilisés en informatique et en mathématique.

    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.

    Branch and bound
    A general algorithmic method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization.

    Buchberger's algorithm
    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 Gröbner 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.

    Data compression
    Data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes.

    Diffie-Hellman key exchange
    Cryptographic protocol which allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

    Dijkstra's algorithm
    Algorithm that solves the single-source shortest path problem for a directed graph with nonnegative edge weights.

    Discrete differentiation
    I.e., the formula f'(x) = (f(x+h) - f(x-h)) / 2h.

    Dynamic programming
    Dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below.

    Euclidean algorithm
    Algorithm to determine the greatest common divisor (gcd) of two integers. It is one of the oldest algorithms known, since it appeared in Euclid's Elements around 300 BC. The algorithm does not require factoring the two integers.

    Expectation-maximization algorithm (EM-Training)
    In statistical computing, an expectation-maximization (EM) algorithm is an algorithm for finding maximum likelihood estimates of parameters in probabilistic models, where the model depends on unobserved latent variables. EM alternates between performing an expectation step, which computes the expected value of the latent variables, and a maximization step, which computes the maximum likelihood estimates of the parameters given the data and setting the latent variables to their expectation.

    Fast Fourier transform (FFT)
    Efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. FFTs are of great importance to a wide variety of applications, from digital signal processing to solving partial differential equations to algorithms for quickly multiplying large integers.

    Gradient descent
    Gradient descent is an optimization algorithm that approaches a local minimum of a function by taking steps proportional to the negative of the gradient (or the approximate gradient) of the function at the current point. If instead one takes steps proportional to the gradient, one approaches a local maximum of that function; the procedure is then known as gradient ascent.

    Hashing
    A function for summarizing or probabilistically identifying data. Typically this means one applies a mathematical formula to the data, producing a string which is probably more or less unique to that data. The string is much shorter than the original data, but can be used to uniquely identify it.

    Heaps (heap sort)
    In computer science a heap is a specialized tree-based data structure. Heaps are favourite data structures for many applications: Heap sort, selection algorithms (finding the min, max or both of them, median or even any kth element in sublinear time), graph algorithms.

    Karatsuba multiplication
    For systems that need to multiply numbers in the range of several thousand digits, such as computer algebra systems and bignum libraries, long multiplication is too slow. These systems employ Karatsuba multiplication, which was discovered in 1962.

    LLL algorithm
    The Lenstra-Lenstra-Lovasz lattice reduction (LLL) algorithm is an algorithm which, given a lattice basis as input, outputs a basis with short, nearly orthogonal vectors. The LLL algorithm has found numerous applications in cryptanalysis of public-key encryption schemes: knapsack cryptosystems, RSA with particular settings, and so forth.

    Maximum flow
    The maximum flow problem is finding a legal flow through a flow network that is maximal. Sometimes it is defined as finding the value of such a flow. The maximum flow problem can be seen as special case of more complex network flow problems. The maximal flow is related to the cuts in a network by the Max-flow min-cut theorem. The Ford-Fulkerson algorithm computes the maximum flow in a flow network.

    Merge sort
    A sorting algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e.g. file streams) into a specified order.

    Newton's method
    Efficient algorithm for finding approximations to the zeros (or roots) of a real-valued function. Newton's method is also a well-known algorithm for finding roots of equations in one or more dimensions. It can also be used to find local maxima and local minima of functions.

    Q-learning
    Q-learning is a reinforcement learning technique that works by learning an action-value function that gives the expected utility of taking a given action in a given state and following a fixed policy thereafter. A strength with Q-learning is that it is able to compare the expected utility of the available actions without requiring a model of the environment.

    Quadratic sieve
    The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the number field sieve, NFS). It is still the fastest for integers under 110 decimal digits or so, and is considerably simpler than the number field sieve.

    RANSAC
    RANSAC is an abbreviation for "RANdom SAmple Consensus". It is an algorithm to estimate parameters of a mathematical model from a set of observed data which contains "outliers". A basic assumption is that the data consists of "inliers", i. e., data points which can be explained by some set of model parameters, and "outliers" which are data points that do not fit the model.

    RSA
    Algorithm for public-key encryption. It was the first algorithm known to be suitable for signing as well as encryption. RSA is still widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys.

    Schönhage-Strassen algorithm
    In mathematics, the Schönhage-Strassen algorithm is an asymptotically fast method for multiplication of large integer numbers. The run-time is O(N log(N) log(log(N))). The algorithm uses Fast Fourier Transforms in rings.

    Simplex algorithm
    In mathematical optimization theory, the simplex algorithm a popular technique for numerical solution of the linear programming problem. A linear programming problem consists of a collection of linear inequalities on a number of real variables and a fixed linear functional which is to be maximized (or minimized).

    Singular value decomposition (SVD)
    In linear algebra, SVD is an important factorization of a rectangular real or complex matrix, with several applications in signal processing and statistics, e.g., computing the pseudoinverse of a matrix (to solve the least squares problem), solving overdetermined linear systems, matrix approximation, numerical weather prediction.

    Solving a system of linear equations
    Systems of linear equations belong to the oldest problems in mathematics and they have many applications, such as in digital signal processing, estimation, forecasting and generally in linear programming and in the approximation of non-linear problems in numerical analysis. An efficient way to solve systems of linear equations is given by the Gauss-Jordan elimination or by the Cholesky decomposition.

    Strukturtensor
    In pattern recognition: Computes a measure for every pixel which tells you if this pixel is located in a homogenous region, if it belongs to an edge, or if it is a vertex.

    Union-find
    Given a set of elements, it is often useful to partition them into a number of separate, nonoverlapping groups. A disjoint-set data structure is a data structure that keeps track of such a partitioning. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:
    Find: Determine which group a particular element is in.
    Union: Combine or merge two groups into a single group.

    Viterbi algorithm
    Dynamic programming algorithm for finding the most likely sequence of hidden states - known as the Viterbi path - that result in a sequence of observed events, especially in the context of hidden Markov models.
    Source : http://www.risc.jku.at/people/ckouts...lgorithms.html The Most Important Algorithms

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

    Comprenez-vous tous ces algorithmes ?

    Si vous aviez participé au brainstorming original, auriez-vous ajouté une autre entrée à cette liste ? Pourquoi ?

  2. #2
    Membre à l'essai
    Profil pro
    Étudiant
    Inscrit en
    janvier 2009
    Messages
    8
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2009
    Messages : 8
    Points : 16
    Points
    16
    Par défaut
    Hé ben ! Il m'en reste pas mal à découvrir

    Je connais et maîtrise l'A*,Dijkstra, la méthode 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 lycée).

    Après je connais certains grand nom comme la transformé de fourier utilisé en réseaux il me semble (les sales souvenirs de matlab à utiliser ça en cours sans savoir ce que c'est) et le RSA. Mais quand même il y en a un paquet que je connais pas

    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 =/

  3. #3
    Membre confirmé Avatar de Lordsephiroth
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mai 2006
    Messages
    199
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : mai 2006
    Messages : 199
    Points : 492
    Points
    492
    Par défaut
    Ca rappelle pas mal de trucs vu en cours cette liste. Je pensais pas un jour tomber à nouveau sur ces termes que j'avais considéré comme "à oublier le lendemain de l'examen" (remarque... comme la plupart des choses que j'ai apprises ).

    Y a quand même 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 Gröbner 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 à répondre à ça : WTF ?
    Always code as if the guy maintaining your application is a violent psychopath!
    Site personnel sur la saga Final Fantasy : http://www.final-fantasy.ch

  4. #4
    Membre expérimenté
    Profil pro
    Inscrit en
    juillet 2005
    Messages
    661
    Détails du profil
    Informations personnelles :
    Localisation : Réunion

    Informations forums :
    Inscription : juillet 2005
    Messages : 661
    Points : 1 500
    Points
    1 500
    Par défaut
    Dommage que ça ne soit pas en français, ça a l'air intéressant...

  5. #5
    Membre éclairé
    Avatar de Floréal
    Profil pro
    Inscrit en
    novembre 2004
    Messages
    456
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations forums :
    Inscription : novembre 2004
    Messages : 456
    Points : 833
    Points
    833
    Par défaut
    La plupart des algorithmes de compression sans lesquels mon 56k de l'époque serait encore entrain de m'envoyer des trucs.
    Ancien membre du projet "Le Dernier Âge".

  6. #6
    Membre actif Avatar de amaury pouly
    Profil pro
    Inscrit en
    décembre 2002
    Messages
    157
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations forums :
    Inscription : décembre 2002
    Messages : 157
    Points : 219
    Points
    219
    Par défaut
    Bonjour,
    cette liste me parait assez bizarre de par le statut des éléments qui la composent. D'une part on a de vrais algorithmes (Dijkstra, dérivation discrète, Karatsuba) et d'autres part on a des méthodes tellement générales que cela a peu de sens (programmation dynamique, compression).
    On peut remarquer par ailleurs que la dernière entrée (Viterbi) rentre dans la catégories de la programmation dynamique.
    Bon j'arrête là de faire mon rabat-joie

    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'arrête là pour certains

  7. #7
    Membre éclairé Avatar de befalimpertinent
    Profil pro
    Inscrit en
    avril 2007
    Messages
    561
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : France, Gironde (Aquitaine)

    Informations forums :
    Inscription : avril 2007
    Messages : 561
    Points : 831
    Points
    831
    Par défaut
    Liste très complète mais je suis surpris de ne pas trouver l'algorithme MinMax que je pensais très utilisé pour gérer l'I.A dans les petits jeux simples. (Ou alors il s'appelle différemment en anglais)
    Linux > *

  8. #8
    Membre confirmé Avatar de Bryce de Mouriès
    Profil pro
    CPI
    Inscrit en
    mars 2007
    Messages
    216
    Détails du profil
    Informations personnelles :
    Âge : 34
    Localisation : France, Hauts de Seine (Île de France)

    Informations professionnelles :
    Activité : CPI

    Informations forums :
    Inscription : mars 2007
    Messages : 216
    Points : 540
    Points
    540
    Par défaut
    Effectivement on retrouve pas mal d'algorithmes vus en cours, personnellement je trouvais ça très intéressant. Ca colle parfaitement à l'idéologie du "partisan du moindre effort" de l'informatique. Des algos puissants, clés en mains et qui ont fait leurs preuves !

    +1 pour le MinMax, très utile dans les jeux à 2 joueurs tour par tour (démineur, échec, morpion...).
    Infinity - To The Top, shoot'em up développé en Haxe / OpenFL pour FLASH et Android, piou piou rythmé dans l'espace

  9. #9
    Membre actif
    Profil pro
    Inscrit en
    février 2005
    Messages
    55
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : février 2005
    Messages : 55
    Points : 208
    Points
    208
    Par défaut
    tiens je vois pas les algos pour générer les nombres aléatoires, ou alors ils considèrent que c'est repris dans le tas, pourtant il y a bien un "data compression" .

  10. #10
    Membre confirmé Avatar de TNT89
    Inscrit en
    juillet 2007
    Messages
    358
    Détails du profil
    Informations personnelles :
    Âge : 31

    Informations forums :
    Inscription : juillet 2007
    Messages : 358
    Points : 611
    Points
    611
    Par défaut
    Discrete differentiation
    C'est pas un algorithme!

  11. #11
    Nouveau membre du Club
    Inscrit en
    avril 2008
    Messages
    20
    Détails du profil
    Informations forums :
    Inscription : avril 2008
    Messages : 20
    Points : 35
    Points
    35
    Par défaut
    Très jolie liste, j'y retrouve plein de classiques.

    J'émets les mêmes 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 découvert ces "algorithmes" en parcourant la liste :

    Buchberger's algorithm
    LLL algorithm
    Q-learning
    Quadratic sieve
    Schönhage-Strassen algorithm (Je suis allé faire un tour sur Wikipedia, c'est très puissant!)
    Strukturtensor

  12. #12
    Membre habitué
    Profil pro
    Inscrit en
    novembre 2002
    Messages
    220
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : novembre 2002
    Messages : 220
    Points : 167
    Points
    167
    Par défaut
    Pour qu'il y ait un top, il faut qu'il y ait un ordre... rien de très rigoureux, enfin ça peut être intéressant.

    Peut-être est-ce un problème de traduction mais je ne vois rien sur les réduction/décomposition de matrice (LU, ...)

  13. #13
    Rédacteur/Modérateur


    Homme Profil pro
    Développeur .NET
    Inscrit en
    février 2004
    Messages
    19 875
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : février 2004
    Messages : 19 875
    Points : 39 737
    Points
    39 737
    Par défaut
    Y a pas le Quicksort dans leur liste ??

    C'est quand même un des algos les plus connus et les plus utilisés au monde, certainement beaucoup plus que certains qui sont mentionnés et que quasiment personne ne connait... Sérieusement, combien de personnes ont déjà entendu parler de "Karatsuba multiplication", et combien connaissent le Quicksort ? A mon avis y a pas photo...

  14. #14
    Membre régulier Avatar de freelibre
    Profil pro
    Inscrit en
    février 2005
    Messages
    68
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : février 2005
    Messages : 68
    Points : 76
    Points
    76
    Par défaut Une grande lecon
    Tout à apprendre on se rend toujours compte avec votre flux Twitter qu'on a beaucoup à apprendre !!

    En tout cas bonne continuation.
    Le Partage est notre Force !

  15. #15
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 062
    Points : 15 892
    Points
    15 892
    Par défaut
    C'est assez disparate comme liste. "Binary search" et "LLL" c'est quand meme pas du même niveau.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  16. #16
    Membre expérimenté
    Profil pro
    chercheur
    Inscrit en
    avril 2004
    Messages
    828
    Détails du profil
    Informations personnelles :
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : chercheur

    Informations forums :
    Inscription : avril 2004
    Messages : 828
    Points : 1 380
    Points
    1 380
    Par défaut Gradient descent est un très mauvais algorithme de minimisation
    Gradient descent est un très mauvais algorithme de minimisation !
    Je doute que quiconque l'utilise vraiment.
    Nelder-Mead ou Levenberg-Marquart sont bien meilleurs.
    Ce qui s'énonce clairement se conçoit bien ( Le hautbois)

  17. #17
    Membre habitué
    Profil pro
    Inscrit en
    novembre 2009
    Messages
    134
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : novembre 2009
    Messages : 134
    Points : 129
    Points
    129
    Par défaut
    Expectation-maximization algorithm (EM-Training)

    Combien de fois j'ai pu utiliser ce dernier...
    Au taf : Quad Core/8Go de RAM sous Win Seven 64 - Matlab 2009b 64bit.
    Perso : Core 2 Duo/8Go de RAM Mac OS X 10.6 - Matlab 2009b 64bit

  18. #18
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    janvier 2006
    Messages
    5 791
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 791
    Points : 9 857
    Points
    9 857
    Par défaut
    C'est absolument pas crédible, ni exhaustif !!!
    Si on en croit leurs critères, 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.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  19. #19
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    juin 2009
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : juin 2009
    Messages : 1
    Points : 3
    Points
    3
    Par défaut
    tres jolie,
    il me reste pas mal d'algorithme a voir.

  20. #20
    Invité
    Invité(e)
    Par défaut
    Citation Envoyé par tomlev Voir le message
    Y a pas le Quicksort dans leur liste ??

    C'est quand même un des algos les plus connus et les plus utilisés au monde, certainement beaucoup plus que certains qui sont mentionnés et que quasiment personne ne connait... Sérieusement, combien de personnes ont déjà 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 génie logiciel associé aux bases de données. Même s'il est possible qu'ils figurent ici sous un nom différent. Cette liste copiée collée me semble sérieusement inexhaustive. Son origine académique est douteuse dans une spécialité où les universités 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 très erotique avec la FFT que j'implémente 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 français) que pour l'analyse alors que cet algo est omniprésent dans la compression destructive de signal (mpeg 1,2,4, 1 layer 3,...) sous sa forme primitive la DCT (transformée en cosinus discrète)

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

Discussions similaires

  1. Réponses: 10
    Dernier message: 17/09/2014, 22h30
  2. Réponses: 25
    Dernier message: 11/12/2013, 09h22
  3. Réponses: 8
    Dernier message: 25/06/2013, 00h22
  4. top 10 des requêtes les plus longues
    Par cseguino dans le forum Administration
    Réponses: 1
    Dernier message: 10/02/2010, 09h46
  5. Réponses: 9
    Dernier message: 30/01/2007, 17h03

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo