I.1 Qu’est-ce qu’un algorithme ?
La notion d’algorithme est une notion difficile : il n’est pas si évident que cela de la définir. L’approche théorique de la notion d’algorithme passe par le concept de “machine de Turing”, modèle simplifié, idéalisation mathématique, d’un ordinateur “réel”. On appelle alors algorithme tout programme tournant sur une machine de Turing. Une fonction f est alors dite calculable s’il existe un algorithme (c’est-à-dire une machine de Turing) qui soit capable de calculer f(x) pour tout x raisonnable. Cette idéalisation de l’ordinateur, possède une certaine universalité. D’autres approches de la notion d’algorithme conduisent a` la même classe de fonctions calculables.
Nous nous contenterons évidemment dans ce cours d’une approche plus concrète : nous appellerons algorithme toute fonction écrite dans un langage de programmation tel que Caml. Signalons quelques problèmes posés par notre définition :
• La dépendance du langage utilisé. Cette dépendance n’est qu’apparente. Si l’on peut écrire un algorithme calculant une fonction f en, mettons, Pascal, on pourra aussi en écrire un en Caml. En revanche, certains algorithmes peuvent être plus performants dans un langage que dans un autre langage. Problème intéressant, mais au-delà de la portée de ce cours. Un algorithme sera dorénavant une fonction Caml.
• Le codage des objets manipulés par un algorithme peut avoir de l’importance. On supposera toujours que l’on a affaire à des codages raisonnables. Il est clair que coder un entier en base 1 ou en base 2 conduira sans doute à des comportements différents des algorithmes : en base 2, 20 s’écrit 10100, et en base 1, il s’écrit 11111111111111111111. Que pensez vous de l’écriture de 1000000 ?
• On ne peut pas coder des ensembles infinis d’objets, ni même certains objets qui sont “infinis” par essence : par exemple, les réels non décimaux posent un problème. Ainsi, on ne peut pas coder l’ensemble des nombres réels, mais seulement un sous-ensemble fini de celui-ci. Les algorithmes de calcul numérique doivent tenir compte de ce fait.
Na¨?vement, la complexité d’un algorithme est le “nombre d’opérations” nécessaires à l’algorithme pour effectuer son travail. Cette complexité donne une idée du temps nécessaire à l’algorithme pour s’exécuter. La notion de complexité n’a réellement de sens que dans le cadre des machines de Turing. Aussi, nous contenterons-nous d’évaluer le nombre d’opérations d’un certain type judicieusement choisi nécessaires à l’exécution d’un algorithme. Ainsi
:
• Dans un algorithme de tri comparatif, une opération significative sera sans doute une comparaison.
• Dans un algorithme de multiplication ou d’addition d’entiers longs, ce sera peut-être une opération sur les bits.
• Dans une multiplication de polynoˆmes à coefficients réels, ce sera suˆrement une somme ou un produit de réels.
• Dans le cas d’une fonction récursive, il pourra être intéressant de calculer le nombre d’appel récursifs.
• Dans un algorithme déplac¸ant beaucoup de données, le nombre d’opérations d’affectation sera certainement révélateur du temps de calcul.
Lors de l’étude d’un algorithme, il n’est pas toujours évident de dégager quelles sont les opérations importantes. L’expérimentation est parfois utile.
Exponentiation dichotomique
La complexité d’un algorithme calculant f(x) dépend bien entendu de la donnée x fournie au départ à cet algorithme. Cette dépendance peut parfois être très complexe. Cela dit, elle est parfois fonction uniquement de la taille de x, que l’on définit comme le nombre de bits nécessaires au codage de x.
Cette taille dépend donc du codage choisi pour les données. Mais tous les codages raisonnables fourniront en général des tailles comparables. Ainsi, par exemple, le codage d’un entier N en base 2 demande k fois plus de bits qu’un codage en base 10, mais le facteur k est indépendant de N.
? Que vaut la constante k ci-dessus ? ?
Ainsi, en travaillant à constante multiplicative près, on pourra s’affranchir de discuter trop sur le codage des données. Ainsi, lorsque nous dirons qu’un objet X est de taille 1, cela signifiera que tous les objets du même type que X ont une taille bornée. A titre indicatif :
• Un entier Caml, un réel Caml sont des données de taille 1.
• Un entier naturel “long” n est une donnée de taille logn.
• Un tableau de n entiers est de taille n (mais un tableau de n entiers longs [x1,···,xn] serait de taille Pni=1 logxi, taille pouvant être bornée par exemple par nmaxi logxi).
• Une matrice m × n d’entiers est de taille m.n
• Un polynoˆme de degré N à coefficients entiers est de taille N.
• Un graphe G possédant M sommets et N arêtes est de taille M + N si l’on choisit de le coder par un tableau étiqueté par les sommets de G, dont les éléments sont des listes formées des sommets adjacents au sommet courant. Mais il sera de taille M2 si on choisit de coder G par une matrice A de taille M × M, dont le coefficient ai,j vaut 1 s’il y a une arête du sommet i vers le sommet j, et 0 sinon.
La complexité d’un algorithme est fonction de cet algorithme et des paramètres fournis à celui-ci. Souvent, un calcul exact de la complexité s’avère très difficile, voire impossible. On s’oriente en général vers les calculs suivants :
• La complexité en pire cas consiste à calculer la quantité C(N) égale au maximum des complexités pour toutes les données de taille N.
• La complexité en moyenne consiste à associer aux données X de taille N une probabilité, et à considérer la moyenne) de la complexité de l’algorithme sur toutes ces données.
Chacune de ces deux complexités est importante. La complexité en pire cas est rassurante. Elle nous affirme que jamais l’algorithme ne se comportera de fac¸on imprévue. La complexité en moyenne nous dit que certains algorithmes, même s’ils s’avèrent peu intéressants sur certaines données, peuvent se comporter de fac¸on tout à fait correcte en général (c’est le cas du tri rapide étudié un peu plus loin).
Etudier un algorithme c’est :´
• Le décrire, généralement au moyen d’une fonction Caml.
• Prouver sa terminaison et sa correction. L’algorithme doit effectivement calculer ce à quoi on s’attend, et ceci se prouve mathématiquement.
• Etudier sa complexité. Les calculs de complexités sont parfois effectués de fac¸on exa´ cte, et parfois en ordre de grandeur. Un résultat du type C(n) = O(nlogn) sera souvent beaucoup plus intéressant que (mais pas toujours).
Nous allons, dans la suite du chapitre, étudier quelques algorithmes choisis au hasard (enfin presque), afin de mettre en pratique ce qui vient d’être raconté.
La méthode d’exponentiation dichotomique repose sur le principe que pour calculer xn, il n’est pas nécessaire d’effectuer n multiplications de x par lui même, étant donné que xn est en gros égal à (x2)n/2, avec une correction éventuelle dans le cas ou` n est un entier impair. L’algorithme peut être décrit en deux versions, l’une récursive et l’autre itérative.
let rec pow x n =
if n = 0 then 1
else
let y = pow ( x * x ) ( n / 2 ) in
if n mod 2 = 0 then y else x * y;;
? L’algorithme ci-dessus fonctionne lorsque x est entier. Réécrire la fonction ci-dessus pour
qu’elle accepte des paramètres de type quelconque, et une multiplication également quel-
conque. ?
On fait une démonstration par récurrence sur n.
• Si n = 0, c’est clair. L’algorithme termine et renvoie effectivement x0.
• Donnons nous n > 0. Supposons que cela fonctionne pour tout entier strictement inférieur à n. Un appel à pow va s’aiguiller dans la partie else. Mais comme n/2 < n, l’appel récursif à pow se termine et y vaut donc (x2)n/2 si n est pair, et (x2)(n?1)/2 si n est impair. D’ou` la preuve.
On va compter le nombre de multiplications d’entiers effectuées par l’algorithme. La division par 2 et le modulo 2 peuvent être réalisés par des décalages binaires. On ne les compte pas. On démontre par récurrence (forte) sur n > 0 que
T(n) ? clgn + d
ou` c et d sont des réels strictement positifs bien choisis. On remarque au préalable que l’algorithme, hormis l’appel récursif, effectue au maximum 2 multiplications (en fait, 0, 1 ou 2 selon que n est nul, pair ou impair).
• Pour n = 1 c¸a fonctionne pour tout c réel positif et tout d ? 2.
• Si c’est vrai pour tout k < n, on a alors
T(n) ? 2 + T(?n/2?)
? 2 + clgn/2 + d = clgn + (d + 2 ? c)
On voit que, par exemple, d = 2 et c = 2 conviennent.
Tri rapide
On considère l’algorithme suivant :
let pow x n =
let z = ref 1 and m = ref n and y = ref x in while !m <> 0 do if !m mod 2 = 1 then z := !z * !y ; m := !m / 2 ; y := !y * !y
done;
!z ;;
A chaque itération, m est remplacé par la partie entière de . Il s’ensuit par récurrence forte que l’algorithme termine toujours. Nous allons prouver que cet algorithme renvoie effectivement xn, puis évaluer le nombre de multiplications. II.2.2 Preuve de l’algorithme
On va montrer que la quantité zym est invariante dans la boucle.
Soient z, y, m les valeurs des variables à l’entrée d’une itération, et z?, y?, m? leurs valeurs à la sortie de cette même itération. Deux cas se présentent :
• m = 2p est pair, non nul. Alors z? = z, y? = y2 et m? = p. On en tire z?y?m? = z(y2)p = zym.
• m = 2p+1 est impair. Alors z? = zy, y? = y2 et m? = p. On en tire z?y?m? = zy(y2)p = zy2p+1 = zym.
En entrée de boucle, on a zym = 1.xn = xn. En sortie de boucle, on a zym = zy0 = z.
Par l’invariance, il vient en sortie de boucle z = xn.
Notons T(n) le nombre de multiplications effectuées par l’algorithme. La complexité de pow est alors majoré par 2 fois le nombre d’itérations de la boucle while (la division de m par 2 n’est pas comptée, elle peut être effectuée à l’aide d’un décalage de bits). Cette quantité peut être calculée exactement en fonction de n.
On écrit ou` les aj valent 0 ou 1, et ak est égal à 1. Ceci est en toute rigueur valable lorsque n 6= 0. Sinon, la boucle n’est pas exécutée. On montre ensuite par récurrence qu’à l’issue de l’étape p, m vaut
k
X aj2j?p?1.
j=p+1
Ainsi m est non nul pour tout p ? k ? 1.
A l’étape k, m devient donc nul. La boucle est exécutée k fois, et à chaque itération on effectue 1 ou 2 multiplications.
On effectue donc entre k et 2k multiplications, et on remarque de plus que l’entier k vérifie très clairement 2k ? n < 2k+1. La boucle est donc parcourue k fois avec k = ?lgn? et le nombre de multiplications est ainsi T(n) = O(lgn).
? Calculer le nombre exact de multiplications effectuées en fonction de n et du nombre ?(n) de chiffres non nuls dans l’écriture de n en base 2 (le nombre de bits non nuls de l’entier n).
?
Le tri rapide est une méthode de tri de tableaux intéressante à plus d’un point :
• Comme son nom l’indique, c’est un tri efficace.
• Le tri rapide permet de trier un tableau sans faire appel à des ressources de mémoire supplémentaires : le tableau est trié sur place.
• Les idées mises en oeuvre dans l’analyse de l’algorithme sont très générales. On retrouve parfois la même analyse pour des algorithmes n’ayant a priori aucun rapport avec le tri rapide.
• Le tri rapide est au programme de l’option info, et vous devez être capables de réécrire l’algorithme à tout instant.
Le principe du tri est le suivant :
• Soit x le premier élément du tableau. On place dans la partie gauche du tableau les éléments inférieurs ou égaux à x, et dans la partie droite le reste des éléments, tout en positionnant x à la charnière entre les deux parties.
• On trie récursivement les deux parties, étant entendu qu’un tableau à 1 élément est considéré comme déjà trié.
L’algorithme de tri se scinde en une fonction de partition, et une fonction de tri proprement dite. La fonction de partition partitionne le sous-tableau du tableau t formé des éléments dont les indices sont compris au sens large entre p et r. Elle renvoie un entier j désignant la limite entre les deux “moitiés” du sous-tableau partitionné.
let permuter t i j = let tmp = t.(i) in t.(i)
t.(j)
let partition t p r =
let x = t.(r) and i = ref (p - 1) in for j = p to r - 1 do
if t.(j) <= x then ( i := !i + 1;
permuter t !i j;
) done;
permuter t (!i + 1) r;
!i + 1;; let rec quicksort t p r =
if p < r then
let q = partition t p r in quicksort t p ( q - 1 ) ; quicksort t ( q + 1 ) r ;; let tri t = quicksort t 0 ( Array.length t - 1 ) ;; Tri rapide
La preuve de la correction de la fonction de partition est délicate. Nous la laissons de coˆté. Cette fonction effectue r ?p comparaisons d’éléments du tableau (et au plus r ?p+1 échanges d’éléments de tableau).
Le tri rapide d’un tableau de taille n commence par partitionner le tableau en prenant comme pivot son premier élément (celui d’indice 0), puis trie récursivement deux soustableaux. Les tailles respectives de ces sous-tableaux ont pour valeurs possibles (0,n ? 1), (1,n ?2), ,(n?2,1), (n?1,0). En faisant l’hypothèse que ces tailles sont équiprobables, on en déduit que le nombre de comparaisons C(n) effectuées par le tri rapide pour trier un tableau de taille n est en moyenne :
avec de plus C(0) = 0, C1 = 0. Il reste à étudier cette récurrence.
Pour n ? 2 on a
nCn ? (n ? 1)Cn?1 = 2(n ? 1) + 2Cn?1
d’ou`
nCn = 2(n ? 1) + (n + 1)Cn?1.
Posons. Il vient pour n ? 2,
d’ou`
.
On a
.
On en tire, puisque D1 = 0, que
.
Cette quantité étant équivalente à lnn, on a donc
Cn ? nlnn.
Nous allons montrer que le pire cas survient lorsque le tableau de départ, de taille n, est déjà trié. Cette démonstration se fait en deux étapes. On prouve tout d’abord que le quicksort demande O(n2) comparaisons sur un tableau trié de n éléments. On montre ensuite que ce O(n2) est maximal, au sens ou` le nombre de comparaisons du tri rapide sur un tableau de taille n est inférieur ou égal à cn2 ou` c est une constante convenablement choisie.
• Prenons un tableau trié. Supposons pour simplifier que les éléments du tableau sont tous distincts. La fonction de partition ne modifie rien dans le tableau. Mais elle effectue au moins n comparaisons. Puis, le tri rapide est appelé sur deux sous-tableaux, l’un de taille 0 et l’autre de taille n ? 1. Ainsi, C(n) ? n + C(n ? 1). D’ou` :
• Montrons maintenant que, pour un tableau quelconque, on a T(n) ? cn2 pour une constante c convenable. On a tout d’abord pour tout n ? 1
T(n) ? n + max (T(k) + T(n ? 1 ? k))
0?k?n?1
Pour n = 0, n’importe quel réel c convient. Supposons trouvé un réel positif c convenant pour tout entier k strictement inférieur à l’entier n > 0. On a alors
On vérifie facilement que la fonction ? : [0,n ? 1] ? R définie par ?(x) = x2 + (n ? 1 ? x)2 atteint son maximum aux bornes de son intervalle de définition, ce maximum étant égal à
(n ? 1)2. On en déduit que
T(n) ? n + c(n ? 1)2
On vérifie alors que, pourvu que c ?, on aura bien T(n) ? cn2. Ainsi, T(n) ? n2.
En conclusion, le tri rapide possède en moyenne des qualités indéniables, mais risque de s’avérer mauvais dans certains cas. On peut montrer que ces cas sont rares d’un point de vue probabiliste (l’écart type du nombre de comparaisons est négligeable devant sa moyenne). De plus, il existe des méthodes simples pour éviter les cas pathologiques. Il suffit par exemple d’échanger le premier élément du tableau à trier (le pivot) avec un élément au hasard pour être “presque suˆr” de tomber sur le cas moyen. Toutes ces affirmations demanderaient bien entendu d’être prouvées soigneusement.
Prenons deux matrices carrées n × n A et B. Le calcul na¨?f du produit C = AB nécessite celui des n2 coefficients de la matrice C. Pour chacun d’entre eux, il faut effectuer n multiplications et n?1 additions, ce qui donne en fin de compte un algorithme en O(n3).
Il est possible de faire mieux, lorsque la taille des matrices est une puissance de 2 (dans le cas général, l’algorithme qui suit peut être adapté).
• Soient, pour commencer, deux matrices carrées 2 × 2 A et B définies par
On calcule les quantités suivantes :
?????????????m1 = (b + d ? a)(d? ? c? + a?) m2 = aa?m3 = cb?m4 = (a ? b)(d? ? c?)
????????????m5 = (b + d)(c? ? a?)
m6 = (c ? b + a ? d)d?m7 = d(a? + d? ? b? ? c?) Tri par paquets
On a alors
|
Il est ainsi possible de multiplier deux matrices 2 × 2 en utilisant 7 multiplications et 24 additions. |
||
|
? |
Montrer que 15 additions sont suffisantes. • Voyons en quoi ceci est une amélioration de l’algorithme na¨?f. Le calcul ci-dessus peut s’appliquer à des multiplications par blocs. Pour multiplier deux matrices 2n × 2n, on les coupe chacune en 4 blocs n×n et on utilise les formules ci-dessus, récursivement bien suˆr. Il est enfin clair que deux matrices 1×1 se multiplient avec 1 multiplication scalaire et 0 addition scalaire. Notons M(n) et A(n) respecivement le nombre de multiplications et d’additions requis pour multiplier deux matrices carrées de taille 2n. On a M(0) = 1 et A(0) = 0. De plus, on a les relations de récurrence M(n) = 7M(n ? 1) A(n) = 7A(n ? 1) + 15.22(n?1) La relation sur M est claire. En ce qui concerne A(n), On a d’une part les additions cachées dans l’appel récursif, et d’autre part les sommes de matrices de taille 2n/2 = 2n?1 qui sont effectuées classiquement et demandent donc pour chacune (2n?1)2 additions scalaires. On obtient pour tout n positif M(n) = 7n. Un calcul en cascade fournit A(n) = 5.7n ? 5.4n. N’oublions pas que ces calculs concernent des matrices de taille 2n. Pour un produit de matrices de taille n, on obtient, en remplac¸ant n par lgn dans les expressions ci-dessus, un nombre de multiplications scalaires égal à nlg7 et un nombre d’additions scalaires égal à 5.nlg7 ? 5.n2. Sachant que lg7 ? 2.8, nous avons donc un algorithme dont le nombre d’opérations est négligeable par rapport à l’algorithme na¨?f. Revenons un instant sur le titre du paragraphe. La multiplication rapide de matrices est-elle rapide ? Nous allons comparer brièvement le nombre total d’opérations (addition, multiplication) effectuées d’une part par l’algorithme na¨?f, d’autre part par l’algorithme que nous venons d’étudier. On a approximativement : • 6.nlg7 opérations pour l’algorithme rapide. • 2.n3 opérations pour l’algorithme na¨?f. On peut considérer que l’algorithme rapide est vraiment rapide lorsque 6.nlg7 ? 2n3, c’est-à-dire lorsque n3?lg7 ? 3 ce qui donne pour n une valeur supérieure à 300. L’algorithme rapide n’a donc d’intérêt que pour des grosses matrices. Signalons en plus les multiples appels récursifs, consommateurs de temps et de mémoire. En fait, une implémentation réelle de la multiplication rapide des matrices devrait être particulièrement soignée et optimisée pour avoir un quelconque intérêt. Dans la pratique, on met en oeuvre un algorithme mixte, ou` l’algorithme na¨?f prend le relais lorsque la taille des matrices devient inférieure à une certaine taille. |
? |
|
? |
Refaire le calcul en en attribuant un poids 2 aux multiplications. |
? |
On désire trier un tableau a de n réels compris entre 0 (au sens large) et 1 (au sens strict), notés a0 ,a1, , an?1. On place ces réels dans un tableau b de n listes,b0,b1, ,bn?1 de sorte que si , alors x ? bi. En plus condensé, ?i ? [0,n ? 1]ai ? b?nai?. On trie ensuite chacune des listes bj par un tri “na¨?f”, de type tri par insertion par exemple. On concatène ensuite les listes triées. Le tableau a est alors trié.
let tri paquets a = let n = Array.length a in let b = n [] in for i=0 to n - 1 do let j = int of float(a.(i) *. (float of int n)) in b.(j)
done;
for j = 0 to n - 1 do
b.(j)
done; let k = ref 0 and i = ref 0 in while !i <= n - 1 do match b.(!k) with
| [] -> k := !k+1
| x::l -> a.(!i) done;;
? Prouver cet algorithme. ?
Nous allons évaluer le nombre moyen de comparaisons effectuées par l’algorithme.
Placer les ai dans le tableau b demande n affectations. La concaténation des bi nécessite 4n affectations. On peut essayer de se convaincre, en effet, que le reste des opérations demande un temps linéaire en n.
Trier la liste bi nécessite O(ni2) comparaisons ou` ni est le nombre d’éléments de bi. Appelons Ti le nombre moyen de comparaisons requises pour trier bi. L’entier k étant pris entre 0 et n, la probabilité que ni soit égal à k vaut avec p = 1/n. La variable aléatoire ni suit en fait une loi binoˆmiale. On a ainsi
Il reste à calculer la somme ci-dessus. Sans utiliser de notions probabilistes de type ”variance” (Ti = E(n2i ) = V (ni) + E(ni)2), introduisons
On vérifie sans peine que
Récurrences classiques
En utilisant l’galité ci-dessus et l’expression factorisée de ?, puis en faisant x = 1, on en tire Ti = np[1 + (n ? 1)p]. Remplac¸ant p par 1/n, on obtient en fin de compte Ti = 2 ? n1 .
La complexité moyenne du tri des bi, i = 0..n est donc 1. Le tri par paquets est donc linéaire en moyenne, à condition de faire des hypothèses de régularité de la distribution probabiliste des éléments du tableau.
Les algorithmes précédents ont mis en évidence des suites récurrentes, dont certaines se doivent d’être connues
De telles suites interviennent fréquemment dans certains algorithmes, comme par exemple tri par sélection ou tri rapide en pire cas. Le calcul de Tn en fonction de n est immédiat et on obtient Tn = O(n2).
On suppose dans tout ce qui suit que a et ? sont réels, avec a > 0 et ? ? 0.
Ces suites interviennent typiquement dans des algorithmes du type “diviser pour régner” comme le tri par fusion, l’exponentiation rapides, les diverses multiplications rapides (Karatsuba, Schonhage-Strassen), etc.
La partie entière pourrait être remplacée sans problème par une fonction “plafond” ( pour x ? R le plafond de x est l’unique entier n, noté ?x?, vérifiant n ? 1 < x ? n). On pourrait éventuellement envisager une combinaison des deux, avec des récurrences du genre T(n) = T(?n/2?) + T(?n/2?) + .
Dans ce paragraphe, nous allons résoudre ces récurrences dans le cas particulier ou` n = 2p est une puissance de 2. Définissons tp = T(2p). On a alors la relation de récurrence
?p ? 1 tp = atp?1 + b2?p
Ecrivons ces égalités en cascade, sommons pour éliminer les´ t intermédiaires. On obtient
tp = apt0 + b(2?ap?1 + 22?ap?2 + + 2p?a0)
On distingue trois cas, selon que a est égal à 2?, strictement inférieur, ou strictement supérieur.
On a alors tp = 2?p(t0 + b2?p) = O(p2?p). En revenant à n, on a donc
T(n) = O(n? lgn).
On rencontre ce cas lors de l’exponentiation dichotomique (? = 0, a = 1) ou dans le tri par fusion (? = 1, a = 2). VI.2.2 Casa < 2?
L’identité remarquable se transforme en
Ainsi, tp = O(2?p), d’ou`
T(n) = O(n?).
Intuitivement, c’est le terme en n? de la récurrence qui est prépondérant sur l’appel récurrent au rang n/2.
Le calcul fait ci-dessus pour la valeur de tp reste valable, mais cette fois, on a tp = O(ap), d’ou`
T(n) = O(nlga).
Ce genre de situation se rencontre, par exemple, dans le cas de la multiplication rapide des matrices (a = 7, ? = 2) ou des polynoˆmes.
Cette fois-ci, l’appel récurrent prend un temps prépondérant sur le “terme correcteur”.
On ne fait plus d’hypothèse sur n dans ce paragraphe. Nous allons montrer que les résultats précédents restent toujours valables dans le cas général. Pour alléger un peu nos calculs introduisons la notation suivante :
Etant donnés´ p entiers ui, i = 0..p, ou` les ui valent 0 ou 1, et up est égal à 1, on note [u0,u1, ,up] = Ppi=0ui2i. On convient également que [0] = 0. Tout entier naturel n s’écrit alors de fac¸on unique n = [u0, ,up] avec les conventions ci-dessus pour les ui. L’entier p, en particulier, est entièrement caractérisé par n. D’ailleurs, pour n non nul, on a 2p ? n < 2p+1 ce qui implique que p = ?lgn?.
Un autre intérêt de cette notation est que si n = [u0, ,up], alors ?n/2? = [u1, ,up]. Cette notation est en revanche peu adaptée lorsque l’on s’intéresse à des “plafonds” au lieu de parties entières.
Revenons à notre récurrence. Soit n = [u0, ,up] un entier non nul. On a alors
T(n) = T([u0, ,up]) = aT(?n/2?) + bn? = aT([u1, ,up]) + [u0, ,up]?
ou encore
T([u0, ,up]) = aT([u1, ,up]) + b2?lg[u0, ,up]
On a ainsi la double inégalité
aT([u1, ,up] + b2?p ? T([u0, ,up] < aT([u1, ,up] + b2?(p+1)
Soient tp et t?p les suites définies par récurrence par (1) et, pour tout p > 0, tp = atp?1 + b2?p et t?p = at?p?1 + b2?2?p. On a tp ? T([u0, ,up]) < t?p. Or, les suites tp et t?p sont du type de celles étudiées dans le cas particulier du paragraphe précédent (n puissance de 2) et leur comportement dépend de la position de a par rapport à 2?. Dans le cas ou`, par exemple, a > 2?, on a
On constate que T(n) est coincé entre deux suites, équivalentes toutes deux à un multiple constant de ap. On a donc T(n) = O(ap) = O(nlga). Les deux autres cas se traitent de fac¸on identique.
Il est bon de remarquer que l’on a également nlga = O(T(n)). Le rapport est à la fois majoré, et minoré par un réel strictement positif lorsque n tend vers l’infini. On note parfois T(n) = ?(nlga).
Ce chapitre ne donne qu’un aperc¸u de ce que l’on peut faire en analyse d’algorithmes. Retenir de tout cela qu’il est possible de prouver les algorithmes. Evaluer leur complexité´ peut être instructif : l’analyse d’un algorithme permet en effet de cerner ses faiblesses, et parfois de les corriger.
Exercices
1/ La recherche du plus petit élément d’un tableau de taille n nécessite n?1 comparaisons. Déterminer un algorithme permettant de trouver le plus petit et le plus grand élément d’un tableau de taille n avec 3 comparaisons.
|
Indication : comparer les éléments du tableau deux par deux. |
|
|
2/ |
La recherche d’un élément dans un tableau trié peut être effectuée avec O(lgn) comparaisons. Ecrire l’algorithme correspondant et prouver cette assertion. |
|
3/ |
On considère l’algorithme suivant, renvoyant le plus grand élément d’un tableau : let maximum t = let n = Array.length t and m = ref t.(0) in for i = 0 to n - 1 do if t.(i) > !m then (*) m := t.(i) done ; !m;; On souhaite déterminer le nombre moyen de fois que la ligne (*) est exécutée. On suppose que le tableau t est une permutation aléatoire de n nombres distincts. (a) Soit x un nombre choisi parmi i + 1 nombres distincts. Quelle est la probabilité p que x soit le plus grand de ces nombres ? (b) Soit i un entier entre 0 et n ? 1. Quelle est la probabilité que la ligne (*) soit exécutée lors de la ième itération ? (c) Soit si la variable aléatoire valant 0 si la ligne (*) n’est pas exécutée à la ième itération et 1 sinon. Montrer que la moyenne de si (son espérance mathématique) |
est égale à .
(d) Soit s la variable aléatoire “nombre de fois que la ligne (*) est exécutée”. Exprimer s à l’aide des si, en déduire la moyenne de s, et motrer que l’affectation (*) est réalisée en moyenne lnn fois sur un tableau de taille n.
4/ Cet exercice n’est pas censé être résolu de fac¸on rigoureuse. On suppose donné un tableau tel que, lors du tri de ce dernier par quicksort, la fonction de partition coupe systématiquement dans une proportion de pour (au lieu du classique moitié-
|
moitié). Montrer que ce n’est pas grave, et que le tableau sera quand même trié avec O(nlgn) comparaisons. |
|
|
5/ |
On considère l’algorithme suivant (Karatsuba), permettant de multiplier deux polynoˆmes P et Q de degré strictement inférieur à n, ou` n est une puissance de 2. Un polynoˆme est modélisé par le tableau de ses coefficients. ? Si n=1, c’est facile. ? Sinon, on écrit P = P1 + Xn/2P2 et Q = Q1 + Xn/2Q2, avec P1, Q1, P2, Q2 de degré strictement inférieur à n/2. Puis, on calcule récursivement les quantités A = (P1 + P2)(Q1 + Q2), B = P1Q1 et C = P2Q2. (a) Exprimer PQ à l’aide des quantités A, B et C. (b) Ecrire un algorithme récursif permettant le calcul de´ PQ. On supposera écrite une fonction somme permettant d’additionner deux polynoˆmes de degré inférieur ou égal à n avec n + 1 additions scalaires. (c) Déterminer le nombre d’additions scalaires et de multiplications de coefficients effectuées par l’algorithme. Peut-on qualifier cet algorithme de “multiplication rapide” de polynoˆmes ? |
|
6/ |
Permutations aléatoires. On considère l’algorithme suivant : |
let random vect n = let t = n 0 in for i = 0 to n - 1 do
t.(i)
done ; for i = 0 to n - 1 do
let a = (i + 1) and b = t.(i) in t.(i)
t.(a)
done ; t ;;
Démontrer que cet algorithme fournit toutes les permutations de l’ensemble {1,2, ,n} en O(n) opérations élémentaires.
|
7/ |
Modifier la fonction de partition du tri rapide pour que, pour une liste L et un entier x, partition x L renvoie un triplet (L1,L2,q) ou` L1 est la liste des éléments de L inférieurs ou égaux à x, L2 est le reste des éléments de L, et q est le nombre d’éléments de L1. On considère la fonction suivante : let rec selection L i = match L with | [] -> failwith "selection" | (x::L’) -> let (L1,L2,q) = partition L’ x in if i < q then selection L1 i else if i = q then x else selection L2 (i - q - 1) ;; (a) Montrer que selection L i renvoie le ième élément de la liste L dans l’ordre croissant. (b) Déterminer l’ordre de grandeur du nombre moyen de comparaisons nécessaires pour le calcul de selection L i. On s’inspirera de l’étude faite en cours pour le tri rapide. (c) Trouver le nombre de comparaisons dans le pire cas. La valeur moyenne vous paraˆ?t-elle intéressante ? On aurait pu plus simplement trier la liste puis prendre le ième élément de la liste triée. Aurait-on eu raison ? |
|
8/ |
Soit P = a0 + a1X + + anXn un polynoˆme à coefficients réels. Soit t un réel. Remarquer que P = a0 + X(a1 + + anXn?1) et en déduire un algorithme de calcul de P(t) ne nécessitant que n additions et n + 1 multiplications. |
|
9/ |
L’algorithme de tri ci-dessous est appelé “tri par insertion”. Pour trier le tableau t = [|a0; ;an?1|], on effectue pour chaque i entre 1 et n ? 1 l’opération suivante : si ai?1> ai on échange ai et ai?1. On recommence avec ai?1 et ai?2, et ainsi de suite jusqu’à ce que l’élément envisagé soit supérieur au précédent. |
let tri insertion t = let n = Array.length t and j = ref 0 in for i = 1 to n-1 do
j := i ;
while !j > 0 && t.(!j) < t.(!j-1) do let tmp = t.(!j) in
t.(!j)
t.(!j-1)
j := !j - 1
Exercices
done
done ;;
(a) Montrer que l’on trie ainsi le tableau.
(b) Déterminer le nombre moyen de comparaisons effectuées par le tri par insertion.
(c) Déterminer le nombre maximal de comparaisons effectuées par ce même tri.
(d) Déterminer le nombre minimal de comparaisons effectuées par ce même tri.
10/ On considère la variante du tri rapide suivante :
On se donne un entier M. Si le nombre d’éléments de la liste L est strictement inférieur à M, on trie L à l’aide d’un tri par insertion (qui demandera comparaisons en moyenne). Sinon, on partitionne et on rappelle récursivement l’algorithme. Le nombre moyen Cn de comparaisons nécessaires au tri d’une liste de taille n est alors donné par la récurrence
) si n ? M
si n < M
(a) Résoudre exactement cette récurrence.
(b) En supprimant les termes négligeables devant n dans l’expression de Cn, trouver une fonction f(M) vérifiant Cn = 2nlnn + f(M)n + o(n).
(c) Déterminer numériquement le minimum de f.
11/ On dit qu’un algorithme de tri de tableau est comparatif lorsque cet algorithme effectue des comparaisons entre éléments du tableau pour effectuer le tri. A chaque algorithme` de tri comparatif est associé un arbre binaire, résumant sur tous les échantillons de tableaux à trier la suite des comparaisons à effectuer. A titre d’exemple, voici l’abre associé au tri par insertion d’un tableau t = [|a,b,c|] contenant trois éléments distincts.
t < t a,b,c t > t
1
a,c,b c,a,b b,c,a c,b,a
(a) Dresser l’arbre associé au tri rapide d’un tableau de taille 3.
(b) On appelle hauteur d’un arbre la distance maximale de la racine de l’arbre à ses feuilles. Combien un arbre binaire de hauteur h a-t-il au maximum de feuilles ? Combien l’arbre associé au tri d’un tableau de taille n doit-il avoir de feuilles ? Quelle est, en fonction de n, la hauteur minimale d’un tel arbre? En conclure un résultat concernant le nombre de comparaisons en pire cas pour les tris comparatifs.
