Next PDF List

1Calculs de complexitéd'algorithmesNotations asymptotiques : 0 et Complexitédes algorithmesExemples de calcul de complexité2Complexités d'un algorithmeUn algorithme àpartir d'une donnée établit un 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 n 3Complexité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 le terme dominant5DéfinitionsOn dit que f est dominéepar g (notéf= O (g)) lorsqueOn dit que f est du même ordre de grandeurque g et l'on note f = (g) lorsque f=O(g) et g=O(f).)()(,,0,00ncgnfnncn6Définitions f est négligeable devant g, (notéf =o(g)) lorsque f(n)/g(n) tend vers 0 quand n tend vers l'infiniOn dit que f est équivalenteàg lorsque f(n)/g(n) tend vers 1 lorsque n tend vers l'infini7Relations entre O, o et autresf est négligeable devant g implique f est dominéepar g ?f est équivalenteàgimpliquef est du même ordre de grandeurque g ?8RemarqueHormis pour l'équivalence, ces notions sont indépendantes des constantes multiplicatives non nulles.Par exemple : si f est négligeable devant g,alors cfest négligeable devant c'g pour tout réels c et c' non nuls.

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

Pour quelles valeurs de p a-t-on P(n)=O(np)? Pour quelles valeurs de p a-t-on P(n)=(np)?10Montrer que pour tout entier k, on a10()nkkiin11Échelle De ComparaisonExerciceSoient les fonctionsf1(n)=n, f2(n)=2n, f3(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(fj),fi=O(fj)fi=(fj).12109Instructions/secondes(1 gigaHertz)n51015201001000log n3 10-9 s4 10-9 s4 10-9 s5 10-9 s7 10-9 s10-8 s2n10 10-9 s2 10-8s3 10-8 s4 10-8 s2 10-7 s2 10-6 snlogn12 10-9 s3 10-8s6 10-8s10-7s7 10-7s10-5sn225 10-9 s10-7 s2,25 10-7 s4 10-7 s10-5 s10-3 sn53 10-6 s10-4 s7,59 10-4 s3 10-3 s10 s106 s= 11 jours2n32 10-9 s10-6 s3,28 10-5 s10-3 s1,2 1021 s4 1011 siècles10292 s3 10282 sièclesn !120 10-9 s4 10-3 s1,4 103s=23 minutes2,4 109 s =77 ans10147 s3 10139 siècles10 500 snn3 10-6 s10 s4,37 108s =13 ans1017s =3 107siècles10191s3 10181siècles10 3000 s13En une Journée, un an jusqu'oùpeut-on, aller ?f(n)1 jour1 ann9 101331 1015log(n)103101010162n4.5 101315 1015n log(n)2 10125 1014n21071.7 108n56002 0002n3255n!1618nn121314Pourquoi Utiliser O Et Pour Mesurer Des Complexités?Expressions àune constante multiplicative prè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 la taille 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 I1;I2a 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 < n; i++) {I1}est en (n*f1(n))19Si une instruction I se trouve au coeur de k boucles for imbriquées, chacune d'elle de la forme for (intim=0; im< n ; im++)où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; im++)où0 < m < (k+1) avec i0=ncombien de fois l'instruction I est elle exécutée ?21Règle 4 Boucle While(C) {I}Évaluation de C en (f(n))I en (f1(n))Boucle while est exécutée (g(n)) foiswhile (C) {I}est en (g(n)*max(f(n),f1(n)))22Estimer les complexités des morceaux de codes suivants, sachant que l'instruction I1est en (1) et I1ne modifie pas les entiers i, j, k et nfor (inti=0; i < n; i++) {for (intj=i; j < n; j++) {for (intk=0; k < j; k++) {I1}}}23Estimer les complexités des morceaux de codes suivants, sachant que et les instructions I1, I2, I3 sont en (1) et ne modifie pas les entiers i, j, k et n inti=1;intj=1;while (i On utilise la méthode "convertionDirecte".

Quelle en est la complexité?public intconvertionDirecte(int[] a, intb) {intrésultat =a[0];intauxiliaire;for (intrang =1; rang < a.length; rang++) {if (a[rang]!= 0) {auxiliaire = a[rang];for (intindice =0; indice

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

Ecrire cette 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.length;intrésultat=a[n-1];for (intrang = n-2; rang >= 0; rang--){résultat = b* résultat +a[rang];}return résultat;}28On désire élever l'entier a àla puissance n.

Quelle est la complexitéde la méthode suivante ?public intpuissance(intn, inta) {intrésultat= a;for(inti =1; i

Quel en est la complexité?public intpuissance(intn, inta) {intaux = n; intpuissanceDea= a;intrésultat=1;while( aux != 0 ) {if (aux mod2 == 1) {résultat = résultat * puissanceDea;}aux=aux/2;puissanceDea= puissanceDea* puissanceDea;}return résultat;}30Programmation 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 L2 de taille "presque" identiquesChercher m1le max de L1Chercher m2le max de L1Retourner le max de m1et m232Combiende comparaisons?On 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 multiplications effectué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 maximum des 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 plus grand parminc(n)=c(n-1)+1c(1)=037Trier unetable de n élémentsSi n=1 rienàfaireSinonrechercherle maximum de la tableéchangerle maximum et le dernierélémenttrierla sous-table constituéedes n-1 premiers é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, char from, 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 exemple: System.out.println("Disk"+n+"from"+from+"to"+to)42Complexitéde moveTowersc(n)=2c(n-1)+k (ouc(n)=2c(n-1)+1)Doncc(n)=a2n+bC(n)=(2n)43On 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 3 piquets sont sur un cercle et les mouvements élémentaires de disques se font du piquet oùest le disque àson suivant dans 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 et mort en 1240 (?), et aurait vécu toute sa vie àPise.

Il a publiéun unique livre, Liber Abaci(une oeuvre collective ?).45Nombres De FibonacciReproduction des lapins: "Possédant au départ un couple de lapins , combien de couples de lapins obtient-on en douze mois si chaque couple engendr