Algorithmes et structures de données 7ème cours Patrick Reuter maître de conférences preuter

Algorithmes et structures de données

7ème cours

Patrick Reutermaître de conférences

http://www.labri.fr/~preuter

Aujourd’hui

- Complexité asymptotique- Fonctions/Procédures

Déclaration de variables

var compteur : integer;

var diviseur : single;

var c : char;

var precision : double;

var nom : string;

var masculin : boolean;

var jours : array[1..12] of byte;

diviseur := 1.1; { Affectation }compteur : = 1;Nom := ‘Gerhard’;

Nombre entier

Nombre à virgule flottante

Nombre à virgule flottante avec double précision

Chaîne de caractères

Tableau

Déclaration de variables

var compteur : integer;

var diviseur : single;

var c : byte;

var precision : double;

var nom : string;

var masculin : boolean;

var jours : array[1..12] of byte;

diviseur := 1.1; { Affectation }compteur : = 1;Nom := ‘Gerhard’;

Nombre entier

Nombre à virgule flottante

Nombre à virgule flottante avec double précision

Chaîne de caractères

Tableau

Déclaration de variables• Types de base prédéfinis

– Integer, boolean, Real, Single, …

• Les types énumérés

– type t_jourdesemaine =(lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche);

– var jour : t_jourdesemaine;

• Type tableau (structure homogène)

– 1 dimension

type t_tableau = array[1..12] of byte;var jours : t_tableau;

– 2 dimensions

type t_damier = array[1..8] of array[1..8] of t_champ;var damier : t_damier;

• Type enregistrement (structure hétérogène)

type t_date = RECORD jour : byte; mois : byte; an : integer; END;

var aujourdhui : t_date

type t_date = RECORDan : integer;mois : byte;

jour : byte;END;var aujourdhui : t_date;

aujourdhui.an #4000

...

#536.870.910#536.870.911

...

aujourdhui.jour;#4005

...

aujourdhui.mois;#400420061024

#0

Occupe de la place successivedans la mémoire

Exigences d’un programme

• Lisibilité

• Extensibilité

• Portabilité

• Réutilisable

• Fiabilité

• Efficacité (faible complexité)

Complexité

• Combien de temps d’exécution le programme dure t’il? Complexité temporelle

De combien de mémoire le programme a t’il besoin? Complexité de mémoire (ou Complexité spatiale)

Comment trouver ces complexités ?

méthode empirique

méthode mathématique

Méthode empirique

• Avec une montre et un logiciel d’analyse de mémoire

• Problème : dépend des facteurs suivants– de la machine utilisée;– du jeu d’instructions utilisées– de l’habileté du programmeur– du jeu de données générées– du compilateur choisi– …

BIEN SUR : Le temps d’exécution dépend de la longueur de l’entrée (par exemple le nombre de chansons dans la collection).

Ce temps est une fonction T(n) où n est la longueur des données d’entrée.

Méthode mathématique

• Théorie de la complexité– Temporelle– Spatiale

• Basée sur une machine abstraite– Random-access memory (RAM)– Instructions de base (affectation, boucle, appel de

fonctions …)

• longueur des données d’entrée n

Instructions de répétition:

Boucle : complexité du corps multipliée par le nombre de fois qu’elle est répétée.

Démarche :

1. déteminer le nombre de répétitions 2. multiplier ce nombre par la complexité du corps de cette boucle.

1er exemple pour T(n)• Trouver l’artiste d’une chanson donnée

‘kaya’

i := 1;tant que i<=n fairesi collection[i].title = ‘kaya’ alors

afficher collection[i].artiste;i := i + 1;

fin tant que

• Affectations : 1 + n• Comparaisons : 2n• Appel de fonctions : n (Attention : considerer le “worst

case”, c-à-d la pire option)• T(n) = 4n+1

2ème exemple pour T(n)i := 1;tant que i<=n faire

j := 1;tant que j<=n faire

si i=j alors a[i][j] := 1;

sinona[i][j] := 0;

fin sij := j + 1;

fin tant quei := i + 1;

fin tant que

• Affectations : 1 + 2n + 2n2

