Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Première année, S2 1 ISITCOM H-S Département Informatique Mohamed EL OUNI TD—Al

Première année, S2 1 ISITCOM H-S Département Informatique Mohamed EL OUNI TD—Algorithmique et structure de données et complexité Classe : 1LM Février 2021 Première année, S2 2 PREFACE Ce fascicule des travaux dirigés d’algorithmique et structures de données et complexité est à l’intention des étudiants de la première année en Licence (1LM + 1IOT). Il aborde brièvement les thèmes les plus classiques et les plus utilisés en informatique : la récursivité, les listes chainées, les piles, les files et les arbres binaires de recherche. Le fascicule comporte 4 TD qui sont réparties comme suit : TD1 : La récursivité TD2 : Les pointeurs et Les listes chainées TD3 : Les piles et les files TD4 : Les arbres binaires de recherche Première année, S2 3 Table des matières TD n°1—La récursivité ………………………...................................................4 TD n°2-- Les pointeurs et Les listes chainées.............................................6 TD n°3 -- Les piles et les files ……………………………………………………7 TD n°4-- Arbre binaire de recherche.................................................................8 BIBLIOGRAPHIE ........................................................................................... 9 Première année, S2 4 TD1—La récursivité Objectifs - Résoudre des programmes récursifs. - Comprendre la démarche de transformation d’un programme itérative en un programme récursive. - Savoir les avantages de l’utilisation de la récursivité pour résoudre les problèmes. EXERCICE 1 1. On souhaite écrire une fonction récursive qui calcule le carré d'un entier. Pour trouver un lien entre carre(n) et carre(n-1), on utilise la formule donnée en énoncé : (n + 1)2 = n2 + 2n + 1. En changeant n en n -1. 2. On veut écrire une fonction récursive qui calcule la somme de 1 à un entier n : 1+2+3+ +(n -1) + n. EXERCICE 2 On rappelle que les nombres de Fibonacci sont définis de la façon suivante : F0=F1=1 Fn = Fn -1 + Fn -2 pour n≥2 1. On applique la définition : F2= ? F3= ?, F4= ?, F5= ?. 2. Pour écrire une fonction récursive qui calcule le nième nombre de Fibonacci, il suffit d'utiliser directement les formules de l'énoncé. 3. Comment écrire une fonction itérative (c'est-‡-dire sans appel récursif) qui calcule la même chose ? On remarque que pour calculer Fn, il faut connaître Fn- 1 et Fn- 2. Mais pour avoir Fn- 2, il faut connaître Fn -3 et Fn- 4 … EXERCICE 3 On définit la fonction suivante : Fonction McCarthy(n : Entier) : Entier Debut Si (n>100) Alors Renvoyer(n-10) Sinon Renvoyer(McCarthy(McCarthy(n+11))) FinSi Fin 1.Pour n > 100, McCarthy(n) ? 2.McCarthy(98) ? 3.En déduire la valeur de McCarthy(n) pour n ≤ 100. Expliquer. Première année, S2 5 TD2—La récursivité EXERCICE 4 Soit la fonction récursive suivante : Fonction mystère (n, p : entier) : entier Début Si (p < 1) alors mystère <-- 0 Sinon mystère <-- n + mystère (n, p-1) Finsi Fin 1. Exécutez à la main la fonction mystère en laissant sur votre copie la trace de l’exécution pour les valeurs respectives 5, 4 pour n et p. 2. Dites ce que fait l’algorithme de cette fonction. 3. Est-ce que la fonction peut être utilisée pour un entier positif et un entier négatif ? 4. Est-ce que la fonction peut être utilisée pour deux entiers négatifs ? 5. Proposez une solution itérative. Première année, S2 6 TD2-- Les pointeurs et les listes chainées Objectifs : - Savoir déclarer, construire des listes chainées. - Manipuler, traiter et apprendre à utiliser des listes chainées. - Distinguer entre les différents types de listes chainées. QUESTIONS DE COURS 1. Qu’est-ce qu’un pointeur ? 2. Quelle est la différence entre une structure de données statique et une structure de données dynamique ? EXERCICE 1 Soit une liste d’entiers L, écrire les actions paramétrées suivantes permettant : 1- Le calcul du nombre d’éléments, et la détermination du maximum et du minimum ; 2- L’insertion d’une valeur val donnée dans une liste triée ; 3- La suppression des doublons (éléments identiques) ; 4- La création de la liste miroir de L (avec ensuite sans création d’une nouvelle liste) ; 5- La duplication d’une liste au début / à la fin; 6- La fusion de deux listes triées d’entiers L1 et L2 en une liste triée L3 ; EXERCICE 2 Soit T un tableau de 26 listes de chaînes de caractères. La liste 1 contient des mots commençant par la lettre ‘A’, la liste 2 contient des mots commençant par la lettre ‘B’…etc. Déclarer T et écrire une Fonction permettant de vérifier l’existence d’un mot M dans la structure. EXERCICE 3 Soient deux listes L1 et L2 de valeurs entières positives : Ecrire une action paramétrée permettant de déplacer (sans allocation ni libération) les valeurs paires de L1 vers L2, et de déplacer les valeurs impaires de L2 vers L1 ; EXERCICE 4 1. Écrire la procédure AjouterTete qui permet d’ajouter au début d’une liste circulaire L un entier e. 2. Écrire la procédure AjouterFin qui permet d’ajouter à la fin d’une liste circulaire L un entier e. 3. Écrire une procédure Affiche qui affiche la liste circulaire qui lui est passée en argument. Première année, S2 7 TD5-- Les piles et les files Objectifs : - Définir et manipuler une pile et une file - Savoir différencier entre la structure d’une pile et la structure de celle d’une file. QUESTIONS DE COURS 1. Rappeler la définition d’une pile et donner les contraintes d’accès à cette dernière. 2. Rappeler la déclaration d’une pile est ces modules de manipulation. 3. Qu’est-ce qu’une file. Présenter un graphe illustrant l’accès à cette derrière. 4. Rappeler la déclaration d’une file est ces modules de manipulation. EXERCICE 1 Copie d’une pile Ecrire une fonction pile_copy(s) recevant une pile (s) comme argument et renvoyant une copie s2 de s. Attention, la pile s doit (bien sûr) être conservée ! Evaluer le coût en mémoire et le nombre d’opérations de la fonction. EXERCICE 2 Ecrire une fonction pile_reverse recevant une pile (s) comme argument et renvoyant une copie inversée rs de s. Attention, la pile s doit être conservée ! Evaluer le coût en mémoire et le nombre d’opérations de la fonction. EXERCICE 3 Permutations circulaires (acte 1) Ecrire une fonction pile_circperm qui reçoit en argument une pile s et un entier n et effectue sur la pile n permutations circulaires successives. Dans cet exercice, c’est la pile s elle-même qui sera modifiée. Exemple avec n=2 : 7 - 11 – 98 – 2 -103 donnera 97- 2- 103 -7 -11 Evaluer le coût en mémoire et le nombre d’opérations de la fonction. EXERCICE 4 Permutations circulaires Reprendre les exercices 1 et 3 de la partie « Piles » mais en traitant cette fois le cas d’une file. Première année, S2 8 TD6-- Arbre binaire de recherche Objectifs : - Définir, créer et manipuler un arbre binaire de recherche. - Savoir comment parcourir un arbre binaire de recherche ? - Trouver un élément dans un arbre. - Savoir passer d’une structure dynamique d’un arbre vers une structure statique représentée par un vecteur. - Savoir fusionner deux arbres. - Connaitre les différents types d’arbres : dégénéré, complet ou parfait. QUESTIONS DE COURS 1. Qu’est-ce qu’un arbre binaire de recherche ? 2. Quel est le nombre minimal des nœuds que peut avoir un arbre binaire de recherche à 5 niveaux ? 3. Combien y a-t-il de formes d’arbres binaire différents à (respectivement) 1, 2, 3, 4 nœuds. EXERCICE 1 Considérer l’ensemble des clés 1, 4, 5, 10, 16, 17, 21. 1. Dessiner des arbres binaires de recherche de cet ensemble de clés avec une hauteur de 2, puis 4, et ensuite 6. 2. Donner les différents types de parcours en profondeur vues en cours (pour l’arbre binaire de recherche de hauteur 2. 3. Ecrire une fonction qui calcule le nombre de nœuds internes d’un arbre binaire. EXERCICE 2 1. Écrire une fonction qui calcule la taille d’un arbre binaire. 2. Écrire une fonction qui calcule la hauteur d’un arbre binaire. 3. Écrire une fonction qui calcule le nombre de nœuds externes (feuilles) d’un arbre binaire. 4. Écrire une fonction qui calcule le nombre de nœuds internes d’un arbre binaire. 5. Écrire une fonction qui calcule la longueur de cheminement externe d’un arbre binaire. EXERCICE 3 Écrire une procédure qui permet de copier un arbre binaire A dans un deuxième arbre B. EXERCICE 4 Écrire une procédure qui permet de fusionner deux arbres binaires A et B, et de renvoyer un arbre C qui contient les deux arbres. Discuter les différents cas possibles. Première année, S2 9 BIBLIOGRAPHIE S. ROHAUT : Algorithmique et Techniques fondamentale de programmation, Edition Eni 2007. LIGNELET P., Algorithmique. Méthodes et modèles, Paris : Masson, 1985. www.intelligentedu.com/blogs/post/free_computer_books/3760/the-algorithm-designmanual/fr/ uploads/Science et Technologie/ fasciculeasdii-lm.pdf