Next PDF List

1Calculs de complexitéd'algorithmesNotations asymptotiques : 0 etComplexitédes algorithmesExemples de calcul de complexité2Complexités d'un algorithmeUn algorithme àpartir d'une donnée établitun résultat .La taille de la donnée est mesurée par un entier n.complexitétemporelleune fonction de n qui mesure le temps de calcul pour une donnée de taille ncomplexitéen mémoireune fonction de n qui mesure la place mémoire utilisée pour le calcul sur une donnée de taille n3Complexités temporellesDans le pire des cas : donne une borne supérieure sur le temps de calcul pour toutes les données de taille nEn moyenne : fait la moyenne des temps de calculs pour toutes les données de taille n4Mesure-t-on vraiment le temps de calcul ?Non, car le temps de calcul dépend de la machineOn évalue le nombre d'opérations "élémentaires" faites (additions, multiplications, etc.)On obtient donc une estimation du temps de calcul àune constante multiplicative près (le temps mis par la machine pour faire une opération "élémentaire")Dans cette estimation, on ne considère que letermedominant5DéfinitionsOn dit que f estdominéepar g(notéf= O (g)) lorsqueOn dit que f estdu même ordre degrandeurque g et l'on note f =(g)lorsque f=O(g) et g=O(f).000ncgnfnncn6Définitionsf est négligeabledevant g, (notéf=o(g))lorsque f(n)/g(n) tend vers 0 quand n tend vers l'infiniOn dit que f estéquivalenteglorsquef(n)/g(n) tend vers 1 lorsque n tend vers l'infini7Relations entre O, o et autresf est négligeabledevant g impliquef estdominéepar g ?f estéquivalenteàgimpliquef estdu même ordre de grandeurque g ?8RemarqueHormis pour l'équivalence, ces notions sont indépendantes des constantes multiplicatives non nulles.Par exemple : sif est négligeabledevant g,alors cfest négligeabledevant c'g pourtout réels c et c' non nuls.

9) Polynômes et notations O etSoit P(n) un polynôme en n.

