Exemples pour démarrer (tri insertion, tri fusion) Maths appliquées Notations asymptotiques (Knuth) Récurrences T(n) = aT(n/b) + f(n) et études de cas

1

Exemples pour démarrer (tri insertion, tri fusion)Maths appliquées Notations asymptotiques (Knuth) Récurrences T(n) = aT(n/b) + f(n) et études de casAutres cas Euclide Exponentiation rapide Classes de complexité, NP-Complétude

V. Complexité

2

Complexité algorithmique

Rappel de l’équifinalité 1 problème, plusieurs algorithmes (façons de le

résoudre) Equivalence fonctionnelle… … mais différence en termes de performance

Temps de réalisation Nombre et durée des opérations de production de la solution Complexité temporelle

Ressources mobilisées Nombre et taille des variables et SDD (résultats

intermédiaires) Complexité spatiale

Complexité Principe

3

Analyse algorithmique

Besoin de pouvoir Connaître a priori les performances d’un algorithme En fonction de la taille (et de la nature) de l’entrée

Analyse algorithmique But : évaluer la complexité d’un algorithme Moyen

Méthodes et techniques de mathématiques Dénombrement, comportements asymptotiques, récurrences, …

Le premier à systématiser la démarche Don Knuth dans TAOCP

Dans la suite du chapitre Focalisation sur l’analyse de la complexité temporelle

Transposable sans difficulté à l’analyse de la complexité spatiale

Complexité Evaluation

4

Tri par insertion

But Trier en ordre croissant un tableau A

d’entiers Principe

On positionne le 2nd élément par rapport au 1er

Puis on positionne le 3ème par rapport aux 2 premiers

Et ainsi de suite…

Complexité Evaluation Exemple 1

5

Algorithme


6

Temps d’exécution

Temps d’exécution de l’algorithme Somme sur l’ensembles des instructions i

élémentaires Du temps constant ai pour l’instruction

Multiplié par Le nombre ki de répétitions de cette instruction

Qui va naturellement dépendre de la taille n de l’entrée

Ici la taille du tableau à trier Mais aussi de la nature de l’entrée

Est-il déjà, au moins partiellement, trié ?


i ii I

T n a k

7

Application au cas

Instruction indexée d’après le numéro de ligne Instructions 2, 3, 4, 5, 6, 7, 9

Par exemple L’affectation j i – 1

Prend un temps constant a4

Est répétée k4 = n – 1 fois

L’évaluation de l’expression j > 0 et A[j] > e Prend un temps constant a5

Elle est répétée un nombre de fois qui varie suivant i 1 ≤ k5(i) ≤ i Notons ti = k5(i)


8

Bilan

Bilan

Impact de la nature de l’entrée Si le tableau est déjà trié (meilleur des cas)

Si le tableau est trié en ordre inverse (pire des cas)

Cas général


2 3 4 9 5 6 72 2

1 1n n

i ii i

T n a a a a n a t a a t

min 2 3 4 6 7 91 1it T n a a a a a a n an b

2maxit i T n cn dn e

min maxT n T n T n

9

Meilleur et pire des cas

Si le tableau est déjà trié (meilleur des cas) Le temps d’exécution est

asymptotiquement proportionnel à n Complexité linéaire

Si le tableau est trié en ordre inverse (pire des cas) Le temps d’exécution est

asymptotiquement proportionnel à n² Complexité quadratique


10

Le pire des cas fait référence Cas moyen

Même ordre de grandeur que le pire des cas Pire des cas

borne supérieure quelque soit l’entrée Pas de mauvaise surprise

On s’intéresse surtout au pire des cas On s’intéresse surtout à l’ordre de grandeur

Constantes et termes non dominants peu significatif Le tri par insertion est de complexité quadratique

dans le pire des cas, ce que l’on note


22i

it T n fn gn h

2n

11

Tri-fusion

But Trier en ordre croissant un tableau A d’entiers

Stratégie Paradigme « diviser pour régner » Descente

Divisions successives du tableau en parties Remontée

Fusion des parties triée (Procédure auxiliaire Fusionner en )

Terminaison de la descente récursive Une partie à un seul élément est naturellement triée


n

12

Algorithme


13

Temps d’exécution

Temps d’exécution de l’algorithme On distingue

T(n) : temps d’exécution sur une entrée de taille n

D(n) : temps passé à diviser le problème en a sous-problèmes de taille n/b (la plupart du

temps a = b) S(n) : temps passé à synthétiser la solution

