Complexité Corrigé
12 mars 2012 Comme la boucle s'exécute n fois le temps d'exécution du programme est alors en Θ(n). 2 Correction de l'exercice 1.2. Le programme étudié est ...
Exercice 1 : Complexité des algorithmes (8 points) DIU Enseigner l
4 juil. 2019 Déterminer ensuite par la méthode du Master Theorem
TD1.1 Analyse dalgorithmes calculs de coûts
comparer des algorithmes selon leur complexité; évaluer la qualité d'un algorithme selon sa complexité. Exercice 1 : Itérations emboîtées (30 min). Compter
TD : Complexité des algorithmes
Quelles conséquences peut-on en tirer ? Page 2. PROPOSITION DE CORRIGE. Durée Exercice 2 Revoir poly transparents 33
SUJET + CORRIGE
Exercice 2 : Algorithmes de rang. (14 points). Le probl`eme de la sélection complexité en O(n × (n − r)). Ainsi la complexité dans le pire des cas est en ...
Algorithmes et structures de données : TD 5 Corrigé
Exercice 5.1 Temps d'un algorithme T(n). Pour chacun des fonctions Ti(n) Déterminer la complexité asymptotique des deux algorithmes dans la notation Grand-O.
Travaux Dirigés Algorithmique no3 - Complexité fonctions usuelles
Pour montrer qu'un algorithme est correct on écrit une propriété P qui est conservée à chaque étape de boucle que l'on appelle invariant de boucle. Exercice 1.
TD 01 – Introduction à lalgorithmique (corrigé)
Exercice 1. Grand Saut Nous allons montrer que la complexité exacte est 3n − ⌊log n⌋ − 3 en exhibant un algorithme ayant cette complexité ainsi qu'en.
TD dalgorithmique avancée Corrigé du TD 2 : récursivité
5. Qu'elle est la complexité (en nombre d'additions) de cet algorithme? La complexité de l'algorithme Fib-Paire en
Algorithme correction
https://pnp.mathematik.uni-stuttgart.de/igt/eiserm/enseignement/mae/mae-chap08.pdf
Complexité Corrigé
12 mars 2012 Comme la boucle s'exécute n fois le temps d'exécution du programme est alors en ?(n). 2 Correction de l'exercice 1.2. Le programme étudié est ...
TD : Complexité des algorithmes
Conclure en donnant la complexité temporelle pour chaque algorithme PROPOSITION DE CORRIGE ... Exercice 2 Revoir poly transparents 33
SUJET + CORRIGE
Dans cet exercice nous allons adapter des algorithmes de tri vus Rappel : La complexité
TD1.1 Analyse dalgorithmes calculs de coûts
évaluer la qualité d'un algorithme selon sa complexité. Exercice 1 : Itérations emboîtées (30 min). Compter le nombre d'opérations Schtroumpfer exécutées
Algorithmes et structures de données : TD 5 Corrigé
Exercice 5.1 Temps d'un algorithme T(n). Pour chacun des fonctions Ti(n) suivant déterminer sa complexité asymptotique dans la.
Algorithmique I - Cours et Travaux Dirigés L3 Ecole Normale
Quelle est la complexité de l'algorithme ? 21. Page 22. Exercice 2.6.2. Plus grand et deuxi`eme plus grand de
Calculs de complexité dalgorithmes
?Complexité des algorithmes ?Un algorithme à partir d'une donnée établit un résultat . ... Exercice. ?Chaque jour pour mon goûter
Algorithmique et complexité de calcul
Exercice : Faire la trace pour l'exemplaire (1753). Modifier cet algorithme pour avoir une seule boucle et en utilisant seulement des variables scalaires. Page
Algorithme correction
https://pnp.mathematik.uni-stuttgart.de/igt/eiserm/enseignement/mae/mae-chap08.pdf
TD 01 – Introduction à lalgorithmique (corrigé)
TD 01 – Introduction à l'algorithmique (corrigé). Exercice 1. Grand Saut La complexité en O(log2(n)) qui est indiquée nous aiguille vers une dichotomie.
Exercice 1 : Complexité des algorithmes (8 points)
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) :
Travaux Pratiques Méthodes Numériques
Exercice 1 : Complexité des algorithmes On considère la fonction suivante réalisant la fusion de deux listes triées passées en paramètres La fonction retourne la liste fusionnée elle-même triée def fusion(liste1liste2) : 1 i1i2 = 00 2 resultat = [] 3 while i1 < len(liste1) and i2 < len(liste2) : 4 if liste1[i1] < liste2[i2] :
TD : Complexité des algorithmes - LIMSI
PROPOSITION DE CORRIGE Durée prévue : une séance Exercice 1 a) tableau à deux dimensions algo : somme := 0 pour cptL := 1 à n faire {pour chaque ligne} pour cptC := 1 à n faire {pour chaque colonne} somme := somme + tab[cptL cptC] 1 complexité spatiale : n * n 2 complexité temporelle : n* n sommes b) tableau à une dimension
TD11 Analyse d'algorithmes calculs de coûts - GitLab
comparer des algorithmes selon leur complexité; évaluer la qualité d'un algorithme selon sa complexité Exercice 1 : Itérations emboîtées (30 min) Compter le nombre d'opérations Schtroumpfer exécutées par chacun des algorithmes suivants 1 (1) pour i = 1 à n faire (2) pour j = 1 à n faire (3) Schtroumpfer() 2 (1) pour i = 1 à n faire
Complexité Corrigé
3 Correction de l’exercice 1 3 Cet exercice ressemble beaucoup à l’exercice 1 2 avec une di?érence fondamentale dans la boucle interne En e?et dans l’exercice 1 2 la boucle interne réalise un nombre constant d’opé-rationsalorsquedansleprésentexercicelenombred’opérationsdépenddescaractéristiquesdes
Quelle est la complexité des algorithmes?
Nous les présentons dans l’ordre de complexité croissante des algorithmes. Dans le cas de la méthode de dichotomie, la seule information utilisée est le signe de la fonction f aux extrémités de sous-intervalles, tandis que pour les autres algorithmes on prend aussi en compte les valeurs de la fonction et/ou de ses dérivées. I.2.
Quelle est l’existence d’un algorithme de résolution de complexité polynomiale?
La question de l’existence d’un algorithme de résolution de complexité polynomiale nous amène à définir des classes de complexité : intuitivement on aimerait avoir une classe des programmes que l’on peut résoudre en temps polynomial, une classe de problème plus compliqués, et un moyen de déterminer à quelle classe appartient un problème.
Quelle est la théorie de la complexité?
La théorie de la complexité a commencé en adaptant les méthodes de la calculabilité au cas du temps de calcul borné. Par exemple, on retrouve de nombreux ingrédients issus de la calculabilité dans la démonstration du théorème 3-AK de Ladner datant de 1975.
Qu'est-ce que la classe de complexité P?
Définition 14 (Classe de complexité P).La classe de complexité P est l’ensemble des problèmes concrets de décision qui sont résolubles en temps polynomial. Pour quoi s’embêter avec des codages plutôt que de définir directement la complexité d’un problème abstrait?
Complexité
Corrigé
Fabrice Rossi
12 mars 2012
1 Correction de l"exercice 1.1
On considère donc le programme suivant :1i = 0
2j = 0
3while(i < n) {
4if( i % 2 == 0) {
5j = j + 1
6} else {
7j = j / 2
9i = i + 1
10} Le programme est constitué d"une phase d"initialisation (lignes 1 et 2), puis d"une boucle. Ondétermine d"abord le nombre d"exécution de la boucle. On remarque que la boucle s"exécute à
chaque fois quei < n. Or,iest initialisé à 0 (ligne 1) et chaque exécution (tour) de la boucle
incrémenteide 1 (ligne 9). La boucle s"exécute donc pour les valeurs dei0, 1, etc. jusqu"àn-1,
soit doncnfois. On constate ensuite que le corps de la boucle (lignes 4 à 9), contient un nombre d"instruction qui ne dépend ni de la valeur deini de celle dej. En effet, les deux lignes 5 et 7 contiennent chacune deux instructions (un calcul et une affectation). Les autres lignes (4 et 9) sont toujours exécutées. De ce fait, le temps d"exécution du corps de la boucle est donc un(1). Comme la boucle s"exécutenfois, le temps d"exécution du programme est alors en(n).2 Correction de l"exercice 1.2
Le programme étudié est le suivant :1x = 0
2for(int i = 1 ; i < tab.length-1 ; i++) {
3for(int j = 0 ; j < 3 ; j++) {
4x = x + tab[i - 1 + j] * (j+1)
L"analyse commence comme toujours par la boucle la plus interne, ici celle de lignes 3 à 5. Laquantité d"opérations réalisé dans un tour de la boucle (ligne 4 essentiellement) ne dépend ni des
valeurs des variablesietj, ni de la taille du tableautab(ou de son contenu). On a en effet : - une affectationx=; - trois additions et une soustractionj+1,i-1+jetx+; - un accès à une case du tableautab; - une multiplication*(j+1); - une incrémentationi++; - une comparaisonj < 3. Globalement, un tour de cette boucle réalise donc(1)opérations. De plus, la boucle s"exécute exactement trois fois pourjprenant les valeurs 0, 1 et 2. Donc le nombre d"opérations réalisées par la boucle complète est un(1).On constate ensuite que l"exécution complète de la boucle des lignes 3 à 5 constitue l"essentiel
de l"exécution d"un tour de la boucle des lignes 2 à 5 (la boucle externe). Un tour de cette boucle
prend donc(1)opérations. Enfin, cette boucle externe s"exécute pour les valeurs deiallant de1 àtab.length-2, bornes incluses. On a donctab.length-2exécutions du corps de la boucle,
soit un nombre total d"opérations en(tab.length-2)(1), c"est-à-dire(tab.length).3 Correction de l"exercice 1.3
Cet exercice ressemble beaucoup à l"exercice 1.2, avec une différence fondamentale dans laboucle interne. En effet, dans l"exercice 1.2, la boucle interne réalise un nombre constant d"opé-
rations alors que dans le présent exercice, le nombre d"opérations dépend des caractéristiques des
données. Le programme est en effet le suivant :1x = 02for(int i = 0 ; i <= tab.length - filter.length ; i++) {
3for(int j = 0 ; j < filter.length ; j++) {
4x = x + tab[i + j] * filter[j]
Comme dans l"exercice précédent, une exécution de la boucle interne (lignes 3 à 5) réalise(1)opé-
rations. Mais cette boucle est exécutéefilter.lengthfois (pourjallant de 0 àfilter.length-1).
Donc le nombre d"opérations de la boucle interne complète est en(filter.length). La boucle externe (lignes 2 à 5) s"exécute elletab.length - filter.length+1fois. Si on note n=tab.lengthetp=filter.length, on a donc un coût total en(np)(p)et donc en ((np)p)(en s"appuyant sur le fait que le corps de la boucle externe consiste essentiellement en l"exécution complète de la boucle interne).4 Correction de l"exercice 3.1
On étudie la recherche dichotomique dans un tableau trié :search1search(x,tab) {
2if(tab.length == 0) {
3return -1
4} else if(tab.length == 1) {
5if(tab[0] == x) {
6return 0
7} else {
8return -1
10} else {
11pos = tab.length/2
12if(tab[pos] == x) {
13return pos
14} else if(tab[pos] < x) {
15subpos = search(x,tab[(pos + 1):(tab.length - 1)])
16if(subpos >= 0) {
17return subpos + pos + 1
18} else {
19return -1
20}21} else {
22subpos = search(x,tab[0:(pos - 1)])
23if(subpos >= 0) {
24return subpos
25} else {
26return -1
27}28}
29}
On noten=tab.lengthetT(n)le nombre d"opérations réalisé dans le cas le pire par un appel à
la fonctionsearchavec comme paramètre un tableau de longueurn. La fonction étant récursive, on cherche à établir une relation de récurrence surT(n).4.1 Casn= 0
Ce cas est facile à traiter car il correspond simplement aux lignes 2 et 3 du programme. Ces lignes effectuent un nombre constant d"opérations (deux exactement, la comparaison et la transmission du résultat). On a doncT(0) = (1):
4.2 Casn= 1
Ce cas est aussi assez facile à traiter. Il correspond au test de la ligne 2, puis aux lignes 4 à 9.
On constate que le nombre d"opérations réalisées est de nouveau constant car chaque cas du test
(lignes 6 et 7) conduisent au même travail, à savoir renvoyer une valeur numérique. On a donc de
nouveauT(1) = (1):
4.3 Casn >1
C"est la partie délicate de l"analyse qui correspond aux lignes 11 à 28 (après avoir réalisé
les tests en ligne 2 et 4). On fait ici une analyse dans le cas le pire car le nombre d"opérations
réalisées dépend fortement de la position dexdans le tableau. En particulier, si cette position est
tab.length/2, on réalise un nombre constant d"opérations seulement. Mais ce n"est bien entendu pas le cas le pire qui correspond au deux autres situations. On traite d"abord le castab[pos] < x, soit les lignes 14 à 20. Le programme commence par construire le sous-tableautab[(pos + 1):(tab.length - 1)]. Notons pour l"instantV(p)le nombre d"opérations nécessaires à la construction d"un sous-tableau de longueurp. Dans le cas
présent, le sous-tableau est de longueur(n1)(bn=2c+1)+1, oùbn=2cdésigne la partie entière
den=2. La longueur du sous-tableau est donc den bn=2c 1. L"appel àsearchengendre ainsiun nombre d"opérations deT(n bn=2c 1). Après l"exécution de l"appel récursif, le programme
passe aux lignes 16 à 20, ce qui engendre(1)opérations dans le cas le pire (on est bien dans une
analyse dans le cas le pire puisqu"on a une ligne 17 qui engendre plus d"opérations que la ligne 19
du cas contraire). Finalement, le nombre d"opérations pour le castab[pos] < xest donc deT(n bn=2c 1) +V(n bn=2c 1) + (1):
Le castab[pos] > xse traite de la même façon, mais en considérant le tableautab[0:(pos -1)]de taillebn=2c, ce qui conduit à un nombre d"opérations de
T(bn=2c) +V(bn=2c) + (1):
On peut affiner ces calculs en tenant compte de la parité den: n= 2k: on a alorsbn=2c=ket donc dans le premier casT(k1) +V(k1) + (1)
opérations, et dans le deuxième casT(k) +V(k) + (1)
opérations. Si on fait l"hypothèse naturelle queTetVsont des fonctions croissantes, l"analysequotesdbs_dbs2.pdfusesText_4[PDF] examen d'algorithmique
[PDF] examen principe de gestion 1ére année
[PDF] examen principe de gestion ihec
[PDF] principe de gestion 2
[PDF] comptabilité générale exercices corrigés maroc
[PDF] examen comptabilité générale s1 corrigé pdf
[PDF] examen de comptabilité générale
[PDF] examen comptabilité générale s1 pdf maroc
[PDF] cours de comptabilité générale s1 pdf
[PDF] examen comptabilité générale corrigé
[PDF] examen de comptabilité générale s2 corrigé
[PDF] exercices corrigés sur le décodage d adresses
[PDF] examen algorithmique récursivité
[PDF] examen algorithmique avancée corrigé
