Discussion :

[nikofybc]

Bonjour tout le monde !
Voila jai un sujet d'algorithme, je suis en master et j'ai des difficultés dans cette matière du fait que je suis dans un option réseau...
Je vous poste le sujet si quelqu'un pourrait m'aider et me donner un TRES grand coup de main ca serait super

sujet :
On considère un ensemble de n objets munis chacun d’une valeur entière et numérotés de 1 à n.
Ces objets peuvent être rangés dans tout type de structure de données (case d’un tableau, nœud d’un arbre…).
On désire structurer ces objets de façon que, une fois la structure
construite, on ait les propriétés suivantes :
- il est possible en O(1) de déterminer un objet de plus grande valeur ;
- il est possible en O(log n) de retirer un objet de plus grande valeur et reconstituer alors
la structure pour qu’elle conserve la propriété précédente (avec n – 1 objets).
1. Proposer une structure(dite ci-dessous structure de rangement) permettant de réaliser cet objectif.


Si quelqu'un a tout compris (oui je n'ai strictement rien compris) ça serait super de m'aider.
Merci beaucoup !
Niko

[ToTo13]

Bonjour,

alors décortiquons un peu le problème :
- des objets ayant des valeurs entières. Imagine une structure type C à un seul champ de type entier. Ben c'est ton objet...
- tu dois créer une structure de stockage, organisation... par exemple une liste chaînée, un graphe, une table de hachage...
- la structure que tu vas créer, dois avoir les propriétés qui sont indiquées lorsque tu retires ou ajoute un élément.

Voilou

[nikofybc]

merci pour ta reponse jy vois deja un peti peu plus claire
par contre que représent O(1) et O(log n) ??

[Hanz Peter Mariol]

Les O sont sensé représenter tes complexités d'algorithme. La realisation de ta premiere tache doit etre indépendante des parametres de ta structure, complexité constante (O(1)), tandis que la réalisation de la seconde a une complexité logarithmique, donc relative au nombre de données à traiter, mais non linéairement(la courbe du logarithme a tendance a s'afesser avec le temps)
J'espère avoir un peu aidé.
Bon appetit!

[wiztricks]

On désire structurer ces objets de façon que, une fois la structure
construite, on ait les propriétés suivantes :
- il est possible en O(1) de déterminer un objet de plus grande valeur ;
- il est possible en O(log n) de retirer un objet de plus grande valeur et reconstituer alors la structure pour qu’elle conserve la propriété précédente (avec n – 1 objets).

La structure qui me paraîtrait la plus adaptée serait une liste circulaire dont les éléments sont rangés par ordre croissants:
- trouver le plus grand = le dernier de la liste = O(1)
- retirer le plus grand = retirer le dernier = O(1) meilleur que O(log(n)).
Quel pourrait être le container qui ait ces propriétés?
- W

[Jedai]

Visiblement, la question est orientée pour aboutir à un tas binaire. Je te laisse faire tes recherches sur le net pour trouver la description de cette structure de données.

(wiztricks : ta suggestion est bonne dans l'absolu, mais en réalité les tas sont utilisés pour créer des files de priorité et ils ont certains avantages par rapport à ta suggestion, par exemple ils se créent en O(n) plutôt que O(n log n), et ajouter un élément à un tas coûte seulement O(log n) plutôt que O(n) dans ta liste triée. Bien sûr la question aurait dû préciser cette dernière complexité aussi mais ... )

--
Jedaï

[wiztricks]

(wiztricks : ta suggestion est bonne dans l'absolu, mais en réalité les tas sont utilisés pour créer des files de priorité et ils ont certains avantages par rapport à ta suggestion, par exemple ils se créent en O(n) plutôt que O(n log n), et ajouter un élément à un tas coûte seulement O(log n) plutôt que O(n) dans ta liste triée. Bien sûr la question aurait dû préciser cette dernière complexité aussi mais ... )

Tu penses à un tas binaire rangé par ordre décroissant?
- W

[Jedai]

Tu penses à un tas binaire rangé par ordre décroissant?
- W

Un max-heap est ce que les complexités demandées suggèrent. Même si elles ne l'imposent pas parce qu'il n'y a pas suffisamment de détails.

--
Jedaï

[nikofybc]

Merci beaucoup pour votre aide ca m'avance deja pas mal, je ne peux pas vous donner plus de détails car je vous ai copié collé le sujet tel que je l'ai eu....je vais faire des recherches sur ce que vous m'avez expliqué
un grand merci

[SpiceGuid]

Visiblement, la question est orientée pour aboutir à un tas binaire.

Tas binaire, file de priorité (voir heap-sort et consort).

La structure qui me paraîtrait la plus adaptée serait une liste circulaire dont les éléments sont rangés par ordre croissants

Jedai a raison, qui dit liste chaînée dit insertion en O(n), donc "inefficace".

[wiztricks]

Jedai a raison, qui dit liste chaînée dit insertion en O(n), donc "inefficace".

Il y a des contraintes sur la complexité pour trouver l'élément max ou le retirer mais nada côté insertion. Et le vrai truc qui coince est la complexité de la suppression qui est O(1) pour la liste chainée alors que l'exercise voudrait un O(log(n)).

- W