Références Bibliographiques 1. Th. Cormen, Ch. Leiserson, R. Rivest, « Introduction à...

Références Bibliographiques

• 1. Th. Cormen, Ch. Leiserson, R. Rivest,• « Introduction à l’algorithmique », DUNOD,

Paris, 1994, (2002)• 2. Ch. Froidevaux, M.-C. Gaudel et M. Soria

Types de données et algorithmes, McGraw-Hill, Collection Informatique,1990

• 3. A. Aho, J. Ulman, « Concepts fondamentaux de l’informatique », DUNOD, 1996

• 4. M. Quercia, « Algorithmique », Vuibert , 2002

Sommaire• Chapitre I. Algorithmes et Algorithmique. Notions de

base• Chapitre II.Rappels mathématiques et complexité• Chapitre III. Algorithmique élémentaire des tableaux

(recherche, tri)• Chapitre IV. Structures linéaires (piles, files, listes

chaînées)• Chapitre V. Tables de hachage• Chapitre VI. Arbres (définition, parcours, représentation)

Chapitre VII. Tri• Chapitre VIII. Introduction aux graphes

Chapitre I. Algorithmes et Algorithmique. Notions de base

• Notion de l’Algorithme• Expression des algorithmes• Types d’algorithmes (récursifs, itératifs)• Critères d’évaluation des algorithmes• 5. Complexité

Notion de l’Algorithme• Algorithme est une notion connue depuis l’antiquité

– Babyloniens, 1800 avant J.C.– Euclide , III siècle de n.è. « algorithme de la division

entière » • Terme « Algorithme » - vient du nom d’un mathématicien

perse « al-Khowa-rismi »• La notion est très liée à l’idée de machine capable

d’exécuter des opérations mathématiques élémentaires.• Machine de Babbage(1833), Ada Lovelace (Byron)

(1840)• Vers 1930 machine abstraite de Turing.•

Machine de Von Neumann(1945)

Mémoire

UALUContrôle

Accumulateur

Programme

Entrées Sorties

Définition

• Un algorithme décrit un traitement sur un certain nombre fini de données (éventuellement aucune).

• Un algorithme est la composition d’un ensemble fini d’étapes, chaque étape étant formée d’un nombre fini d’opérations dont chacune est :– définie de façon rigoureuse et non ambiguë;– effective, c’est à dire pouvant être effectivement

réalisée par une machine. • Quelle que soit la donnée sur la quelle il travaille, un

algorithme doit toujours se terminer après un nombre fini d’opérations et fournir un résultat [1].

• Algorithmes « déterministes » vs « stochastiques »

Expression des algorithmes

• Pseudo-code Exalgo : langage proche au Pascal, C++, …permet d’écriture logique

• Exemple :const int N=100;int Sigma =0;for (int i=0;i<N;i++) Sigma++=i;

…

Algorithme « Somme N premiers »var Sigma, i : entiers;Const N=100;Sigma:=0;Pour i allant de 0 à N faire (par pas de 1) Sigma:=Sigma+i;Fin Pour…

Pseudo-CodeStructure d’un programme :

• Partie déclarative : types, variables, constantesExemples :

Type Enregistrement : entier a;

caractère c;Fin Enregistrement; //

Var a,b : réelles;Const entier c;

• Partie « exécutable » : instructions– Parenthèses opératoires « Début », « Fin MonProgramme »– « Début » et « Fin » pour des blocs d’instructions

Type pointeur

• Si T est un type quelconque, alors ^T représente un pointeur sur le type T

• Type1 = Enregistrement

a : entier;

suivant : ^Type1;

Fin Enregistrement;

12 16 28

Structures de contrôle (1)

(1) Séquence d’instructions :

a := 12;b := 21;c := a+b;

(2) Alternative : Si condition

alors exemple : max(a,b) (A)

sinon (B)

Fin-Si

Structures de contrôle (2)• Répétition: Tant que, Pour, Répéter jusqu’à• Exemple : calcul de f(x)=x2 sur [a;b] en a, a+∆, a+2∆,…• (1) Tant que a<b faire • f= a*a;

afficher f ;

a:=a+delta;• FinTq• (2) n:=(b-a) div delta• Pour i allant de 1 à n par pas 1 faire • f= a*a;

afficher f ;

a:=a+delta;• FinPour

Strucutres de contrôle (3)

• Repeter • //traitement• c:=lire_un_caractère();• afficher_un_caractère(c);• Jusqu’à c =‘!’ //condition d’arrêt

