Ç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
D’accord je vois ce que tu veux dire. Pourquoi pas, mais après les tableaux des exemples utilisés sont tout simplement énormes et difficiles à représenter en entier (d’où l’avantage de ce schéma fictif), et j’avoue qu’insérer un nouvel exemple dans cette partie de l’article qui est déjà très dense en explications pourrait perturber la lecture. Je vais voir comment intégrer cela sans trop gêner.
Je voulais simplement vous informer que je ne serais que très peu disponible durant ce mois de juillet (c’est pourquoi j’ai mis l’article en bêta légèrement plus tôt que prévu). Cependant, n’hésitez pas à me faire parvenir vos retours, car je lirais sans doute les commentaires et je pourrais déjà commencer à réfléchir sur la manière de corriger telle ou telle partie avant mon retour (par exemple la remarque de JuDePom).
On sent bien l’influence FIOI ici. D’ailleurs par réflexe j’ai frémi sur l’indexation de objet à partir de 1 alors que NB_OBJETS_MAX vaut 1000 (et pas 1001).
Sinon ma vision préférée de l’idée ça reste dynamique = plus court chemin dans un DAG. Ça permet de bien s’abstraire du problème (et on retrouve l’itératif modulo un tri topologique). C’est vachement plus utile de travailler là-dessus que ce qu’on voit dans le scolaire/académique avec les gens qui essayent de faire des "diviser pour régner" à tout va.
L’énoncé que j’ai écris n’impose pas de contrainte explicite pour NB_OBJETS_MAX j’avais donc pris 1000 comme simple constante. En revanche, le code original utilisait effectivement des index commençant à 0 et je n’avais pas changé le 1000 en 1001, mais encore une fois ça n’a pas réellement d’importance dans notre cas.
Sinon ma vision préférée de l’idée ça reste dynamique = plus court chemin dans un DAG. Ça permet de bien s’abstraire du problème (et on retrouve l’itératif modulo un tri topologique).
Hm, ta méthode est sans doute plus intéressante (d’ailleurs si tu pouvais un peu plus la détailler ça serait avec grand plaisir pour que je me rende bien compte des différences), mais je ne sais pas si le fait de "bien s’abstraire du problème" est réellement efficace pour une introduction à un concept, je trouve qu’au contraire il faut s’appuyer sur un exemple assez parlant pour bien illustrer les nouvelles notions.
C’est vachement plus utile de travailler là-dessus que ce qu’on voit dans le scolaire/académique avec les gens qui essayent de faire des "diviser pour régner" à tout va.
L’énoncé que j’ai écris n’impose pas de contrainte explicite pour NB_OBJETS_MAX j’avais donc pris 1000 comme simple constante. En revanche, le code original utilisait effectivement des index commençant à 0 et je n’avais pas changé le 1000 en 1001, mais encore une fois ça n’a pas réellement d’importance dans notre cas.
Oui j’ai bien remarqué qu’il n’y avait pas de contrainte ici, c’est pour ça que je disais que c’était un réflexe. Mais d’expérience les contraintes c’est toujours $\le 1000$ et jamais $< 1000$.
Plus sérieusement, ça veut ptete aussi dire que NB_OBJET_MAX est pas très bien nommé, parce que son utilisation montre qu’il doit valoir le nombre maximal d’objets… plus 1 ! C’est pour ça que de mon point de vue il est plus rassurant pour le relecteur — et plus cohérent pour le codeur — d’avoir un +1 dans la taille d’un tableau indexé à partir de 1 plutôt que de cacher ça dans la constante.
Hm, ta méthode est sans doute plus intéressante (d’ailleurs si tu pouvais un peu plus la détailler ça serait avec grand plaisir pour que je me rende bien compte des différences), mais je ne sais pas si le fait de "bien s’abstraire du problème" est réellement efficace pour une introduction à un concept, je trouve qu’au contraire il faut s’appuyer sur un exemple assez parlant pour bien illustrer les nouvelles notions.
Non mais ce que je dis ne remet pas en cause ce que tu as écrit, et c’est même probablement une mauvaise idée pédagogique que de vouloir introduire les choses comme ça ; par contre, c’est une vision qu’il me paraît intéressante de garder en mémoire dans un deuxième temps.
Bon je vais détailler un peu ce à quoi je pensais, mais je suis pas sûr de t’apprendre beaucoup de choses.
Déjà on peut décrire un algorithme dynamique exactement par la donnée d’un ensemble de situations et de transitions entre ces situations (on met une transition entre $s_1$ et $s_2$ si pour calculer la valeur pour $s_1$ on "utilise" le résultat pour $s_2$). Si maintenant on regarde le graphe orienté $G$ dont les nœuds sont les situations et les arêtes correspondent aux transitions, une condition « rassurante » pour que le dynamique fonctionne bien est l’acyclicité de $G$.
Une idée bien connue pour chercher une solution à un problème consiste donc à formuler une relation de récurrence sur la valeur du résultat en décrivant situations et transitions, et à regarder la forme du graphe des dépendances. On sait déjà que s’il est acyclique on va pouvoir faire un dynamique.
Or, empiriquement on remarque que souvent la relation de dépendance peut se mettre sous une forme assez simple, disons semblable à :
Remarquons que cette reformulation fonctionne entre autres dès qu’on a un $\max$ à la place du $\min$ (passer à l’opposé) ou encore si on a un produit à la place de la somme (passer au $\log$, très courant quand on fait des dynamiques sur des probas d’événements indépendants).
Dans ce cas (pas si) particulier, on a donc exactement une relation de type « plus court chemin ». On peut donc appliquer tous les algos typiques là-dessus :
Les coûts $c(u,v)$ sur les arêtes sont $\ge 0$ ? Dijkstra en $O(|V|^2)$ ou $O(|E|+|V|\log |V|)$.
Le graphe est acyclique ? Dynamique en $O(|E|)$.
Rien de particulier ? Bellman-Ford en $O(|V||E|)$.
Donc dans ce cas un dynamique c’est simplement un algorithme efficace de calcul de plus court chemin dans un DAG. On peut d’ailleurs s’amuser à regarder ce que donnent les optimisations typiques dans le langage de la théorie des graphes. Par exemple, calculer itérativement le dynamique revient à calculer un tri topologique du DAG et à considérer les situations dans cet ordre (en particulier, ça montre qu’on peut toujours rendre un dynamique itératif — en substance j’entends, pas juste déplier).
Cette vision n’est évidemment pas parfaite, en particulier pour les raisons suivantes :
(important) On perd de l’info en éliminant toute la structure sur l’ensemble des situations. Par exemple dans le cas où les situations forment un produit cartésien « 2D », on a pas du tout la vision d’où on prend les dépendances dans les transitions (exemple typique de l’opti mémoire que tu présentes dans ton article, qui devient invisible ici).
(à relativiser) Elle n’est pas exhaustive : toutes les relations de dépendance ne se mettent pas sous la forme donnée plus haut. Un exemple qui me vient en tête est celui du dynamique sur intervalles où la transition est de choisir un point de coupure (exemple canonique pour l’opti de Knuth). Il faut aussi rajouter à cela les dynamiques combinatoires (où la fonction objectif est un certain « nombre de possibilités »), mais ce ne sont généralement pas les problèmes les plus difficiles.
Néanmoins, tout ça colle bien avec l’idée « commencer par exprimer une relation de récurrence », puis voir ce qu’on peut faire avec. Ce qu’a montré ici, c’est qu’en regardant la forme de la relation et du graphe associé, on a déjà des algos tous prêts avec des complexités claires. C’est sans doute la méthode la plus fondamentale pour résoudre un problème de graphe implicite.
Concrètement, pour ton article ça pourrait être intéressant de présenter des idées similaires qui, je pense, aident à appliquer des dynamiques sur des problèmes réels. Évidemment pas en introduction, mais on pourrait réfléchir à en parler vers la fin (à voir si y a d’autres concepts semblables qui pourraient être évoqués à ce moment-là).
Et si j’opposais à cela ce qu’on fait dans le scolaire, c’est parce que je trouve qu’en laissant le lecteur à la fin sans méthodologie, il est réduit à essayer réfléchir en fonction des algorithmes et pas de la forme du problème. Et pour moi, voir un problème et se demander : « tiens, est-ce que je peux faire un diviser pour régner/un dynamique/un Dijkstra », c’est le témoignage d’une mauvaise méthodologie.
Merci beaucoup pour ton message aussi détaillé Lucas-84.
Plus sérieusement, ça veut ptete aussi dire que NB_OBJET_MAX est pas très bien nommé, parce que son utilisation montre qu’il doit valoir le nombre maximal d’objets… plus 1 ! C’est pour ça que de mon point de vue il est plus rassurant pour le relecteur — et plus cohérent pour le codeur — d’avoir un +1 dans la taille d’un tableau indexé à partir de 1 plutôt que de cacher ça dans la constante.
Effectivement, expliciter le +1 dans la taille du tableau serait plus judicieux.
Non mais ce que je dis ne remet pas en cause ce que tu as écrit, et c’est même probablement une mauvaise idée pédagogique que de vouloir introduire les choses comme ça ; par contre, c’est une vision qu’il me paraît intéressante de garder en mémoire dans un deuxième temps.
Je trouve que c’est en effet une excellente idée que d’aborder ce côté méthodologie dans un "deuxième temps", mais cela pose aussi un autre problème :
Soit je rajoute une partie à l’article. Problème : l’introduction est déjà longue et je doute que rajouter encore du texte soit une bonne idée (surtout pour une partie aussi importante, nécessitant pas mal d’explications et de détails).
Soit j’écris un nouvel article à part entière pour bien prendre le temps d’aborder clairement toutes ces notions de méthodologie. Problème : je ne pense pas que l’écriture d’article sera une priorité pour moi durant les prochains mois/années et je ne peux donc rien assurer.
Personnellement la deuxième option me semble clairement la plus appropriée, mais il faudra attendre un bon moment pour que j’y vienne à bout pour la raison que j’ai évoquée précédemment (ou alors d’ici là un autre membre aura déjà rédigé l’article).
Et si j’opposais à cela ce qu’on fait dans le scolaire, c’est parce que je trouve qu’en laissant le lecteur à la fin sans méthodologie, il est réduit à essayer réfléchir en fonction des algorithmes et pas de la forme du problème. Et pour moi, voir un problème et se demander : « tiens, est-ce que je peux faire un diviser pour régner/un dynamique/un Dijkstra », c’est le témoignage d’une mauvaise méthodologie.
Entièrement d’accord, c’est pour cela que je préfère la deuxième option, car la méthodologie est extrêmement importante, notamment avec la programmation dynamique.
Dis-moi ce que tu penses de ma décision vis-à-vis l’écriture d’un article séparé (quitte à attendre).
Encore désolé du retard pour répondre à ton message.
Salut ! Juste pour dire que, étant parfaitement étranger au sujet, j’ai trouvé ton tuto super intéressant (il s’avère qu’il répondait à une question que je me posais en ce moment).
Merci de ton retour, cela fait toujours plaisir à entendre. As-tu d’autres remarques, questions, incompréhensions par rapport à l’article ? Des points à améliorer, des choses qu’une personne, comme tu le dis, "étrangère au sujet" pourrait ne pas bien appréhender ? Et sinon, quelle était ta question à la base ?
Bon je réponds vachement tard à ta question, mais en fait, je me posais des questions sur les stratégies d’optimisation mises en place sur des algorithmes nécessitant un grand nombre de calculs (du style rendu vidéo), généralement en parallèle. Parce que jusqu’à présent j’ai plus tendance à coder de manière naïve. Donc ça répondait assez clairement à mes attentes du moment.
Désolé du retard, je ne suis plus trop actif ces derniers temps. L’article en lui-même est fini, mais Lucas-84 avait soulevé un point très important : l’aspect méthodologique lié à la programmation dynamique. Comme je l’avais dit dans mon message, je pense qu’il serait mieux de créer un article à part car il y a énormément de choses à développer à ce sujet, mais je ne suis clairement pas sûr d’avoir le temps pour cela.
S’il s’agit d’un autre article, et d’un deuxième temps (vous semblez tous les deux d’accord là-dessus), la publication du premier temps (donc cet article), quitte à dire en conclusion qu’il serait sage d’aller plus loin (logique pour une Introduction à), n’est-elle pas envisageable ?
Ce serait bête d’avoir un article presque fini qui ne parait pas parce que tu ne comptes pas écrire la suite. Qui sait, quelqu’un a peut-être envie d’écrire un article plus avancé sur le sujet, mais ne se lance pas car il devrait écrire une introduction qui ne l’intéresse pas.
Effectivement, dans ce cas pourquoi pas le publier (est-ce qu’il a un processus de validation ou c’est uniquement réservé aux tutoriels ?). Par contre, je préfère discuter de cet aspect méthodologique dans les commentaires de l’article plutôt que dans la conclusion car cette dernière est déjà bien longue.
D’ailleurs par réflexe j’ai frémi sur l’indexation de 
