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:

(a) 10, 15, 8, 20, 30, 12

(b) 8, 10, 15, 20, 30, 12

(c) 10, 15, 20, 30, 8, 12

3. (a) Combien y a-t-il de formes possibles d’un arbre binaire; de 2 sommets, de 3 sommets, de 4 sommets, de 5 sommets?

(b) 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?

(c) Selon les mathématiciens la hauteur moyenne d’un arbre binaire de n sommets est Ω(\sqrt{n}) mais selon le cours elle est O(log n); expliquez la contradiction.

4. (a) 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.)

(b) Si la hauteur de l’arbre était h avant la rotation quelles sont les hauteurs possibles après?