Spécification des algorithmes

• La spécification d’un algorithme décrit ce que l’algorithme fait, sans détailler comment.

• Il est important d’indiquer les entrées et les sorties

Exemple• On considère le problème de recherche suivant :• Entrée : Une séquence de n Nombres A={a1, a2, …, an} et une valeur v.• Sortie : Un indice i tel que v=A[i], ou la valeur spéciale NIL si v n’appartient

pas à A.

Procédures et fonctions

• Le pseudo-code admet trois formes de représentation d’un algorithme– programme– procédure– fonction

• A proprement parler, les 3 peuvent être exprimés à l’aide des deux derniers.

• (Remarquons que ce n’est pas le cas des langages de programmation moderne tel le C++ où tout algorithme peut être exprimé sous forme d’une fonction)

• Néanmoins nous allons garder cette partition en « fonction » et « procédure ».

Procédure vs fonction

• Procédure Division_Euclidéenne(val a,b:entiers,

réf p,q:entiers);

• Fonction PGCD(val a,b:entiers):entier;

• Une procédure est nécessaire quand il s’agit de modifier la valeur de plusieurs variables de sortie

• Une fonction renvoie toujours un résultat (qui peut être représenté sous forme d’un ensemble, d’un vecteur, … d’une collection d’objets)

Passage par valeur ou par référence?

• Passage par valeur : les valeurs d’appel restent inchangées quelles que soient opérations effectuées sur les variables à l’intérieur de la procédure/fonction

• Passage par référence : c’est l’adresse d’emplacement

dans la mémoire de la machine abstraite

• Exemple : Procédure qui additionne et soustrait deux nombresProcédure AddSous(val a,b:entier, réf somme, reste : entiers) OuProcédure AddSous(réf a,b : entiers)

Types d’algorithmes (récursifs, itératifs)

• L’expression des algorithmes sous forme récursive permet des descriptions concises qui se prêtent bien à des démonstrations par récurrence.

• Le principe de récursivité : utiliser pour décrire l’algorithme sur une donnée d, l’algorithme lui-même appliqué à un sous-ensemble de d ou à une donnée d’ plus petite.

• Pour un algorithme récursif on définit :– relation de récurrence ;– base de récursivité ;– domaine de récursivité (rejoint le domaine de validité)

Algorithmes récursifs (1)

• Exemple 1. Factorielle• Def.

1. Relation de récurrence :

2. Base :

3. Domaine : N

1!0,1...21! nnnn

)1()( nfnnf

1)0( f

Algorithmes récursifs (2)

Version récursive Version itérative

Fonction Fact(val n: entier):entierVar fct : entier;Debut Si n=0 alors fct := 1; sinon fct := n*Fact(n-1); FinSiretourner fct; Fin Fact

Fonction Fact(val n: entier):entierVar fct : entier; Si n=0 alors fct=1; sinon fct:=n; Tant que (n>1) fct:=fct*(n-1); n:=n-1; FinTantQue FinSi retourner fct; Fin Fact

Algorithmes récursifs (3)

Exemple 2 : pgcd

On utilise la propriété suivante pour tout a>=0 et b>0

pgcd(a,b) = pgcd(b, a mod b);

A. Version récursive

1. Relation de récurrence

pgcd(a,b)=pgcd(b, a mod b);

2. Base de récursivité

a mod b =0=>pgcd=b

3. Domaine a>=0, b>0.

Algorithmes récursifs (4)

Fonction pgcd(val a,b : entiers):entierVar r : entier;Début /* a est supposé supérieur ou égal à b*/r:= a mod b;Si r=0 alors retourner b; sinon retourner pgcd(b,r); /* b est supéieur à r*/FinSiFin pgcd

Algorithmes récursifs (5)Exemple 2 : pgcd

B) Version itérative

Fonction pgcd(val a,b : entiers):entierVar r : entier;Debut

r:= a-(a/b)*b /* rappel du modulo*/ Tant que r!=0 faire a:=b;

b:=r; r:= a-(a/b)*b; FinTq retourner b;Fin pgcd

Critères d’évaluation des algorithmes

• Terminaison• Validité• Lisibilité• Complexité

5. Complexité

L’objet de l’analyse de la complexité d’un algorithme est de quantifier les deux grandeurs physiques « temps d’exécution » et « place mémoire » dans le but de comparer entre eux différents algorithmes qui résolvent le même problème.

