J'ai besoin de votre aide pour comprendre la signification d'une partie d'une structure de données abstraite, concernant la "file de priorité" :
type tas de t avec fonction <=(t,t):bool
référence sur un multi-ensemble d'éléments de type t
tas_vide():tas
[[tas_vide()]]=ref(Ø)
est_vide(tas):bool
[[est_vide(h)]]=vrai si ![[h]]=Ø
[[est_vide(h)]]=faux sinon
insere(t, tas):void
[[insere(elt, h)]]=[[h]]←{elt}U[[!h]]
minimum(tas):t
[[minimum(h)]]=min(![[h]]),
Précondition: ![[h]]≠Ø
/* C'est ci-dessous que je ne comprend plus */
extrais_min(tas):t
[[extrais_min(h)]]=[[h]]←![[h]]\{min(![[h]])};min(![[h]]),
Précondition: ![[h]]≠Ø
Pour l'extraction du chiffre minimum, je ne comprend bien l'emploi du signe "\" ainsi que l'utilisation du ";".
En effet, je comprend que la valeur du tas h, prend son ancienne valeur auquel on doit soustraire le minimum, mais alors pourquoi celui-ci est utilisé deux fois ? Pourriez-vous me traduire plus littéralement cette phrase ? Je n'arrive pas à trouver d'exemple sur internet.
Merci beaucoup pour votre aide.
EDIT : Intuitivement, je dirais que cela signifie : "h prend son ancienne valeur auquel on soustrait l’élément minimum, et l'on renvoi l'élément minimum"
J'avais passé ce sujet en "Résolu" pensant que le "\" signifie la soustraction, et que donc :
[[extrais_min(h)]] = [[ h ]] ← ![[ h ]] \ { min(![[ h ]]) } ; min(![[h]])
signifie "h prend son ancienne valeur auquel on soustrait l’élément minimum, et l'on renvoi l'élément minimum"
Le problème est qu'en continuant ma lecture, je tombe sur une précondition de la fonction remonte(h, nœud), qui remonte un nœud dans le tas binaire, si celui-ci est plus petit que son parent, sous cette forme :
pour tout i ϵ [1, |h| - 1] \ [[nœud]], [[ h[pere(i)] ]] <= [[ h.[i] ]]
Je ne pense que cela signifie que "i doit appartenir à n'importe quel nœud du tableau, excepté le nœud 0 qui n'a pas de père, auquel on soustrait le nœud, puis que le père de i doit être plus petit que i".
En effet la soustraction n'a ici pas vraiment de sens, cela devrait plutôt être, "i doit appartenir à n'importe quel nœud du tableau, excepté le nœud 0, et doit valoir la valeur de "nœud", puis que le père de i doit être plus petit que i".
Sauf que dans ce cas là, si on retourne à la signification du "\" dans la structure de donnée abstraite de "extrais_min(h)", le sens deviendrait : "h prend son ancienne valeur, et la valeur minimum du tas, et l'on renvoi le minimum", or dans ce cas, il n'y a plus de suppression de nœud, la fonction ne fait plus ce qu'elle devrait.
Merci pour le déplacement, j'espère que j'aurai plus de chance d'obtenir une réponse dans le forum mathématique, ma question étant plus théorique qu'appliquée à un langage de programmation quel conque.
Quoi qu'il en soit, je ne sais toujours pas comment je dois interpréter ce " \ ", d'une certaine manière, je me suis dit que la soustraction pouvait avoir un sens, s'il s'agit de soustraire tout le nœud, bien que cela coince un peu dans ma façon de visualiser le problème, on pourrait imaginer :
Un arbre avec 5 nœuds :
La soustraction du nœud 2, permet de s'abstraire des nœuds 4 et 5 et ainsi de vérifier seulement le haut de l'arbre et non les branches suivantes ?
Cela me semble tout de même un peu tirer par les cheveux comme explication.
D'une part, on vide h, et on le réinitialise avec 9 éléments, en retirant la valeur mini : [[h]]←![[h]]\{min(![[h]])}
D'autre part on récupère la valeur mini de h
Et on renvoie une structure avec un tableau de 9 nombres, et un nombre seul.
En relisant la syntaxe de déclaration :
extrais_min(tas):t
J'interprète cela de façon très légèrement différente, et je pense qu'en retour, on a un tableau de 10 éléments dans mon exemple, et on a simplement mis l'élément mini en dernier, les autres éléments sont restés triés comme en entrée.
J'ai interprété comme toi également, bien que la syntaxe devrait peut-être alors être : extrais_min(tas):void
Cela me semble être tout de même plus plausible que ta deuxième interprétation, d'autant que pour compléter j'ai sa correspondance en structure concrète :
fonction extraire_min(tas h) =
soit l:= longueur(h)-1;
h.[0] <-> h.[l];
supprimer l'indice l de h;
descend(h,0)
La cellule qui contient la valeur la plus petite h.[0] est échangée avec la cellule qui contient la valeur la plus grande h.[l] Ensuite la cellule h.[l] est supprimée Pour finir, la valeur de h.[0], dorénavant la plus grande du tas, redescend jusqu'en bas du tas Donc, je pense que l'on voit bien que le tableau est réduit de 1
(il manque le renvoie de la valeur minimum, mais je pense que cela est juste un ajout dans la structure de données abstraite, et que l'important de cette fonction, est surtout de retirer la valeur minimum du tas, car aucune autre fonction ne le fais; pour connaître la valeur minimum du tas, on a déjà la fonction minimum)
En revanche, cela ne permet toujours pas de comprendre le cas de la précondition de remonte :
pour tout i ϵ [1, |h| - 1] \ [[nœud]], [[ h[pere(i)] ]] <= [[ h.[i] ]]
Pour compléter voici la structure concrète de remonte() :
fonction remonte(tas h, entier nœud) =
si nœud≠0 ET h.[nœud] < h.[pere(nœud)] alors
h.[nœud]<->h.[pere(nœud)];
remonte(h, pere(nœud))
Il y a également l'invariant de remonte() qui garantie que le tas est correctement ordonné, le père est plus petit que le fils, et donc l'élément le plus petit est en racine (sur h.[0]) :
pour tout i ϵ [1, |h| - 1], [[ h[pere(i)] ]] <= [[ h.[i] ]]
Du coup la seule différence avec la précondition est l'ajoute de "\ [[noeud]]", il est précisé que cette précondition est une relaxation de l'invariant. Mais cela ne me permet pas d'en comprendre la signification.
J'ai obtenu une réponse de la part de l'auteur de ces énoncés, le symbole "\" en mathématiques signifie "privé de", donc:
-extrait_min renvoie un tas où on a enlevé le minimum; le deuxième min après le " ; " est une erreur dans l'énoncée.
-dans la précondition, on enlève l'indice "noeud" de l'ensemble des entiers compris entre 1 et |H|-1.
Merci encore pour votre aide, je passe le topic en résolu
Structure de données abstraite "file de priorité"
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Pas d'aide concernant le code par MP, le forum est là pour ça :)