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

Algorithmes et structures de données Discussion :

Des chercheurs du MIT créent KLOS, un algorithme puissant de parcours de graphe non orienté


Sujet :

Algorithmes et structures de données

  1. #1
    Expert éminent sénior

    Homme Profil pro
    Administrateur systèmes et réseaux
    Inscrit en
    mars 2013
    Messages
    426
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Cameroun

    Informations professionnelles :
    Activité : Administrateur systèmes et réseaux
    Secteur : Enseignement

    Informations forums :
    Inscription : mars 2013
    Messages : 426
    Points : 32 558
    Points
    32 558
    Par défaut Des chercheurs du MIT créent KLOS, un algorithme puissant de parcours de graphe non orienté
    Des chercheurs du MIT créent KLOS, un algorithme puissant de parcours de graphe non orienté
    plus performant que les algorithmes de flots maximum connus

    Qu’est ce qu’un graphe ? Des points et des lignes. En tout cas, c’est la réponse que donnerait n’importe quel profane s’il était mis en présence de cette structure simple, mais puissante, dont les applications tant en génétique qu’en informatique sont légions.

    La méthode de compression des fichiers au format Zip créée par l’américain David Huffman en 1952 est une application de la théorie des graphes. On peut également citer l’algorithme de recherche du plus court chemin proposé par le néerlandais Edgser Dijkstra, algorithme très employé dans le domaine des réseaux informatiques, où son utilité permet aux routeurs de déterminer le plus court chemin que doit emprunter un paquet pour atteindre sa destination.

    Les graphes sont omniprésents en informatique. Leur origine est associée aux travaux du mathématicien Leonhard Euler en 1736, mais ils sont cependant très discrets. Combien sont-ils au courant de leur existence, alors qu’ils sont quotidiennement employés ?

    Il n’est donc pas surprenant que le tout nouvel algorithme des chercheurs du MIT n’attire lui non plus l’attention, autant que le ferait la sortie d’un tout nouveau smartphone comme l’iPhone 5s par exemple.

    Les travaux des chercheurs du MIT ont en effet porté sur la création d’un nouvel algorithme de parcours de graphe, dont l’évolution est quasi linéaire. Ils l’ont sobrement baptisé « KLOS algorithm », en l’honneur des chercheurs qui lui ont donné naissance (Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia et Aaron Sidford).

    KLOS est présenté comme l’algorithme de parcours de graphe le plus abouti à l’heure actuelle. Il serait plus performant que les algorithmes de flot maximum (max flot) connus. KLOS sera présenté au cours du symposium sur les algorithmes discrets qui se tiendra à portland cette semaine.

    Existe-t-il déjà des bibliothèques d’implémentation de KLOS ? Aucune à l’heure actuelle. Les développeurs sont appelés à être patients, car ça ne saurait tarder.

    Source: Rapport de recherche PDF

    Et vous ?

    Attendez-vous avec impatience des bibliothèques d'implémentation de KLOS ?

  2. #2
    Membre actif
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2009
    Messages
    389
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2009
    Messages : 389
    Points : 234
    Points
    234
    Par défaut
    Attendez-vous avec impatience des bibliothèques d'implémentation de KLOS ?
    Attendre peut etre pas, je vais surtout remonter mes manches et implémenter ceci dans l'API Graphstream

  3. #3
    Membre confirmé Avatar de KsassPeuk
    Homme Profil pro
    Post-Doctorant
    Inscrit en
    juillet 2013
    Messages
    127
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Post-Doctorant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : juillet 2013
    Messages : 127
    Points : 544
    Points
    544
    Par défaut
    L'important ici n'est clairement pas le parcours mais le flot maximum, or on a l'impression que c'est le parcours qui nous intéresse ici. Avec une structure de donnée basique, on peut déjà faire du linéaire en (n+m) pour le parcours.

  4. #4
    Expert confirmé
    Avatar de GLDavid
    Homme Profil pro
    Team & Project Manager
    Inscrit en
    janvier 2003
    Messages
    2 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Team & Project Manager
    Secteur : Industrie Pharmaceutique

    Informations forums :
    Inscription : janvier 2003
    Messages : 2 793
    Points : 4 356
    Points
    4 356
    Par défaut
    Bonjour

    Je vois déjà une bonne implémentation de ces différents algorithmes dans mon domaine: la bioinformatique.
    Savez-vous ce qu'est l'interactomique ? Il s'agit de la science d'étude des interactions entre les différentes protéines et les métabolites. Cette science utilise donc des graphes pour retranscrire le réseau d'interactions. Ces réseaux sont importants afin d'étudier toute la voie de signalisation d'une cellule, ce qui explique notamment des processus de pathologie comme le cancer. Mais également de mettre en évidence des voies de thérapies sur des cibles clairement identifiées par ce biais.
    Ce qui émerge c'est l'inférence de réseaux: si une protéine est normalement produite, quel est l'impact dans la cascade des évènement si je la surexprime ? Ou si je la sous-exprime ?
    Evidemment, des initiatives existent déjà pour encoder ces réseaux (XML et HUPO-PSI-MI notamment, plus RDF). Pour le jeu d'algorithmes comme la recherche de voisins ou le plus court chemoin, tout cela est intéressant pour gagner en performances.

    A voir donc dans ce domaine.

    @++
    GLDavid
    Consultez la FAQ Perl ainsi que mes cours de Perl.
    N'oubliez pas les balises code ni le tag

    Je ne répond à aucune question technique par MP.

  5. #5
    Invité
    Invité(e)
    Par défaut
    Peut-être une question stupide mais je me lance

    A fortiori, KLOS devrait être applicable à des graphes orientés ?

    Steph

  6. #6
    Membre éclairé Avatar de srvremi
    Homme Profil pro
    Directeur d'école d'ingénieurs
    Inscrit en
    mars 2002
    Messages
    554
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Directeur d'école d'ingénieurs
    Secteur : Enseignement

    Informations forums :
    Inscription : mars 2002
    Messages : 554
    Points : 656
    Points
    656
    Par défaut
    Pour mes cours j'ai hâte de voir si ce sera implémentable par des élèves de niveau bac +3/+4.

    @+
    Rémi

  7. #7
    Membre averti
    Avatar de if_zen
    Homme Profil pro
    Développeur Java
    Inscrit en
    juin 2004
    Messages
    275
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Puy de Dôme (Auvergne)

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

    Informations forums :
    Inscription : juin 2004
    Messages : 275
    Points : 316
    Points
    316
    Par défaut
    Petite question : est-ce que ce genre d'algorithme pourrait simplifier et améliorer les performances et résultats de l'algorithme du "voyageur de commerce" (cf. Wikipedia, ne pas confondre avec Dijkstra) consistant à trouver le plus court chemin sur un ensemble d'étapes pré-établi ?

  8. #8
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    mars 2012
    Messages
    10
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2012
    Messages : 10
    Points : 21
    Points
    21
    Par défaut
    @if_zen je me posais la même question. De très bon algorithmes pour résoudre ce problème se basent sur les algos de flots, donc j'aurais tendance à dire qu'il y aura des répercussions sur pas mal de problèmes de ce genre ...

    wait & see

  9. #9
    Membre expérimenté
    Avatar de Patriarch24
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    septembre 2003
    Messages
    1 047
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France

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

    Informations forums :
    Inscription : septembre 2003
    Messages : 1 047
    Points : 1 633
    Points
    1 633
    Par défaut
    J'ai jeté un œil au papier, mais malheureusement mes compétences en mathématiques sont loin derrière moi et cela m'empêche de comprendre le tout (si tant est que mes compétences passées fussent suffisantes). Il faut être au point en algèbre...
    En premier lieu, utilisez un moteur de recherche.
    En second lieu, postez sur le forum adéquat !

  10. #10
    Membre éclairé
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    mars 2011
    Messages
    222
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mars 2011
    Messages : 222
    Points : 763
    Points
    763
    Par défaut
    Petite précision sur le nom "KLOS": ce ne sont pas les auteurs qui ont nommés cet algorithme KLOS, ils ne lui ont pas donné de nom (y aurait-il une raison de le faire d'ailleurs?). Alors c'est tout simplement nous tous qui utilisons KLOS par simplicité.

    J'ai vaguement parcouru l’article ce week-end, j'ai été assez vite dépassé, je pense qu'il faut déjà connaître un peu les travaux antérieurs, en tout cas le vocabulaire, pour suivre.

    Ils expliquent dans l’introduction qu'il s'agit d'une amélioration des algorithmes existant, leur permettant d'atteindre pour la première fois une complexité "quasi-linéaire" pour une résolution approchée du problème.

    Le problème en question est un problème d'optimisation, celui du flot maximum: dans le graphe il y a une source et un puits et il s'agit de trouver comment répartir l'utilisation des arrêtes (chacune ayant sa limite de capacité) pour obtenir un flot maximum qui part de la source pour tomber dans le puits.

  11. #11
    Membre habitué Avatar de Teto45
    Profil pro
    Inscrit en
    juillet 2009
    Messages
    145
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : juillet 2009
    Messages : 145
    Points : 145
    Points
    145
    Par défaut
    Citation Envoyé par Cedric Chevalier Voir le message
    ... Les développeurs sont appelés à être patients, car ça ne saurait tarder.
    Heu... cette phrase a comme un problème... Pourquoi être patient si l'implémentation ne saurait tarder ?

  12. #12
    Expert confirmé
    Inscrit en
    avril 2008
    Messages
    2 545
    Détails du profil
    Informations personnelles :
    Âge : 62

    Informations forums :
    Inscription : avril 2008
    Messages : 2 545
    Points : 4 351
    Points
    4 351
    Par défaut
    bonjour

    KLOS sera présenté au cours du symposium sur les algorithmes discrets qui se tiendra à portland cette semaine.
    Pourquoi presentent -t-ils seulement l'application du Laplacien d'un graphe (matrice associe à un graphe voir wiki fr) au probleme de Flot Max ramene à un probleme Kirchoff(loix des noeuds et des mailles) + contraintes sur les capacites des arcs
    Le theoreme de Kirchoff calcule l'ecoulement max des flots "naturels" de fluides ou de courants electriques dans les reseaux.(sans contraintes sur capacites)...Les contraintes sur capacites compliquent serieusement le probleme de Kirchoff dans les modeles pratiques

    Le comportement physique naturel des reseaux est tel que l'equiblibre s'etablit au max de flot transmissible....

    L'amelioration attendu de cet algo KLOS dans le cas du MaxFlot ,est que le MaxFlot existant calcule un chemin augmentant à la fois ,l'un apres l'autre,ce qui prend trop de temps pour un reseau ou il peut y avoir des millions de noeuds à traiter ...
    Le nouvel algo utilise le Laplacien du graphe pour resoudre un probleme de Kirchoff ...
    Comme un probleme de Kirchoff est un systeme d'equations lineaires ,la methode iterative du gradient conjuque est utilise avec calcul simultane sur tous les chemins augmentants possibles ....Hic:une methode iterative est approximante....d'ou le titre

    Voir ce lien de (Algorithmic Primitives for Network Analysis:
    Through the Lens of the Laplacian Paradigm):
    http://www.google.fr/url?q=http://ww...RJpEfjdq727wew

    Ensuite ce lien plus instructif sur le home page de l'un des auteurs de "KLOSS" Aleksander Madry ou il livre une serie de pdf sur ses recherches :max flow,voyageur du commerce et spanning traites par des methodes algebriques...http://www.google.fr/url?q=http://th...HcrAq5kW8DRcFg

    Ce qui intrigue : l'utilisation de cette methode algebrique est limite au flot max à la presentation de portland...

    Vpici un papier de 2 gourous de Microsoft Research Center bien detaille sur ce lien pour ceux desireux de s'informer :
    http://www.google.fr/url?q=http://research.microsoft.com/en-us/um/people/nvishno/site/Lxb-Web.pdf&sa=U&ei=jefeUt2UBvT3ygOorYD4DA&ved=0CCMQFjAA&usg=AFQjCNFRbmJD6qjyGoVBn498UUJcrr4w



    bonne lecture........

Discussions similaires

  1. Des chercheurs du MIT testent le programme probabiliste Picture
    Par Olivier Famien dans le forum Langages de programmation
    Réponses: 8
    Dernier message: 04/05/2015, 10h19
  2. Des chercheurs du MIT mettent au point un algorithme pour détecter les erreurs du type débordements d'entier
    Par Stéphane le calme dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 01/04/2015, 14h11
  3. Des chercheurs de l’Illinois créent une microbatterie révolutionnaire
    Par Cedric Chevalier dans le forum Actualités
    Réponses: 12
    Dernier message: 27/04/2013, 19h21
  4. Des chercheurs du NCSU créent des fils électriques étirables
    Par Hinault Romaric dans le forum Actualités
    Réponses: 17
    Dernier message: 23/03/2013, 05h43
  5. Réponses: 9
    Dernier message: 14/08/2012, 17h38

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