Complexité en temps : le nombre d’opérations effectuées par le programme et le temps d’exécution

Complexité en espace : le nombre d’instructions et le nombre de données du programme avec le nombre de mots mémoire nécessaires pour stocker chacune d’entre elles, ainsi que le nombre de mots mémoire supplémentaires pour la manipulation des données.

Le but de l’analyse de la complexité des algorithmes est d’établir des résultats généraux, permettant d’estimer l’efficacité intrinsèque de la méthode utilisée par un algorithme, indépendamment de la machine, du langage de programmation, du compilateur et de tous les détails d’implémentation.

Complexité en temps

• Mesure de complexité : nombre d’opérations fondamentales

• Exemples : - recherche séquentielle dans une liste – OF est

celle de comparaison;- calcul de la somme de n nombres – OF est celle

d’addition;- multiplication des matrices – OF sont l’addition

et la multiplicationEtc…

Calcul de complexité (1)• Dénotons C(X) le nombre d’opérations fondamentales de la

construction X

1. Lorsque les opérations sont dans une séquence d’instructions, leur nombres s’ajoutent (ex. incrémenter n variables)

2. Pour les branchements conditionnels C(Si Cond alors I1 sinon I2)< C(Cond)+max(C(I1),C(I2)) –

majoration

3. Pour les boucles, le nombre d’opérations dans la boucle est

Avec n – le nombre d’itérations dans la boucle, C(i) – le nombre d’opérations fondamentales à chaque itération

n

i

iP1

)(

Calcul de complexité (2)4. Pour les appels des procédures ou fonctions : s’il n’y a pas d’appels récursifs, on

peut toujours trouver une façon d’ordonner les procédures et fonctions de telle sorte que chacune d’entre elles n’appelle que des procédures et des fonctions dont le nombre d’opérations fondamentales a déjà été évalué.

5. Appels récursifs : résolution de la relation de récurrence

• Exemple (factorielle)

Fonction Fact(val n: entier):entierVar fct : entier;Debut Si n=0 alors fct := 1; sinon fct := n*Fact(n-1); FinSiretourner fct; Fin Fact

• Dénotons T(n) le nombre des opérations fondamentales (multiplications). T(0)=0, T(n)=T(n-1)+1, T(n)=T(n-2)+1+1, … T(n)=T(0) + 1+1+….=n

• Ordre de grandeur, récurrences => bases mathématiques.

Complexité : du meilleur au pire (1)• Exemple : algorithme de recherche séquentielle dans un tableau.

Son temps d’exécution dépend de la donnée sur laquelle il opère.• On peut définir plusieurs quantités pour caractériser le

comportement d’un algorithme sur l’ensemble Dn des données de taille n.

• Notons coûtA(d) la complexité en temps de l’algorithme A sur la donnée d (de taille n).

A) La complexité dans le meilleur des cas

B) La complexité dans le pire des cas

C) La complexité en moyenne

nAA DddcoûtnMin ,min

nAA DddcoûtnMax ,max

nDd

AA dcoûtdpnMoy )( ddeéprobabilitdp )(

Complexité : du meilleur au pire (2)• Relations entre les complexités

• Si le comportement de l’algorithme ne dépend que de la taille des données, alors les trois sont égales.

• Un exemple : Algorithme de la recherche séquentielle d’un élément dans un tableau non-ordonné. Le résultat est l’indice de l’élément ou 0

Var L: tableau[1…n] des entiersX: entier

J: entierDébutj:=1TQ (j<=n et L[j]!=X) faire j:=j+1;FTQSi j>n alors j:=0 Fsi

nMaxnMoynMin AAA

Complexité : du meilleur au pire (3)

• Analyse de la complexité• Opération fondamentale : comparaison

1.

2.

3. • Solution : dénotons q la probabilité que X se trouve dans le tableau.

Supposons que toutes les places sont équiprobables p(i)=1/n• Ainsi la probabilité que X se trouve dans le tableau en i-ème place est

p(Dn,i)=qxp(i)=q/n

• La probabilité que X ne se trouve pas dans le tableau est : p(Dn,i)=1-q

1nMinA

nnMaxA

?nMoyA

2/)1()1(/)1(),().,(0 1

qnnqnqinqiDncoûtiDnpnMoyn

i

n

iA

2/1/2

1/

1

nqnnn

qnqin

i

Comparaisons de complexités

• Comparer sur un ensemble des données très grand;

• « Ordre de grandeur », « Comportement asymptotique »