42
Cours d'algorithmique 1 - Cours d'algorithmique 1 - Intranet Intranet 1 6 novembre 2006 6 novembre 2006 Cours d’Algorithmique Cours d’Algorithmique Marc Gengler Marc Gengler [email protected] [email protected] mrs.fr mrs.fr Alexandra Bac - Henry Kanoui - Alain Alexandra Bac - Henry Kanoui - Alain Samuel Samuel 24h de cours 24h de cours 24h de TD 24h de TD des devoirs des devoirs un projet un projet et un et un examen examen

Cours Algo 1 Resume

Embed Size (px)

DESCRIPTION

introduction a l algorithmique commencer a comprendre

Citation preview

Page 1: Cours Algo 1   Resume

Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 116 novembre 20066 novembre 2006

Cours d’AlgorithmiqueCours d’AlgorithmiqueMarc GenglerMarc Gengler

[email protected]@esil.univ-mrs.fr

Alexandra Bac - Henry Kanoui - Alain SamuelAlexandra Bac - Henry Kanoui - Alain Samuel

24h de cours24h de cours24h de TD24h de TDdes devoirsdes devoirsun projetun projet… … et un et un examenexamen

Page 2: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 22

• Trier et chercherTrier et chercher• Listes et arbresListes et arbres• Le back-trackLe back-track• Arbres équilibrésArbres équilibrés• Récursivité et induction sur la structureRécursivité et induction sur la structure• Divide and conquerDivide and conquer• MinimaxMinimax• DérécursionDérécursion• Divers problèmes particuliersDivers problèmes particuliers• Logique de HoareLogique de Hoare• Programmation dynamiqueProgrammation dynamique• Complexité et calculabilitéComplexité et calculabilité

Les grandes lignes du coursLes grandes lignes du cours

Page 3: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 33

BibliographieBibliographie

• Tout ce qui contientTout ce qui contient– algorithmes, algorithms.algorithmes, algorithms.

• InternetInternet– souvent, c’est très (trop) simplifié,souvent, c’est très (trop) simplifié,– et pas toujours correct.et pas toujours correct.

• Mes choixMes choix– Introduction to Algorithms, Leiserson et al.Introduction to Algorithms, Leiserson et al.– Algorithms, Sedgewick.Algorithms, Sedgewick.– Fundamental Algorithms, Knuth.Fundamental Algorithms, Knuth.– des anciens cours ;-)des anciens cours ;-)

• D’autres choixD’autres choix– Introduction à l’algorithmique, Leiserson et al.Introduction à l’algorithmique, Leiserson et al. chez Dunod.chez Dunod.– Initiation à l’algorithmique et aux structures de données, Initiation à l’algorithmique et aux structures de données,

Courtin et Kowarski.Courtin et Kowarski.

Page 4: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 44

Al KhwarizmiAl Khwarizmi

• Célèbre mathématicien à Bagdad,Célèbre mathématicien à Bagdad,

vers 780-850.vers 780-850.

• « Kitâb « Kitâb al-jabral-jabr wa al-muqâbala ». Livre sur la science de la wa al-muqâbala ». Livre sur la science de la transposition et de la réduction : résolution systématique de transposition et de la réduction : résolution systématique de l’équation du second degré.l’équation du second degré.

• Traduit en latin au 12Traduit en latin au 12ee siècle par Gherardo di Cremona sous le siècle par Gherardo di Cremona sous le titre titre « « Dixit Dixit AlgorismiAlgorismi ». ».

• Aussi : « Kitâb al Jami wa al Tafriq bi Hisab al Hind ». Livre de Aussi : « Kitâb al Jami wa al Tafriq bi Hisab al Hind ». Livre de l'addition et de la soustraction d'après le calcul des indiens.l'addition et de la soustraction d'après le calcul des indiens.

• http ://trucsmaths.free.fr/alkhwarizmi.htmhttp ://trucsmaths.free.fr/alkhwarizmi.htm

• http://publimath.irem.univ-mrs.fr/glossaire/AL016.htmhttp://publimath.irem.univ-mrs.fr/glossaire/AL016.htm

Page 5: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 55

Al KhwarizmiAl Khwarizmi

1616 + + X^2 X^2 + + 8 * X8 * X = 33 + = 33 + 1616

