Bonjour,
je ne comprends pas bien la réponse à la question 4.9.1 du quizz 39.
J’ai testé en python, et je n’obtiens pas la même réponse que l’officielle. Cependant, je ne sais pas comment poser ma question sans donner au moins ma réponse.
Que puis-je faire?
Bien cordialement,
Robert Sebille.
Bonjour zenjo,
Peut-être peux-tu donner ton programme Python ici ?
Cela permettra peut-être de comprendre pourquoi les réponses sont différentes ?
Bonjour isabelle,
effectivement. Voici (c’est un mix de pgm de Thierry Parmentelat, sur les notebooks):
counter = 0
def substitution_cost(base1, base2):
return 1 if base1 != base2 else 0
def insertion_cost(base):
return 1
def needleman_wunsch_rec(dna1, dna2, i=None, j=None):
"""
Calcule l'écart entre deux chaines d'ADN selon
l'algorithme de Needleman et Wunsch
en version récursive
Utilise les fonctions
* insertion_cost(base) et
* substitution_cost(base1, base2)
L'appelant en général ne spécifie pas i et j, qui sont utilisés
lors des appels récursifs
"""
# si on n'a pas précisé i ou j cela signifie
global counter
counter += 1
#print("le couple ({}, {})".format(i, j))
# qu'on veut travailler sur toute la chaine
i = i if i is not None else len(dna1)
j = j if j is not None else len(dna2)
### la condition d'arrêt
# le bord supérieur
if j == 0:
return sum(insertion_cost(base) for base in dna1[:i])
# le bord gauche
elif i == 0:
return sum(insertion_cost(base) for base in dna2[:j])
# dans le cas général on peut appliquer la formule telle quelle
return min(
# substitution
needleman_wunsch_rec(dna1, dna2, i-1, j-1) + substitution_cost(dna1[i-1], dna2[j-1]),
# insertion
needleman_wunsch_rec(dna1, dna2, i, j-1) + insertion_cost(dna2[j-1]),
# insertion
needleman_wunsch_rec(dna1, dna2, i-1, j) + insertion_cost(dna1[i-1]))
needleman_wunsch_rec("ACG", "ACG", 0, 1)
print(counter)
Personnellement, le code et ses réponses me paraissent logiques.
Bien cordialement et merci de ton attention.
Robert.
Si j’ai bien compris, on cherche à savoir combien de fois il est fait appel à la fonction avec les arguments i = 0 et j = 0 lorsqu’on l’appelle pour 2, 2.
Je changerais donc l’appel en
needleman_wunsch_rec("ACG", "ACG", 2, 2)
et n’incrémenterais counter que dans les cas où (i, j) est égal à (0, 1).
Bonjour Isabelle,
je dois préciser ici. La question posée est:
“Si l’on considère une grille de dimension de 3x3 et que l’on utilise l’algorithme récursif vu dans la séquence 8, combien de fois allons-nous calculer le coût du noeud (0,1) ? Cela revient à compter combien de fois la fonction ComputeCost est appelée avec les arguments (0,1), c’est-à-dire combien de fois l’appel ComputeCost(0,1) est exécuté.”
Ayant suivi studieusement ce complément python, pour moi la réponse était d’emblée claire, à l’oeil nu ;-), que ce soit d’ailleurs pour le noeud (0,0), (1,0), (0,1), je soulève un peu le voile, c’est la même - et quelque soit d’ailleurs la longueur des séquences >= 0
Néanmoins, mon grand age m’a appris que 1 vérification vaut mieux qu’aucune, et j’ai vérifié, avec ce mix de programme récupéré du complémént et que je t’ai mis dans mon précédent post. Ces vérifications ont conforté ma logique, et je ne comprends vraiment pas la réponse officielle (mais ici, je ne peux rien dire de plus)
J’ai posté 2 réponses au quizz:
- ça ne m’a pas vraiment aidé ;( )Euh mwouais 
, but Simple is better than complex. , j’incrémente counter pour le nombre d’appel quelque soit le noeud.
j’incrémente counter pour le nombre d’appel quelque soit le nœud.
Alors, je pense que nous ne comprenons pas la question de la même façon, parce que ce n’est pas ce que l’on nous demande ici justement.
Il me semble que le but est de déterminer le nombre de fois où la fonction computeCost est appelée avec les arguments 0, 1 lorsqu’on détermine le coût du nœud (2, 2) de la grille 3x3.
La réponse attendue n’est donc pas le nombre total de fois où l’on utilise l’algorithme, mais le nombre de fois où celui-ci demande de déterminer le coût du nœud (0, 1), donc le nombre de fois où la fonction s’appelle elle-même mais avec les arguments i = 0 et j = 1.
Et ce nombre n’est d’ailleurs pas le même que celui obtenu si la question portait sur computeCost(0, 0).
Bonjour Isabelle,
oui, ta compréhension, c’est exactement cela. Si je vérifie (parce que cette fois-ci, à l’oeil nu, c’est plus difficile 
), j’obtiens la bonne réponse et tout est logique.
Ouf, je dois bien avouer que j’ai eu du mal à comprendre cette question, et que la réponse m’apparait plus facile que la question !
Sans doute, cette question mériterait-elle d’être posée un peu plus clairement, mais bon, pas très grave, finalement j’ai compris.
Merci beaucoup pour tes explications, j’avais l’impression de tourner en rond.
Cordialement.
Ce qui peut peut-être aider à la compréhension de la question, c’est d’avoir en tête que le but est de montrer l’inefficacité de la récursion ici.
Bonne continuation !
Bonjour Isabelle,
c’est cette phrase qui a fait “tilt” dans mon cerveau pour la compréhension. Du coup, et je ne sais pas si ça peut servir, mais, j’ai réécrit la question à ma façon, voici toujours:
Si l’on considère une grille de dimension de 3x3 et que l’on utilise l’algorithme récursif vu dans la séquence 8, combien de fois la fonction récursive computeCost est-elle appelée pour le noeud i, j = 0, 1 lorsqu’on détermine le coût du noeud 2, 2 de la grille 3x3 donc, avec l’appel computeCost(2, 2, 0, 1) ?
Voilà; bon, maintenant, il y a parfois des questions qui résistent et ce n’est pas facile de poser des questions pour la compréhension de tous, tant de subtiles et petites différences culturelles ou habitudes de parler peuvent rendre cette compréhension difficile.
Finalement, j’ai fini par comprendre, merci pour l’entraide!
cordialement.
Bonjour!
Pour ceux qui ont besoin de quelque chose d’un peu visuel (comme c’est mon cas), on cherche finalement tous les chemins qui partent du point (2,2) pour mener au point (0,1).
Sauf que … attention à ne pas se faire avoir car dès qu’on est sur le bord supérieur du graphe ou le bord gauche (i=0 ou j=0) on a directement la formule qui nous donne le coût pour ce point là (voir le code de 4.8 pour cela), donc on ne peut pas relier deux points qui se trouvent sur ce bord supérieur ou ce bord gauche.
En espérant que cela puisse en aider certains.
Bonne continuation!