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
    Membre confirmé

    Profil pro
    Inscrit en
    octobre 2009
    Messages
    104
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : octobre 2009
    Messages : 104
    Points : 614
    Points
    614

    Par défaut Résolution de problèmes de sac à dos par méta-programmation

    Bonjour,

    Je vous propose un nouvel article sur la résolution de problèmes de sac à dos à la compilation en utilisant des techniques de méta-programmation.

    Le synopsis est le suivant :
    Le problème du sac à dos est un problème d'optimisation combinatoire NP-difficile, ce qui signifie que nous ne connaissons pas d'algorithme polynomial permettant de le résoudre. Cependant, il existe en pratique des algorithmes donnant de très bons résultats.
    Nous nous intéressons dans cet article au comportement d'un compilateur face à la résolution d'un tel problème. Pour cela, nous implémentons deux algorithmes en n'utilisant que des techniques de méta-programmation. En pratique, cela signifie que nous allons écrire les données du problème dans le code, puis que nous laisserons au compilateur le soin de sa résolution.
    La première partie de cet article introduit le problème. Elle est suivie par la deuxième section dans laquelle un algorithme naïf ainsi qu'une technique de programmation dynamique sont décrits et implémentés de manière classique. La troisième section présente des techniques de méta-programmation et montre ensuite les patrons de classe permettant la résolution lors de la compilation en utilisant l'un des deux algorithmes. Enfin, la dernière partie concerne la comparaison des performances obtenues avec chacune des ces approches.
    N'hésitez pas à laisser vos remarques et suggestions dans ce fil de discussion.

    Merci

  2. #2
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    Consultant informatique
    Inscrit en
    octobre 2004
    Messages
    10 896
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Belgique

    Informations professionnelles :
    Activité : Consultant informatique

    Informations forums :
    Inscription : octobre 2004
    Messages : 10 896
    Points : 25 473
    Points
    25 473

    Par défaut

    Bravo pour le travail
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  3. #3
    Membre chevronné
    Avatar de Goten
    Profil pro
    Inscrit en
    juillet 2008
    Messages
    1 580
    Détails du profil
    Informations personnelles :
    Âge : 28
    Localisation : France

    Informations forums :
    Inscription : juillet 2008
    Messages : 1 580
    Points : 2 202
    Points
    2 202

    Par défaut

    Pareil, bravo . Sa fait plaisir de voir un peu de MP ici .
    "Hardcoded types are to generic code what magic constants are to regular code." --A. Alexandrescu

Discussions similaires

  1. Résolution du problème du sac-à-dos quadratique en variables bivalentes
    Par nounou88 dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 16/01/2012, 14h55
  2. Compréhension d'un algorithme sur le problème du sac à dos
    Par Treuze dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 18/12/2006, 16h26

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