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

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 log2 n <10

n2 3,16

n3 2,15

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 :

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)

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 si

i := i + 1;

fin tant que

result := position;

En-tête de la fonction

fin si

i := i + 1;

fin tant que

result := position;

Corps de la fonction

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

fin si

i := i + 1;

fin tant que

result := position;

Paramètres de la fonction(arguments)

fin si

i := i + 1;

fin tant que

result := position;

Type de retourde la fonction

Valeur de retourde la fonction

fin si

i := i + 1;

fin tant que

result := position;

fin si

i := i + 1;

fin tant que

result := position;

bouclemax n itérations

fin si

i := i + 1;

fin tant que

result := position;

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

fin si

i := i + 1;

fin tant que

result := position;

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

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

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

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

Documents

Les 7ème Olympiades de VTB

Matinée Recyclage Educateurs Poules Label U12-U13...Envoi des feuilles de liaison (pour les 2 clubs !) Les prochaines dates ... Journée Finale 7ème Journée 7ème Journée 7ème

7ème Journée Annuelle – Cognac - 09.04.2013

Les Français et la notoriété du 7ème continent - IFOP€¦ · Les Français et la notoriété du 7ème continent Novembre 2015 6.La notoriété spontanée du 7ème continent

Le Radeau du 7ème Continent

Conception de Site Webs Interactifs Cours 9 Patrick Reuter preuter@labri.fr

Conception de Site Webs Interactifs Cours 3 Patrick Reuter preuter@labri.fr

Algorithmes et structures de données Cours 8 Patrick Reuter preuter

L'Enfant & le 7ème art

Conception de Site Webs dynamiques Cours 5 Patrick Reuter preuter@labri.fr

Algorithmes et structures de données 5ème cours Patrick Reuter preuter

Tribut 7ème Edition

Algorithmes et structures de données Cours 1 Patrick Reuter preuter

Algorithmes et structures de données avancées 6ème cours Patrick Reuter preuter

1 Dr GEOFFRAY-Dr ISARDON-Dr RENAUD Dr REUTER-Dr ROUDIL

Chercheur à l'école: Bob Reuter au Lycée Ermesinde 31 mars 2017

Cas cliniques Dr GEOFFRAY-Dr ISNARDON-Dr RENAUD Dr REUTER-Dr ROUDIL

Algorithmes et structures de données Patrick Reuter maître de conférences preuter

Conception de Site Webs dynamiques Cours 6 Patrick Reuter preuter@labri.fr

BILAN 7ème édition 2015