Module Informatique 2 - LORIA · cours d’algo. et prog. par Y.Q. Song 12 Correction d’un algorithme récursif • Preuve de la correction – Terminaison (l’algorithme se termine)

Partie

Algorithmique et Programmation

YeQiong SONG

Professeur à l’ENSEM-INPL, [email protected]

Module Informatique 2

cours d’algo. et prog. par Y.Q. Song 2

Objectifs et contenu

• Objectifs:

– Base sur l’algorithmique

• Contenu:

– Récursivité de méthodes

– Complexité des algorithmes

– Structures de données dynamiques (vector,

liste chaînée (définition récursive), graphe,

…)


-Récursivité

-Quelques algorithmes fondamentaux

-Notion de complexité des algorithmes

-Structures de données

Références:

• R. Sedgewick, « Algorithmes en Java », Pearson Education, 3ème

édition, 2004.

• V. Granet, « Algorithmique et programmation en Java », Dunod, 2ème

édition, 2004.

• F. Morain, « Les bases de l’informatique et de la programmation », cours

école polytechnique

Algorithmique:


Récursivité des

méthodes

D’après le cours de l’école polytechnique de F. Morain

Séance 1: Points à aborder aujourd’hui


Récursivité

• Récursivité est une forme particulière de l’itération

• Proche de la relation de récurrence en

mathématique. E.g. factorielle et fibonacci

• Fonction/méthode récursive: une

fonction/méthode qui s’appelle elle-même

• Les fonctions/méthodes récursives permettent

d’une écriture plus lisible, parfois plus facile à

écrire dans certains traitements récursifs (e.g.

tours de Hanoï)


Factorielle

factorielle(entier k) :

si k=0

alors renvoyer 1

sinon

renvoyer k * factorielle(k-1)

finsi

Ceci peut alors se traduire par le programme suivant en pseudo-langage :


Factorielle

0!=1!=1; n! = n × (n-1)!

De manière itérative, on écrit : static int factorielle(int n){

int f = 1;

for(int k = n; k > 1; k--)

f *= k;

return f;

}

static int fact(int n){

if(n = = 0 ) return 1; // cas de base

else return n * fact(n-1);

}

De manière récursive, on peut écrire :


Factorielle

Empilement:

Dépilement:

fact(0)=1

fact(3)=3*fact(2)=3*(2*fact(1))=3*(2*(1*fact(0)))=3*2*1*1


Problème de terminaison


if(n = = 0) return 1; // cas de base

else return n * fact(n+1);

}

Ce programme ne termine pas

Pile débordée!

static int f(int n){

if(n > 100)

return n - 10;

else

return f(f(n+11));

}

Exercice: ce programme termine t-il?

Réponse:

la fonction retourne

91 si n ≤ 100

n-10 si n > 100


Règles de conception

• Régle1: Tout algorithme récursif doit distinguer plusieurs cas, dont l’un au moins ne doit pas comporter d’appel récursif. Sinon risque de cercle vicieux et de calcul infini

• Condition de terminaison, cas de base – Les cas non récursifs d’un algorithme récursif sont appelés cas de

base

– Les conditions que doivent satisfaire les données dans ces cas de base sont appelées conditions de terminaison

static int fact(int n){return n * fact(n-1);}

fact(1) 1*fact(0) 1*0*fact(-1) …

Calcul infini


Règles de conception

Attention:

Même avec un cas de base un algorithme récursif peut ne

produire aucun résultat


if(n = = 0) return 1; // cas de base

else return fact(n+1)/(n+1);

}

fact(1) fact(2)/2 fact(3)/(2*3) …

Calcul infini

• Régle2: tout appel récursif doit se faire avec des données de plus

en plus « proches » de données satisfaisant une condition de

terminaison


Correction d’un algorithme récursif

• Preuve de la correction

– Terminaison (l’algorithme se termine)

– Correction partielle (l’algorithme fait bien ce qu’on attend de lui)

• Terminaison

Il s'agit de fournir un ordre sur les paramètres de l'algorithme. Cet ordre doit

d'abord ne pas avoir de chaînes infinies descendantes et ensuite il doit être tel

que si on invoque l'algorithme avec des paramètres, les invocations suivantes

plus internes doivent se faire avec des paramètres plus petits pour l'ordre.

Cf. Wikipédia pour le théorème.

Il faut montrer que si les appels internes à l'algorithme font ce qu'on attend

d'eux, alors l'algorithme entier fait ce qu'on attend de lui.

• Correction partielle


Suite de fibonacci – récursivité multiple

F0 = 0, F1 = 1, ∀ n≥ 2, Fn = Fn-1 + Fn-2

static int fib(int n){

if(n <= 1) return n; // cas de base

else return fib(n-1)+fib(n-2);

}

Carrés de Fibonacci en spirale:

(extrait de Wikipedia)


Problème de complexité

Deux critères de performances: temps d’exécution et place en mémoire

Nombre d’appels (temps d’exécution) à la fonction trop important!


Suite de fibonacci

static int fib(int n){

int i, u, v, w;

// u = F(0); v = F(1)

u = 0; v = 1;

for(i = 2; i <= n; i++){

// u = F(i-2); v = F(i-1)

w = u+v;

u = v;

v = w;

}

return v;

}

On calcule de proche en

proche les valeurs du

couple (Fi, Fi+1).

Le calcul de Fn ne coûte

plus que n appels (i.e.,

n additions).


Calcul du PGCD

Ecrire sous forme récursive le calcul du PGCD de deux nombres

– Pour a et b positifs, le PGCD de a et b est le plus grand entier divisant a et b.

– Alors les propriétés suivantes permettent de construire un algorithme récursif du calcul (algorithme d’Euclide):

• pgcd (a,0) = a

