Introduction à la programmation dynamique !

Tout le monde se secoue !

Suite à un conseil de Hod, je vais commencer à transférer les articles de mon site sur Zeste de Savoir pour contribuer à la section "Algorithmique". Je commence donc avec un premier court article qui se veut être une introduction au concept de la programmation dynamique. N'hésitez pas à me faire part de vos retours et de vos remarques sur l'article que vous pouvez retrouver ici :

Merci d'avance de votre lecture

Puisque tu parles de la complexité, et que tu as envie de faire un article, peux-tu faire un lien vers ce tuto : https://zestedesavoir.com/tutoriels/484/nos-algorithmes-sont-ils-vraiment-comparables/

Le but est de créer du liant entre les contenus de zds.

De plus pour la mémoire, je me sens bien de faire un petit jsfiddle pour représenter l'espace mémoire pris au fur et à mesure du temps.

Bien sûr, pas de soucis !

Hm je ne connais pas, je vais me renseigner dessus.

Merci pour la publicite artragis.

J'ai lu en diagonale et il y a un petit truc qui me manque lorsque tu compares diviser pour mieux regner a la programmation dynamique: divide and conquer est une approche top-down par design, la ou la programmation dynamique est l'oppose, c'est a dire a une approche bottom-up.

C'est a mon sens la difference fondamentale qui ensuite explique pourquoi la programmation dynamique permet de ne pas recalculer certain sous-problemes (aka principe d'optimalite de Bellman).

A mon avis c'est quelque chose qui devrait figurer dans l'introduction pour vraiment que le lecteur qui n'y connait rien voit tout de suite la difference d'approche entre les deux.

Bon, sinon comme je te l'ai dit sur IRC, c'est une bonne initiative et j'attends aussi tes ecrits sur l'apprentissage.

Techniquement on peut faire des deux avec la programmation dynamique (et j'en parle justement), mais c'est pour ça que je préfère évoquer l'idée des sous-problèmes communs dans l'introduction comme principale différence entre diviser pour régner et programmation dynamique. Si je présente cette méthode comme uniquement ascendante, je me prive d'une étape assez importante dans l’appréhension du principe. Je vais voir si je peux tout de même l'évoquer en introduction car c'est effectivement un bon point.

Merci de ton soutien, mais j'ai déjà évoqué l'idée d'aider peut être les personnes qui sont en train de faire un tutoriel sur l'apprentissage artificiel plutôt que de publier mon article de mon côté (d'ailleurs je compte faire de même pour le tutoriel sur les algorithmes de graphe sans doute).

Pour le js fiddle c'est un moyen sympa d'insérer un peu d'interactivité dans le tutoriel. C'est ce qu'on fait dans l'article sur les nombres premiers dans le cadre du crible d'ératostène ainsi que dans le tuto sur la balise video en html.

C'est une possibilité qui est propre à zds (oc ne l'a pas par exemple) mais elle est assez peu utilisée. Or comme nos membres n'ont pas trop l'air friants de vidéo, j'essaie de voir comment intégrer un maximum cette fonctionalité pour donner un peu d'originalité à nos contenus.

Ah effectivement, je ne savais même pas pour cette fonctionnalité ! Après personnellement je ne code pas en js, mais si une personne fait un code intéressant et qui apporte quelque chose à l'article, ça sera avec plaisir que je l'intégrerais

Hm, je ne pensais pas qu'une mise à jour de la bêta afficherait un message (je m'excuse de cette notification). J'ai juste pris en compte les deux remarques faites (sur le lien vers le tutoriel, et sur l'intro).

Pas besoin de t'excuser, c'est au contraire bien pour nous aider à suivre de voir que tu as mis à jour

Au fait, j'ai aussi un tuto en cours de rédaction sur la programmation dynamique. C'est une reprise de mon tuto sur le SdZ. Si tu est intéressé par une collaboration sur le sujet c'est bienvenu de mon coté (je n'ai jamais pris le temps de le finaliser proprement pour ZdS).

Avec plaisir, tu préfères me rajouter sur ton tutoriel ou l'inverse ?

Merci pour la publicite artragis.

Sinon, je n'ai parcouru le tuto que vite fait, c'est assez sympa à lire !

Juste un truc par rapport au code C pour Fibnoacci : tu dis mettre -1 car toutes les valeurs sont positives. C'est vrai, mais vu que tu stockes dans un unsigned long long, ton résultat sera tout de même considéré comme un nombre positif. Ce sera en réalité le plus grand nombre positif que peut stocker un ull.

Oups, merci d'avoir vu cette erreur. Je corrige !

Comme tu veux, ce qui est surtout intéressant est de savoir comment intégrer les deux tutos pour n'en faire qu'un. Si tu veux on en discute par MP.

Salut,

La rédaction est-elle toujours en cours ? Du nouveau du coté de la fusion des deux contenus ?

Salut !

Non malheureusement la rédaction n'a pas avancé pour un manque de temps tout d'abord, et puis plus récemment j'avais la tête ailleurs. Mais comme j'envisageais de toute façon de ré-écrire une bonne partie de l'article, je pense m'y remettre bientôt, à voir si yoch est aussi disponible.

Entendu (parce que ce serait dommage de perdre cet article, c'est un bon premier jet).

Bonjour,

La bêta du contenu « Introduction à la programmation dynamique ! » a été désactivée.

Bonjour à tous !

J’aimerais tout d’abord m’excuser pour ce "délai" de plusieurs mois. Il s’est passé beaucoup de choses entre temps, et écrire l’article n’était pas une de mes priorités. J’ai cependant repris l’écriture il y a un peu plus d’un mois. L’article a été totalement réécrit, à la base pour tenter d’inclure l’autre tutoriel de yoch sur le sujet, puis j’ai voulu reprendre entièrement le projet pour adopter une approche plus concrète et moins superflue que celle que j’avais mise en place lors de la bêta précédente. L’article est certes plus long, mais j’ai essayé d’être à la fois complet et synthétique dans mes explications et de suivre un raisonnement logique et le plus naturel possible.

J’attends avec impatience vos retours sur l’article !

Bonjour,

Ça me semble assez clair, cependant, j’aurais bien aimé retrouver des images, une avec le tableau une fois rempli et l’autre avec le chemin emprunté. Car celle avec les ronds verts n’est pas forcément explicite.

C’est l’image en elle-même que tu ne trouves pas claire ou bien les explications qui vont avec (ou les deux) ? Car cette image a pour but de présenter le cas général, et de faire apparaître les 3 informations nécessaires pour mettre en place notre algorithme itératif parcourant le tableau (les points de départ, les liens de dépendance d’une case à l’autre et l’objectif final).

Il n’est pas réellement possible de montrer le chemin emprunté car encore une fois c’est un cas général puisque le résultat d’une case varie en fonction du poids des objets. Après, même en prenant un exemple et en appliquant le schéma à cet exemple bien spécifique, je ne suis pas certain de l’intérêt d’expliciter le chemin suivi car l’algorithme ne "suit" pas réellement un chemin mais se contente de remplir le tableau. Je pense que cela pourrait porter à confusion dans la compréhension de l’algorithme. L’image a pour but d’expliquer comment le résultat d’une case est calculée (le point bleu), donc les explications pour les autres cases du "chemin" seront exactement les mêmes.

Je vais tout de même essayer de réfléchir à une manière d’améliorer ce point, merci de ton retour