À partir des solutions aux sous-problèmes

Il existe un seuil ε : n < ε T(n) constant Traduction formelle :


1 si

sinonnb

nT n

aT D n S n

14

Application au cas

D(n) : division du tableau en deux parties : a = b = 2 S(n) : Procédure fusion : n < 1 T(1) = Expression du temps d’exécution du tri-

fusion

Cette récurrence se résout en En attendant de savoir le démontrer : …


2

1 si 1

2 sinonn

nT n

T n

1

n 1

2logT n n n

15

Application au cas

Montrer par induction que :


22

2 si 2log

2 si 2kn

nT n T n n n

T n n

16

Comparaison

Le tri-fusion est, dans le pire des cas, bien plus performant que le tri par insertion n = 109

Machine qui effectue 109 opérations par seconde Tri par insertion : ~30 ans Tri-fusion : ~30 secondes


17


V. Complexité

18

Borne approchée

Définition formelle de

Si alors on dit que est une borne approchée asymptotiquement pour

est une classe d’équivalence doit être asymptotiquement positive

Complexité Nota. Asympt. Borne approchée

0 min max

0 min max

|

, /

0

f n

g n n c c

n n c g n f n c g n

f n g n g n

f n

g n

g n

19

Borne approchée

Exercice Soit une fonction polynomiale Montrer que Indice

On note abusivement pour Si vous vous demandiez encore en L1 à

quoi peut bien vous servir concrètement l’analyse en informatique, vous avez là un début de réponse

Complexité Nota. Asympt. Borne approchée

2T n n

2 , 0T n an bn c a

f n g n f n g n

2 2 2min maxc n an bn c c n

20

Borne supérieure

Définition formelle

Si alors on dit que est une borne asymptotique supérieure pour

est une classe d’équivalence La borne peut être asymptotiquement

approchée

Complexité Nota. Asympt.

Borne supérieure

0

0

|

/

0

f n

g n n c

n n f n cg n

f n g n g n

f n

g n

21

Borne inférieure


Si alors on dit que est une borne asymptotique inférieure pour

est une classe d’équivalence

Complexité Nota. Asympt.

Borne inférieure

0

0

|

/

0

f n

g n n c

n n cg n f n

f n g n g n

f n

g n

g n g n g n

22

Borne strictement supérieure Définition formelle

Si alors on dit que est asymptotiquement négligeable devant

Classe usuelle en analyse (développements limités)

Complexité Nota.

Asympt. Borne >

0

0

|

/

0

f n

g n c n

n n f n cg n

f n g n f n

g n

| lim 0f n

g nng n f n

23

Borne strictement inférieure


Si alors on dit que est asymptotiquement négligeable devant

Complexité Nota. Asympt. Borne <

0

0

|

/

0

f n

g n c n

n n cg n f n

f n g n g n

f n

| lim f n

g nng n f n

f n g n g n f n

24

Illustrations

Classes d’équivalence, i.e.

Relation d’équivalence Transitivité Réflexivité Symétrie

Valable pour les 5 notations

Complexité Nota. Asympt. Exemples, propriétés

2 2 2 3n n n n n

2n n n n

2 2n n n n

x y x y

25

Exemples pour démarrer (tri insertion, tri fusion)Maths appliquées Notations asymptotiques (Knuth) Récurrences T(n) = aT(n/b) + f(n) et études casAutres cas Euclide Exponentiation rapideClasses de complexité, NP-Complétude

V. Complexité

26

Problématique

Algorithmes conçus cf. diviser pour régner Ne conduisent pas directement à T(n) en

fonction de n Mais à une récurrence, i.e. T(n) en fonction

de T(n – 1) Rappel pour tri-fusion

Comment établir que ? Complexité Récurrences Problématiq

ue

2

1 si 1

2 sinonn

nT n

T n

2logT n n n

27

3 méthodes de résolution

Des récurrences de la forme 1. Inductive

On connait l’expression fonction de n a priori (conject.)

On utilise un argument de récurrence 2. Itérative

On transforme la récurrence en sommations que l’on peut ensuite borner (pour les fans de Faulhaber)

3. Méthode (quasi) générale de résolution Un théorème à appréhender en profondeur Trois cas à envisager en pratique Reste quelques cas irrésolubles (avec cette méthode)

Complexité Récurrences Méthodes

nbT n aT f n

28

Méthode générale

