Brahim BESSAA - الموقع الأول للدراسة في
Les Structures de Contrôle (Conditionnelles – Itératives) Exercices Corrigés d’Algorithmique – 1ére Année MI 5 EXERCICE 1 Ecrire un algorithme qui demande un nombre à l’utilisateur, puis calcule et affiche le carré de ce nombre
Complexité des algorithmes - diluniv-mrsfr
Evaluation de T(n) (boucle) Somme des coûts des passages successifs tant que < condition > faire Traitement Ti(n) fin faire Pk i=1 Ti(n) Ti(n) : coût de la i`eme itération souvent défini par une équation récursive Cours complexité – Stéphane Grandcolas – p 8/28
Exercice 1 : Complexité des algorithmes (8 points)
Question 1 1: On considère le code suivant, comportant deux « tant que » imbriqués On cherche à mesurer la complexité de cette imbrication en fonction de n Pour cela, on utilise la variable compteur, qui est incrémentée à chaque passage dans le « tant que » interne def procedure(n) : 1 compteur = 0 2 i = 1 3 while i < n :
Algorithmique et programmation - USTO-MB
l'algorithme mais aussi le programme Fortran correspondant avec éventuellement une ou des variantes et également les données nécessaires à son exécution Toutes les solutions proposées ne sont pas commentées autant que nous l'aurions voulu On soumettra toutes les solutions proposées à une critique attentive
1 BOUCLES ET COMPLEXITE
On dit que f est un O(g) s’ il existe une constante k > 0 telle que pour n assez grand, on ait f(n) = k g(n) On note abusivement f = O(g) et on dit que « f est dominée par g » Par exemple 2n 3 - 15 = O(n), mais n2 est aussi un O(n3) Contrairement aux mathématiciens, les informaticiens diront qu’ un algorithme est « en n2 »
TD 8 : Les boucles en langage C - LIPN
On suppose qu’on utilise la boucle for que lorsque l’on connait les bornes Pensez-vous que l’on peut toujours changer une boucle while par une boucle for Indication: essayer avec l’algorithme suivant (et le programme C associ) : (x entier 1) Si x=1 alors stop Sinon Tant que (x>1) Faire si x pair alors x
Examen écrit de structures de données
Ecrivez un algorithme qui détermine quel est ce nombre de bits (utilisez ce que vous avez fait dans la première partie de cette question) L'algorithme doit être efficace : si n est le nombre de bits, il doit prendre un temps de l'ordre de n et non pas de 2n
Cours d’Algorithmique et structures de données 1
On peut énoncer les cinq propriétés suivantes que doit satisfaire un algorithme : 1 Généralité : un algorithme doit toujours être conçu de manière à envisager toutes les éventualités d’un traitement 2 Finitude : Un algorithme doit s’arrêter au bout d’un temps fini 3
Correction du Partiel THL Theorie des - cours, examens
leur grammaire, puisqu’ils en font deux, alors que leur grammaire n’en accepte qu’un Les accolades sont aussi souvent oubliées Enfin, certains me rajoutent un symbole pour EOF : c’est totalement inutile ici, ça n’est intéressant que lors-qu’on calcule un parseur (LL ou LR), mais quand on fait une étude théorique de la
[PDF] boucle while javascript PDF Cours,Exercices ,Examens
[PDF] boucle while python PDF Cours,Exercices ,Examens
[PDF] boucles d'opérations ( niveau 2nde) 2nde Mathématiques
[PDF] Boucles et fonctions Terminale Informatique
[PDF] bouder quelqu'un en anglais PDF Cours,Exercices ,Examens
[PDF] bouder synonyme PDF Cours,Exercices ,Examens
[PDF] Bougainville, de Brest a Saint-Malo via Tahiti 2nde Histoire
[PDF] Boujour demain j'ai controle sur le calcul littéral et je ne comprend rien 4ème Mathématiques
[PDF] boujour j'ai besoin de vous pour juste 2 exercices d'allemands 2nde Allemand
[PDF] Boujour pouvez-vous m'aider, j'ai un dm de math je n'y arrive pas l'exercice 1 3ème Mathématiques
[PDF] Boujour vous pouvez m'aider s'il vous plait pas très fort en français 4ème Français
[PDF] boujour, es que vous pouvez m'expliquer ce qu'es la lecture analytique 2nde Français
[PDF] boujour, pouvez vous m'aidez rapidement s'il vous plait merci d'avance 3ème Mathématiques
[PDF] boujours j'ai un devoir a faire mais je bloque a une question pouvez vous m'aidez merci d'avance 2nde Mathématiques
Documents et téléphones portables interditsB IH NMUqPH HVP GRQQp j PLPUH LQGLŃMPLIB 7UMYMLOOH] MX NURXLOORQ G·MNRUG
de sorte à rendre une copie propre. Il sera tenu compte de la présentation et de la clarté de vos réponses.
Exercice 1 : Complexité des algorithmes (8 points)Question 1.1 : On considère le code suivant, comportant deux " tant que » imbriqués. On cherche à mesurer la
complexité de cette imbrication en fonction de n. Pour cela, on utilise la variable compteur, qui est incrémentée à
chaque passage dans le " tant que » interne. def procedure(n) :1 compteur = 0
= 13 while i < n :
4 j = i + 1
5 while j <= n :
6 compteur = compteur + 1
7 j = j + 1
8 i = i * 2
a. Quelle est la valeur finale du compteur dans le cas où n = 16 ?b. Considérons le cas particulier où n est une puissance de 2 : on suppose que ݊Lt avec p connu.
Quelle est la valeur finale du compteur en fonction de p ? Justifiez votre réponse. c. Exprimez le résultat précédent en fonction de n. d. En conclure la complexité dans le pire des cas, en notation ܱ a. Pour i=1, j varie de 2 à 16 inclus, on fait donc 15 incrémentations du compteur. Pour i=2, j varie de 3 à 16 inclus, on fait donc 14 incrémentations du compteur. Pour i=4, j varie de 5 à 16 inclus, on fait donc 12 incrémentations du compteur. Pour i=8, j varie de 9 à 16 inclus, on fait donc 8 incrémentations du compteur. Ensuite, i vaut 16, donc on sort du " while i < n ».Au total, on a donc fait 15+14+12+8 = 49 incrémentations du compteur. Donc compteur vaut 49 en sortie du
programme. b.i prend successivement les valeurs suivantes : 20, 21, 22, ... 2p-1, soit 2k avec k variant de 0 à (p-1). Pour chacune de ces
valeurs, on fait (n-i) incrémentations, soit (2p - 2k) incrémentations. Ensuite i vaut 2p, ce qui provoque la sortie du
" while i < n ªB 2Q QH IMLP SMV G·LQŃUpPHQPMPLRQV GX ŃRPSPHXU SRXU ŃHPPH GHUQière valeur de i.
d. On a donc une complexité en ܱAnnée universitaire : 2018 / 2019
GH8 (QVHLJQHU O·HQIRUPMPLTXH MX I\ŃpH Epreuve Commune Anonyme
UE 2 ² Algorithmique Date : 4 juillet 2019
Durée : 2h
Question 1.2 : Donner la fonction Python de recherche dichotomique dans une liste triéeB IM OLVPH HP O·pOpPHQP j
UHFKHUFKHUVRQWGRQQpVHQSDUDPqWUHV/DIRQFWLRQUHWRXUQHOquotesdbs_dbs7.pdfusesText_13