• Comparaisons : n+ 2n2

• T(n) = 4n2+3n+1

Théorie de la complexité

• Comment peut on résoudre des problèmes de plus grande échelle (plus grand longueur des données d’entrée n ) ?

1. On utilise une machine plus puissante

2. On choisit un algorithme avec une meilleure complexité

Théorie de la complexité• Comment peut on résoudre des problèmes de plus grande échelle (plus

grande longueur des données d’entrée n ) ?

1. On utilise une machine plus puissante (p.ex.10 fois plus )

Ti(n) Facteur de croissance de longueur des données d’entrée n

log2n >10

n 10

n log2 n <10

n2 3,16

n3 2,15

2n 1

Théorie de la complexité – Diminuer les constantes

• Comment peut-on optimiser T(n) ?

• T(n) = 4n2+3n+1• 1ère solution :

diminuer les constantes a,b,c

• Exemple : – T1(n) = 4n2+3n+1– T2(n) = 4n2

– T3(n) = n2

n 1 2 3 10 20 100 1000

T1(n) 8 25 46 431 1661 40301 4003001

T2(n) 4 16 36 400 1600 40000 4000000

T3(n) 1 4 9 100 400 10000 1000000

T1/T2 2 1,56 1,28 1,08 1,04 1,01 1

T1/T3 8 6,25 5,11 4,31 4,15 4,04 4

Théorie de la complexité – Diminuer les constantes

• 2 fonctions– T1(n) = a1n2+b1n+c1

– T2(n) = a2n2+b2n+c2

• Amélioration :– lim n ∞ T1(n) /T2(n) = a1/a2

• Pour des grand n, seule la constante du plus grand degré est significative


• Comment peut on résoudre des problèmes de plus grande échelle (plus grande longueur des données d’entrée n ) ?*

2. On choisit un algorithme avec une meilleure complexité !!!

Théorie de la complexité – Changement de la fonction

2ème solution

changer la fonction

• T1(n) = log2n

logarithmique

• T2(n) = n

linéaire

• T3(n) = n log2 n

Quasi-linéaire

• T4(n) = n2

quadratique

• T5(n) = n3

cubique

• T6(n) = 2n

exponentiel

Théorie de la complexité – Changement de la fonction

• Quel taille de n peut être résolue en 1 seconde, une minute, une heure ?– Avec une machine de 1000 instructions par seconde

Ti(n) 1 sec 1 min 1 heurelog2n 21000 260000 23600000

N 1000 60000 36000000n log2 n 140 4893 20000n2 131 244 1897n3 10 39 1532n 9 15 21


• Notation Grand-O

• Exemple :

Si

T(n) ≤ c n

pour une constante c et toutes les valeurs de n>n0, on dit

« T(n) est dans O(n) » ou bien

T(n) O(n) ou, par abus d’écriture,

T(n) = O(n)


• Notation Grand-O

• Exemple : (Rappel de T(n) = 4n+1)

Si

T(n) ≤ c n

pour une constante c et toutes les valeurs de n>n0, on dit

« T(n) est dans O(n) » ou bien

T(n) O(n) ou, par abus d’écriture,

T(n) = O(n)

1er exemple pour T(n)• Trouver l’artiste d’une chanson donnée

‘kaya’

i := 1;tant que i<=nsi collection[i].title = ‘kaya’ alors

afficher collection[i].artiste;i := i + 1;

fin tant que

• Affectations : 1 + n• Comparaisons : 2n• Appel de fonctions : n (Attention : considerer le “worst

case”, c-à-d la pire option)

• T(n) = 4n+1 O(n) !


• En général :

O(f) = {g | c > 0 : n0 > 0 : n ≥ n0 : g(n) ≤ c f(n)}

Soit g une fonction non négative.

g est dans O(f) s’il existe deux constantes positives c et n0 telles que g cf(n) pour tout n > n0.

EXEMPLE : T(n) = 9n2 O(n2) f = n2, g = 9n2

2ème exemple pour T(n)i := 1;tant que i<=n faire

j := 1;tant que j<=n faire

SI i=j ALORS a[i][j] := 1;

SINONa[i][j] := 0;