Soit deux constantes a ≥ 1 et b ≥ 1, une fonction f(n) définie pour les entiers positifs par la récurrence

Alors T(n) peut être borné asymptotiquement comme suit : 1. 2. 3.

Récurrences Méth. générale Théorème

nbT n aT f n

log log0 / b ba af n n T n n log log lnb ba af n n T n n n

log0 00 / 1 / :b a n

bf n n c n n n af cf

T n f n

29

Interprétation

Comparaison asymptotique de f(n) et Si l’une des deux domine l’autre (cas 1 et 3)

Elle fixe la complexité de T(n) Cas 1 : Cas 3 :

Sinon (cas 2), si elle sont équivalentes La complexité de T(n) est leur complexité fois

ln n Cas 2 :

Mais attention aux conditions !! Certains cas ne peuvent être résolus

Récurrences Méth. générale

Intuitivement

logb an

logb aT n n T n f n

logln lnb aT n f n n n n

30

Exemples d’application

Tri-fusion Karatsuba

Récurrences Méth. générale Exemples

39 nT n T n

23 1nT n T

43 lnnT n T n n

22 lnnT n T n n

31

Exemple d’application 1

est naturellement dominée par Formellement : Le cas 1 s’applique et par conséquent :

Récurrences Méth. générale Exemple 1

39 nT n T n

9, 3,a b f n n

3log log 9 2 2b an n n n

f n n n

f n 2n

log , 1b af n n n

log 2b aT n n n

32


est du même ordre que Formellement : Le cas 2 s’applique et par conséquent :


23 1nT n T

321, , 1a b f n

32

log 1log 0 1b an n n

1 1f n

f n

logb af n n

ln lnT n f n n n

logb an

33


domine : Pour : Le cas 3 s’applique et par conséquent :


43 lnnT n T n n

3, 4, lna b f n n n

4log log 3 0,793b an n n

lnf n n n

f n log , 0, 207b af n n n

lnT n f n n n

logb an

n 3 34 4 4ln ln , 1n n n

baf n n cf n c

34


domine : On pourrait s’attendre à pouvoir appliquer le

cas 3 Mais : Donc, pour tout , Par conséquent, le théorème ne peut

s’appliquerRécurrences Méth.

générale Exemple 3

22 lnnT n T n n

2, 2, lna b f n n n

2log log 2b an n n

lnf n n n

f n f n nlogb an

log ln

b a

f nn

n

0 log lnb a

f nn n

n

35

Application au tri-fusion

est du même ordre que Formellement : Le cas 2 s’applique et par conséquent :

Récurrences Méth. générale Tri-fusion

22 nT n T n

2, 2,a b f n n

logb an n

f n n

f n

logb af n n

ln lnT n f n n n n

logb an

36

Multiplication de deux nombres en numération de position Nombres de 2n chiffres Décomposition en deux moitiés

Représentation algébrique de la multiplication naïve

Les multiplications sont plus coûteuses que les additions Version naïve : 4 multiplications intermédiaires

Forme équivalente de Karatsuba Complexification

Mémorisation et réutilisation de résultats intermédiaires Ajout de 3 opérations additives supplémentaires

On tombe à 3 multiplications ! Application récursive du procédé : O(n2) O(n1,58)

Application à Karatsuba

Récurrences Méth. générale Karatsuba

nM m

nM m

A A b A

B B b B

2n n n nM m M m M M M m m M m mAB A b A B b B A B b A B A B b A B

2n nM M M m M m M M m m m mAB A B b A A B B A B A B b A B

37

Application à Karatsuba

est dominée d’un exposant 0,58 par Formellement : Le cas 1 s’applique et par conséquent :

Récurrences Méth. générale Karatsuba

23 nT n T n

3, 2,a b f n n

2log log 3 1,58b an n n

f n n

f n

log , 0,58b af n n n

log 1,58b aT n n n

logb an

38

Exemples pour démarrer (tri insertion, tri fusion)Maths appliquées Notations asymptotiques (Knuth) Récurrences T(n) = aT(n/b) + f(n) et études de cas Autres cas Euclide Exponentiation rapideClasses de complexité, NP-Complétude

V. Complexité

39

Complexité de l’algorithme d’Euclide

Quelle complexité ? Réponse

au + 5 fois le nombre de chiffre en base 10 du plus petit de a et b.

Pas facile d’appliquer ce qui a été vu plus haut Nous allons démontrer le théorème de Lamé Les nombres de Fibonacci s’invitent dans la partie Au tableau, avec la participation des volontaires