• si a> b, pgcd (a,b) = pgcd ( a-b,b) et a=a-b, sinon pgcd (a,b) = pgcd (a, b-a) et b=b-a


Algorithme d’Euclide

[Extrait de Wikipedia]


Algorithme d’Euclide

- Notons par r-1 le plus grand des deux nombres et r0 le plus petit

- Faire les divisions euclidiennes:

r-1 = r0 *q1 + r1

r0 = r1 *q2 + r2

r1 = r2 *q3 + r3

…

rk = rk+1 *qk+2 + rk+2

…

rn-2 = rn-1 *qn + rn

rn-1 = rn *qn+1 + 0

- PGCD(r-1 , r0 ) = rn

Exemple: PGCD(791, 336) = 7

791 = 336x2 + 119

336 = 119x2 + 98

119 = 98x1 + 21

98 = 21x4 + 14

21 = 14x1 + 7

14 = 7x2 + 0


Calcul du PGCD

public int pgcd (int a, int b) {

int pgcd ;

if (a == b ) { pgcd = a ;}

else {

if (b == 0 ) { pgcd = a ;}

else {

if ( a>b ) { pgcd = pgcd ( a-b , b) ;}

else {pgcd = pgcd (b –a , a);} } } ;

return pgcd; }

Exercices: - comment calculer le PGCD(a,b,c)?

- donner la version itérative du calcul du PGCD


Les tours de Hanoï


http://fr.wikipedia.org/wiki/Image:Tower_of_Hanoi_4.gif


static void Hanoi(int n, int D, int M, int A){

if(n > 0){

Hanoi(n-1, D, A, M);

System.out.println("On bouge "+D+" vers "+A);

Hanoi(n-1, M, D, A);

}

}

Exercice: trouver une version itérative


Séances 2, 3 et 4: Points à aborder

• Séance 2 : Quelques algorithmes de tri et de recherche et

Introduction à la complexité des algorithmes

• Séance 3: Structures linéaires et récursivité de définitions

– Listes

– Piles

– Files

• Séance 4 : Structures linéaires et récursivité de définitions

– Graphes

– Structures arborescentes

• Arbres

• Arbre binaire


Séance 2 : Quelques algorithmes de tri et de

recherche et Introduction à la complexité

des algorithmes

• Pour résoudre un même problème, il existe souvent de nombreuses solutions plus ou moins efficaces

• En informatique, la recherche de l’algorithme le plus performant constitue en une tâche fondamentale et perpétuelle

• Critères de performances: temps d’exécution et encombrement mémoire

• Au lieu de mesurer les performances d’un programme sur une machine donnée (donc dépendantes d’un environnement particulier), on s’intéresse aux performances des algorithmes ou encore la complexité (qui donne une mesure théorique indépendamment d’un environnement matériel et logiciel particulier)


Complexité des algorithmes

• Complexité: fonction d’éléments caractéristiques de l’algorithme

• Comment mesurer la complexité (temps d’exécution et place mémoire) ? – On suppose que chaque opération de l’algorithme prend un temps

unitaire, on calcule le temps global pour exécuter l’algorithme, en meilleur cas, en cas moyen, en pire cas

• La complexité ne nous permet pas de prévoir un temps d’exécution exact, mais ce qui nous intéresse c’est l’ordre de grandeur de l’évolution du temps d’exécution (ou encombrement mémoire) en fonction d’éléments caractéristiques de l’algorithme (e.g. nombre d’éléments à trier dans un tableau)


Exemple: complexité de l’algorithme de

tri par Sélection

|53 914 827 302 631 785 230 11 567 350

11 |914 827 302 631 785 230 53 567 350

11 53 |827 302 631 785 230 914 567 350

11 53 230 |302 631 785 827 914 567 350

11 53 230 302 |631 785 827 914 567 350

11 53 230 302 350 |785 827 914 567 631

11 53 230 302 350 567 |827 914 785 631

11 53 230 302 350 567 631 |914 785 827

11 53 230 302 350 567 631 785 |914 827

11 53 230 302 350 567 631 785 827 |914

i=0

i=1

.

.

.



tri par Sélection

-À la ième étape, la sous-liste t[0] à t[i-1] est triée et tous ces éléments sont

inférieurs ou égaux aux éléments t[i] à t[n-1]

-Le nombre d’étape est n-1

Algorithme triParSélection(tab[n]) //dans l’ordre croissant

pourtout i de 0 à n-1 faire

min = i

//chercher l’indice du minimum sur l’intervalle de i à n-1

pourtout j de i+1 à n-1 faire

si tab[min] > tab[j] alors min=j finsi

finpour

//échanger tab[i] et tab[min]

tmp_min=tab[i]

tab[i] = tab[min]

tab[min]=tmp_min

finpour

//le tableau de tab[0] à tab[n-1] est trié



tri par sélection

On prend comme mesure de complexité le nombre de comparaison d’éléments

exprimé en fonction du nombre d’éléments à trier.

Il y a n-1 étapes

À la ième étape, le nombre de comparaisons est n-i

Le nombre total de comparaisons (c.à.d. l’instruction si tab[j] < tab[min]) est

alors (pour le cas moyen, meilleur ou pire): 121

2

1

( 1) ( 2) ... 1 ( )n

i

n n i n n

On dit que la complexité temporelle de l’algorithme de tri par sélection est

d’ordre quadratique et est notée par O(n2)

Si on multiplie par 100 le nombre d’éléments à trier, on peut alors prédire

que le temps d’exécution du tri sera multiplié par 10 000.

La complexité spatiale du tri par sélection est linéaire O(n) car on ne stocke

qu’un tableau de n éléments. Si on multiple par 100 le nombre d’éléments à

trier, le programme utilisera un tableau 100 fois plus grand.



