Discussion :

[jeremux]

Bonjour à tous j'ai à faire un programme qui trie un tableau sans utiliser de tableau intermédiaire, juste avant ça (dans l'exercice) on pouvait et j'ai proposé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
let fusion t a m b=
  let deb=m+1 and t_bis=(Array.create (m-a+1) 0) in
  let compt1=ref(a) and compt2=ref(deb) in
 
  for i=a to m do
    t_bis.(i-a)<-t.(i) 
  done;
 
  for i=a to b do
    if (!compt1)=deb then
      ()
    else if (!compt2)=(b+1) then
      begin
        t.(i)<-t_bis.(!compt1-a);
        compt1:=(!compt1)+1
      end
    else if t.(!compt1-a) < t.(!compt2) then
      begin
        t.(i)<-t_bis.(!compt1-a);
        compt1:=(!compt1)+1
      end
    else
      begin
        t.(i)<-t.(!compt2);
        compt2:=(!compt2)+1;
      end
  done;
t;;

Mais dans la méthode sans recopie du tableau, je ne vois pas vraiment comment m'y prendre. On dit je cite

"La seconde méthode ne nécessite pas de recopier les deux moitiés de t dans des tableaux
auxiliaires. Il s'agit cette fois d'insérer les éléments de la seconde moitié dans la première en les
décalant vers le début du tableau case après case jusqu'à leur position finale.
Par exemple si t = [|2; 5; 1; 3; 4|] le premier élément de la seconde moitié est 1, comme il est
plus petit que 5 on les échange. Maintenant t = [|2; 1; 5; 3; 4|]. Comme 1 est plus petit que 2 on
échange les deux valeurs et 1 atteint sa place finale. Ensuite c'est 3, le deuxième élément de la
seconde moitié, qui doit être placé, comme il est plus petit que 5 on les échange etc."

Merci pour vos aides.

[drunkskater]

Salut,

Tout d'abord assure-toi d'avoir bien compris l'algorithme de tri. Pour ça le mieux c'est (je pense) d'essayer de le faire tourner à la main sur plusieurs exemples précis, de plus en plus gros et de plus en plus tordus, de façon à voir comment ça se passe concrètement .

Attention, c'est pas un super conseil dans l'absolu car justement des fois on programme des trucs sans avoir la moindre idée de ce qui se passe concrètement (Tu as déjà entendu parler du jeu des tours d'Hanoi ?), et c'est précisément ce qui fait la beauté de la programmation non-impérative

Mais je sais que ça m'aidait pour les différents algorithmes de tris d'avoir des petits bouts de papier que je faisais bouger bêtement en suivant les règles de l'énoncé, de façon à voir en gros comment ça allait marcher.

Une fois que tu vois comment ça marche, essaie de scinder ton problème : demande-toi quelles sont les "opérations de bases" qu'utilise ton algorithme. Code-les, assure toi qu'elles marchent, puis assemble-les pour écrire ta fonction de tri.

Voilà, je vois pas trop comment t'aider plus sans te donner la solution... Bonne chance !

[gasche]

Attention, c'est pas un super conseil dans l'absolu car justement des fois on programme des trucs sans avoir la moindre idée de ce qui se passe concrètement (Tu as déjà entendu parler du jeu des tours d'Hanoi ?), et c'est précisément ce qui fait la beauté de la programmation non-impérative.

Je dirais plutôt qu'il y a différents modes de raisonnement sur le code et qu'il faut savoir passer des uns aux autres selon les besoins d'une application. Entre autres :
- un raisonnement "opérationnel" où on exécute pas à pas le code dans sa tête pour comprendre son fonctionnement
- un raisonnement "ëquationnel" où on remplace dans sa tête (ou pas) des bouts de code par des versions de même signification, mais permettant d'autres transformations ou ayant des propriétés différentes
- un raisonnement "dénotationnel" où on attribue une "signification" (instinctive en général) aux objets du programme (valeurs, fonctions...) et on essaie de comprendre ou tester la signification d'un gros morceau en assemblant les significations de ses composants (y compris lui-même si c'est une fonction récursive)


Ces méthodes de réflexion jouent sur plusieurs niveaux et il est bon de pouvoir passer de l'un à l'autre. Par exemple un raisonnement opérationnel est une bonne façon de comprendre un algorithme impératif (ici ce tri) ou de se faire une idée des performances d'un programme; un raisonnement équationnel est adapté quand on veut ré-écrire un programme pour le simplifier ou l'optimiser, débugguer, et un raisonnement dénotationnel est utile pour comprendre les fonctions récursives (car il est plus "abstrait", ou grand pas; vérifier une fonction récursive en supposant qu'elle marche dans les sous-appels c'est juste génial), mais pas la tail-récursion par exemple (ce qui demande de repasser en opérationnel).

[drunkskater]

C'est super intéressant d'avoir l'avis de quelqu'un d'expérimenté sur la question. Bizarrement, je ne voyais pas exactement les choses comme ça (notamment la différence entre les raisonnements "équationnels" et "dénotationnels", dont je n'étais pas du tout conscient et que j'ai encore un peu de mal à bien cerner), mais quand j'y repense il me semble que tu as tout à fait raison.

Ma formulation était peu gauche ( "sans avoir la moindre idée de ce qui se passe concrètement" ) mais en gros je voulais dire "il existe d'autres modes de raisonnements que l'opérationnel".

Je me souviens que ça m'avait choqué la première fois que j'ai vu les tours d'Hanoi. J'avais déjà écrit des fonctions récursives (factorielle... ) et même tail-recursives, mais en fait je pensais toujours en "opérationnel" à savoir qu'avant de lancer un programme je le relisais en me demandant quelles opérations il allait effectuer et dans quel ordre. Avec les tours d'Hanoi, c'était différent. J'avais trouvé la bonne solution et un code bon modulo les erreurs de syntaxe, mais je n'osais pas l'exécuter parce que ça me semblait impossible que ça marche étant donné que je voyais pas du tout ce qu'il allait commencer par faire...

En gros je crois pour moi la différence se résume (pour l'instant ?) essentiellement en deux types de raisonnements :

- Ceux "opérationnels" (un peu comme cet algorithme), pour lesquels j'essaie sur un exemple concret pour me convaincre que ça marche.

- Les autres, pour lesquels un raisonnement que je sais correct me montre que ça marche, sans forcément que je vois bien pourquoi.

[Cacophrene]

Bonjour,

Comme souvent, bluestorm a le mérite de mettre des mots sur des notions intuitives mais non formulées. C'est utile car ce n'est que lorsqu'on a correctement nommé ce que l'on pressent qu'on le comprend bien.

Clairement, beaucoup d'étudiants ont du mal avec les fonctions récursives parce que, précisément, ils essaient d'y appliquer un point de vue opérationnel en « imaginant » le déroulement du programme. C'est le meilleur moyen de ne pas comprendre un algo récursif (et l'abus de #trace n'y est pas pour rien).

La programmation fonctionnelle dans un contexte impur comme celui d'OCaml oblige a pratiquer tous ces points de vue : entre la manipulation d'un tableau et l'écriture d'un code avec des continuations, adopter le même regard n'est tout simplement pas possible. Programmer efficacement en OCaml suppose que cette gymnastique est acquise, fort heureusement ça vient avec l'entraînement.

Cordialement,
Cacophrène