Devoir 5

Devoir 5: comparaison d’arbres évolutifs (algorithmique de l’arbre binaire).

Énoncé: devoir5

 

Publicités

23 commentaires

    1. Bonjour,

      c’est du travail individuel. (Lignes directrices usuelles: (1) Vous avez le droit d’en discuter entre vous en personne, mais ne prenez/échangez pas de notes, ni écrites ni numériques. (2) Écrivez votre rapport en s’appuyant sur vos propres ressources mentales. (3) Citez vos sources, s’il y en a. 🙂

      J'aime

      Réponse

  1. Bonjour,

    Pour la question 5.1b), que voulez-vous dire par « par les récurrences de (5.1).?

    J’en comprends que notre algo doit être récursif, mais doit-on utiliser nécessairement utiliser l’algo en 5.1a) pour déterminer N(x)? Ça me semble absurde puisque 5.1a) génère idx..On se retrouverait donc à régénérer inutilement idx.

    Merci de votre aide,
    Bonne soirée!

    J'aime

    Réponse

    1. C’est exactement les même formules pour la récession, sauf que idx[] est déjà calculé: on utilise le même indexage à travers les arbres différents pour les espèces placés aux noeuds externes. En conséquence, N(x), R(x), L(x) peuvent être comparés à l’arbre de référence (1er arbre) et ainsi on trouve l’équivalence pour noeud x.

      J'aime

      Réponse

  2. Bonjour!

    Ma question concerne la partie 5.2.
    Je me demandais si H[0..n-1] était un tableau de tableau de grandeur 2 (Pour l’indice L et pour l’indice R).
    Parce que je ne suis pas sûre de grand comprendre à quoi réfère la cellule H[R] ou H[L] dans le tableau.
    En fait, je comprends plus ou moins cette phrase de l’énoncé:
    « Dès qu’on détermine l’intervalle L..R = L(x)..R(x) au nœud interne x ∈ T1, on met L..R soit dans la cellule H[R], soit dans la cellule H[L]. »

    Merci!

    J'aime

    Réponse

    1. Il y a plusieurs façons de représenter les intervalles dans H[]. Mais pour toute intervalle a..b, on la trouvera soir dans la cellule a, soit dans la cellule b. P.e. l’example de figure 3 montre l’intervalle 2..7 qui se trouve dans cellule 2.

      (1) classe dédiée (variables privées L et R): Interval[] H;
      (2) 2 entiers, dans petits tableaux de taille 2: int[][] H
      (3) juste un seul entier: int[] H Parce que toute cellule H[i] contient soit une intervalle i..j ou j..i avec j quelconque => il suffit de stocker j.

      J'aime

      Réponse

  3. Serait-il possible d’avoir nos notes du devoir2 et devoir 3 pour avoir une idée de comment évolue nos notes pour ce cours?

    Car, nous ne faisons que des devoirs et aucune note n’est affichée a part le devoir1.

    Faites l’effort d’afficher les notes.

    J'aime

    Réponse

  4. Bonjour,

    Pour 5.2, l’énoncé dit que pour un noeud x, H[R(x)] est vide si x est le premier enfant ou H[L(x)] est vide quand x nest pas premier enfant. Mais selon la figure 3, pour [2..3], H[2] et H[3] son tout les deux remplie.
    Pouvez-vous nous clarifier cet énoncé?

    Merci!

    J'aime

    Réponse

    1. Lors du parcours, on visite l’ancêtre commun de H et A; c’est l’intervalle 2..3 et on peut la mettre dans cellule 3. Plus tard, on visite son parent qui est l’ancêtre de H,A,E,F,C,G avec l’intervalle 2..7 et on peut la placer en cellule 2.

      J'aime

      Réponse

  5. Pour 5.2, l’algorithme ne semble pas tenir pour les noeuds externes…
    Est-ce qu’il faut les ignorer lors du remplissage du tableau H?

    J'aime

    Réponse

    1. Bonjour,

      Moi aussi je me posais cette question. L’exercice demande plus que quelques lignes de code. Cela implique des classes et des méthodes qu’il est nécessaire (selon ce que je comprends) de bien définir.

      Sinon je pourrais y aller avec simplement :

      MYSpecialTree tree = new MySpecialTree();
      tree.execute();

      Ce qui est génant et pas très intéressant.

      Donc j’en déduit que dans mon pseudo code je dois définir ce qui ce passe dans mon arbre (methodes, etc.) et comment mes noeuds fonctionnent et comment mes clades fonctionnent, etc.

      Ce qui revient à expliciter pratiquement tout le code, non?

      Merci de répondre rapidement.

      J'aime

      Réponse

  6. Donc si j’ai bien compris, vu qu’on parle de gorilles dans l’énoncé. Si Harambe tire la jambe gauche de l’enfant on va a droite dans H(R)?

    J'aime

    Réponse

  7. Monsieur Miklos,

    Pourquoi vous repondez aux messages concernant le devoir mais vous ne repondez JAMAIS quand on vous pose la question sur NOS NOTES des devoirs. Il me semble que sur le reglements les etudiant ont droit a leurs note avant la date limite d’abondon, hors nous n’avons a ce jour, PAS ENCORE recu nos notes. Cela est intolerable d’autant plus que la session est pratiquement terminé !
    Il est de votre responsabilité d’agir s’il vous plait.

    Merci

    J'aime

    Réponse

  8. Bonjour,

    Je ne comprends pas ce qu’il faut prouver dans la deuxième partie du devoir.

    Est-ce qu’il est possible de l’expliquer en d’autre mots?

    Merci.

    J'aime

    Réponse

Posez votre question ou ajoutez un commentaire (bien sûr, ne compte pas dans la note finale)

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s