Algorithmique Avancée - Contrôle Continu - Master MSID (S1) - Université Mohammed V de Rabat - 2023/2024 PDF

Université Mohammed V de Rabat Faculté des Sciences Master MSID (S1) Année Universitaire 2023/2024 Algorithmique Avancée [Contrôle Continu (Duré...

Université Mohammed V de Rabat Faculté des Sciences Master MSID (S1) Année Universitaire 2023/2024 Algorithmique Avancée [Contrôle Continu (Durée : 30mn)] ———————————————– Correction ———————————————– 1. Quelle propriété d’un arbre n’est pas toujours conservée par une rotation ? a) son nombre de feuilles b) son nombre de racines c) son nombre de nœuds d) son nombre d’arêtes Justification : Une rotation peut modifier la structure de l’arbre et entraîner un changement dans les feuilles (nœuds sans enfant). Cependant, le nombre de racines, de nœuds, et d’arêtes reste constant. 2. Lors d’une double rotation pour le rééquilibrage d’un arbre AVL, deux nœuds sont utilisés comme départs pour une rotation dans un sens puis dans l’autre. Ces deux nœuds sont : a) un nœud puis son fils b) un nœud puis son père c) un nœud puis son frère d) deux nœuds quelconques Justification : (Je ne suis pas sûr de cette réponse.) 3. Laquelle de ces structures de données utiliseriez-vous pour implémenter efficacement une file de priorité ? a) une liste b) une table de hachage c) un tas d) un graphe Justification : Un tas (notamment un tas binaire) permet d’implémenter efficacement une file de priorité. Il permet d’insérer un élément et d’en extraire un avec la priorité maximale ou mini- male en temps logarithmique (O(log n)), ce qui est optimal pour ce type de structure. Les autres structures proposées (liste, table de hachage, graphe) ne permettent pas d’effectuer ces opérations aussi efficacement. 4. On veut ranger n entiers dans une structure de données de façon à pouvoir ajouter de nouveaux entiers et en supprimer en temps O(log n). On veut aussi pouvoir chercher le plus petit entier plus grand qu’un entier donné en temps O(log n) dans le pire cas. Quelle structure proposez-vous d’utiliser ? a) une liste b) une table de hachage c) un tas d) un arbre AVL Justification : Un arbre AVL est un arbre binaire de recherche auto-équilibré qui permet de maintenir un ordre sur les éléments. Il garantit que les opérations d’ajout, de suppression et de 1  recherche (y compris la recherche du plus petit entier plus grand qu’un entier donné) sont effectuées en temps logarithmique (O(log n)) dans le pire cas. Les autres structures (liste, table de hachage, tas) ne garantissent pas ces performances pour toutes les opérations spécifiées. 5. Quelle est la complexité d’une opération de rotation à gauche à la racine d’un arbre AVL contenant n nœuds ? a) O(1) b) O(log n) c) O(n) d) O(n log n) Justification : La rotation à gauche à la racine d’un arbre AVL consiste à réorganiser les pointeurs de la racine et de ses enfants immédiats. Cette opération ne nécessite de modifier qu’un nombre constant de nœuds, et donc sa complexité est Θ(1), c’est-à-dire en temps constant. 6. Combien de nœuds un arbre AVL de hauteur 3 contient-il au minimum ? a) 5 b) 6 c) 7 d) 15 Justification : Le nombre minimum de nœuds d’un arbre AVL de hauteur h est donné par la relation de récurrence N (h) = N (h − 1) + N (h − 2) + 1, où N (h) représente le nombre minimum de nœuds pour un arbre AVL de hauteur h. En appliquant cette relation : N (0) = 1, N (1) = 2 N (2) = N (1) + N (0) + 1 = 2 + 1 + 1 = 4 N (3) = N (2) + N (1) + 1 = 4 + 2 + 1 = 7 Ainsi, un arbre AVL de hauteur 3 contient au minimum 7 nœuds. 7. Dans un arbre AVL vide, on insère dans l’ordre les clés suivantes : 20, 40, 15, 25, 30, 80, 75, 95, 35, 90. Quelle clé serait à la racine de l’arbre AVL après avoir inséré toutes les clés ? a) 75 b) 40 c) 35 d) 30 Justification : 8. On implémente un annuaire à l’aide d’une table à adressage direct : à un login est associé un en- semble d’informations liées à une personne. Laquelle des opérations suivantes est la plus coûteuse ? a) insérer une nouvelle personne b) rechercher une personne ayant un login donné c) supprimer une personne ayant un login donné d) ces 3 opérations ont le même coût. Dans une table à adressage direct, l’accès aux éléments est effectué directement à l’index correspon- dant au login, ce qui permet d’effectuer toutes les opérations (insertion, recherche et suppression) en temps constant, c’est-à-dire en O(1). Chaque opération consiste à accéder à un index spécifique dans la table, et aucune recherche ou comparaison supplémentaire n’est nécessaire. Ainsi, les opé- rations d’insertion, de recherche et de suppression ont toutes un coût de O(1), et donc elles ont le même coût. 9. Le parcours en largeur d’un tas-min H est 5, 10, 8, 12, 20, 70, 21, 35, 32, 23. Si un élément 9 est inséré dans H, alors le parcours en ordre postfixe de H sera : 2  a) 35, 32, 23, 20, 12, 10, 70, 21, 9, 8, 5 b) 35, 32, 12, 23, 20, 10, 9, 70, 21, 8, 5 c) 35, 12, 32, 9, 23, 10, 20, 5, 70, 21, 8 d) 35, 32, 12, 23, 20, 9, 10, 70, 21, 8, 5 Justification : Avant d’insérer l’élément 9 dans le tas-min H, analysons d’abord l’état actuel du tas. Le parcours en largeur (ou niveau) du tas donné est le suivant : 5, 10, 8, 12, 20, 70, 21, 35, 32, 23 Cela représente un arbre binaire où chaque nœud satisfait la propriété du tas-min (le parent est toujours plus petit que ses enfants). Étapes de l’insertion de l’élément 9 : 1. Insertion de 9 : Le tas est complet à ce niveau, donc 9 est inséré à la fin du tableau, ce qui donne : 5, 10, 8, 12, 20, 70, 21, 35, 32, 23, 9 2. Réajustement (percolation vers le haut) : Après l’insertion, l’élément 9 doit être comparé avec son parent. L’élément 9 est inséré après 23, donc son parent est 23. - 9 < 23, donc on échange 9 avec 23. Ce réajustement donne : 5, 10, 8, 12, 20, 70, 21, 35, 32, 9, 23 3. Nouvelle vérification de la condition de tas : Ensuite, l’élément 9 est comparé avec son nouveau parent, qui est 12. - 9 < 12, donc on échange 9 avec 12. Ce réajustement donne : 5, 10, 8, 9, 20, 70, 21, 35, 32, 12, 23 4. Vérification finale : Maintenant, 9 est comparé avec son nouveau parent, qui est 10. - 9 < 10, donc on échange 9 avec 10. Ce réajustement donne finalement : 5, 9, 8, 10, 20, 70, 21, 35, 32, 12, 23 Après ces échanges, l’élément 9 est correctement positionné dans le tas-min. 10. Combien de feuilles un arbre binaire de hauteur h contient-il au maximum ? a) h b) 2h c) 2h d) 2h − 1 Justification : Un arbre binaire complet (ou parfait) de hauteur h contient au maximum 2h feuilles. Cela peut être compris en observant que chaque niveau de l’arbre double le nombre de nœuds par rapport au niveau précédent : - Le niveau 0 (la racine) contient 1 nœud. - Le niveau 1 contient 2 nœuds. - Le niveau 2 contient 4 nœuds, et ainsi de suite. Le nombre total de feuilles dans un arbre binaire parfait est donc 2h , car ce sont les nœuds du dernier niveau qui constituent les feuilles de l’arbre. Par conséquent, un arbre binaire de hauteur h peut contenir au maximum 2h feuilles. 11. Quelle est la complexité de la pire performance d’une recherche d’élément dans une table de hachage à adressage fermé (de taille m contenant n éléments) ? Réponse : O(n) Justification : Dans une table de hachage à adressage fermé (ou chaîné), chaque position du tableau contient une liste ou une chaîne de collisions. Dans le pire des cas, tous les éléments peuvent se trouver dans la même chaîne, ce qui conduit à une recherche dans une liste linéaire, avec une complexité O(n). 3  12. Quelle est la complexité de la pire performance d’une recherche d’élément dans une table de hachage à adressage ouvert (de taille m contenant n éléments) ? Réponse : O(m) Justification : Dans une table de hachage à adressage ouvert, les éléments sont stockés directement dans le tableau. En cas de collisions, la recherche continue à travers les positions suivantes jusqu’à trouver l’élément ou un emplacement vide. Dans le pire des cas, une recherche peut nécessiter de parcourir tout le tableau, ce qui donne une complexité O(m), où m est la taille du tableau. Exercice de Programmation : Écrire en C la fonction, void affiche_impair(Arbre Bin Abr), qui affiche en ordre croissant tous les éléments (des nombres entiers) d’un arbre binaire de recherche Abr qui sont des nombres impairs. Écrire en C la fonction, int nbre_feuille(Arbre Bin Ab), qui retourne le nombre de feuilles d’un arbre binaire Ab. 4