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?
2013-2014Année SpécialeTD : Complexité des algorithmes
Exercice 1
On considère deux manières de représenter ce que l'on appelle des " matrices creuses », c'est-à-dire des
matrices d'entiers contenant environ 90% d'éléments nuls :a)La matrice est représentée par un tableau à deux dimensions dont les cases contiennent les
éléments.
b)La matrice est représentée par un tableau à une dimension. On ne s'intéresse qu'aux éléments de la matrice qui ne sont pas nuls. Chaque case du tableau contient un triplet (i, j,a) correspondant à l'indice de ligne, l'indice de colonne, et la valeur d'un élément non nul.
Le problème considéré consiste à calculer la somme des éléments d'une matrice. On demande d'écrire un
algorithme permettant de calculer cette somme, pour chacune des deux représentations, puis decomparer leur complexité spatiale (espace mémoire occupé) et leur complexité temporelle (nombre
d'opérations à effectuer). Que peut-on conclure de cette comparaison ? Montrer qu'il existe une valeur
critique du nombre d'éléments non nuls à partir de laquelle une méthode l'emporte sur l'autre.
Exercice 2
On considère, pour effectuer la recherche d'un élément dans un tableau, la recherche séquentielle et la
recherche dichotomique. On s'intéresse à leur complexité temporelle.Pour cela, considérer un tableau ayant mille éléments (version trié, et version non trié). Pour chaque
algorithme, et pour chaque version du tableau, combien de comparaisons sont à effectuer pour : -trouver un élément qui y figure ? -trouver un élément qui n'y figure pas ?Quels sont les cas où le tableau est parcouru complètement et les cas où un parcours partiel est
suffisant ? Conclure en donnant la complexité temporelle pour chaque algorithmeExercice 3
On considère un tableau à une dimension contenant des lettres majuscules. On désire compter la
fréquence de chacune des 26 lettres de l'alphabet. Ecrire deux procédures qui donnent en sortie un
tableau de fréquence: l'une où le tableau est parcouru 26 fois, et l'autre (plus performante !) où le calcul
est fait en un seul parcours. On pourra supposer que l'on dispose d'une fonction auxiliaire position(lettre)
qui pour chaque lettre donne sa position dans l'alphabet : position('A') = 1, ..., position('Z) = 26.
Exercice 4
On considère trois tris élémentaires : le tri sélection, le tri par insertion (trois variantes), et le tri bulle.
On considère pour un tableau les deux cas extrêmes où le tableau est déjà trié (dans l'ordre croissant),
et celui où il est trié dans l'ordre décroissant. Décrire avec précision le comportement et la complexité de
chacun des algorithmes dans ces deux cas. Quelles conséquences peut-on en tirer ?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 dimensionDonner un exemple de matrice presque vide et leur faire mettre sous forme de tableau à une dimension pour
comprendre cette représentation de matrice. algo : somme := tab[1].val pour cpt := 2 à m faire somme := somme + tab[cpt].val3.complexité spatiale : 3 * m
4.complexité temporelle : m-1
La complexité temporelle est toujours favorable à la représentation avec un tableau à 1 dimension.
La complexité spatiale l'est également tant que 3 * m < n * n, c'est à dire m < (n*n)/3.Exercice 2 Revoir poly, transparents 33, 34, et 35. Les coefficients du polynôme sont mémorisés dans un tableau
a. a) Calcul de la valeur d'un polynôme en un point (1) p := a[0] pour i :=1 à n faire xpi := puissance(x, i) p := p + a[i]* xpi fpour5.nombre d'additions : n
6.nombre de multiplications : pour calculer xpi : i-1 multiplications,
pour calculer a[i]*xpi : 1 + (i-1) = i multiplications, donc, pour la boucle : 1 + 2 + 3 + ... + i + ... + n = n(n+1)/28 algorithme en O(n2)
b) Calcul de la valeur d'un polynôme en un point (2) p := a[0] xpi := 1 pour i := 1 à n faire xpi := xpi * x faire p := p + a[i]* xpi7.nombre d'additions : n
8.nombre de multiplications : 2n
8 algorithme en O(n)
c) Calcul de la valeur d'un polynôme en un point (3) (méthode de Horner) p := a[n] pour i := n - 1 à 0, pas -1 faire p := p*x + a[i]9.nombre d'additions : n
10.nombre de multiplications : n
algorithme en O(n)Exercice 3
Recherche d'un élément dans un tableau -- Revoir poly, transparents 36 et 37 Opérations élémentaires retenues: les comparaisons1. Recherche séquentielle dans un tableau de 1000 éléments non trié
11.élément ne s'y trouvant pas (complexité au pire) : 1000 comparaisons (tableau est parcouru complètement)
12.élément qui s'y trouve (complexité moyenne) : n/2=500 comparaisons (parcours partiel suffisant)
algorithme en O(n)2. Recherche séquentielle dans un tableau trié
13.élément ne s'y trouvant pas (complexité au pire) : 1000 comparaisons (parcours partiel suffisant)
14.élément qui s'y trouve (complexité moyenne) : n/2=500 comparaisons (parcours partiel suffisant)
algorithme en O(n)3. Recherche dichotomique (dans un tableau non trié) : impossible
4. Recherche dichotomique (dans un tableau trié)
15.complexité au pire = complexité moyenne = nombre p d'intervalles considérés
Exemple avec n = 8 = 23 tableau de 8 éléments8 3 comparaisonsNiveau 0
Niveau 1
Niveau 2
Niveau 3
Profondeur de l'arbre de décision : de l'ordre de log2n Donc pour un tableau de 1000 éléments, disons 1024 10 comparaisons algorithme en O(log2n) Exercice 4 fréquence de chacune des 26 lettres dans un texteLa méthode qui parcourt le tableau 26 fois consiste à parcourir le texte pour compter d'abord tous les A, recommencer
pour compter tous les B, etc. On utilise un tableau d'entiers de 26 cases, qui sert à mémoriser les occurrences.
La deuxième méthode demande de disposer de la conversion d'une lettre en un entier, qui correspond à sa place dans
l'alphabet. (En c++, on ferait tout simplement appel à i = car - 'A'). char texte[TMAX] int cpt, pos, occ[26] pour cpt := 1 à 26 faire occ[cpt]:= 0 {initialisation à zéro} cpt := 1 tant que (texte[cpt] ¹ CARFIN) faire pos := conversion(texte[cpt]) occ[pos] := occ[pos] + 1 cpt := cpt + 1 ftqExercice 5 Fibonacci
tab: tableau [0,n] d'entiers tab[0] := 1 ; tab[1] := 1 pour i := 2 à n faire tab[i]=tab[i-1] + tab[i-2] retourner tab[n]16.complexité spatiale : n+1
17.complexité temporelle : n-2 additions
Variante :
tab: tableau [0,1] d'entiers tab[0] := 1 ; tab[1] := 1 pour i := 1 à n/2 faire tab[0]=tab[0] + tab[1] tab[1]=tab[0] + tab[1] si n pair alors retourner tab[0] sinon retourner tab[1]18.complexité spatiale : 2
19.complexité temporelle : n additions
Exercice 6 Les trois tris
Le tri sélection fait autant de comparaisons dans tous les cas. La seule différence tient au nombre de mises à jour du
minimum.Ce tri a cependant l'avantage de ne faire que peu d'échanges, ce qui peut être important pour des données de grande
taille.Le tri par insertion sous la dernière variante donnée en cours ne fait qu'un test par tour de boucle si le tableau est trié,
d'où une complexité linéaire dans ce cas : avantage pour les tableaux presque triés.Pour le tri bulle, le comportement dépend du fait que l'on ait ou pas modifié l'algorithme pour qu'il s'aperçoive qu'un
tableau est trié (ce qui est le cas si aucune permutation n'a été faite au cours d'une passe).
quotesdbs_dbs41.pdfusesText_41[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é
