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?
Master BioInformatiqueAnn
ee :2013/2014Semestre de decembre 2013PARCOURS :Master 1
UE J1BS7202 :Algorithmique et Programmation
Epreuve :Examen
Date :Jeudi 19 decembre 2013
Heure :9 heures
Duree :2 heures
Documents : autorises
Epreuve de M. AlainGriffaultSUJET + CORRIGE
Avertissement
La plupart des questions son tind ependantes.
A chaque question, vous pouvez au choix
repondre par un algorithme ou bien par un programme python.Les inden tationsdes f onctions ecritesen Python
doivent ^etre respectees. L'espace laiss ep ourles r eponsesest susan t(sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement deconseille).QuestionPointsScoreMise en bouche7
Algorithmes de rang14
Liste doublement chainee9
Total:30
Exercice 1 : Mise en bouche (7 points)
(a) (1 p oint)Deux nom bresson topp osessi le ursom meest egale a0. Deux nombres sont inverses si leur produit est egal a1.Ecrire un algorithmesontInvOuOpp(a,b)ouaetbsont deux nombres, qui retourneVraisiaetbsont inverses ou opposes,Fauxsinon.Solution:Deux solutions parmi d'autres.
defsontInvOuOpp(a ,b): returna+b==0orab==1Algorithme 1:SontInvOuOpp(a,b)Donnees:Deux nom bresa et b retourner(a+b=0) OU (a*b=1);(b)(2 p oints) Ecrire un algorithmeexisteInvOuOppConsecutifs(T)ouTest un tableau de nombres, qui retourneVraisiTcontient deux nombresconsecutifsopposes ou inverses,Fauxsinon.Solution:Deux solutions parmi d'autres.
defexisteInvOuOppConsecutifs (T): foriinrange ( len (T)1): ifsontInvOuOpp(T[ i ] ,T[ i +1]): returnTrue returnFalseAlgorithme 2:ExisteInvOuOppConsecutifs(T)Donnees:Un tabl eauT de n ombres pouri=0alen(T)-2fairesisontInvOuOpp(T[i],T[i+1])alorsretournerTrue;retournerFalse;(c)(2 p oints) Ecrire un algorithmeexisteInvOuOpp(T)ouTest un tableau de nombres, qui retourne VraisiTcontient deux nombres,ayant des indices dierents, opposes ou inverses,Fauxsinon. UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013Solution:Deux solutions parmi d'autres.
defexisteInvOuOpp(T): foriinrange ( len (T)1): forjinrange ( i +1,len (T)): ifsontInvOuOpp(T[ i ] ,T[ j ] ) : returnTrue returnFalseAlgorithme 3:ExisteInvOuOpp(T)Donnees:Un tableau T de nom brespouri=0alen(T)-2fairepourj=i+1alen(T)-1fairesisontInvOuOpp(T[i],T[j])alorsretournerTrue;retournerFalse;(d)(2 p oints)
Ecrire un algorithmenbInvOuOpp(T)ouTest un tableau de nombres, qui retourne le nombre de paires d'indices(i,j)telles que : d'une partipouri=0alen(T)-2fairepourj=i+1alen(T)-1fairesisontInvOuOpp(T[i],T[j])alorsnb nb+1;retournernb;Exercice 2 : Algorithmes de rang (14 points)
Le probleme de la selection consiste a trouver dans un tableau de nombres l'element dit de rangi. Pour cet exercice, du fait que les indices d'un tableauTsont compris entre0etlongueur(T)-1, nous admettrons que l'element de rang0est le plus petit element du tableau, et que l'element de rang longueur(T)-1est le plus grand.Exemple :SoitT= [8;6;53;8;2;9;3;10], alors :
Les elementsde rang <0sont indenis.
L' elementde rang 0est 2.
L' elementde rang 1est 3.
L' elementde rang 2est 6.
L' elementde rang 3est 8.
L' elementde rang 4est 8.
L' elementde rang 5est 9.
L' elementde rang 6est 10.
L' elementde rang 7est 53.
Les elementsde rang >7sont indenis.
Page 2 sur 10
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013 Remarque 1 :Une solution simple au probleme de la selection consiste a utiliser un algorithmequelconque de tri, puis de retourner l'element de rang souhaite.Algorithme 5:Rang(T,rang)Donnees:Un tabl eauT de n ombres,et rang un en tier
Resultat:Si rang est un indice, alors T[rang] apr esa voirtri eT sirang<0 OU ranglongueur(T)alorsretournernil;Trier(T);retournerT[rang];Remarque 2 :Il est facile de se persuader qu'il n'est pas utile de triertoutle tableau pour avoir une
solution au probleme de la selection. Dans cet exercice, nous allons adapter des algorithmes de tri vus
en cours an d'obtenir des algorithmes de rang plusecacesque le precedent.Dans toute la suite de l'exercice, vous pourrez utiliser la fonction classiqueEchange(T,i,j)qui echange
les valeurs du tableauTindicees parietj. defechange(T, i , j ):TMP = T[ i ]
T[ i ] = T[ j ]
T[ j ] = TMPAlgorithme 6:Echange(T,i,j)Donnees:Un tableau T de nom bres,et deux indices i et jResultat:T[i] et T[j] echanges
aux T[i];T[i] T[j];
T[j] aux;(a)Solution adapt eedu tri par s electionvu en cours. deftriSelection (T): foriinrange ( len (T)): iMin = i forjinrange ( i +1,len (T)): ifT[ j]Page 3 sur 10
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013 i. (2 p oints) Ecrire un algorithmerangSelection(T,r)fortement inspire de l'algorithme ou du programme pythontriSelection(T)qui resout le probleme de la selection. Ne pas oublier de s'assurer que le rang desire correspond a un indice du tableau.Solution:Deux solutions parmi d'autres.
defrangSelection (T, r ): ifr<0orr>=len (T): returnNone foriinrange ( r+1): iMin = i forjinrange ( i +1,len (T)): ifT[ j]Temps (meilleur des cas)
(n2) (nr)Temps (pire des cas)O(n2)O(nr)Espace (meilleur des cas) (1) (1)Espace (pire des cas)O(1)O(1)Non demande :Il est facile d'ameliorer (un peu) la solution en selectionnant les valeurs minimales
(comme ici) lorsquer < n=2, et en selectionnant les valeurs maximales lorsquern=2. Les complexites s'expriment alors en remplacantrparmin(r;nr).(b)Solution adapt eedu tri abulle vu en cours. deftriBulle (T): foriinrange ( len (T)1,0,1): forjinrange ( i ): ifT[ j]>T[ j +1]: echange(T, j , j+1)Algorithme 9:TriBulle(T)Donnees:Un tableau T de nom bresResultat:Le tableau T tri een ordre
croissant pouri=len(T)-1a1 decroissantfairepourj=0ai-1fairesiT[j]>T [j+1]alorsEchange(T,j,j+1);Il semble evident qu'une fois la valeur desireebien placeedans le tableau, il est inutile de continuer
le tri. i. (2 p oints) Ecrire un algorithmerangBulle(T,r)fortement inspire de l'algorithme ou du programme pythontriBulle(T)qui resout le probleme de la selection. Ne pas oublier de s'assurer que le rang desire correspond a un indice du tableau.Page 4 sur 10
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013Solution:Deux solutions parmi d'autres.
defrangBulle (T, r ): ifr<0orr>=len (T): returnNone foriinrange ( len (T)1,r1,1): forjinrange ( i ): ifT[ j]>T[ j +1]: echange(T, j , j+1) returnT[ r ]Algorithme 10:RangBulle(T,r)Donnees:Un tableau T de nom breset un indice rResultat:L' elementde rang r du tableau T
sir<0 OU rlongueur(T)alorsretournernil;pouri=len(T)-1ar, decroissantfairepourj=0ai-1fairesiT[j]>T [j+1]alorsEchange(T,j,j+1);
retournerT[r];ii.(1 p oint)Compl eterle tableau des complexit esen fonction d en=longueur(T)et du rangr.
Solution:TriBulle(T)RangBulle(T,r)
Temps (meilleur des cas)
(n2) (n(nr))Temps (pire des cas)O(n2)O(n(nr))Espace (meilleur des cas) (1) (1)Espace (pire des cas)O(1)O(1)Non demande :Il est facile d'ameliorer (un peu) la solution en faisant monter les grosses bulles
(comme ici) lorsquern=2, et en faisant descendre les petites bulles lorsquer < n=2. Les complexites s'expriment alors en remplacantnrparmin(r;nr).(c)Solution adapt eedu tri rapide vu e ncours. Soit la variante suivante de l'algorithme de partition basee sur l'algorithme du drapeau Hollandais vu en cours. Cet algorithmepartitionnele tableau en trois zones : la premiere contient des valeurs strictement inferieures a la valeur du pivot; la seconde contient des valeurs egales a la valeur du pivot; et la troisieme des valeurs strictement superieures a la valeur du pivot.Page 5 sur 10
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013 deftroisPartitionner (T,g ,d): pivot = T[ g ] i = g j = i k = d whilej<= k: ifT[ j ] == pivot : j += 1 elifT[ j ]T= [17;3;21;13;17;25;4];g= 0;d= 6
Solution:Temps!pivot17
couple d'indices echanges(0,1)(2,6)(1,2)(2,3)(5,5) i0123 j012345 k654Page 6 sur 10
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013 ii. (2 p oints)Cette v ersionamelioreedu tri rapide tire prot des trois zones, en ne faisant pas d'appel recursif sur la zone intermediaire, car les valeurs de cette zone sont correctement placees. deftriRapideRec (T,g ,d): ifgResultat:Le tableau T[g..d] tri ee n
ordre croissant sigResultat:Le tableau T tri een ordre
croissantTriRapideRec(T,0,longueur(T)-1);
Ecrire des algorithmesrangRapide(T,r)etrangRapideRec(T,g,d,r)fortement inspires des algorithmestriRapide(T)ettriRapideRec(T,g,d), qui resolvent le probleme de la selection. Ne pas oublier de s'assurer que le rang desire correspond a un indice du tableau.Solution:Deux solutions parmi d'autres.
defrangRapideRec(T,g ,d, r ): ifgResultat:P ositionnel' elementde rang r du
tableau T sigResultat:L' elementde rang r du tableau T
sir<0 OU rlongueur(T)alorsretournernil;RangRapideRec(T,0,longueur(T)-1,r);retournerT[r];iii.(1 p oint)Compl eterle tableau des c omplexitesen fonction de n=longueur(T)et du rangr.
Page 7 sur 10
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013Solution:
TriRapide(T)RangRapide(T,r)
Temps (meilleur des cas)
(n) (n)(Toutes les valeurs identiques)Temps (pire des cas)O(n2)O(nr)(tableau trie)
Espace (meilleur des cas)
(1) (1)Espace (pire des cas)O(n)O(r)(d)La solution naturelleau probleme de selection base sur le tri rapide est une solution recursive.
En examinant le deroulement de votre programme, vous devez vous apercevoir qu'aucun calcul pertinantn'est realise des que l'on commence a depiler les appels recursifs de la pile d'execution.Dans de tel cas, il est assez facile de transformer une solution recusrsive en une solution iterative.
i. (2 p oints) Ecrire un algorithmerangRapideIteratif(T,r)obtenu a partir de votre solution a la question precedente.Solution:Deux solutions parmi d'autres.
defrangRapideIteratif (T, r ): ifr<0orr>=len (T): returnNone g = 0 d = len (T)1 whileTrue : i , j ,k = troisPartitionner (T,g ,d) ifrk: g = k+1 else: returnT[ r ]Algorithme 16:RangRapideIteratif(T,r)Donnees:Un tableau T de nom bres,et un indice rResultat:L' elementde rang r du tableau T
sir<0 OU rlongueur(T)alorsretournernil;g 0; d longueur(T)-1; tant queTruefaire(i,j,k) troisPartitionner(T,g,d); sirretournerT[r];ii.(1 p oint)Compl eterle tableau des complexit esen fonction d en=longueur(T)et du rangr.
Temps (meilleur des cas)
(n) (n)(Toutes les valeurs identiques)Temps (pire des cas)O(n2)O(nr)(tableau trie)
Espace (meilleur des cas)
(1) (1)Espace (pire des cas)O(n)O(1)Non demande :En realite le pire des cas est soit un tableau trie, ce qui donne une complexite en
O(nr), soit un tableau trie en ordre decroissant qui donne une complexite enO(n(nr)). Ainsi la complexite dans le pire des cas est enO(nmax(r;nr)).Page 8 sur 10 UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013 (e) (1 p oint)En pr atique,le cas standardcorrespond a un tableau initial non trie, et ayant peu de valeurs repetees. L'algorithme de partitionnement retourne alors souvent trois zones telles que l'intermediaire estpetiteet a peu pres au centre du tableau. Completer le tableau en fonction den=longueur(T)et du rangrpour ce casmoyen. Temps moyen(nlog2(n))(n)(n)(zone 2 petite et centree)Exercice 3 : Liste doublement chainee (9 points)
Denition :Uneliste doublement cha^neeest une structure dynamiqueLcomposee de cellules ayant chacune : Un c hampinfopour stocker les donnees de la liste.Un p ointeursuccqui contient l'adresse de la cellule suivante dans la liste si elle existe, la valeurnil
sinon.Un p ointeurpredqui contient l'adresse de la cellule precedente dans la liste si elle existe, la valeur
nilsinon.La listeLest un pointeur ayant pour valeurnilsi la liste est vide, sinon l'adresse de l'unique cellule
dont le pointeurpredest egal anil.L infopred succ-infopred succ- ...infopred succ-Figure1 { Une liste doublement cha^nee
Les listes doublement cha^nees sont manipulees par les primitives suivantes :1.Derniere_Cellule(L)qui retourne un pointeur sur la derniere cellule de la liste si elle existe, la
valeurnilsinon.2.Inserer_Apres(L,X,P)qui insere dans la listeLla celluleXapres la cellule pointee parP.
3.Inserer_Tete(L,X)qui insere en t^ete de la listeLla celluleX.
4.Concatener(L1,L2)qui retourne le resultat de la concatenation des listesL1etL2dans la liste
L1. (a) (2 p oints) Ecrire l'algorithme de la primitiveDerniere_Cellule(L).Solution:
defderniereCellule (L): Aux = L# L pourrait etre utilise , mais par habitude . . . ifL!=None: whileAux. succ!=None:Aux = Aux. succ
returnAux(b)(2 p oints) Ecrire l'algorithme de la primitiveInserer_Apres(L,X,P). Vous supposerez quePest un pointeur valide sur une cellule deL.Solution:
definsererApres (L,X,P):# ne change pas L, inutile de retournerC = creerListeDC (X)Page 9 sur 10
UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013C. pred = P
ifP. succ!=None:C. succ = P. succ
P. succ . pred = C
P. succ = C(c)(2 p oints)
Ecrire l'algorithme de la primitiveInserer_Tete(L,X).Solution:
definsererTete (L,X):# change L, i l faut retourner la nouvelle valeurC = creerListeDC (X)
ifL!=None:C. succ = L
L. pred = C
returnC(d)(3 p oints) Ecrire l'algorithme de la primitiveConcatener(L1,L2).Solution:
defconcatener (L1,L2 ):# peut changer L1, i l faut retourner la valeur ifL1!=None: ifL2!=None:Aux = derniereCellule (L1)
Aux. succ = L2
L2. pred = Aux
returnL1 else: returnL2Page 10 sur 10quotesdbs_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é
