Licence Info
Algorithmique Avancée
TD 2: Octobre 2006

1. On considère l'algorithme glouton pour le problème du sac-à-dos discret, qui consiste à regarder tous les objets dans leur ordre de valeur/poids et de mettre un objet dans le sac si son poids ne dépasse pas la capacité restante.

   • Est-il vrai que cette méthode est garantie de trouver une solution avec valeur totale au moins 50% de celle de la solution optimale?
   • Quel est le plus grand c pour lequel cette méthode est garantie de trouver une solution avec valeur totale au moins c fois celle de la solution optimale?
2. Dessiner l'arbre engendré par l'insertion dans un arbre binaire de recherche (vide au départ) de:

   1. 10, 15, 8, 20, 30, 12
   2. 8, 10, 15, 20, 30, 12
   3. 10, 15, 20, 30, 8, 12

3. 1. Combien y a-t-il de formes possibles d'un arbre binaire; de 2 sommets, de 3 sommets, de 4 sommets, de 5 sommets?
   2. Si j'insère les entiers 1, 2, 3, 4, 5 (dans un arbre binaire de recherche vide au départ) dans un ordre aléatoire, montrer un arbre avec probabilité 1/120 d'être engendré et un autre avec probabilité 1/15; quelles sont les autres probabilités possibles pour d'autres arbres?
   3. Selon les mathématiciens la hauteur moyenne d'un arbre binaire de n sommets est Ω(√n) mais selon le cours elle est O(log n); expliquez la contradiction.

4. 1. Donner du code pour les deux types de rotations utilisées pour rééquilibrer des arbres AVL. On supposera que P est une variable de type pointeur qui pointe vers la racine de l'arbre où le rééquilibrage est nécesaire et que le sous-arbre rendu trop haut par l'insertion est celui de droite (l'image miroir des exemples vus en cours.)
   2. Si la hauteur de l'arbre était h avant la rotation quelles sont les hauteurs possibles après?

---

File translated from T_EX by T_TH, version 3.05.
On 4 Oct 2006, 16:43.