Pour quelles valeurs de p a-t-on P(n)=O(npPour quelles valeurs de p a-t-on P(n)=(np10Montrer que pour tout entier k, on a10nkkiin11Échelle De ComparaisonExerciceSoient les fonctionsf1(n)=n, f2(n)=2nf3(n)=n2, f4(n)=2n,f5(n)=nn, f6(n)=log n, f7(n)=n!, f8(n)= nlognPour chaque couple (i, j) dire si on afi=o(fjfi=O(fjfi(fj12109Instructions/secondes(1 gigaHertz)n51015201001000logn310-9s410-9s410-9s510-9s710-9s10-8s2n10 10-9s210-8s310-8s410-8s210-7s210-6snlogn12 10-9s310-8s610-8s10-7s710-7s10-5sn225 10-9s10-7s22510-7s410-7s10-5s10-3sn53 10-6s10-4s75910-4s310-3s10s106s11 jours2n32 10-9s10-6s32810-5s10-3s121021s4 1011siècles10292s3 10282sièclesn !120 10-9s410-3s1,4 103s=23 minutes2,4 109s =77 ans10147s3 10139siècles10500snn3 10-6s10 s437 108s =13 ans1017s =3 107siècles10191s3 10181siècles103000s13En uneJournée, un an jusqu'oùpeut-on, allerf(n)1 jour1 ann9101331 1015log(n)103101010162n4.5 101315 1015n log(n)2 10125 1014n21071.7 108n56002 0002n3255n!1618nn121314Pourquoi Utiliser O EtPour Mesurer DesComplexités?Expressions àune constante multiplicativeprès, indépendante du temps de calcul d'une instruction de baseToute instruction de base prend le temps 1Terme dominant uniquement donc expression simple15n, c'est quoi?La complexités'exprime en fonction de lataille de la donnéeA vous de dire quelle fonction taille vous avez choisieEt la donnée c'est quoi ?16Règle 1Composition SéquentielleI1complexitétemporelle en(f1(n))I2complexitétemporelle en(f2(n))Le bloc d'instructions I1I2a une complexitétemporelle en(max(f1(n), f2(n)))17Règle 2if (C) I1 elseI2Évaluation de la condition C est en(f(n))De I1en(f1(n)),de I2en(f2(n))Alors la complexitéde l'instructionif (C) I1elseI2est en O(max(f(n),f1(n),f2(n)))18Règle 3Boucle forEn supposant que :I1a une complexitétemporelle en(f1(n))I1n'a aucun effet sur les variables i et n,la complexitétemporelle de la bouclefor (int i=0; i < ni++) {I1est en(n*f1(n))19Si une instruction I se trouve au coeur dek boucles for imbriquées, chacune d'elle de la forme for (intim=0; im< n ; imoù0 < m < (k+1)combien de fois l'instruction I est elle exécutée ?20Si une instruction I se trouve au coeur de k boucles for imbriquées, chacune d'elle de la forme for (intim=0; im< im-1; imoù0 < m < (k+1)avec i0=ncombien de fois l'instruction I est elle exécutée ?21Règle 4 Boucle WhileC) {I}Évaluation de C en(f(n))I en(f1(n))Boucle while est exécutée(g(n)) foiswhile (C) {Iest en(g(n)*max(f(n),f1(n)))22Estimer les complexités des morceaux de codes suivants, sachant que l'instruction I1est en(1) etI1ne modifie pas les entiers i, j, k et nfor (inti=0; i < ni++) {for (intj=i; j < nj++) {for (intk=0; k < jk++) {I1}23Estimer les complexités des morceaux de codes suivants, sachant que et lesinstructions I1, I2, I3 sont en(1) et ne modifie pas les entiers i, j, k et ninti=1intj=1while (i

On utilise la méthodeconvertionDirecteQuelleen est la complexité?public intconvertionDirecte(int[] a, intb) {intrésultat =a[0]intauxiliairefor (intrang =1; rang < a.lengthrang++) {if (a[rang]!= 0) {auxiliaire = a[rang]for (intindice =0; indice

On utilise la méthode "convertionDirecteV2" dans laquelle on mémorisedans une variable monomebrang.

Ecrirecette méthode"convertionDirecteV2" et en donner la complexité273. Prouvez que la méthode suivante dite de Horner, effectue bien le même travail.

Quelle en est la complexitépublic inthorner(int[] a, intb) {intn = a.lengthintrésultat=a[n-1]for (intrang = n-2; rang >= 0rang--){résultat = b* résultat +a[rang]return résultat28On désire élever l'entier a àla puissance n.Quelle est la complexitéde la méthode suivante ?public intpuissance(intn, inta) {intrésultat= afor(inti =1; i

Quel en est la complexitépublic intpuissance(intn, inta) {intaux = nintpuissanceDeaaintrésultat=1while( aux!= 0 ) {if (aux mod2 == 1) {résultat = résultat * puissanceDeaaux=aux/2puissanceDeapuissanceDea* puissanceDea}return résultat30Programmation récursiveQuelques exemplesEquations de récurrencesQuelques méthodes de résolution31Recherche dichotomique du plus grand élémentL contient n élémentsAlgorithme (récursif)Si L contient un seul élément : c'est finiSinon :Couper L en deux listes L1et L2de taille"presque" identiquesChercher m1le max de L1Chercher m2le max de L1Retourner le max de m1et m232Combiende comparaisonsOn note c(n) le nombrede comparaisonsnécessairespour la recherchedichotomiquedu plus grand élémentdansunelistede taillenc(1) = 0c(n) = c(n/2)+c(n/2)+133Déterminezla complexitéde la méthodesuivanteintfactorial(intn) {if (n == 0) {return 1;}else {return (n*factorial(n-1));34MéthodefactorielleSoitc(n) la nombrede multiplicationseffectuéesdansle calculde factorial(n).On a c(n)=c(n-1)+1, c(1)=035Recherchedu maximum dansunetable de n élémentsSi n=1, renvoyerl'uniqueélémentSinoncalculerrécursivementle maximumdes n-1 premiers élements;Le comparer avec le dernierélément;renvoyerle plus grand des deux.36Analyse : nombrede comparaisonseffectuéesC(n)= complexitéde la recherchedu plusgrand parminc(n)=c(n-1)+1c(1)=037Trier unetable de n élémentsSi n=1 rienfaireSinonrechercherle maximum de la tableéchangerle maximum et le dernierélémenttrierla sous-table constituéedes n-1premiers éléments38c(n)=c(n-1)+an+bc(1)=139Tours de HanoiCombien de mouvements au minimum pour déplacer une tour de n disques40Tour de Hanoipublic class Towers {static intnDisks=7;public static void main(String[]args){moveTowers(nDisks,'A','B','C');41// Pré-condition : n > 0public static void moveTowers(intn, charfrom, char inter, char to) {if (n==1) {moveDisk(1,from,to);}else {moveTowers(n-1,from,to,inter);moveDisk(n,from,to);moveTowers(n-1,inter,from,to);}oùmoveDisk(n,from,to) peutêtrepar exempleSystem.out.println("Disknfromfromtoto)42Complexitéde moveTowersc(n)=2c(n-1)+k (ouc(n)=2c(n-1)+1)Doncc(n)=a2n+bC(n)=(2n43On considère deux versions modifiées des tours de Hanoi.

Dans chacun des cas, on demande quel est le nombre minimum de déplacements de disques nécessaires.La pile contient initialement 2n disques, de n tailles différentes, il y a deux disques de chaque taille.

Les disques de même taille sont indistinguables.La pile comporte n disques de taille différente, mais les 3piquets sont sur un cercle et les mouvements élémentaires de disques se font du piquet oùest le disque àson suivantdans le sens des aiguilles d'une montre.44Nombres De FibonacciLa suite de FibonacciLeonardo de Pise, surnomméFibonacciest un mystère de l'histoire des mathématiques.

Il serait névers 1175 etmort en 1240 (?), et aurait vécu toute sa vie àPise.

Il a publiéun unique livre,LiberAbaci(une oeuvre collective ?).45Nombres De FibonacciReproduction des lapins: "Possédant au départ un couple delapins , combien de couples de lapins obtient-on en douze mois sichaque couple engendre tous les mois un nouveau couple àcompter du second mois de son existenceJanvier1 coupleFévrier1 coupleMars: 1 + 1 = 2 couplesAvril2 + 1 = 3 couplesMai3 + 2 = 5 couplesJuin: 5 + 3 = 8 couplesJuillet: 8 +5 =13 couplesAoût: 13 +8 =21 couplesSeptembre21 + 13 =34 couplesOctobre34 +21 =55 couplesNovembre: 55 +34 =89 couplesDécembre: 89 +55 =144 couplesJanvier144 +89 =233 couples46Nombres De FibonacciJanvier1 coupleFévrier1 coupleMars: 1 + 1 = 2 couplesAvril2 + 1 = 3 couplesMai3 + 2 = 5 couplesJuin: 5 + 3 = 8 couplesJuillet: 8 +5 =13 couplesAoût: 13 +8 =21 couplesSeptembre21 + 13 =34 couplesOctobre34 +21 =55 couplesNovembre: 55 +34 =89 couplesDécembre: 89 +55 =144 couplesJanvier144 +89 =233 couplesLe tableau correspond àce qu'on appelle lasuite des nombres de Fibonacci.47On note Fn le nombre de couples de lapins aumois n.F(n) = nombre de couples au mois (n-1)+ nombre de couples nés au mois n= nombre de couples au mois ( n-1)+ nombre de couples productifs au mois (n-1)= nombre de couples au mois ( n-1)+ nombre de couples nés au mois (n-2)F(n) = F(n-1) + F(n-2)48Nombres De Fibonaccipublic int fibonacci (int n) {if (n==0) return 0elseif (n==1) return 1elsereturn fibonacci(n-1)+fibonacci(n-2);49Analyse de la complexitéc(n)=c(n-1)+c(n-2)+1c(1)=c(0)=150Complexitéd'uneméthoderécursiverésolutiond'uneéquationderécurrenceAvec un outilde calculformel(type maple)Avec des théorèmesde maths51Récurrences linéairesDéfinition:Une relation de récurrence linéaire homogène d'ordre k , àcoefficients constants est définie parune équation de la formeLe polynôme caractéristique associéest11RuauauknknnkkkkarararrP11152Solutions d'unequationde récurrencelinéaired'ordrekL'ensembledes solutions formeun espacevectorielde dimension kSi r estracinedu polynômecaractéristiquealorsestsolution del'équation.Casdes racinesmultiplesnnru53Méthode du polynôme caractéristiqueSoit E l'équation de récurrence.Soient ri, les q racines du polynômecaractéristique de (E), riayant multiplicitémiLes solutions de (E) s'écrivent sous la formeoùles Pi(n)sont des polynômes e de degrémi-1.niqiirnP154ExempleDéterminer en fonction de u0et u1, la suitetelle queun=un-1-2un-255Réponseunu02i2u1u027r1nu02i2u1u027r2nr21i72r11i7256ExerciceUtilisezla méthodedu polynômecaractéristiquepour résoudrel'équationderécurrence61441021uuuuunnn57ExerciceChaque jour, pour mon goûter , je m'achèteou ou2F 2F 4FSoit gnle nombre de choix de goûters possibles si l'on a nFrancsDéterminer g1, g2, g3et g4Déterminer et résoudre l'équation de récurrence liant lesgn58Donnez l'ensemble des solutions des équations de récurrences suivantesun=2un-1-un-2vn=vn-1+ 6vn-259Déterminez la suite un, telle que :un= 5un-1-8un-2+ 4un-3u1= 3, u2= 11, u3= 3160Equations non homogènesSoit R'l'équation non homogèneOn lui associe l'équation homogène RLa différence entre deux solutions de R'est une solution de Rnkuna1un1akunkbnnkuna1un1akunk61Espace affine/Espace vectorielSoit snune solution particulière de R'.Toute solution de R'est obtenue àpartird'une solution de R en lui ajoutant sn62Une recette de cuisineSi l'équation est de la formeil existe une solution particulière de la formeoùQi(n) est un polynôme de degréd(Pi)+miavec mi=0 si bin'est pas racine du polynômecaractéristique, et mi= la multiplicitépourune racinenk,una1un1akunkbini1lPi(nbini1lQi(n63Exercices01201uuunn02211unuunnn64Donnez l'ensemble des solutions des équations de récurrence suivantesun= 3un-1-2un-2+ nvn= vn-1+ 6vn-2+ 5nwn= wn-1+ 6wn-2+ 3n65Résoudre l'équation de récurrenceun= 3un-1-2un-2+ n, u0= 0, u1= 066Soit sommeFactoriel, la fonction définie par Evaluer la complexitéen nombre demultiplications des méthodes récursives après67public intsommeFactoriel(intn) {intfactorielnif (n<=1) {return n+1;else {factorielnn *sommeFactoriel(n-1)sommeFactorieln-2)return sommeFactoriel(n-1) + factorieln68public intsommeFactoriel(intn){intfactorielnsommeif (n<=1) {return n+1;else {somme= sommeFactorieln-1)factorieln= n*(somme-sommeFactoriel(n-2))return somme + factorieln69public class DeuxEntiersintsommeintfactoriel;DeuxEntiersfactorieletSommeFactoriel(intnDeuxEntiersresultatif (n==0) {resultat.somme1resultat.factoriel1return resultat}else {resultatfactorieletSommeFactoriel(n-1);resultat.factoriel= n*resultat.factoriel;resultat.somme= resultat.sommeresultat.factorielreturn resultat70public intsommeFactoriel(intnDeuxEntiersresultatresultat=factorieletSommeFactoriel(n)return resultat.somme71Parmiles méthodesrécursivesvuesen exemplequellessontcellesdonton peutmaintenantcalculerla complexité?FactorielleTriTours de HanoiLes nombresde FibonnacciMaispas la recherchedichotomique72Le casde FibonacciOn obtientunecomplexitéexponentiellepour la programmationrécursive.Il existedes programmationsplusefficacesdu calculdu nièmenombredeFibonacci.73Fibonacci V2public int fibonacci(intninti =2;intfiMoins2 = 0// f(0) = 0intfiMoins1 = 1// f(1) = 1intfi = 1// f(2) = 1for (inti=3; i < n+1; i++) {// mise àjour de fiMoins2 et de fiMoins1fiMoins2= fiMoins1;fiMoins1= fi;// calcul de fifi= fiMoins2 + fiMoins1;// fi est égal au ièmeterme de la suite// fi est le nièmeterme de la suite pour tout n > 0if (n==0) return 0elsereturn fi74Complexitéde la V2Cettefoisla complexitéestlinéaire75Méthode RapideOn utilise une autre relation d'inductionOn décompose n en base 2La suite d0=1, di=2di1+decomposition(p-i),est telle que dp=n.

On calcule les fdi.111221222kkkkkkkFFFFFFFipiin2iondécomposit1076Calcul des nombres de Fibonacci V3public int[] decompose(intn) {intplog2nintauxiliaire = nint[p] decompositionfor (int indice = 0indice < p,indice ++) {decomposition[indice] = auxiliairemod2auxiliaire = auxiliaire / 2;}return decomposition77Calcul Des Nombres De Fibonacci V3public int fibonacci (int n) {inta=0;int b =1intplog2nintauxiliaireintp] decomposition = decompose (n)for (int indice =1; indice < = pindice++){auxiliaire = aa = a*a + b*b;b = (2*auxiliaire+b)*b;if (decompose(p-indice)==1 ) {b = a+b ; a = b-a ;}if (n== 1) return 1;elsereturn a78Analyse de la version 3Cettefoisla complexitéesten log(n)79Et la recherchedichotomiqueOn vaconsidérerun casplus général80Solutions de typediviser pour régnerPour résoudre un problème de taille n on divise le problème en a problèmes de taille n/b et chaque sous-problème est résolu récursivementLa phase de division et combinaison des résultats partiels a une complexitéen f(n)81Léquation de récurrence dessolutionsdiviser pour régnerT(1) = constanteT(n) = a T(n/b) + f(n)82ThéorèmeT(n) peut alors être bornéasymptotiquementcomme suitSi f(n)= O(nlogba-e) pour une constante e>0,alors T(n) =nlogbaSi f(n)=nlogba) , alors T(n) = OlognnlogbaSi f(n)=(nlogba+e)pour une constante e>0, etsi af(n/b) < cf(n) pour une constante c<1 alors T(n) =(f(n))83Lemme 1T(n)=T(bk(nlogbaPosons g(n)=10jkjjbnfa10jkjjbnfa84Lemme 2Si f(n)= O(nlogba-e) pour une constante e>0,alors g(n))=nlogbaSi f(n)=nlogbaalors g(n) =OlognnlogbaSi af(n/b) < cf(n) pour une constante c<1 alors g(n) =(f(n))85Si f(n)= O(nlogba-e) pour une constantee>0, alors g(n)=nlogbaeabjkjjngbnalog10OOn a alorsOr11loglogloglog101010logeeeabbeabbaeabeabjkjjbnnnnbnakjjekjjeab86Exempled'applicationdu cas1Recherchedichotomiquedu maximumc(n)=2c(n/2)+187Si f(n)=nlogba), alorsg(n) =OlognnlogbaOn obtientcettefoisOrabjkjjngbnalog10nnknnnbnababababbaababjkjjkjjkjjajblogloglog1logloglog101010log88Exemplede cecasLe tri dichotomiquec(n)=2c(n/2)+n89Si af(n/b) < cf(n) pour une constante c<1 alors g(n) =(f(n))cnfnfcbnfangkjjjkjj1101090On se propose de multiplier entre eux des grands nombresa) Si l'on utilise la méthode naïve, combiende multiplications élémentaires sont effectuées91Soient U et V deux nombres de 2n chiffresen base B.On peut donc écrireU=U1Bn+U2etV=V1Bn+ V2oùU1,U2,V1, V2sont des nombres ànchiffresen base B.92b) Onutilisel'égalité(U1Bn+U2)(V1Bn+ V2U1V1B2n+ (U1V2+ U2V.

1) Bn+ U2V2pour calculer récursivement la multiplication.C'est àdire que l'on ramène le problèmed'une multiplication de deux nombres de 2n chiffres àcelui de 4 multiplications dedeux nombres de n chiffres, 4 décalages et trois additions.93On suppose qu'additions et décalagess'effectuent en(n). Établir une relationde récurrence permettant d'évaluer la complexitéde cet algorithme récursif demultiplications et la résoudre.94c) On utilise maintenant l'égalité(U1Bn+ U2)(V1Bn+ V2U1V1B2n+((U1-U2)(V2-V1) + U2V2+ U1V1BnU2V2pour calculer récursivement la multiplication.

C'est àdire que l'on ramène le problème d'une multiplication de deux nombres de 2n chiffres àcelui de 3multiplications de deux nombres de n chiffres, 5 décalages et 6 additions.

On suppose qu'additions et décalages s'effectuent en(n). Établir une relationde récurrence permettant d'évaluer la complexitédecet algorithme récursif de multiplications et la résoudre.95On se propose dans cet exercice de calculerla complexitéde plusieurs algorithmesdont le but est de fusionner les p listes triées de longueur n contenues dans un tableau de listes en une seule liste triée de longueur np.96On suppose définie une classe Listecontenant entre autre une méthode permettant de fusionner une liste l1 triée de longueur n1 et un liste triée l2 de longueur n2 dont la signature estpublic staticListe fusion (Liste l1, Liste l2)et la complexitéest en(n1+n2).97Déterminer la complexitéde la méthodesuivante en fonction de n et de p.public staticListe fusionMultiple(Liste[]mesListes) {ListeL=mesListes[1];for (inti=2; i < mesListes.length; i++){L= Liste.fusion(L,mesListes[i]);}return L;98On suppose maintenant que p est une puissance de 2 et l'onpropose maintenant d'utiliser l'algorithme de multifusionrécursif suivantPour multifusionnerplistes de taille nSi p=2 utiliser fusionSinonMultifusionnerrécursivement) les p/2 première listesMultifusionnerrécursivement ) les p/2 dernières listesUtiliser fusion pour fusionner le résultat des deuxpremières étapes.99Soit c(n,p) = la complexitéde la fusion de plistes de taille n par cette méthode.Déterminez la relation de récurrence suiviepar cette suite, ainsi que c(n,2).100Posez d(n,p)=c(n,p)/n.Déterminez la relation de récurrence suivie par cette suite.Montrez que d(n,p) ne dépend pas de p.

On pourra montrer par induction sur p que pour tout p >=2, d(n,p)=d(1,p) pour tout n >0.Posez d(1,p)=f(p), et déterminez l'équation de récurrence suivie par f(p).

Résoudre cette équation.

En déduire c(n,p).101On consid