X^2X^2

2 * X2 * X44

( X + 4 )^2 = 7^2( X + 4 )^2 = 7^2

Page 6: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 66

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

• Tableau d’entrées 0 à n-1.Tableau d’entrées 0 à n-1.• Entiers naturels, mais n’importe quel Entiers naturels, mais n’importe quel

ensemble ordonné peut convenir.ensemble ordonné peut convenir.• Les répétitions sont possibles.Les répétitions sont possibles.

Les hypothèses :Les hypothèses :

Le but :Le but :

• Ordonner le tableau par valeurs non Ordonner le tableau par valeurs non décroissantes.décroissantes.

Page 7: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 77

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

• En général, l’ordre est imposé par le monde En général, l’ordre est imposé par le monde extérieur.extérieur.

• Je peux trier des personnes :Je peux trier des personnes :

– d’après l’âge,d’après l’âge,– d’après le poids,d’après le poids,– d’après la taille,d’après la taille,– d’après l’ordre lexicographique des patronymes,d’après l’ordre lexicographique des patronymes,– . . .. . .

Quelle relation d’ordre ?Quelle relation d’ordre ?

Page 8: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 88

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Situation initialeSituation initiale

ValeursValeurs

0 1 2 3 …0 1 2 3 … n-n-11

Page 9: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 99

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Situation finaleSituation finale

ValeursValeurs

0 1 2 3 …0 1 2 3 … n-n-11

Page 10: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 1010

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par échange --- situation intermédiaireTri par échange --- situation intermédiaire

ValeursValeurs

0 1 2 3 …0 1 2 3 … n-n-11

TriéesTriées

Non triées etNon triées etplus grandesplus grandes

i-1i-1

Page 11: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 1111

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par échange - suiteTri par échange - suite

• Les entrées de 0 à i-1 sont triées.Les entrées de 0 à i-1 sont triées.

• Elles sont plus petites que les entrées suivantes.Elles sont plus petites que les entrées suivantes.

• Les entrées à partir de l’indice i ne sont pas triées.Les entrées à partir de l’indice i ne sont pas triées.

Les hypothèses Les hypothèses ::

A faire pour mettre en place l’entrée i :A faire pour mettre en place l’entrée i :

• Chercher l’indice j du minimum à partir de i.Chercher l’indice j du minimum à partir de i.

• Echanger les éléments i et j.Echanger les éléments i et j.

Page 12: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 1212

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par échange --- situation intermédiaireTri par échange --- situation intermédiaire

ValeursValeurs

0 1 2 3 …0 1 2 3 … n-n-11

TriéesTriées

Non triées etNon triées etplus grandesplus grandes

ii jj

<- échange -<- échange ->>

Page 13: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 1313

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par échange --- situation intermédiaireTri par échange --- situation intermédiaire

ValeursValeurs

0 1 2 3 …0 1 2 3 … n-n-11

TriéesTriées

Non triées etNon triées etplus grandesplus grandes

ii jj

Page 14: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 1414

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par échange --- propriété invarianteTri par échange --- propriété invariante

• Nous avions une certaine situation sur l’intervalle [ 0 .. i-1 ] :Nous avions une certaine situation sur l’intervalle [ 0 .. i-1 ] :– les éléments jusqu’à i-1 sont triés,les éléments jusqu’à i-1 sont triés,– ceux qui suivent sont plus grands, mais pas triés.ceux qui suivent sont plus grands, mais pas triés.

• Nous retrouvons la même situation sur l’intervalle [ 0 .. i ] :Nous retrouvons la même situation sur l’intervalle [ 0 .. i ] :– les éléments jusqu’à i sont triés,les éléments jusqu’à i sont triés,– ceux qui suivent sont plus grands, mais pas triés.ceux qui suivent sont plus grands, mais pas triés.

• Cette propriété est donc invariante avec i, on l’appelleCette propriété est donc invariante avec i, on l’appelle

Page 15: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 1515

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par échange --- le codeTri par échange --- le code

for ( i=0 ; i<n-1 ; i++ )

{ind_min = i;

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

if ( t[j] < t[ind_min] )

ind_min = j;

aux = t[i];

t[i] = t[ind_min];

t[ind_min] = aux;

}

