Algorithmique & Programmation Orientée Objet Semestre 2 ST Précision, rapidité & complexité
Cours | TD | TP
Problématique | Précision des calculs | Notions d'efficacité | Evaluer les performances | La complexité
Version PDF
Clavier.class - Ecran.class - Documentation
Problématique Pas d'impasse possible sur les notions de véracité des résultats, d'efficacité et de rapidité au cours de la conception d'algorithmes "complexes" Implanter une solution informatique correcte et s'assurer que les résultats obtenus correspondent aux résultats attendus Précision des ordinateurs non infinie -> Erreurs de calcul inévitables -> S'assurer qu'elles ne dépassent pas une limite acceptable Capacités des ordinateurs non infinies -> Impossibilité pratique d'utiliser une solution algorithmiquement correcte -> S'assurer de la possibilité pratique d'exécuter les algorithmes conçus Délai d'exécution acceptable Quantité de ressources utilisée acceptable (mémoire, disque, bande passante réseau, ...) Exemple Modélisation d'un phénomène physique réel Existence ou non d'une solution "analytique" Si pas de solution analytique, "simulation" numérique -> Différence intrinsèque avec la réalité car modélisation informatique avec des approximations possiblement nombreuses -> Validation par test -> Recalage du modèle (du code informatique) pour tendre vers la meilleure solution possible -> Arbitrage entre temps de calcul, qualité de la solution trouvée et précision du modèle Précision de calcul Limitations intrinsèques liées aux types des variables Valeurs minimales et maximales pour les variables entières -> Risque de dépassement Valeurs minimales et maximales de l'exposant pour les variables réelles -> Risque de dépassement Nombre de chiffres de précision de la mantisse pour les variables réelles -> Erreurs d'arrondi -> Perte de précision float 8 chiffres de précision au maximum sur la mantisse Exposant de -38 à +38 avec 8 chiffres de précision sur la mantisse double 16 chiffres de précision au maximum sur la mantisse Exposant de -308 à + 308 avec 16 chiffres de précision sur la mantisse Codage des nombres réels imprécis par nature Erreur de calcul infinitésimale possible à chaque opération en réel (+, -, *, /, pow, log, sin , ...) -> 2 sources d'erreur Souvent, accumulation et amplification des erreurs successives au lieu de compensation -> Résultats aberrants Utilisation de variables de type float
/* Test de precision sur les float */ public static void main(String [] args) { /* Travail sur des float (simple precision) */ float v; /* Stockage de la valeur 1.0 */ /* -> Pas de perte de precision */ /* -> Pas de probleme */ v = 1.0F; Ecran.formater("%22.20f\n\n",v); /* Stockage de la valeur 1.0e-08 */ /* -> Perte de precision sur le stockage */ /* -> Probleme */ v = 1.0e-8F; Ecran.formater("%22.20f\n\n",v); /* Ajout a 1.0 de la valeur 1.0e-8 */ /* "Disparition" de la valeur ajoutee */ /* -> Perte de precision sur le stockage */ /* -> Probleme */ v = 1.0F + 1.0e-8F; Ecran.formater("%22.20f\n",v); Ecran.formater("%22.20f\n\n",1.00000001F); /* Ajout a 1.0 de la valeur 1.0e-7 */ /* Perte de precision sur le stockage */ /* -> Probleme */ v = 1.0F + 1.0e-7F; Ecran.formater("%22.20f\n",v); Ecran.formater("%22.20f\n\n",1.0000001F); /* Execution d'une operation mathematique */ /* sur une valeur entachee d'une erreur */ /* de stockage */ /* Perte de precision avec accumulation */ /* -> Probleme */ v = (1.0F + 1.0e-7F)*4.0F; Ecran.formater("%22.20f\n",v); Ecran.formater("%22.20f\n\n",4.0000004F); /* Stockage de la valeur 0.3e10 float */ /* Pas de perte de precision */ /* -> Pas de probleme */ v = 0.3e10F; Ecran.formater("%22.20f\n\n",v); /* Multiplication de 0.3e10 float */ /* par 0.3e10 float */ /* Erreur de calcul et/ou perte de precision */ /* -> Probleme */ v = 0.3e10F*0.3e10F; Ecran.formater("%22.20f\n",v); Ecran.formater("%22.20f\n\n",0.9e19F); /* Depassement de capacite */ /* -> Probleme */ v = 0.3e10F*0.3e10F*0.3e10F*0.3e10F*0.3e10F; Ecran.formater("%22.20f\n\n",v); }
TestPrecisionFloat.java - Exemple d'exécution
Utilisation de variables de type double
/* Test de precision sur les double */ public static void main(String [] args) { /* Travail sur des double (double precision) */ double v; /* Stockage de 1.0 */ /* -> Pas de perte de precision sur le stockage */ /* -> Pas de probleme */ v = 1.0; Ecran.formater("%26.18f\n\n",v); /* Stockage de 0.9999999999999999 */ /* -> Pas de perte de precision sur le stockage */ /* -> Pas de probleme */ v = 0.9999999999999999; Ecran.formater("%26.18f\n\n",v); /* Stockage de 0.99999999999999999 */ /* -> Perte de precision sur le stockage */ /* -> Probleme */ v = 0.99999999999999999; Ecran.formater("%26.18f\n\n",v); /* Stockage de 1.0e-16 */ /* -> Pas de perte de precision sur le stockage */ /* -> Pas de probleme */ v = 1.0e-16; Ecran.formater("%26.18f\n\n",v); /* Ajout a 1.0 de la valeur 1.0e-15 */ /* -> Pas de perte de precision sur le stockage */ /* ni d'erreur de calcul */ /* -> Pas de probleme */ v = 1.0 + 1.0e-15; Ecran.formater("%26.18f\n",v); Ecran.formater("%26.18f\n\n",1.000000000000001); /* Ajout a 1.0 de la valeur 1.0e-16 */ /* -> perte de precision sur le stockage */ /* ou erreur de calcul */ /* -> Probleme */ v = 1.0 + 1.0e-16; Ecran.formater("%26.18f\n",v); Ecran.formater("%26.18f\n\n",1.0000000000000001); /* Stockage de la valeur 1.000000000000001 */ /* -> Pas de probleme */ /* Multiplication par 6.0 */ /* -> Erreur de calcul */ /* Pas de perte de precision sur le stockage */ /* car bonne valeur stockable */ /* -> Probleme */ v = 1.00000000000011; Ecran.formater("%26.18f\n",v); v = v*6.0; Ecran.formater("%26.18f\n",v); Ecran.formater("%26.18f\n\n",6.00000000000066); /* Stockage de la valeur 1.111e100 */ /* -> Pas de perte de precision */ /* -> Pas de probleme */ v = 1.111e100; Ecran.formater("%26.18e\n\n",v); /* Multiplication de 1.111e100 par 1.111e100 */ /* -> Erreur de calcul */ /* Pas de perte de precision sur le stockage */ /* car bonne valeur stockable */ /* -> Probleme */ v = 1.111e100*1.111e100; Ecran.formater("%26.18e\n",v); Ecran.formater("%26.18e\n\n",1.234321e200); /* Depassement de capacite */ /* -> Probleme */ v = 1.111e100*1.111e200*1.111e100*1.111e200; Ecran.formater("%26.18f\n\n",v); }
TestPrecisionDouble.java - Exemple d'exécution
Erreurs de calcul -> Conclusion erronnée
/* Test de precision sur les double */ /* Obtention d'une conclusion erronnee */ /* a un test d'orthogonalite */ /* Un type agrege de stockage d'une direction */ /* dans un espace a trois dimensions */ /* a coordonnees reelles */ static class Direction3D { double x = 0.0; double y = 0.0; double z = 0.0; } /* Calcul du produit vectoriel */ /* de deux Direction3D */ static Direction3D produitVectoriel(Direction3D d1,Direction3D d2) { Direction3D d = new Direction3D(); d.x = d1.y*d2.z - d1.z*d2.y; d.y = d1.z*d2.x - d1.x*d2.z; d.z = d1.x*d2.y - d1.y*d2.x; return(d); } /* Calcul du produit scalaire */ /* de deux Direction3D */ static double produitScalaire(Direction3D d1,Direction3D d2) { double res = d1.x*d2.x+d1.y*d2.y+d1.z*d2.z; return(res); } /* Test d'orthogonalite entre deux Direction3D */ static boolean estOrthogonal(Direction3D d1,Direction3D d2) { boolean res = ( produitScalaire(d1,d2) == 0.0 ); return(res); } /* Affichage ecran d'une Direction3D */ static void afficher(Direction3D d) { Ecran.formater("%20.20f\n",d.x); Ecran.formater("%20.20f\n",d.y); Ecran.formater("%20.20f\n",d.z); } /* Programme principal */ public static void main(String [] args) { /* Declaration et initialisation */ /* de deux Direction3D */ Direction3D d1 = new Direction3D(); Direction3D d2 = new Direction3D(); d1.x = 1.1; d1.y = 2.1; d1.z = 3.3; d2.x = 3.7; d2.y = 2.6; d2.z = 1.3; /* Calcul d'une direction orthogonale */ /* à d1 et à d2 */ Direction3D d3 = produitVectoriel(d1,d2); /* Affichage ecran de d1, d2 et d3 */ Ecran.afficherln("d1 :"); afficher(d1); Ecran.afficherln("d2 :"); afficher(d2); Ecran.afficherln("d3 :"); afficher(d3); Ecran.sautDeLigne(); /* Tests d'orthogonalite */ /* entre d1 et d3 et entre d2 et d3 */ /* et affichage ecran des resultats */ Ecran.afficherln("d1 orthogonal à d3 : ",estOrthogonal(d1,d3)); Ecran.afficherln("d2 orthogonal à d3 : ",estOrthogonal(d2,d3)); /* Affichage ecran des produits scalaires */ /* sur lesquels sont bases les tests */ /* d'orthogonalite */ Ecran.formater("Produit scalaire de d1 et d3 : %20.20f\n",produitScalaire(d1,d3)); Ecran.formater("Produit scalaire de d2 et d3 : %20.20f\n",produitScalaire(d2,d3)); }
TestPrecision.java - Exemple d'exécution
Amplification des erreurs de calcul
/* Precision non infinie des reels stockes */ /* dans des variables de type float */ /* Erreurs de calcul successives */ /* sur la fonction Math.sqrt */ /* -> Amplification de l'erreur resultante */ public static void main(String [] args) { float v; for ( int i = 1 ; i <= 25 ; i++ ) { Ecran.formater("%2d",i); v = 2.0F; for ( int j = 0 ; j < i ; j++ ) { v =(float) Math.sqrt(v); } Ecran.formater("%24.19f",v); for ( int j = 0 ; j < i ; j++ ) { v = v*v; } Ecran.formater("%24.19f\n",v); } }
TestPrecisionSqrtFloat.java - Exemple d'exécution
/* Precision non infinie des reels stockes */ /* dans des variables de type double */ /* Erreurs de calcul successives */ /* sur la fonction Math.sqrt */ /* -> Amplification de l'erreur resultante */ public static void main(String [] args) { double v; for ( int i = 1 ; i <= 55 ; i++ ) { Ecran.formater("%2d",i); v = 2.0; for ( int j = 0 ; j < i ; j++ ) { v = Math.sqrt(v); } Ecran.formater("%24.19f",v); for ( int j = 0 ; j < i ; j++ ) { v = v*v; } Ecran.formater("%24.19f\n",v); } }
TestPrecisionSqrtDouble.java - Exemple d'exécution
Conclusion Quel type réel choisir lors de l'implantation effective d'un programme? Sauf à devoir économiser de la mémoire, choisir le type le plus précis -> En Java, choisir le type double Toujours être prudent avec un test d'égalité entre un réel et une valeur numérique Quelles notions d'efficacité? Rapidité et facilité de développement (algorithmes plus ou moins complexes) Empreinte mémoire Rapidité intrinsèque d'exécution Gagner sur un point -> Perdre sur l'un ou l'autre point, voire les deux -> Compromis Puissance CPU (Central Processor Unit) Nombre d'opérations pouvant être réalisées par seconde Unités Kilo (103, millier) Méga (106, million) Giga (109, milliard) Téra (1012, million de millions) Péta (1015, million de milliards) Exa (1018) Zetta (1021) ... Unités Milli (10-3, millième) Micro (10-6, millionième) Nano (10-9, milliardième) Pico (10-12) Femto (10-15) ... Nombre de coeurs implantés: Un ou plusieurs coeurs (1, 2, 4, 6, 8, 10, 12, 15, 18, plusieurs dizaines d'ici à la fin de la prochaine décennie) dans les ordinateurs classiques Un, deux, quatre ou huit coeurs implantés dans les téléphones portables Un, deux ou quatre coeurs dans les tablettes Des centaines de milliers, voire des millions de coeurs dans les super-ordinateurs D'une centaine à plusieurs milliers de coeurs sur les cartes graphiques des ordinateurs personnels (UC et ordinateurs portables) De quelques à quelques dizaines de coeurs sur les puces graphiques des tablettes et des téléphones portables Coeurs cadencés de 1 à 5 Ghz (milliards de "cycles" par seconde) De l'ordre d'une opération (calcul mathématique, test, ...) par Hz et par coeur -> Nombre d'opérations réalisables par seconde (ops) = nombre de coeurs x fréquence - Ops (Operation Per Second): Opération par seconde - Flops (FLoating point Operation Per Second): Opération flottante (sur valeur réelle) par seconde - Ips (Integer operation Per Second): Opération entière (sur valeur entière) par seconde Puissance brute: Ordinateurs personnels: De quelques à quelques dizaines de Gops (giga, milliards d'opérations par seconde) Super-calculateurs: Actuellement une quarantaine de Pops (peta, millions de milliards d'opérations par seconde) pour la machine la plus puissante au monde (une centaine de milliers de coeurs) Prévisions météorologiques Evolution climatique Simulation nucléaire Industrie automobile Industrie aéronautique Industrie pharmaceutique Astronomie Physique fondamentale ... Cartes graphiques des ordinateurs personnels: Plusieurs centaines de Gops à plusieurs Tops (téra, milliers de milliards d'opérations par seconde) (calcul d'images, compression/décompression de flux vidéo, traitement d'images, intelligence artificielle, ...) Quantité de mémoire vive Ordinateurs personnels: Quelques à quelques dizaines de Go (milliards d'octets) Super-calculateurs: Plusieurs dizaines de To (milliers de milliards d'octets)
/* Test d'utilisation de de plus en plus */ /* de memoire jusqu'a plantage */ /* Structure de reservation d'un tableau */ /* de float pour 1 Mo de memoire */ static class Structure { float [] t = new float[256*1024]; } /* Programme principal */ public static void main(String [] args) { Structure [] tst = new Structure[1000]; int i = 0; boolean go = true; while ( go ) { try { tst[i] = new Structure(); Ecran.formater("%10d :%10d\n",i,i*4*256*1024); i++; } catch (Error error) { Ecran.afficherln("Plus de memoire!"); Ecran.afficherln(error); go = false; } } Ecran.afficherln(i," Mo reservables"); }
TestMemoire.java - Exemple d'exécution
Evaluer expérimentalement les performances Interrogation de l'une des horloges de l'ordinateur pour calculer un temps d'exécution Problème: Précision par forcément très bonne tant en temps absolu (date:heure) qu'en temps relatif (temps écoulé entre deux tops horloge) Sur les PC sous Windows, méthodes usuelles d'accès à l'horloge précises à environ un 60ème de seconde (15 ou 16 ms, très très long à l'échelle de l'ordinateur) En langage Java, plusieurs méthodes pour mesurer le temps Méthode 1 Appel à la fonction long System.currentTimeMillis() -> Un entier long contenant le nombre de ms (millième de seconde) écoulés depuis le 1er janvier 1970 à 0h GMT selon l'horloge de l'ordinateur -> Un temps absolu Précision de l'ordre de 16 ms sur les PC
/* Mesure du temps dans un programme Java */ public class MesurerLeTemps { /* Programme principal */ public static void main(String [] args) { /* Temps ecoule depuis le 1/1/70 0h GMT */ long t = System.currentTimeMillis(); Ecran.afficherln(t," ms depuis le 1/1/70 0h GMT"); Ecran.formater("%d j, %d h, %d mn, %d s, %d ms\n", t/1000/60/60/24, (t/1000/60/60)%24, (t/1000/60)%60, (t/1000)%60, t%1000); Ecran.sautDeLigne(); /* Temps ecoule entre deux appels successifs */ /* a System.currentTimeMillis() */ /* Dix executions successives */ for ( int cpt = 0 ; cpt < 10 ; cpt++ ) { long t1 = System.currentTimeMillis(); long t2 = System.currentTimeMillis(); Ecran.formater("%d-%d = %d ms\n",t1,t2,t2-t1); } Ecran.sautDeLigne(); /* Temps ecoule entre deux appels */ /* a System.currentTimeMillis() */ /* avec "quelque chose" entre */ /* Dix executions successives */ long j = 0; for ( int cpt = 0 ; cpt < 10 ; cpt++ ) { long t1 = System.currentTimeMillis(); for ( long i = 0L ; i < 1000000000L ; i++ ) { j++; } long t2 = System.currentTimeMillis(); Ecran.formater("%d-%d = %d ms\n",t1,t2,t2-t1); } } }
MesurerLeTemps.java - Exemple d'exécution
Méthode 2 Appel à la fonction long System.nanoTime() -> Un entier long contenant une référence de temps non absolue comptée en ns (milliardième de seconde) Différence entre les deux valeurs obtenues par appel à cette fonction: Temps (en ns) écoulé entre les deux appels Temps compté en ns, mais précision pas aussi bonne que la ns et fonction de l'ordinateur
/* Mesure du temps dans un programme Java */ public class MesurerLeTempsAvecPrecision { /* Programme principal */ public static void main(String [] args) { /* Temps ecoule entre deux appels successifs */ /* a System.nanoTime() */ /* Dix executions successives */ for ( int cpt = 0 ; cpt < 10 ; cpt++ ) { long t1 = System.nanoTime(); long t2 = System.nanoTime(); Ecran.formater("%d-%d = %d ns\n",t1,t2,t2-t1); } Ecran.sautDeLigne(); /* Temps ecoule entre deux appels */ /* a System.nanoTime() */ /* avec "quelque chose" entre */ /* Dix executions successives */ long j = 0; for ( int cpt = 0 ; cpt < 10 ; cpt++ ) { long t1 = System.nanoTime(); for ( long i = 0L ; i < 1000000000L ; i++ ) { j++; } long t2 = System.nanoTime(); long dt = t2-t1; long ns = dt%1000; dt = dt/1000; long mls = dt%1000; dt = dt/1000; long ms = dt%1000; long s = dt/1000; Ecran.formater("%3d s, %3d ms, %3d mls, %3d ns\n",s,ms,mls,ns); } } }
MesurerLeTempsAvecPrecision.java - Exemple d'exécution
Variations assez sensibles des temps d'exécution d'un même programme (ou sous-programme) d'un lancement à un autre lancement Pas qu'une seule application en exécution à chaque instant sur une machine Puissance CPU disponible partagée entre tous les processus en cours d'exécution -> Plus ou moins de ressources disponibles avec pour conséquence des temps d'exécution plus ou moins longs Ralentissement automatique des processeurs quand ils chauffent trop Ralentissement automatique des processeurs lorsqu'ils n'ont rien à faire, retour automatique à la vitesse nominale après un certain temps de travail "à 100%" Pour les programmes Java: Optimisation d'une seconde exécution par analyse automatique de ce qui s'est passé au cours de la première exécution (optimisation du code "à la volée") -> Cela va plus vite à la seconde exécution La complexité Autre paramètre important à prendre en compte dans l'évaluation des performances d'un algorithme: La capacité en terme de "scalabilité" Notion appliquée à tous les problèmes consistant à traiter un ensemble de données dont la taille impacte la rapidité de traitement But: Conservation de temps d'exécution acceptables pour les tailles des ensembles traités Analyse du fonctionnement de l'algorithme -> Evaluation de l'"ordre de temps" ("en quel temps?") de cet algorithme Evaluation définie en fonction de la taille n de l'ensemble de données traité Notée sous la forme O(f(n)) où f(n) est la fonction mathématique définissant les temps d'exécution relatifs en fonction de n -> Suppression des coefficients constants: O(2n) est simplifié en O(n) -> Suppression des termes mineurs: O(n2+n) est simplifié en O(n2) Temps "classiques" Du mieux au pire: O(1): Temps d'exécution "constant" -> Traiter un ensemble de taille k*n prend autant de temps que traiter un ensemble de taille n O(log(n)): Temps d'exécution "logarithmique" -> Traiter un ensemble de taille k*n prend log(k) fois plus de temps que traiter un ensemble de taille n O(n): Temps d'exécution "linéaire" -> Traiter un ensemble de taille k*n prend k fois plus de temps que traiter un ensemble de taille n O(n*log(n)): Temps d'exécution "log-linéaire" -> Traiter un ensemble de taille k*n prend k*log(k) fois plus de temps que traiter un ensemble de taille n O(n2): Temps d'exécution "quadratique" -> Traiter un ensemble de taille k*n prend k2 fois plus de temps que traiter un ensemble de taille n 4 fois plus long pour 2 fois plus grand 100 fois plus long pour 10 fois plus grand O(n3): Temps d'exécution "cubique" -> Traiter un ensemble de taille k*n prend k3 fois plus de temps que traiter un ensemble de taille n 1000 fois plus long pour 10 fois plus grand O(2n): Temps d'exécution en "puissance de 2" -> Traiter un ensemble de taille k*n prend 2k fois plus de temps que traiter un ensemble de taille n 210 soit environ 1000 fois plus long pour 10 fois plus grand 220 soit environ 1000000 fois plus long pour 20 fois plus grand O(n!): Temps d'exécution "factoriel" O(n*m): Temps d'exécution linéaire en n et linéaire en m (Cas d'un problème dépendant de 2 ensembles de tailles n et m) Détermination de l'ordre de temps d'un algorithme Recherche de la fonction mathématique définissant combien de fois est exécutée l'instruction qui est exécutée le plus de fois Analyse du cas le plus défavorable susceptible d'arriver Exemple: Si temps linéaire dans le cas général, mais temps quadratique dans au moins un cas particulier -> Temps quadratique Analyse des "nids de boucles" (boucles imbriquées) à la recherche de celles dépendant de la taille de l'ensemble Exercice possiblement difficile pour tant que pour et tant que dans des fonctions -> Instructions plus ou moins masquées récursivité Exemples n: Taille de l'ensemble Une boucle "pour i de 1 à n faire" -> Temps en O(n) Une boucle "pour i de 1 à 2*n faire" -> Temps est en O(2n) -> Temps en O(n) Une boucle "pour i de 1 à n faire" contenant une boucle "pour j de 1 à n faire" -> Temps en O(n2) Une boucle "pour i de 1 à n faire" contenant une boucle "pour j de 1 à i faire" -> Temps en O(n2) car i de la deuxième boucle dépendant de n Algorithmes en O(n): Algorithmes de recherche séquentiel Contruits sous la forme d'une boucle indicée sur n Algorithmes en O(n2): Algorithmes de tri par sélection, par insertion et à bulle Tous trois construits sous la forme de deux boucles imbriquées indicées sur n Différences de vitesses dues à des différences d'efficacité d'exécution du contenu de boucle et pas à l'architecture de l'algorithme Algorithmes à base de décomposition dichotomique: Nombre d'étapes de l'ordre log2(n) -> Temps d'exécution caractérisé par un terme en log(n) Recherche dichotomique: Pas d'autre boucle -> Temps d'exécution en O(log(n)) Tris à base de décomposition dichotomique (fusion, quicksort): A chaque étape, fusion ou réorganisation basée sur une boucle indicée en n -> Temps d'exécution en O(n*log(n)) Exemple 1: Résolution d'un système de n équations linéaires à n inconnues par pivot de Gauss
/* Permutation de Gauss */ static void permutation(int l,double [][] m,double [] v) { int ll = l; int n = v.length; double aux; while ( m[ll][l] == 0.0 ) { ll++; } for ( int i = l ; i < n ; i++ ) { aux = m[l][i]; m[l][i] = m[ll][i]; m[ll][i] = aux; } aux = v[l]; v[l] = v[ll]; v[ll] = aux; } /* Transformation de Gauss */ static void transformation(double [][] m,double [] v) { double facteur; int n = v.length; for ( int i = 1 ; i < n ; i++ ) { if ( m[i-1][i-1] == 0.0 ) permutation(i-1,m,v); for ( int j = i ; j < n ; j++ ) { facteur = m[j][i-1]/m[i-1][i-1]; for ( int k = i-1 ; k < n ; k++ ) { m[j][k] = m[j][k] - m[i-1][k]*facteur; } v[j] = v[j] - v[i-1]*facteur; } } } /* Extraction de Gauss */ static double [] extraction(double [][] a,double [] b) { int n = b.length; double [] v = new double[n]; v[n-1] = b[n-1]/a[n-1][n-1]; for ( int i = n-2 ; i >= 0 ; i-- ) { v[i] = b[i]; for ( int j = n-1 ; j > i ; j-- ) { v[i] = v[i] - v[j]*a[i][j]; } v[i] = v[i]/a[i][i]; } return v; } /* Resolution de Gauss */ static double [] resolution(double [][] a,double [] b) { double [] v; transformation(a,b); v = extraction(a,b); return v; }
TempsSystemeEquationsLineaires.java - Exemple d'exécution
Transformation de Gauss (triangularisation): Trois boucles pour imbriquées où chaque boucle est exécutée de l'ordre de n fois Extraction de Gauss: Deux boucles pour imbriquées où chaque boucle est exécutée de l'ordre de n fois -> Algorithme en O(n3+n2) -> Algorithme en O(n3) par suppression du terme quadratique mineur Exemple 2: Nombre de Fibonacci par méthode récursive
/* Calcul de Fib(n) par methode recursive */ /* - Fib(0) = 0 */ /* - Fib(1) = 1 */ /* - Fib(n) = Fib(n-1)+Fib(n-2) */ static long fib(int n) { long res; switch (n) { case 0 : case 1 : { res = n; } break; default : { res = fib(n-1)+fib(n-2); } break; } return res; }
TempsFibonacci.java - Exemple d'exécution
Conséquence d'un appel à fib(n): Nombre d'appels à fib égal à 1 + nombre d'appels entraîné par l'appel à fib(n-1) + nombre d'appels entraîné par l'appel à fib(n-2) selon la définition récurrente: f0 = 1 f1 = 1 fn = 1+fn-1+fn-2 -> Algorithme en O(f(n)) où f est une fonction de Fibonacci
/* Variable globale de calcul du nombre */ /* d'appels a la fonction fib */ static long nb; /* Calcul de Fib(n) par methode recursive */ /* - Fib(0) = 0 */ /* - Fib(1) = 1 */ /* - Fib(n) = Fib(n-1)+Fib(n-2) */ static long fib(int n) { long res; nb++; switch (n) { case 0 : case 1 : { res = n; } break; default : { res = fib(n-1)+fib(n-2); } break; } return res; }
TempsFibonacci2.java - Exemple d'exécution
Trois colonnes: Temps de calcul de fib(n) Nombre d'appels à fib() lors du calcul de fib(n) Temps moyen d'un appel à fib()
Conclusion Problème: Que faire si l'ordre de temps déterminé pour un algorithme est non satisfaisant? Solution: Changer d'algorithme ou modifier le design Pas toujours simple Pas toujours possible Meilleur ordre de temps possible pas forcément bon Exemple: Les algorithmes de tri