tri par sélection Si on s’intéresse au nombre d’échanges (opération d’affectation), on

doit distinguer les cas moyen, meilleur et pire.

Meilleur cas: les éléments sont déjà dans l’ordre voulu. Le nombre

d’échanges est donc 0;

Pire cas: les éléments sont tous dans l’ordre inverse. On a un

échange par étape. Le nombre d’échanges est alors n-1;

Cas moyen: on suppose qu’à l’étape i, il y a une chance sur i que le

ième élément est déjà le minimum. Le nombre d’échanges est alors : 1

1

( 1) (1/ ) ln( )n

i

n i n n

Dans la pratique, on prend souvent la cas moyen (sauf indication

particulière), la complexité en termes du nombre d’échanges est alors

d’ordre O(n).



Pourquoi utiliser O(n2) au lieu du nombre exact (n2 – n)/2 ?

Soient deux fonctions positives f et g, on dit que f(n) est O(g(n)) s’il existe

deux constantes positives c et n0 telle que f(n) cg(n) pour tout n n0.

L’idée est donc d’établir un ordre de comparaison relatif entre les fonctions f

et g. Cette définition indique qu’il existe une valeur n0 à partir de laquelle f(n)

est toujours inférieure ou égale à cg(n). On dit alors que f(n) est de l’ordre de

g(n). Temps d’exécution ou

encombrement mémoire

Éléments caractéristique

de l’algorithme n0

f(n)

cg(n)


Complexité des algorithmes Nous pouvons montrer facilement que la fonction (n2 – n)/2 est de l’ordre

de O(n2). Pour que (n2 – n)/2 c n2, en prenant c = ½, il est évident que n’importe

quel n0 > 0 vérifie l’inégalité.

Remarque: on aurait pu aussi bien écrire que (n2 – n)/2 est O(n3) ou

O(n5), mais O(n2) est plus précis.

D’une façon générale, on choisira une fonction g la plus proche possible

de f, en respectant les règles suivantes:

-cf(n) = O(f(n)) pour tout facteur constant c

-f(n) +c = O(f(n)) pour tout facteur constant c

-f(n)+g(n) = O(max(f(n), g(n)))

-f(n) x g(n) = O(f(n) x g(n))

-Si f(n) est un polynôme de degré m,

f(n) = a0 + a1n + a2n2 + …+ amnm, alors f(n) est de O(nm).

-cn = O(cn) pour tout c > 1

-log nm = O(log n) pour tout m > 0

-log n = O(log n)



• Les algorithmes usuels peuvent être classés

en un certain nombre de grandes classes de

complexité

– Sous-linéaire: O(log n)

– Lineaire: O(n) ou O(n log n)

– Polynômiale: O(nk)

– Exponentielle: O(cn), c > 1



10 20 30 40 50 60

n 0,00001secondes

0,00002secondes

0,00003secondes

0,00004 secondes

0,00005 secondes

0,00006secondes

n2 0,0001 secondes

0,0004 secondes

0,0009 secondes

0,0016 secondes

0,0025 secondes

0,0036 secondes

n3 0,001 secondes

0,008 secondes

0,027 secondes

0,064 secondes

0,125 secondes

0,216 secondes

n5 0,1 secondes

3,2 secondes

24,3 secondes

1,7

minutes

5,2

minutes

13,0

minutes

2n 0,001 secondes

1,0 secondes

17,9

minutes

12,7

jours

35,7

ans

366

siècles

3n 0,059 secondes

58

minutes

6,5

ans

3855

siècles

2x108

siècles

1,3x1013

siècles

n

complexité



recherche linéaire

Recherche du plus petit élément

static int plusPetit (int[] x){

int k = 0, n = x.length;

for(int i = 1; i < n; i++)

// invariant : k est l'indice du plus petit

// élément de x[0..i-1]

if(x[i] < x[k])

k = i;

return k;

}

On exécute n – 1 tests de comparaison, la complexité est donc O(n).



recherche dichotomique

Si t est un tableau d'entiers triés de taille n, on peut écrire

une fonction qui cherche si un entier donné se trouve dans le

tableau.

Comme le tableau est trié, on peut procéder par dichotomie :

