TD6 Complexité
Télécharger le TD6 Complexite en pdf
Page 1 : Pré-ING1Semestre 2 - 2022/2023Informatique IITD 6 : ComplexitéLes exercices de ce TD mise à part l’exercice 1, sont résolvables par le calcul direct ou la programmation.Exercice 1Soit le jeu suivant consistant à tirer au sort un "vainqueur" parmi un groupe d’enfants, au moyen d’une pièce de monnaie :• S’il n’y a qu’un enfant, il est évidemment vainqueur.• S’il y en a plusieurs, on lance la pièce. Si c’est face qui sort, on élimine au hasard par un jeu de type "chaises musicales"par exemple un des enfants ; si c’est pile on en élimine deux à moins qu’il n’en reste que deux, auquel cas on n’en éliminequ’un.• Le gagnant est le dernier enfant non éliminé.Si l’on considère le lancer d’une pièce comme opération fondamentale.1. Trouver l’équation de récurrence correspondant à ce jeu dans le cas moyen.2. Montrer par récurrence, à partir de cette équation, que l’algorithme précédent est en On, où n est le nombre initiald’enfants considerer le pire cas, c’est à dire maximiser le nombre d’opérations à effectuer.Exercice 2On considère le code suivant :PROGRAMME Test5VARIABLESi,s,j : EntierDEBUTi ←5Tant que i 0s ←0Pour j de 0 à is ←s + 1Fin pouri ←i – 1Fin de tant queFINCalculer sa complexité en nombre de comparaisons, d’affectations et d’opérations arithmétiques. Vérifier votre réponsepar la programmation.Exercice 3On considère la fonction suivante :FONCTION exn : Entier : EntierVARIABLESa, b : EntierDEBUTa ←2 b ←1Tant que a na ←a2b ←b + 1Fin de tant queretourner bFIN1. Que vaut exn si n est une puissance de 2 ? Que vaut exn Pour un argument n quelconque ?2. Quelle est la complexité de cette fonction en nombre de comparaisons, de multiplications et d’affectations en fonctionde n.Exercice 4Donner l’ordre de complexité des algorithmes suivants en fonction des variables n et m1
Page 2 : a DEBUTx ←1Pour i de 0 à n fairePour j de 0 à m fairex ←x+1Fin pourFin pourFINb DEBUTx ←1Pour i de 0 à n fairex ←x+1Fin pourPour j de 0 à m fairex ←x+1Fin pourFINc DEBUTx ←1Pour i de n à n+7 fairePour j de m à m+4 fairex ←x+1Fin pourFin pourFINd DEBUTx ←1i ←1j ←1Tant que i=n et j=m fairex ←x+1i ←i+1j ←j+1Fin de tant queTant que i=n fairex ←x+1i ←i+1Fin de tant queTant que j=m fairex ←x+1j ←j+1Fin de tant queFINExercice 51. Quel est le nombre d’additions réalisées par l’algorithme suivant dansa le meilleur casb le pire casc le cas moyen, en supposant que les valeurs de T sont aléatoires equiprobables entre 1 et 100 inclus.Fonction foo T tableau d’entier de taille N : entierVARIABLESi,s : entierDEBUTs ←0Pour i de 0 à N faireSiTiTi100 alorss←s + TiFin siFin pourretourner sFIN2
Page 3 : 2. Voici deux versions différentes permettant de calculer nk. Comparer leur ordre de complexité il suffira de s’intéresserà un seul type d’opération élémentaire :Fonction puissancen,k : entier : entierDEBUTSik=0 alorsretourner 1Sinonpuissance ←npuissancen,k-1Fin siFINFonction puissanceV2n,k : entier : entierDEBUTSik=0 alorsretourner 1Sinon Si k mod 2 = 0retourner puissanceV2nn, k DIV 2Sinon Siretourner x puissanceV2n,k-1Fin siFIN3