Complexité Cas spéciaux Euclide

ND

LR :

Eucl

ide é

tait

un m

art

ien

40

Complexité de l’algorithme d’Euclide

Temps d’exécution T(n) de l’algorithme d’Euclide Grosso modo le nombre k d’appels récursifs

Premier point : soit le PGCD(a, b) On force la convention a > b ≥ 0

Raisonnable Si b > a ≥ 0 alors un seul appel récursif supplémentaire

a mod b = a et donc le 1er appel récursif est PGCD(b, a) Si a = b ≥ 0 alors un seul appel récursif

a mod b = 0 et donc le 1er appel PGCD(b, 0) retourne b Si cet ordre est vérifié pour un appel récursif

Elle sera alors vérifiée pour tous les appels suivants


ND

LR :

Eucl

ide é

tait

un m

art

ien

41

Fibonacci (Léonard de Pise, dit)

Suite de Fibonacci Suite de nombres entiers Etude de la reproduction des lapins Interviennent dans la nature vivante

Définition

Premiers termes : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144


ND

LR :

Eucl

ide é

tait

un m

art

ien

0

1

1 2

0

1

, 2 : n n nn n

F

F

F F F

42

Propriétés de la suite de Fibonacci

Strictement croissante à partir du rang 2 Reliée au nombre d’or (phi)

D’où


ND

LR :

Eucl

ide é

tait

un m

art

ien

1 52

1 52

1,618, avec

5 0,618

nn

n

F

5

n

n

F

43

Lemme

Si a > b ≥ 0 et si PGCD(a, b) effectue k appels récursifs alors et

Preuve par récurrence P(1) : Supposons P(k)

Soit a > b ≥ 0 tq PGCD(a, b) effectue k + 1 appels récursifs

Alors PGCD(a, b) appelle PGCD(b, a mod b) qui effectue k appels récursifs et donc, d’après P(k) : et

Or, de Il vient Et donc , soit P(k + 1)


ND

LR :

Eucl

ide é

tait

un m

art

ien

2ka a F 1kb a F

20 0 1 1k b k b a F 32a b a a F

2kb a F 1mod ka b a Fmod et 0, i.e. 1a a

b ba b a b a b a

mod 1 abb a b a b a a

2 1 3mod k k ka b a b a F F F

44

Théorème de Lamé

Si a > b ≥ 0 et si alors PGCD(a, b) effectue moins de k appels récursifs

Preuve : contraposée du lemme Propriété : la borne de Lamé est optimale

Preuve : elle peut être atteinte Cas où a et b sont deux nombres de Fibonacci

successifs un seul appel récursif Soit k ≥ 2, on vérifie aisément que Par conséquent appelle C’est-à-dire que effectue k – 1 appels

récursifs


ND

LR :

Eucl

ide é

tait

un m

art

ien

1kb a F

3 2, 2,1PGCD PGCDa F F

1 1modk k k F F F

1,k kPGCD a F F 1,k kPGCD a F F 1,k kPGCD a F F

45

Conséquences

Borne de Lamé : La complexité de l’algorithme d’Euclide est

linéaire par rapport à la longueur de son plus petit opérande

La règle empirique :

D’où la règle empirique bien connue : Le nombre d’appels récursifs de l’algorithme

d’Euclide est au + 5 fois le nombre de chiffre en base 10 du plus petit de a et b

Exemple : PGCD(144, 89) : 10 appelsComplexité Cas

spéciaux Euclide

ND

LR :

Eucl

ide é

tait

un m

art

ien

ln 5 ln log5

k

b b k k b b

10

ln10 ln ln5 5 5log

ln ln10 ln

b bk b

46

Complexité de l’expon. rapide

Voir corrigé du DE L2 2015, exo 6 En tirer un argument pour affirmer la complexité en log2 n Corrigé détaillé dans « Exercices et problèmes d’algorithmique

numérique » p 191


ND

LR :

Eucl

ide é

tait

un m

art

ien

47


V. Complexité

48

De quoi est-il question ? Exemples de problèmes NP-complets Le problème ouvert : P = NP ? Consultation de la littérature pour les

plus motivés

NP-complétude

Complexité Classes NP-Complétude

Documents

Exemples pour démarrer (tri insertion, tri fusion) Maths appliquées Notations asymptotiques (Knuth) Récurrences T(n) = aT(n/b) + f(n) et études de cas