si x est dans t[g..d[, on calcule m = (g+d)/2 et on compare x à

t[m].

Si x=t[m], on a gagné,

sinon on réessaie avec t[g..m[ si t[m] < x

et avec t[m+1..d[ sinon.

Principe de « diviser pour régner »




static int rechercheDichotomique(int[] t, int x){

int m, g, d;

g = 0; d = N-1;

do{

m = (g+d)/2;

if(t[m] == x) return m;

else

if(t[m] < x)

d = m-1;

else

g = m+1;

} while(g <= d);

return -1; //on retourne –1 si x n’y est pas

}


On peut aussi écrire cette fonction sous forme récursive :

// recherche de x dans t[g..d[

static int dichoRec(int[] t, int x, int g, int d){

int m;

if(g >= d) // l'intervalle est vide

return -1;

m = (g+d)/2;

if(t[m] == x)

return m;

else if(t[m] > x)

return dichoRec(t, x, g, m);

else

return dichoRec(t, x, m+1, d);

}

static int rechercheDicho(int[] t, int x){

return dichoRec(t, x, 0, t.length);

}




Le nombre maximal de comparaisons à effectuer pour un

tableau de taille n est: T(n) = 1 + T(n/2).

Pour résoudre cette récurrence, on écrit n = 2t, ce qui

conduit à

T(2t) = T(2t-1)+1 = T(2t-2)+2 = … = T(2t-t)+t =T(1)+t

Comme t = log2n, on a: T(2t) = T(n) = c + t = c + log2n

d'où un coût en O(logn).


Exercice sur complexité: tri à bulles

1. Donnez le déroulement de l’algorithme de tri à bulles sur le

tableau des entiers suivants (à trier dans l’ordre croissant):

53 914 230 785 121 350 567 631 11 827 180

2. Quel est le nombre de comparaisons dans cet

algorithme ?

3. Quel est le nombre d’échanges dans le meilleur cas et

dans le pire cas ?

4. Supposons qu’une comparaison a le même coût

d’exécution qu’un échange, c’est à dire une unité de temps,

quelle est la complexité temporelle de cet algorithme (on

considère le pire cas) ?



On commence par la droite car on veut trier dans l’ordre croissant.

N

iter. comp. Nb éch.

pire meil. 53 914 230 785 121 350 567 631 11 827 180

11 53 914 230 785 121 350 567 631 180 827 1 n-1 n-1 0

11 53 121 914 230 785 180 350 567 631 827 2 n-2 . .

11 53 121 180 914 230 785 350 567 631 827 . . .

11 53 121 180 230 914 350 785 567 631 827 . . .

11 53 121 180 230 350 914 567 785 631 827 i n-i

11 53 121 180 230 350 567 914 631 785 827 .

11 53 121 180 230 350 567 631 914 785 827 .

11 53 121 180 230 350 567 631 785 914 827 n-2 2 2

11 53 121 180 230 350 567 631 785 827 914 n-1 1 1 0



12 21

2

1

( 1) ( 2) ... 1 ( ) ( )n

i

n n i n n O n

Le nombre de comparaisons:

Le nombre d’échanges:

- pire cas: tout est dans l’ordre inverse

- meilleur cas: tout est dans l’ordre, 0 échange.

12 21

2

1

( 1) ( 2) ... 1 ( ) ( )n

i

n n i n n O n

- cas moyen: la moitié est dans l’ordre 1

2 21 1 1 1 12 2 2 2 2

1

( 1) ( 2) ... ( ) ( )n

i

n n i n n O n


Tri par fusion: un algorithme à O(nlogn)

Tri par fusion est un exemple typique de diviser pour résoudre

Principe:

-couper en deux le tableau à trier

-trier chacune des deux moitiés

-Interclasser les deux tableaux

Exemple de fusion: int[] t = {3, 5, 7, 3, 4, 6};



static int[] fusionner(int[] tg, int[] td){

int[] f = new int[tg.length + td.length];

int g = 0, d = 0;

for(int k = 0; k < f.length; k++){

// f[k] est la case à remplir

if(g >= tg.length) // g est invalide

f[k] = td[d++];

else if(d >= td.length) // d est invalide

f[k] = tg[g++];

else // g et d sont valides

if(tg[g] <= td[d])

f[k] = tg[g++];

else // tg[g] > td[d]

f[k] = td[d++];

}

return f;

} Nb de comparaisons: O(n)



static int[] triFusion(int[] t){

if(t.length == 1) return t;

int m = t.length / 2;

int[] tg = sousTableau(t, 0, m);

int[] td = sousTableau(t, m, t.length);

// on trie les deux moitiés

tg = triFusion(tg);

td = triFusion(td);

// on fusionne

return fusionner(tg, td);

} // on crée un tableau contenant t[g..d[

static int[] sousTableau(int[] t, int g, int d){

int[] s = new int[d-g];

for(int i = g; i < d; i++)

s[i-g] = t[i];

return s;

}



La complexité spatiale (place mémoire nécessaire): 2n = O(n)

La complexité temporelle: T(n) = 2T(n/2) + n

//correspond au tri de deux tableaux de n/2, plus copie d’un tableau n

Résolution de l’équation récurrente:

-diviser par n: T(n)/n = T(n/2)/(n/2) + 1

-poser n = 2k, on a: 1 2

1 2

(2 ) (2 ) (2 ) (1)1 2 ...

2 2 2 1

k k k

k k k

T T T Tk

-comme k=log2n, on a:

2 2(2 ) ( ) ( 1)2 (log 1) ( log )k kT T n k n n O n n


Séance 3: Structures linéaires (liste)

• Modèles de données les plus élémentaires

• Une séquence non ordonnée d’éléments, accessibles de façon séquentielle s = <e1, e2, …, en>

• Chaque élément a un successeur, sauf le dernier

• Opérations de base: ajout et suppression

• Les structures les plus connues: liste (et ses formes particulières: pile et file)


Les listes

• Liste: une séquence finie d’éléments repérés selon leur

rang (indice)

• Ajout et suppression peuvent se faire à n’importe où dans

la séquence

• Peut être implantée en utilisant un tableau ou une

structure chaînée

- ensemble d’éléments

- longeur()

- ième()

- supprimer()

- ajouter()

• « Vector » est un exemple de listes


Les listes

• Implantation en Java

Public interface Liste{

public int longueur();

public Object ième(int r) throws RangInvalideExcept;

public void supprimer(int r) throws RangInvalideExcept;

public void ajouter(int r Object e) throws RangInvalideExcept;

}

Public class RangInvalideExcept extends RuntimeException {

public RangInvalideExcept(){

super();

}

}


Listes implantées avec tableaux

éléments

lg = 5

5 -13 23 182 100 … …

0 1 2 3 4 éléments.length-1

Algorithme supprimer(r)

pourtout i de r à lg faire

éléments[i-1] = éléments[i]

finpour

lg = lg-1

En utilisant un tableau, l’opération ième() est simple grâce à l’indice

du tableau

Algorithme ajouter(r, e)

pourtout i de lg-1 à r-1 faire

éléments[i+1] = éléments[i]

finpour

éléments[i-1] = e

lg = lg+1

Rmq: la suppression de l’élément de tête est coûteuse à cause du décalage de tous

les éléments temps de calcul long (e.g. cas dans une file d’attente FIFO)


Listes implantées avec tableaux

• Solution: gestion circulaire d’un tableau

– Indice de début et indice de fin de la liste

– Plus besoin du décalage lors de la suppression de l’élément de tête, donc

plus rapide. Demande un peu plus de mémoire (deux indices au lieu d’un)

éléments 23 182 100 20 30

tête queue

éléments 100 20 30

queue tête

23 182

Incrémentation en fin du tableau (suppr en tête ou ajout en queue):

tête = (tête= = éléments.length-1) ? 0 : ++tête

queue = (queue= = éléments.length-1) ? 0 : ++queue

Décrémentation en début du tableau (suppr en queue ou ajout en tête ):

tête = (tête= = 0) ? éléments.length-1 : --tête

queue = (queue= = 0) ? éléments.length-1 : -- queue

Indice r = tête+r-1


Listes implantées avec structures

chaînées

• Liste avec chaînage simple, permet un parcours de tête vers la queue

tête tête

5 20 4 9 45

• Liste avec chaînage double, permet un parcours dans les deux sens

tête

5 20 4 9 45

queue tête queue



chaînées

• Opérations de suppression et d’ajout dans la liste chaînée simple

Nœud de rang r

…

Nœud de rang r

…



chaînées

• Opérations de suppression et d’ajout dans la liste chaînée double

Nœud

de rang r

…

Nœud de rang r

…


Définition d’une liste chaînée en Java

• Une liste chaînée simple est la référence (ou pointeur) d'un noeud, noeud qui contient la donnée et la référence (pointeur) du nœud suivant.

• On définit un nœud de la liste par deux attributs

– La donnée

– La référence du nœud suivant

• On définit alors une liste de façon récursive

class Liste{ int contenu;

Liste suivant;}

Liste

4 12 3 null

@30: 4, @10

@20: 3, @null

@10: 12, @20


Définition d’une liste chaînée en Java

public class Liste{

int contenu;

Liste suivant;

public Liste(int c, Liste suiv){

this.contenu = c;

this.suivant = suiv;

}

public static void main(String[] args){

Liste l; // l = null

l = new Liste(3, null); // l = @20 (1)

l = new Liste(12, l); // l = @10 (2)

l = new Liste(4, l); // l = @30 (3)

}

}


Exemple d’utilisation de listes chaînées

Liste chaînée circulaire : l’élection de Joseph

1 2

3

4

5 6

7

8

9

1 2

3

4

6 7

8

9

…

2

8 8

L’algorithme travaille de la manière suivante.

- méthode de construction d’une liste circulaire

créer un simple nœud pour la personne 1

insérer à la suite les nœuds pour les personnes de 2 à N

- méthode d’élimination de nœuds

tant que il reste plus d’un noeud

parcourir la liste en comptant jusqu’à M-1

supprimer le prochain nœud (en pensant à refermer le cercle)

fin tant que.


Exemple d’utilisation de listes chaînées

public class Noeud {

int val;

Noeud next;

Noeud(int v) { val = v; }

}


public class electionJeseph {

public static void main(String[] args)

{ int N = 9;

int M = 5;

Noeud t = new Noeud(1);

Noeud x = t;

for (int i = 2; i <= N; i++)

x = (x.next = new Noeud(i));

x.next = t;

while (x != x.next)

{

for (int i = 1; i < M; i++) x = x.next;

System.out.println("Le numéro " + x.next.val+" est éliminé" );

x.next = x.next.next;

}

System.out.println("Le survivant est " + x.val);

}

}


Les piles

• Opérations empiler (ajouter) et dépiler

(supprimer) au sommet de la pile

• Structure très utilisée en informatique:

e.g. undo des logiciels, appel des

sous-programmes/fontions/méthodes,

opérations récursives, …

• Peuvent être implantées en utilisant

un tableau, un vecteur, une structure

chaînée

empiler dépiler


Piles implantées avec tableaux

class Pile {

int hauteur;

int[] t;

public Pile (int taille){

t = new int[taille];

hauteur = -1;

}

public boolean estVide(){

return hauteur == -1;

}

public void empiler(int x){

hauteur += 1;

t[hauteur] = x;

}

public int depiler(){

return t[hauteur--];

}

}


Piles implantées avec tableaux

• Un petit programme de test pourra être:

class TesterPile{


Pile p = new Pile(10);

int x;

p.empiler(1);

p.empiler(2);

x = p.depiler();

System.out.println(x);

}

}

Exercice: proposez une pile implémentée avec la liste chaînée


Piles: quelques détails d’implantation

• En utilisant un tableau. Pb: dimension fixe

• En utilisant une structure dynamique (cf. doc de java dans java.util.*): – Vector

– Stack qui « extends Vector »

– LinkedList

• Ces classes ne peuvent pas contenir des types élémentaires (ou primitifs), il faut alors définir sa propre classe d’objets. Exemple, une pile des int n’est pas possible, il faut redéfinir int par une classe entier: class entier {int n;

public entier(int x){n=x}

}


Les Files d’attente

• La forme la plus utilisée est FIFO (premier arrivée, premier sortie). Suppression en tête, ajout en queue

• Peuvent être implantées en utilisant un tableau, un vecteur, ou une structure chaînée

• Un exemple d’implantation avec un tableau

ajout suppression


Files implantées avec tableaux

class Queue{

int fin;

int[] t;

public Queue(int taille){

t = new int[taille];

fin = 0;

}

}

public boolean estVide(){

return fin == 0;

}



public boolean ajouter(int i){

if(fin >= t.length)

return false;

t[fin] = i;

fin += 1;

return true;

}

public void servirClient(){

if(!estVide()){

System.out.println("Je sers le client "+t[0]);

for(int i = 1; i < fin; i++)

t[i-1] = t[i];

fin -= 1;

}

}



• Un programme d’essai pourra être:

class Poste{

static final int TMAX = 100;


Queue q = new Queue(TMAX);

q.ajouter(1);

q.ajouter(2);

q.servirClient();

q.servirClient();

q.servirClient(); }

}

Exercice: implanter une file avec

(1) un tableau circulaire,

(2) une liste chaînée.


Tableau circulaire

éléments 23 182 100 20 30

debut fin

éléments 23 182 100 20 30

debut fin Après 2 clients servis:

éléments 100 20 30

debut

Après 2 clients arrivés:

1 2

fin


Séance 4: Graphes

Un graphe (orienté) G(V,E) est un ensemble de sommets V (vertices) reliés par des arcs E (Edges), avec a=(x,y) E qui possède une extrémité initiale x V et une extrémité finale y V. Si x=y, l’arc est appelé une boucle.

Si les relations entre les sommets sont symétriques, on peut avoir un graphe non orienté. On parle alors des arêtes au lieu des arcs.

Il est possible d’ajouter des informations sur les sommets pour les identifier, ou sur les arcs pour les pondérer. Un graphe dont les arcs (ou arêtes) portent des valuations est appelé graphe valué.

s1

s2

s9

s4 s3

s5 s6

s7 s8


Graphes: terminologie

• Un chemin est une liste de sommets dans lequel deux sommets

successifs sont reliés par un arc. La longueur d’un chemin est égale au

nombre d’arcs. Un chemin ne rencontrant pas deux fois le même

sommet est dit élémentaire. Un cycle est un chemin dont le premier

sommet et le dernier sommet sont identique

• Un graphe est dit connexe s’il existe un chemin reliant toute paire de

sommets. (Dans l’exemple de graphe précédent, il existe deux

composantes connexes)

• Un graphe est dit creux s’il existe peu d’arcs (ou arêtes) et dense dans

le cas contraire

• Un graphe simple est un graphe sans boucle, ni arc multiple. Le

nombre d’arcs d’un graphe simple à n sommets est compris entre 0 et

n(n-1), et n(n-1)/2 si le graphe est non orienté

• Deux arcs sont dits adjacents s’ils ont au moins un sommet commun


Graphes: représentation avec une

matrice d’adjacence (un tableau)

s1 s2 s3 s4 s5 s6 s7 s8 s9

s1 0 1 0 1 0 0 0 0 1

s2 0 0 0 0 0 0 0 0 0

s3 0 0 0 1 0 0 0 0 0

s4 0 0 1 0 0 1 0 0 0

s5 0 0 0 1 0 0 0 0 0

s6 0 0 0 0 1 0 0 0 0

s7 0 0 0 0 0 0 0 1 0

s8 0 0 0 0 0 0 0 1 0

s9 0 0 0 0 0 0 0 0 0

Elle a une complexité spatiale (espace mémoire) de n2

s1

s2 s9

s4 s3

s5 s6


Graphes: représentation avec une liste

d’adjacence (tableau de listes chaînées)

s1 s2 s3 s4 s5 s6 s7 s8 s9

s2

s4

s9

s4 s3 s4 s5 s8 s8

s6

Pour un graphe de n sommets et p arcs,

cette représentation a une complexité spatiale (espace mémoire)

de n+p si le graphe est orienté, et n+2p si le graphe est non

orienté

Elle est intéressante pour un graphe creux (p<<n) en terme de

besoin en mémoire

s1

s2 s9

s4 s3

s5 s6


Implantation en Java avec un tableau

import utilensemjava.*;

public class AdjacencyMatrix {


int V = Lecture.lireEntier("nombre de sommets =? ");

int E = Lecture.lireEntier("nombre d'arêtes =? ");

boolean adj[][] = new boolean[V][V];

for (int i = 0; i < V; i++)

for (int j = 0; j < V; j++)

adj[i][j] = false;

for (int i = 0; i < V; i++) adj[i][i] = true;

System.out.println("saisir les arêtes");

for (int k=0; k<E; k++){

int i = Lecture.lireEntier("sommet 1 du "+k+ arête =? ");

int j = Lecture.lireEntier("sommet 2 du "+k+" arête =? ");

adj[i][j] = true; adj[j][i] = true;

}

} 0 1

2 3


Implantation en Java avec un tableau

0 1

2 3 0 1 2 3

0 true true true true

1 true true true false

2 true true true true

3 true false true true

a0

a1

a2

a3 a4


Implantation avec une liste chaînée

public class AdjacencyLists {

static class Node {

int v; Node next;

Node (int v, Node t)

{ this.v = v; next = t; }

}

public static void main(String[] args)

{ int V = Lecture.lireEntier("nombre de sommets =? ");

int E = Lecture.lireEntier("nombre d'arêtes =? ");

Node adj[] = new Node[V];

for (int i = 0; i < V; i++) adj[i] = null;

for (int k=0; k<E; k++){

int i = Lecture.lireEntier("sommet 1 du "+k+" arête =? ");

int j = Lecture.lireEntier("sommet 2 du "+k+" arête =? ");

adj[j] = new Node(i, adj[j]);

adj[i] = new Node(j, adj[i]);

}

}

Voir un exemple plus loin


Algorithmes de parcours de graphes

• Deux méthodes: recherches en-profondeur-d’abord et en-

largeur-d’abord

• Exemple d’un graphe non orienté:

0

1 7

2

5

3

4

6 0

1

2

3

4

5

6

7

7 5 2 1 6

7 0

7 0

5 4

6 5 7 3

0 4 3

1 2 0 4

4 0


Algorithmes de parcours de graphes

• Recherche en-profondeur-d’abord (depth-first search)

Démarrer à un nœud v

• passer par v;

• Passer (récursivement) par chaque nœud

attaché à v (par lequel nous ne sommes pas

déjà passés)

• Si le graphe est connexe, on atteint tous

les nœuds


Algorithmes de parcours

de graphes

Arbre de recherche

en-profondeur-d’abord

0

7

1 2 4

3

6 5

0

1

2

3

4

5

6

7

7 5 2 1 6

7 0

7 0

5 4

6 5 7 3

0 4 3

1 2 0 4

4 0

0

1 7

2

5

3

4

6


0

1 7

2

5

3

4

6

En-profondeur-d’abord

0

1 7

2

5

3

4

6

En-largeur-d’abord

0

1

2

3

4

5

6

7

7 5 2 1 6

7 0

7 0

5 4

6 5 7 3

0 4 3

1 2 0 4

4 0


Graphes: application

• Problème de recherche du plus court chemin dans un graphe

• Solution de Dijkstra (algorithme de Dijkstra [1959])

• Exemple d’un graphe valué

S0 S1

S2

S4 S3

S5

1

7

2

1 10 8

4

2

s: source

x = (sx, dx)

où

dx =min(tous les chemins)

On note: dx= si pas de chemin entre s et sx

dx=0 si x=s

L’ensemble solution S pour source s=s0: S = {(s0,0), (s1,1), (s2,4), (s3,6),(s4,2), (s5, )}



• Algorithme de Dijkstra (condition: valeur des arcs >= 0)

aussi connu sous SPF (Shortest Path First)

Construire l’ensemble S de façon itérative:

Au début:

dx= si pas de chemin entre s et sx

dx=0 si sx=s

S =

D = {(s0,0), (s1, ), (s2, ), (s3, ),(s4, ), (s5, )}

A chaque itération:

m = (sm,dm) D, t.q. x D, dm=min(dx)

m est alors retiré de l’ensemble D et ajouté dans S

(Affirmation: dm est le plus court chemin entre s et sm)

S0 S1

S2

S4 S3

S5

1

7

2

1 10 8

4

2


Graphes: application Ensuite, on calcule dx de chaque x D qui possède un arc avec sm :

Si dm + valeurArc(sm,sx) < dx alors

dx = dm + valeurArc(sm,sx)

Finsi

Où valeurArc(sm,sx) est la valeur de l’arc entre sm et sx

A la dernière itération, D= et S contient la solution.

Exemple:

S D

{(s0,0)}

{(s0,0), (s1,1)}

{(s0,0), (s1,1), (s4,2)}

{(s0,0), (s1,1), (s4,2), (s2, 4)}

{(s0,0), (s1,1), (s4,2), (s2, 4), (s3,6)}

{(s0,0), (s1,1), (s4,2), (s2, 4), (s3,6), (s5, )}

{(s1,1), (s2, ), (s3,10), (s4, ), (s5, )}

{(s2, 8), (s3,9), (s4, 2), (s5, )}

{(s2, 4), (s3,6), (s5, )}

{(s3,6), (s5, )}

{(s5, )}

S0 S1

S2

S4 S3

S5

1

7

2

1 10 8

4

2



• Peut être représenté par un tableau

Source dest valeur

S0 S1 1

S0 S3 10

S1 S2 7

S1 S3 8

S1 S4 1

S4 S2 2

S4 S3 4

S5 S3 2

S0 S1

S2

S4 S3

S5

1

7

2

1 10 8

4

2



• Représenté par un tableau de listes chaînées

S0 S1

S2

S4 S3

S5

1

7

2

1 10 8

4

2

•Tab[i] pointe vers la liste des sommets directement connectés au sommet « si »

•Pour simplifier, un sommet est codé par un entier, avec i = si

s1 1 s3 10 null

s2 7 s3 8

s2 2 s3 4 null

s3 2 null

0

1

2

3

4

5

s4 1 null

null

null



• Représenté par un tableau de listes chaînées

public class GrapheParListe {

public Liste adj[ ]; //un tableau de listes chaînées

//constructeur

GrapheParListe(int nb_sommets, int nb_arcs){

adj = new Liste[nb_sommets];

for (int i = 0; i < nb_sommets; i++) adj[i] = null;

//on saisie les arcs par sommet du départ

for (int k=0; k<nb_arcs; k++) {

int i = Lecture.lireEntier(

"sommet sortant du "+(k+1)+"ème arc (0-"+(nb_sommets-1)+")=? ");

int j = Lecture.lireEntier(

"sommet d'arrivée du "+(k+1)+"ème arc (0-"+(nb_sommets-1)+")=? ");

int val=Lecture.lireEntier("valeur du "+(k+1)+"ème arc =? ");

adj[i] = new Liste(j, adj[i], val);

}

}



• listes chaînées public class Liste {

int num_noeud; //pour représenter le numéro d'un sommet

int valeur; //pour représneter la valuer de l'arc

Liste suivant;

Liste (int n, Liste t, int v) {

num_noeud = n;

suivant = t;

valeur=v;

}

}

Exercice sur liste chaînée:

Que donne schématiquement la liste après l’exécution de: Liste a = new Liste(2, new Liste(7, new Liste(11, null, 1), 2),3)



• Les éléments dans les deux ensembles D et S

peuvent être représentés par une classe

public class Element { //(sx,dx)

int sommet; //on code le numéro d'un sommet par un entier

int distance; //distance vers le sommet source

Element(int s, int d){

sommet=s;

distance=d;

}

}

Un tel élément peut être stocké soit dans une liste chaînée, soit dans un Vector



Attribut:

- Liste adj[ ]

Méthodes

- constructeur

- void afficher()

- boolean arc (int source, int dest)

{//parcourt de la liste chaînée}

- int valeurArc(int source, int dest)

- Vector plusCourtChemin(int num_sommet)

{Algo. Dijkstra}

Graphe

Liste Element

Vector - int num_noeud

- int valeur

- Liste suivant

- int sommet

- int distance



• Parcourir une liste chaînée

public boolean arc (int source, int dest){

boolean arcExiste=false;

if (adj[source]!=null) {

Liste a = adj[source];

while (a != null) {

if (a.num_noeud == dest) arcExiste = true;

if (arcExiste) a=null;

else a = a.suivant;

}

}

return arcExiste;

}


Les structures arborescentes

• Un arbre est une forme particulière

d’un graphe

• Les structures arborescentes sont

largement utilisées en informatique:

système d’organisation de fichiers

dans un disque, …

• En informatique, on s’intéresse à

des formes particulières d’un arbre

de plus en plus contraintes: arbre

libre, arbre enraciné, arbre ordonné,

arbre binaire, arbre équilibré, …

+

2 x

b a

a x b + 2


Arbres libres

Un arbre libre G(S,A) est un graphe non orienté, non vide,

connexe et sans cycle (ou circuit)

Propriétés: -Deux nœuds quelconques de S sont connectés par un chemin simple unique,

-G est connexe, mais ne l’est plus si l’on retire une arête quelconque,

-G est sans circuit, mais ne l’est plus si l’on ajoute une arête quelconque,

-G est connexe, et Card(A) = Card(S) – 1,

-G est sans cycle, et Card(A) = Card(S) – 1


Arbres enracinés

Un arbre enraciné ou arbre (rooted tree) est un arbre libre

muni d’un nœud distingué, appelé racine. 1

2 3 4

5 6 7 8 9

Soit T un arbre de racine r.

Pour tout nœud x il existe un chemin simple unique

de r à x.

Tout nœud y sur ce chemin est un ancêtre de x, et

x est un descendant de y.

Le sous-arbre de racine x est l’arbre contenant

tous les descendant de x.

L’avant-dernier nœud y sur l’unique chemin reliant

r à x est le parent de x, et x est un enfant de y.

L’arité d’un nœud est le nombre de ses enfants.

Un nœud sans enfant est une feuille, un nœud

d’arité >0 est appelé nœud interne.

La hauteur d’un arbre T est la longueur maximale

d’un chemin reliant sa racine à une feuille.

Un arbre réduit à une seul nœud est de hauteur 0.


Arbres enracinés

1

2 3 4

5 6 7 8 9

Les arbres admettent une définition récursive: un arbre sur un ensemble

fini de nœuds est un couple formé de sa racine et d’une partition des

nœuds restants en un ensemble d’arbres.

Exemple de l’arbre ci-contre:

T = (1, {(2, {(5), (6)}), (3, {(7), (8), (9)}), (4)})

Une forêt est un ensemble d’arbres


Arbres ordonnés

Un arbre ordonné est un arbre dans lequel l’ensemble des enfants de

chaque nœud est totalement ordonné.

1 2 3

1.1 1.2 2.1 2.2 2.3

1.2.1 1.2.2


Arbres binaires

Un arbre binaire est un arbre qui possède au plus deux fils, un sous-

arbre gauche, et un sous-arbre droit.

Un arbre binaire non vide est représenté sous forme d’un triplet:

A = (Ag, r, Ad).

Exemple: les deux arbres binaires suivants sont différents

1

2

3

1

2

3

(, 1, ((, 3, ), 2, )) ((, 2, (, 3, )), 1, )


Arbres binaires Propriété: Soit A un arbre binaire à n nœuds, de hauteur h. Alors h+1 log2(n+1).

Exercice: prouver cette propriété.

Cette propriété permet de déterminer la complexité de la plupart des

algorithmes sur les arbres binaires: entre O(log2n) et O(n). Preuve: n-1+1 h+1 log2(n+1) n-1 h log2(n+1) -1 et le nombre

d’opérations est souvent h.

Arbre équilibré: Comme la complexité dépend de la hauteur h, et au

pire cas = n-1, il est toujours intéressant de structurer les données avec

un arbre « équilibré » afin d’avoir h proche de la moyenne.

Par exemple, un arbre binaire équilibré AVL (Adel’son-Velskii et Landis

1962) a pour tout nœud, les hauteurs des sous-arbres gauche et droit

diffèrent d’au plus 1. Sa hauteur est donc bornée par:

Il existe d’autres familles d’arbres équilibrés: 2-3, rouge et noir, ... 2 2log ( 1) 1 log ( 2), avec 1,44n h n


Arbres: application public class tournoi {

static class Node

{ double val; Node l; Node r;

Node(double v, Node l, Node r)

{ this.val = v; this.l = l; this.r = r; }

}

public static void main(String[] args) {

double[] tab={1, 3, 5, 4, 2, 6, 9, 7};

System.out.println(max(tab, 0, 7).val);

}

static Node max(double a[], int l, int r) {

int m = (l+r)/2;

Node x = new Node(a[m], null, null);

if (l == r) return x;

x.l = max(a, l, m);

x.r = max(a, m+1, r);

double u = x.l.val, v = x.r.val;

if (u > v) x.val = u; else x.val = v;

return x;

}

}


Arbres: parcours

• Préfixe

• Infixe

• Postfixe


Type abstrait de données et Résumé

sur la récursivité de définition

• Type abstrait de données

• Structure récursive

– Nœud

– Liste

– Arbre

• Algorithmes récursifs pour le parcours des

structures

Exo moyenne classe S2_1 09/10


1 3 null

2 3

2 3 null

3 null

0

1

2

3

4

5

4 null

null

null

S0 S1

S2

S4 S3

S5

1

7

2

1 10 8

4

2

Documents

Module Informatique 2 - LORIA · cours d’algo. et prog. par Y.Q. Song 12 Correction d’un algorithme récursif • Preuve de la correction – Terminaison (l’algorithme se termine)