Page 16: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 1616

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par échange --- la complexitéTri par échange --- la complexité

• Ont fait n-1 fois, pour i de 0 à n-2 :Ont fait n-1 fois, pour i de 0 à n-2 :

• Un parcours de [i..n-1].Un parcours de [i..n-1].

• Il y a donc un nombre de lectures qui vaut :Il y a donc un nombre de lectures qui vaut :

(n-i) = 0 (n-i) = 0 (n^2)(n^2)i=0..n-2i=0..n-2

Tri en complexité quadratique.Tri en complexité quadratique.

Page 17: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 1717

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par insertion --- situation intermédiaireTri par insertion --- situation intermédiaire

ValeursValeurs

0 1 2 3 …0 1 2 3 … n-n-11

TriéesTriées

Non triées etNon triées etquelconquesquelconques

i-1i-1

Page 18: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 1818

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par insertion - suiteTri par insertion - suite

• Les entrées de 0 à i-1 sont triées.Les entrées de 0 à i-1 sont triées.

• Elles sont plus petites que les entrées suivantes.Elles sont plus petites que les entrées suivantes.

• Les entrées à partir de l’indice i ne sont pas triées.Les entrées à partir de l’indice i ne sont pas triées.

Les hypothèses Les hypothèses ::

A faire pour mettre en place l’entrée i :A faire pour mettre en place l’entrée i :

• Si elle est plus grande que les précédentes : RIEN !Si elle est plus grande que les précédentes : RIEN !

• Si elle est plus petite que certaines précédentes : Si elle est plus petite que certaines précédentes : l’insérer plus à gauche en décalant d’autres entrées.l’insérer plus à gauche en décalant d’autres entrées.

////////////////////////////////////////////

Page 19: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 1919

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par insertion --- situation intermédiaireTri par insertion --- situation intermédiaire

ValeursValeurs

0 1 2 3 …0 1 2 3 … n-n-11

TriéesTriées

i-1i-1

Plus Plus grande :grande :Rien à Rien à faire !faire !

Non triées etNon triées etquelconquesquelconques

Page 20: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 2020

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par insertion --- situation intermédiaireTri par insertion --- situation intermédiaire

ValeursValeurs

0 1 2 3 …0 1 2 3 … n-n-11

TriéesTriées

i-1i-1

Non triées etNon triées etquelconquesquelconques

Plus petit :Plus petit :L’insérer à L’insérer à gauche.gauche.

Page 21: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 2121

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par insertion --- situation intermédiaireTri par insertion --- situation intermédiaire

• Vous avez vu qu’il y a à nouveau un INVARIANT ?Vous avez vu qu’il y a à nouveau un INVARIANT ?

• Lequel est-ce ??????????????????Lequel est-ce ??????????????????

• Les éléments déjà traités sont triés,Les éléments déjà traités sont triés,

• les autres sont dans le désordre et sans les autres sont dans le désordre et sans rapport particulier (ni plus grands, ni plus rapport particulier (ni plus grands, ni plus petits) aux premiers.petits) aux premiers.

Page 22: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 2222

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par insertion --- le codeTri par insertion --- le code

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

{cont = 1;

j = i;

while ( j>0 && cont )

{if ( t[j] < t[j-1] )

echange(t, j-1, j);

else

cont = 0;

j--; } }

Page 23: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 2323

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri par insertion --- la complexitéTri par insertion --- la complexité

• Ont fait n-1 fois, pour i de 1 à n-1 :Ont fait n-1 fois, pour i de 1 à n-1 :

• Jusqu’à i échanges au maximum (peut-être moins).Jusqu’à i échanges au maximum (peut-être moins).

• Le nombre d’échanges peut donc atteindre :Le nombre d’échanges peut donc atteindre :

i = 0 i = 0 (n^2)(n^2)i=1..n-1i=1..n-1

Tri en complexité quadratique.Tri en complexité quadratique.

Page 24: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 2424

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri bulleTri bulle

ValeursValeurs

0 1 2 3 …0 1 2 3 … n-n-11

SituationSituationnormalenormale

SituationSituationanormale :anormale :Une bulleUne bulle

Page 25: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 2525

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri bulle : on échange l’ordre dans la bulleTri bulle : on échange l’ordre dans la bulle

