Algorithmique & Programmation Orientée Objet Semestre 2 ST Précision, rapidité & complexité
Cours | TD - Corrections | TP
Exercice n°1 On donne les versions classique et récursive du sous-algorithme de calcul de n!:
Factoriel.lda { Calcul de n! par methode recursive } entier fonction factoriel(-> entier n) entier res si n == 0 alors res <- 1 sinon res <- factoriel(n-1)*n fsi retourner res fin fonction { Calcul de n! par methode sequentielle } entier fonction factoriel(-> entier n) entier i entier res <- 1 si n > 1 alors pour i de 2 à n faire res <- res * i fait fsi retourner res fin fonction Clavier.class - Ecran.class - Exemple d'exécution
Evaluer les temps d'exécution de ce calcul sous ces deux formes. Exercice n°2 On donne le sous-algorithme de calcul du produit matrice-vecteur:
ProduitMatriceVecteur.lda { Fonction de calcul du produit d'une matrice } { carree de reel de taille n.n par un tableau } { de reel de taille n } { n quelconque } { Resultat: Un tableau de taille n } action produitMatriceVecteur(-> reel [][] m, -> reel [][] v, reel [][] w ->) entier n <- longueur(v) entier i entier j pour i de 0 à n-1 faire w[i] <- 0.0 pour j de 0 à n-1 faire w[i] <- w[i] + m[i][j]*v[j] fait fait fin action Clavier.class - Ecran.class - Exemple d'exécution
Evaluer son ordre de temps d'exécution. On donne les sous-algorithmes de calcul du produit matrice-matrice en versions carré et générale:
ProduitsMatriceMatrice.lda { Fonction de calcul du produit d'un tableau } { de reel de dimension 2 de taille n.n } { par un tableau de reel de dimension 2 } { de taille n.n } { (n quelconque) } { Retour: Un tableau de dimension 2 } { de taille n.n } reel [][] fonction produitMatricesCarrees(-> reel [][] m1, -> reel [][] m2) entier i entier j entier k entier n <- longueur(1,m1) reel [n][n] r pour i de 0 à n-1 faire pour j de 0 à n-1 faire r[i][j] <- 0.0 pour k de 0 à n-1 faire r[i][j] <- r[i][j] + m1[i][k]*m2[k][j] fait fait fait retourner r fin fonction { Fonction de calcul du produit d'un tableau } { de reel de dimension 2 de taille n.m } { par un tableau de reel de dimension 2 } { de taille m.p } { n, m et p quelconques } { Retour: Un tableau de reel de dimension 2 } { de taille n.p } reel [][] fonction produitMatriceMatrice(-> reel [][] m1, -> reel [][] m2) entier n <- longueur(1,m1) entier m <- longueur(2,m1) entier p <- longueur(2,m2) reel [n][p] r entier i entier j entier k pour i de 0 à n-1 faire pour j de 0 à p-1 faire r[i][j] <- 0.0 pour k de 0 à m-1 faire r[i][j] <- r[i][j] + m1[i][k]*m2[k][j] fait fait fait retourner r fin fonction Clavier.class - Ecran.class - Exemple d'exécution
Evaluer leurs ordres de temps d'exécution. Exercice n°3 On donne les sous-algorithmes suivants:
RecursiviteEnArbreParfait.lda { Parcours recursif en arbre unaire } { de profondeur n } entier fonction parcoursUnaire(-> entier n) entier nb <- 1 si n > 0 alors nb <- nb+parcoursUnaire(n-1) fsi retourner nb fin fonction { Parcours recursif en arbre binaire parfait } { de profondeur n } entier fonction parcoursBinaire(-> entier n) entier nb <- 1 si n > 0 alors nb <- nb+parcoursBinaire(n-1) nb <- nb+parcoursBinaire(n-1) fsi retourner nb fin fonction { Parcours recursif en arbre ternaire parfait } { de profondeur n } entier fonction parcoursTernaire(-> entier n) entier nb <- 1 si n > 0 alors nb <- nb+parcoursTernaire(n-1) nb <- nb+parcoursTernaire(n-1) nb <- nb+parcoursTernaire(n-1) fsi retourner nb fin fonction Clavier.class - Ecran.class - Exemple d'exécution
a) Quel est le résultat de l'appel au sous-algorithme parcoursUnaire sur les valeurs 0, 1, 2, 3, 4, 5, 6. b) Quel est le résultat de l'appel au sous-algorithme parcoursBinaire sur les valeurs 0, 1, 2, 3, 4, 5, 6. c) Quel est le résultat de l'appel au sous-algorithme parcoursTernaire sur les valeurs 0, 1, 2, 3, 4, 5, 6. d) Quel est l'ordre de temps d'exécution de chacun de ces 3 sous-algorithmes.