j := j + 1;fin tant quei := i + 1;

fin tant que

• Affectations : 1 + 2n + 2n2

• Comparaisons : n+ 2n2

• • T(n) = 4n2+3n+1 O(n2) !

Théorie de la complexitéClasses de Grand-O• O(1) complexité constante

• O(log n) complexité logarithmique

• O(n) complexité linéaire

• O(n log n) complexité quasi-linéaire

• O(na) complexité polynomiale– O(n2) complexité quadratique

– O(n3) complexité cubique

• O(an) complexité exponentielle

O(log n) O(n) O(n log n) O(n2) O(n3) O(2n)

Instructions de répétition:

Boucle : complexité du corps multipliée par le nombre de fois qu’elle est répétée.

Démarche :

1. déteminer le nombre de répétitions 2. multiplier ce nombre par la complexité du corps de cette boucle.

• On analyse les boucles pour comme les boucles tant quetant que

Pour i de 1 à n faireFin pour

• Instruction si: maximum entre le alors et le sinon

• cas: maximum parmi les différents cas

Appels de fonctions: Temps d’exécution de la fonction

Procédures et fonctions:

leur complexité est déteminée par celle de leur corps.

type t_tableau = array[1..n] of integer;var tab : t_tableau;

function dedans(quoi : integer, n : integer) : integer;

var position : integer;var i : integer;

débutposition := 0;i := 1;

tant que (i<=n) faire

si (quoi = tab[i]) alors position := i;

fin si

i := i + 1;

fin tant que

result := position;

fin







fin si

i := i + 1;

fin tant que

result := position;

fin

En-tête de la fonction







fin si

i := i + 1;

fin tant que

result := position;

fin

Corps de la fonction






si (quoi = tab[i]) alors position :=i;

fin si

i := i + 1;

fin tant que

result := position;

fin

Paramètres de la fonction(arguments)







fin si

i := i + 1;

fin tant que

result := position;

fin

Type de retourde la fonction

Valeur de retourde la fonction







fin si

i := i + 1;

fin tant que

result := position;

fin







fin si

i := i + 1;

fin tant que

result := position;

fin

bouclemax n itérations







fin si

i := i + 1;

fin tant que

result := position;

fin





tant que (i<=n ET position = 0) faire


fin si

i := i + 1;

fin tant que

result := position;

fin

T(n) = 4n+3 O(n) !

type t_tableau = array[1..15] of integer;var tab : t_tableau;

function enigme(quoi : integer, n : integer) : integer;

var inf, sup, milieu : integer;var trouve : boolean;

débutinf := 1;sup := n;trouve := FAUX;

tant que (sup >=inf ET trouve = FAUX) faire milieu := (inf + sup) DIV 2; si (quoi = tab[milieu]) alors trouve := VRAI; sinon si (quoi < tab[milieu]) alors sup := milieu -1; sinon inf := milieu + 1; fin si fin si fin tant que si (trouve = FAUX) alors result := 0; sinon result := milieu; fin si

fin






fin






fin

bouclemax. log2n itérations

• Pourquoi log2n ?– n entrées dans le tableau– intervalle [sup, inf]

– à chaque itération, l’intervalle est divisé par 2• Soit

milieu := (inf + sup) DIV 2;

sup := milieu -1;• Soit

milieu := (inf + sup) DIV 2;

inf := milieu +1;

– condition d’arrêt : sup = inf• c-à-d que l’intervalle est inférieur à 1

max log2n itérations

• Pourquoi log2n ?– n entrées dans le tableau– intervalle [sup, inf]

– à chaque itération, l’intervalle est divisé par 2

• Soitmilieu := (inf + sup)

DIV 2;sup := milieu -1;

• Soitmilieu := (inf + sup)

DIV 2;inf := milieu +1;

– condition d’arret : sup = inf• c-à-d que l’intervalle est inférieur à 1

itération sup-inf

sup-inf DIV 2

1 15 7

2 7 3

3 3 1

4 1 1






fin T(n) = 7log2n+5 O(log n) !

Documents

Algorithmes et structures de données 7ème cours Patrick Reuter maître de conférences preuter