ValeursValeurs

0 1 2 3 …0 1 2 3 … n-n-11

SituationSituationnormalenormale

La bulleLa bullea disparua disparupar échangepar échange

Page 26: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 2626

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri bulle : évolution des bullesTri bulle : évolution des bulles

ValeursValeurs

0 1 2 3 …0 1 2 3 … n-n-11

Régions qui peuventRégions qui peuventêtre ignorées lorsêtre ignorées lorsdu prochain passage.du prochain passage.

Page 27: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 2727

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri bulle - principe des Tri bulle - principe des algorithmesalgorithmes

• Tant qu’il y a des bulles,Tant qu’il y a des bulles,

• on en choisit une et on la fait monter.on en choisit une et on la fait monter.

L’idée :L’idée :

De nombreuses optimisations :De nombreuses optimisations :

• Suivre une bulle et la faire monter aussi haut que possible.Suivre une bulle et la faire monter aussi haut que possible.

• Si au dernier passage la première bulle était ( i , i+1 ) , il ne Si au dernier passage la première bulle était ( i , i+1 ) , il ne peut y avoir de bulle avant ( i-1 , i ) au passage courant.peut y avoir de bulle avant ( i-1 , i ) au passage courant.

• Faire alternativement monter et descendre des bulles.Faire alternativement monter et descendre des bulles.

• … … et puis d’autres trucs !et puis d’autres trucs !

Page 28: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 2828

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Tri bulle - complexitéTri bulle - complexité

• Le tri bulle a une complexité quadratique, car il existe des Le tri bulle a une complexité quadratique, car il existe des instances pour lesquels il faut 0 (n^2) échanges.instances pour lesquels il faut 0 (n^2) échanges.

• Par contre, pour de nombreuses instances, le nombre des Par contre, pour de nombreuses instances, le nombre des échanges est bien plus petit.échanges est bien plus petit.

• Le tri bulle est bien adapté, comme d’autres tris, pour Le tri bulle est bien adapté, comme d’autres tris, pour rétablir l’ordre dans un tableau presque trié (léger désordre rétablir l’ordre dans un tableau presque trié (léger désordre produit par quelques insertions d’éléments par exemple).produit par quelques insertions d’éléments par exemple).

Page 29: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 2929

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Différentes notions de complexitéDifférentes notions de complexité

• Complexité du meilleur cas :Complexité du meilleur cas :– inintéressante, car ce n’est pas le cas typique.inintéressante, car ce n’est pas le cas typique.

• Complexité du cas moyen :Complexité du cas moyen :– intéressante, mais difficile à établir,intéressante, mais difficile à établir,– est-ce que mes instances du problème sont dans la moyenne ?est-ce que mes instances du problème sont dans la moyenne ?

• Complexité du pire cas :Complexité du pire cas :– donne une limite supérieure pour le nombre d’opérations,donne une limite supérieure pour le nombre d’opérations,– celle-ci peut être atypique,celle-ci peut être atypique,– souvent assez facile à calculer,souvent assez facile à calculer,– mais, c’est la COMPLEXITE utilisée PAR DEFAUT.mais, c’est la COMPLEXITE utilisée PAR DEFAUT.

Page 30: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 3030

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Principe du tri par fusionPrincipe du tri par fusion

• Couper le tableau en deux (mentalement et de Couper le tableau en deux (mentalement et de façon non violente),façon non violente),

• trier récursivement chaque partietrier récursivement chaque partie

• et fusionner les deux parties triées (cf. cours et fusionner les deux parties triées (cf. cours d’Introduction à la programmation).d’Introduction à la programmation).

Page 31: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 3131

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Principe du tri par fusionPrincipe du tri par fusion

Tri récursifTri récursifdes deuxdes deuxmoitiés.moitiés.

Fusion desFusion desdeux suites.deux suites.

Page 32: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 3232

Les tris sur tableauxLes tris sur tableaux----------------------------------------------------------------------------------------------------------------------------------

Complexité du tri par fusionComplexité du tri par fusion• Soit f(n) la fonction de complexité pour trier n éléments.Soit f(n) la fonction de complexité pour trier n éléments.

• Le découpage se fait en temps constant ou 0( n ), s’il y a copie.Le découpage se fait en temps constant ou 0( n ), s’il y a copie.

