TD06 Complexite
Télécharger le TD06 Complexite en pdf
Page 1 : Pré-ING1Semestre 2 - 2024/2025Informatique 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 :1. S’il n’y a qu’un enfant, il est évidemment vainqueur.2. 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élimine qu’un.3. 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.1
Page 2 : Exercice 4Donner l’ordre de complexité des algorithmes suivants en fonction des variables n et m :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 queFIN2
Page 3 : Exercice 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. 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
