Examen 2016- Question 19

Examen 2016- Question 19

by Angelica Lola Danhaive -
Number of replies: 8

Bonjour,

J'ai quelques soucis avec la question 15 de l' examen 2016, qui demande de réécrire l'algo sous forme non récursive. Premièrement je voulais savoir si quelqu'un avait des astuces pour répondre à ce type de questions, car personnellement j'ai toujours du mal à comprendre ce que font exactement les algorithmes récursif, et encore plus de mal à ensuite les écrire sous forme non récursive. 

En fait dans celui ci, je ne comprends pas comment lier la sortie que l'on obtient dans la boucle "Si L1(1)<L2(2)" et celle que l'on obtient à la fin de l'algorithme. (C'est à dire ce qu'on fait une fois sortis de la boucle "si")

Finalement, je regardais la correction pour cette question, et je ne vois pas en quoi l'algorithme marche avec une entrée de listes non-ordonnées, car pour moi il ne fonctionne bien que quand les listes en entrée sont ordonnées. 

J'espère que mes questions soient assez compréhensibles. 

Merci beaucoup,

Lola


In reply to Angelica Lola Danhaive

Examen 2016- Question 19

by Parzival Hans Nussbaum -
Salut,

Malheureusement il n’existe pas un trique secret pour décomposer des algorithmes récursifs en algorithmes interatifs. ;)
La seule méthode qui fonctionne toujours c’est d’essayer de comprendre l‘algorithme (bien sûr avec le temps on développe une certaine intuition mais cela prends du temps): Ça ce fait en soit faire tourner des exemples à mains si on ne le comprend vraiment pas (et surtout si on a assez de temps) où en analysant deux facteurs:
a) «La condition de terminaison de la récurrence » (Dans ce cas la je vois que quand une de le liste est vide je retourne le reste de l’autre liste)
Et b) « L’appelle de la récurrence » (Si le premier élément de la première liste est plus grand que le premier de l’autre. Et je le mets à côté. Je prends la première liste sans le plus petit élément et l’autre liste et je rapplique la même fonction.)

Je ne comprends pas en totalité pourquoi tu parle « de boucle » pour le « si ». Mais tu ne vas jamais sortir de la condition si car tu vas sortir avec le « sortir » de cette instance de la fonction de la récurrence.

Le algorithme « truc » fonctionne pour des liste non ordonnée car il est en utilisant la fonction « machin » un algorithme de tris (Merge sort). En faite il va décomposer la liste non ordonnée en des singleton (qui sont par définition ordonnée) et les rassembler avec la fonction « machin ». Qui fonctionne bien sûr seulement avec des listes ordonnées. Mais car les singletons sont ordonnée et là sortie de « machin » aussi, tout les listes intermédiaires seront aussi ordonnées.

Si jamais tu as encore des questions à propos de mes explications moyennes n’hésite pas a les poser.

Parzival

In reply to Parzival Hans Nussbaum

Re: Examen 2016- Question 19

by Angelica Lola Danhaive -

Merci beaucoup! Je comprends déjà un peu mieux. Par contre j’avais mal formulé ma question, mais en fait je voulais savoir pourquoi l’algorithme « machin » mais en version non récursive marchait pour les listes non ordonnées (celui qui est offert en terme de correction).

Merci encore,

Lola

In reply to Angelica Lola Danhaive

Examen 2016- Question 19

by Parzival Hans Nussbaum -
À mon avis « machin » en version non récursive ne fonctionne pas non plus pour les liste non ordonnées. Ça doit être une faute dans le corrigé...
In reply to Parzival Hans Nussbaum

Re: Examen 2016- Question 19

by Jean-Cédric Chappelier -

Attention à la spécification du problème : machin DOIT recevoir deux listes ordonnées : c'est écrit dans la spécification de son entrée ! (dans la donnée)

(et ensuite justifié comme expliqué par Yassin ; mais ce n'est pas le plus important, le plus important c'est la spécification formelle des entrées fournies à l'algorithme ; comme des axiomes en maths)

Finalement, que la version proposée soit plus générale que cela et n'ai plus besoin (elle-même, seule) de l'hypothèse de "trier" pour fonctionner est un détail. (qui peut le plus peut le moins)

In reply to Angelica Lola Danhaive

Re: Examen 2016- Question 19

by Yassin Kammoun -

Bonjour,

Les deux listes reçues en entrée par la fonction machin sont en fait ordonnées. Pour s'en convaincre, il faut comprendre comment fonctionne le tri fusion. Ci-dessous une animation qui résume le fonctionnement du tri:

https://en.wikipedia.org/wiki/Merge_sort#/media/File:Merge-sort-example-300px.gif

truc est représenté par les divisions de listes en sous-listes; machin est représenté par la fusion des sous-listes en liste mise en évidence par les carrés rouges.

Notez qu'en examen, il n'y a pas d'animation. Si l'algorithme n'est pas évident à comprendre, il vous faut donc prendre un exemple et simuler l'algorithme sur papier pour comprendre comment il fonctionne.

Bref, la décomposition de la liste en sous-listes a lieu dans truc. Elle se fait par le biais de deux appels récursifs. La fusion des sous-listes a lieu dans machin.

Concrètement, on divise nos listes de départ en sous-listes encore et encore jusqu'à ce qu'elles contiennent (au plus) un élément. Deux listes à un seul élément sont de nature triées. En conséquence, on peut les fusionner dans une nouvelle liste.

On répète le processus avec des sous-listes à deux éléments, puis à quatre, et ainsi de suite.

J'espère que l'animation proposée et mes explications suffiront à vous convaincre que machin est correct et que machin reçoit systématiquement deux listes triées.

In reply to Yassin Kammoun

Re: Examen 2016- Question 19

by Jean-Cédric Chappelier -
> il vous faut donc prendre un exemple et simuler l'algorithme sur papier pour comprendre comment il fonctionne.

et c'est exactement pour cela qu'il y a les questions 17 et 18 ... ;-)
In reply to Angelica Lola Danhaive

Re: Examen 2016- Question 19

by Noé Romain Alexis Hollande -

Salut, j’ai pas fait le sujet de 2016 donc je peux pas trop t aider mais il y’a une méthode assez générale pour les algorithmes récursif. En utilisant les résultats précédents pour les incrémenter, ils vont généralement soit faire un tri soit être traduisible en une suite arithmétique ou géométrique classique. Le plus important est de comprendre ce qu’ils font, quelle sortie ils vont produire , une fois que c’est fait il suffit d’imaginer un algorithme qui arrive à cette sortie sans utiliser de récurrence. J’espère que ça t’auras un peu aidé .