• Les deux appels récursifs nécessitent 2 * f( n/2 ).Les deux appels récursifs nécessitent 2 * f( n/2 ).

• La fusion se fait en 0( n ).La fusion se fait en 0( n ).

• Donc f(n) = 0(n) + 2 * f(n/2)Donc f(n) = 0(n) + 2 * f(n/2)

= 0(n) + 2 * ( 0(n/2) + 2 * f(n/4) )= 0(n) + 2 * ( 0(n/2) + 2 * f(n/4) )

= 2 * 0(n) + 2^2 * f(n/2^2)= 2 * 0(n) + 2^2 * f(n/2^2)

= 3 * 0(n) + 2^3 * f(n/(2^3))= 3 * 0(n) + 2^3 * f(n/(2^3))

= k * O(n) + 2^k * f(n/(2^k))= k * O(n) + 2^k * f(n/(2^k))

= 0(n * log n) + 2^(log n) * f(n/(2^(log n)))= 0(n * log n) + 2^(log n) * f(n/(2^(log n)))

= 0(n * log n) car f(n/(2^(log n))) = f(1) = 0= 0(n * log n) car f(n/(2^(log n))) = f(1) = 0

Tri en complexité n log n.Tri en complexité n log n.

Page 33: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 3333

Recherche dans des tableaux triésRecherche dans des tableaux triés----------------------------------------------------------------------------------------------------------------------------------

• On utilise l’ordre pourOn utilise l’ordre pour– anticiper l’abandon dans une recherche linéaire,anticiper l’abandon dans une recherche linéaire,– guider la recherche : recherche par dichotomie.guider la recherche : recherche par dichotomie.

petipetitt

grandgrandmoyenmoyen

00 n-1n-1(n-1)/2(n-1)/2

XX

X < moyenX < moyenOui !Oui !

Chercher X dansChercher X dans[ 0 .. (n-1)/2- 1 ][ 0 .. (n-1)/2- 1 ]

Non !Non !Chercher X dansChercher X dans[ (n-1)/2 .. n-1 ][ (n-1)/2 .. n-1 ]

Page 34: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 3434

Recherche dans des tableaux triésRecherche dans des tableaux triés----------------------------------------------------------------------------------------------------------------------------------

Recherche par dichotomie - Recherche par dichotomie - complexitécomplexité

• 1 test -> n/2 éléments.1 test -> n/2 éléments.

• 2 tests -> n/4 éléments.2 tests -> n/4 éléments.

• 0( log n) tests -> 1 élément.0( log n) tests -> 1 élément.

• Est-ce bien lui ? Donc un test en plus.Est-ce bien lui ? Donc un test en plus.

• Il existe des arguments théoriques (théorie de Il existe des arguments théoriques (théorie de l’information) qui montrent que l’on ne peut l’information) qui montrent que l’on ne peut pas faire mieux.pas faire mieux.

Page 35: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 3535

Recherche dans des tableaux triésRecherche dans des tableaux triés----------------------------------------------------------------------------------------------------------------------------------

d = 0;

f = n-1;

While ( d < f )

if ( d == f-1 )

if ( x == t[d] )

f = d;

else

d = f;

else

{m = (d+f)/2;

if ( x < t[m] )

f = m-1;

else

d = m; }

Return ( x == t[d] ); Résultat.Résultat.

Cas général.Cas général.

Intervalle de 2 éléments.Intervalle de 2 éléments.

Initialisation.Initialisation.

Page 36: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 3636

Recherche dans des tableaux triésRecherche dans des tableaux triés----------------------------------------------------------------------------------------------------------------------------------

Di-chotomie - Tri-chotomie - etc.Di-chotomie - Tri-chotomie - etc.

• Di-chotomie :Di-chotomie :– 1 test -> 2 intervalles de n/2 éléments.1 test -> 2 intervalles de n/2 éléments.– Donc, 1 * log_2 (n) + 1 tests.Donc, 1 * log_2 (n) + 1 tests.

• Tri-chotomie :Tri-chotomie :– 2 tests -> 3 intervalles de n/3 éléments.2 tests -> 3 intervalles de n/3 éléments.– Donc, 2 * log_3(n) + 1 tests.Donc, 2 * log_3(n) + 1 tests.

• K-chotomie :K-chotomie :– k-1 tests -> k intervalles de n/k éléments.k-1 tests -> k intervalles de n/k éléments.– Donc, (k-1) * log_k(n) + 1 tests.Donc, (k-1) * log_k(n) + 1 tests.

Optimal si k = 2 ! ! !Optimal si k = 2 ! ! !

Page 37: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 3737

Soyons critiques !Soyons critiques !----------------------------------------------------------------------------------------------------------------------------------• Tableau trié :Tableau trié :

– Recherche efficace Recherche efficace – Insertions et suppressions pénibles Insertions et suppressions pénibles

• Liste triée :Liste triée :

– Insertions et suppressions efficaces Insertions et suppressions efficaces – Recherche pénible Recherche pénible

• Hashage sur tableaux & arbres de recherche équilibrés :Hashage sur tableaux & arbres de recherche équilibrés :

– Toutes les opérations sont efficaces Toutes les opérations sont efficaces

Page 38: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 3838

HashageHashage----------------------------------------------------------------------------------------------------------------------------------

H : Eléments à stocker Indices d’un H : Eléments à stocker Indices d’un tableautableau

INSEE(Marc Gengler) 1.61.01 …INSEE(Marc Gengler) 1.61.01 …

1.61.01 …1.61.01 … MGMG

Attention, certaines casesAttention, certaines casesdu tableau contiennentdu tableau contiennentdes valeurs alors quedes valeurs alors qued’autres sont vides.d’autres sont vides.

Page 39: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 3939

HashageHashage----------------------------------------------------------------------------------------------------------------------------------

• Parfait, si H est injectiveParfait, si H est injective

– Si H(x) = H(y) alors x = y.Si H(x) = H(y) alors x = y.

• Souvent, H ne l’est pas :Souvent, H ne l’est pas :

– x = y mais H(x) = H(y) - il y a donc collision !x = y mais H(x) = H(y) - il y a donc collision !

– Il y a différentes manières de gérer les collisions.Il y a différentes manières de gérer les collisions.

/

Page 40: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 4040

HashageHashage----------------------------------------------------------------------------------------------------------------------------------

• Résolution locale des collisions :Résolution locale des collisions :

– Petite recherche séquentielle dans une liste chainée.Petite recherche séquentielle dans une liste chainée.– Prendre la première case libre en séquence dans le tableau.Prendre la première case libre en séquence dans le tableau.– Et si on peut supprimer des éléments ????? Des éléments Et si on peut supprimer des éléments ????? Des éléments

qui étaient responsables d’une collision viennent à qui étaient responsables d’une collision viennent à disparaître !disparaître !

• Re-hashage :Re-hashage :

– Si H(x) est déjà occupé on calcule H’(x) ou H(x+Si H(x) est déjà occupé on calcule H’(x) ou H(x+), etc. ), etc. jusqu’à trouver une place.jusqu’à trouver une place.

– Et si on peut supprimer des éléments ?????Et si on peut supprimer des éléments ?????

Page 41: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 4141

HashageHashage----------------------------------------------------------------------------------------------------------------------------------

XX

XX

YY

YY //

Page 42: Cours Algo 1   Resume

6 novembre 20066 novembre 2006 Cours d'algorithmique 1 - IntranetCours d'algorithmique 1 - Intranet 4242

HashageHashage----------------------------------------------------------------------------------------------------------------------------------

• Faits :Faits :

– La fonction de hashage doit être « uniforme » : pour des La fonction de hashage doit être « uniforme » : pour des choix au hasard de données d , les indices H( d ) doivent choix au hasard de données d , les indices H( d ) doivent être répartis le plus uniformément possible.être répartis le plus uniformément possible.

– A ce moment, le taux de remplissage donne la proportion A ce moment, le taux de remplissage donne la proportion des collisions.des collisions.

• Coût :Coût :

– Coût du calcul de H multiplié par le nombre moyen de Coût du calcul de H multiplié par le nombre moyen de collisions (re-hashage).collisions (re-hashage).

– Coût du calcul de H plus le coût de la recherche dans la Coût du calcul de H plus le coût de la recherche dans la liste chainée.liste chainée.

– ……