[PDF] [PDF] Algorithmes de Tris

[PDF] Recherche dichotomique dans un tableau dentiers - LAMSADE

13 sept 2000 · LANGAGE C - EXEMPLES DE PROGRAMMES Programm int main() e de recherche dichotomique d'un élément dans une liste d'entiers */

[PDF] Algorithmes de Tris

Recherche dans un tableau, dichotomie 7 de 47 Recherche dichotomique itérative Remarque : La recherche dichotomique est récursive terminale Algorithme 

[PDF] Algorithmique et Recherche Dichotomique

Peut-on éviter de parcourir tout le tableau pour rechercher le maximum d'un tableau d'entiers non trié ? Exercice 2 Recherche séquentielle dans un annuaire On 

[PDF] PLAN DU COURS ALGORITHME DE RECHERCHE

12 mar 2013 · 3 RECHERCHE DICHOTOMIQUE Algorithme recherche_dichotomique { Recherche le premier indice où se trouve la valeur val en utilisant la 

[PDF] Recherche dichotomique dans un tableau [re04] Exercice - Unisciel

Soit une structure tabulaire A[1 n] triée en ordre croissant On effectue une recherche dichotomique d'une valeur x comme suit Soient : • g l'indice de gauche 

[PDF] Méthodes de programmation Algorithmes de recherche, tri et sélection

(résultat légérement meilleur que pour un vecteur non-ordonné) Opérations sur tableaux ordonnés : – recherche sequentielle O(N) – suppression, insertion : O( N)

[PDF] 4 slides par page - Montefiore Institute ULg

23 déc 2019 · Consolider et étendre vos connaissances d'un langage de programmation (le Recherche dichotomique : 256000 vérifications par seconde

[PDF] Recherche et dénombrement dans des tableaux - Licence 1 - LISIC

28 avr 2013 · Recherche dichotomique d'un élément dans un tableau 3 Dénombrement Dénombrement Recherche itérative : langage algorithmique

[PDF] Récursion Récursivité - Pages Perso

factorielle, Fibonaci, exponenÄaÄon rapide, recherche dichotomique, tri fusion gérée par le langage de programmaÄon : une pile LIFO de taille préfixée

[PDF] recherche dichotomique recursive langage c

[PDF] exemple de manuel de procedure informatique

[PDF] organisation d une dsi type

[PDF] manuel de procédures informatiques

[PDF] cyberlux 8

[PDF] organisation d'un service informatique dans une entreprise

[PDF] cyberlux 8 crack

[PDF] exemple dossier exploitation informatique

[PDF] cyberlux 8 full

[PDF] bibliographie de max weber

[PDF] max weber pdf

[PDF] max weber économie et société tome 2 pdf

[PDF] max weber le savant et le politique pdf

[PDF] max weber économie et société fiche de lecture

[PDF] max weber économie et société tome 1 résumé

1 de 47

Algorithmique

Trier et Trouver

Florent Hivert

Mél :Florent.Hivert@lri.fr

Page personnelle :http://www.lri.fr/˜hivert

2 de 47

Algorithmes et structures de données

La plupart des bons algorithmes fonctionnent grâce à une méthode astucieuse pour organiser les données. Par exemple, on sait très bien, intuitivement, que pour retrouver une carte dans un jeu, il est très utile que le jeu soit trié. Trouver et Trier :Donald E. Knuth,The Art of Computer Programming (TAOCP), Volume 3 : Sorting and Searching, Addison-Wesley, 1998.

2 de 47

Algorithmes et structures de données

La plupart des bons algorithmes fonctionnent grâce à une méthode astucieuse pour organiser les données. Par exemple, on sait très bien, intuitivement, que pour retrouver une carte dans un jeu, il est très utile que le jeu soit trié.Trouver et Trier :

Donald E. Knuth,The Art of Computer Programming

(TAOCP), Volume 3 : Sorting and Searching, Addison-Wesley, 1998.

Recherche dans un tableau, dichotomie

3 de 47Recherche dans un

tableau, dichotomie

Recherche dans un tableau, dichotomie

4 de 47Algorithme de recherche d"un élément dans un tableau

Algorithme

Entrée :un tableautabde tailletailleet un élémente.Sortie :itel quetab[i] = eouNonTrouvé(ex :1).

pour i de 0 à taille-1 faire si tab[i] = e alors retourner i retourner NonTrouvé )Complexité :O(taille)\ (1).

Recherche dans un tableau, dichotomie

5 de 47Recherche d"un élément dans un tableau

La complexité précédente est trop élevée, surtout sachant que la recherche dans un tableau est une opération de base utilisée dans de nombreux algorithmes. Pour aller plus vite, on peut utiliser lestableaux triéset la dichotomie(méthode "diviser pour régner») :Retenir (Idée)

Si le tableautabest trié, pour tout indicei,les élémentsetab[i]sont d"indicei;les élémentse>tab[i]sont d"indice>i.On essaye aveciau milieu du tableau.

Recherche dans un tableau, dichotomie

6 de 47Recherche dichotomique

Algorithme (RechDichoRec: recherche dans un tableau trié)Entrée :un tableautriétab, un intervalle[min;max]avec

0minmax si min = max alors si tab[min] = e alors retourner min sinon retourner NonTrouvé mid <- (min + max) / 2 si tab[mid] < e alors retourner RechDichoRec(tab, mid+1, max, e) sinon retourner RechDichoRec(tab, min, mid, e) )Complexité :(log2(taille)).

Recherche dans un tableau, dichotomie

7 de 47Recherche dichotomique itérative

Remarque : La recherche dichotomique est récursive terminale.Algorithme (RechDichoItrecherche dichotomique itérative)min <- 0;

max <- taille - 1 tant que min < max faire mid <- (min + max) / 2 si tab[mid] < e alors min <- mid+1 sinon max <- mid si tab[min] = e alors retourner min sinon retourner NonTrouvé )Complexité :(log2(taille)).

Recherche dans un tableau, dichotomie

8 de 47On peut stopper la recherche plus tôt si l"on a trouvé!

Algorithme (Recherche dichotomique variante)

min <- 0; max <- taille - 1 tant que min < max faire mid <- (min + max) / 2 si tab[mid] = e alors retourner mid sinon si tab[mid] < e alors min <- mid+1 sinon max <- mid-1 si tab[min] = e alors retourner min sinon retourner NonTrouvé )Complexité :O(log2(taille))\ (1).

Recherche dans un tableau, dichotomie

9 de 47Autre application de la recherche dichotomique

Jeu du nombre inconnu où l"on répond soit "plus grand» soit "plus petit» soit "gagné».Calcul d"une racine d"une fonction croissante (exemple : px).Algorithme de pointage, de visée. Recherche de l"apparition d"un bug dans l"historique d"un programme (commandeshg bisect,git-bisect...) Exemple : 100 modifications, 10 minutes de tests pour chaque modifications. L"algorithme naif demande 1000 min16h40 au lieu de 70min1h10 par dichotomie.

Tableaux triés, algorithmes de tris

10 de 47Tableaux triés,

algorithmes de tris

Tableaux triés, algorithmes de tris

11 de 47Insertion dans un tableau trié

Algorithme (Insert)Entrées :

Tableautab,max_tailleéléments alloués

un élémente.Précondition :tabest trié (tab[i]tab[i+1]).Effet :eajouté àtabtrié. i <- taille tant que i > 0 et tab[i-1] > e faire tab[i] <- tab[i-1] i <- i-1 tab[i] <- e taille <- taille + 1 )Complexité :O(taille)

Tableaux triés, algorithmes de tris

12 de 47Tri par insertion

Algorithme (InsertSort)Entrée :TableauTde tailletaille.Effet :Ttrié. pour i de 1 à taille-1 faire e <- t[i] // Insérer e à sa place dans T[0], ..., T[i-1] j <- i tant que j > 0 et T[j-1] > e faire t[j] <- t[j-1] j <- j-1

T[j] <- e

)Complexité :O(taille2) Algorithmes plus efficaces : Diviser pour régner

13 de 47Algorithmes plus efficaces :

Diviser pour régner

Algorithmes plus efficaces : Diviser pour régner

14 de 47Diviser pour régner

Du latin " Divide ut imperes » (Machiavel)

On divise un problème de grande taille en plusieurs (deux)

sous-problèmes analogues. Différentes stratégies :1récursivité sur les données :on sépare les données en deux

parties arbitraires, puis on résout les sous-problèmes, pour

enfin combiner les résultats.2récursivité sur le résultat :on effectue un pré-traitement

pour bien découper les données, afin que, après avoir résolu les sous-problèmes, les sous-résultats se combinent d"eux-mêmes. Algorithmes plus efficaces : Diviser pour régner

14 de 47Diviser pour régner

Du latin " Divide ut imperes » (Machiavel)

On divise un problème de grande taille en plusieurs (deux)

sous-problèmes analogues. Différentes stratégies :1récursivité sur les données :on sépare les données en deux

parties arbitraires, puis on résout les sous-problèmes, pour

enfin combiner les résultats.2récursivité sur le résultat :on effectue un pré-traitement

pour bien découper les données, afin que, après avoir résolu les sous-problèmes, les sous-résultats se combinent d"eux-mêmes. Algorithmes plus efficaces : Diviser pour régner

15 de 47Récursivité sur les données :

On sépare les données en deux parties arbitraires, puis on résout les

sous-problèmes, pour enfin combiner les résultats.Comment obtenir un tableau trié, si l"on sait

trier chaque moitié?Fusion de tableaux trié! Algorithmes plus efficaces : Diviser pour régner

15 de 47Récursivité sur les données :

On sépare les données en deux parties arbitraires, puis on résout les

sous-problèmes, pour enfin combiner les résultats.Comment obtenir un tableau trié, si l"on sait

trier chaque moitié?Fusion de tableaux trié! Algorithmes plus efficaces : Diviser pour régner

15 de 47Récursivité sur les données :

On sépare les données en deux parties arbitraires, puis on résout les

sous-problèmes, pour enfin combiner les résultats.Comment obtenir un tableau trié, si l"on sait

trier chaque moitié?Fusion de tableaux trié! Algorithmes plus efficaces : Diviser pour régner

16 de 47Fusion de deux tableaux triés

Algorithme (Fusionde tableaux triée)Entrée :TableauxT1,T2triés de taillet1,t2, TableauTalloué de taillet=t1+t2Sortie :Tavec les contenusT1etT2trié i1 <- 0; i2 <- 0; i <- 0 tant que i1 < t1 et i2 < t2 faire si T1[i1] < T2[i2] alors

T[i] <- T1[i1]; i++; i1++

sinon

T[i] <- T2[i2]; i++; i2++

si i1 < t1 alors tant que i1 < t1 faire

T[i] <- T1[i1]; i++; i1++

sinon tant que i2 < t2 faire

T[i] <- T2[i2]; i++; i2++

)Complexité :(t) Algorithmes plus efficaces : Diviser pour régner

17 de 47Variantes et applications de la fusion

Opérations ensemblistes sur les tableaux trié :inclusion; intersection, réunion;différence et différence

symétrique.Algorithme (Inclusion de tableau trié)Entrée :TableauxT1,T2triés de taillet1,t2,Sortie :VraisiT1T2

i1 <- 0; i2 <- 0 tant que i1 < t1 et i2 < t2 faire si T1[i1] = T2[i2] alors i1++; i2++ sinon si T1[i1] > T2[i2] alors i2++ sinon retourner Faux retourner i1 = t1 Algorithmes plus efficaces : Diviser pour régner

18 de 47Tri par fusion (MergeSort)

Algorithme (TriFusion)Entrée :TableauxTde taillet,0minmaxTableauTmpalloué de tailletSortie :Ttrié.

si min <> max alors mid <- (min+max) / 2

TriFusion(T, min, mid)

TriFusion(T, mid+1, max)

Fusion(T[min..mid], T[mid+1..max], Tmp)

Copie de Tmp dans T[min..max]

)Complexité :(tlog(t)) Algorithmes plus efficaces : Diviser pour régner

19 de 47Complexité du tri par Fusion (1)

Pour simplifier, on suppose que la taille du tableau est une puissance de 2. On noteck=dnle nombre de copies d"éléments siTest de taille n=2k. On trouvec

0=d1=0c

1=d2=2+2 (fusion + copie)c

2=d4=2c1+4+4=16 (rec + fusion + copie)c

3=d8=2c2+8+8=48 (rec + fusion + copie)c

4=d16=2c3+16+16=128 (rec + fusion + copie)c

5=d32=2c4+32+32=320 (rec + fusion + copie)c

6=d64=2c5+64+64=768 (rec + fusion + copie)c

7=d128=2c6+128+128=1792 (rec + fusion + copie)

Algorithmes plus efficaces : Diviser pour régner

19 de 47Complexité du tri par Fusion (1)

Pour simplifier, on suppose que la taille du tableau est une puissance de 2. On noteck=dnle nombre de copies d"éléments siTest de taille n=2k. On trouvec

0=d1=0c

1=d2=2+2 (fusion + copie)c

2=d4=2c1+4+4=16 (rec + fusion + copie)c

3=d8=2c2+8+8=48 (rec + fusion + copie)c

4=d16=2c3+16+16=128 (rec + fusion + copie)c

5=d32=2c4+32+32=320 (rec + fusion + copie)c

6=d64=2c5+64+64=768 (rec + fusion + copie)c

7=d128=2c6+128+128=1792 (rec + fusion + copie)

Algorithmes plus efficaces : Diviser pour régner

19 de 47Complexité du tri par Fusion (1)

Pour simplifier, on suppose que la taille du tableau est une puissance de 2. On noteck=dnle nombre de copies d"éléments siTest de taille n=2k. On trouvec

0=d1=0c

1=d2=2+2 (fusion + copie)c

2=d4=2c1+4+4=16 (rec + fusion + copie)c

3=d8=2c2+8+8=48 (rec + fusion + copie)c

4=d16=2c3+16+16=128 (rec + fusion + copie)c

5=d32=2c4+32+32=320 (rec + fusion + copie)c

6=d64=2c5+64+64=768 (rec + fusion + copie)c

7=d128=2c6+128+128=1792 (rec + fusion + copie)

Algorithmes plus efficaces : Diviser pour régner

19 de 47Complexité du tri par Fusion (1)

Pour simplifier, on suppose que la taille du tableau est une puissance de 2. On noteck=dnle nombre de copies d"éléments siTest de taille n=2k. On trouvec

0=d1=0c

1=d2=2+2 (fusion + copie)c

2=d4=2c1+4+4=16 (rec + fusion + copie)c

3=d8=2c2+8+8=48 (rec + fusion + copie)c

4=d16=2c3+16+16=128 (rec + fusion + copie)c

5=d32=2c4+32+32=320 (rec + fusion + copie)c

6=d64=2c5+64+64=768 (rec + fusion + copie)c

7=d128=2c6+128+128=1792 (rec + fusion + copie)

Algorithmes plus efficaces : Diviser pour régner

19 de 47Complexité du tri par Fusion (1)

Pour simplifier, on suppose que la taille du tableau est une puissance de 2. On noteck=dnle nombre de copies d"éléments siTest de taille n=2k. On trouvec

0=d1=0c

1=d2=2+2 (fusion + copie)c

2=d4=2c1+4+4=16 (rec + fusion + copie)c

3=d8=2c2+8+8=48 (rec + fusion + copie)c

4=d16=2c3+16+16=128 (rec + fusion + copie)c

5=d32=2c4+32+32=320 (rec + fusion + copie)c

6=d64=2c5+64+64=768 (rec + fusion + copie)c

7=d128=2c6+128+128=1792 (rec + fusion + copie)

Algorithmes plus efficaces : Diviser pour régner

19 de 47Complexité du tri par Fusion (1)

Pour simplifier, on suppose que la taille du tableau est une puissance de 2. On noteck=dnle nombre de copies d"éléments siTest de taille n=2k. On trouvec

0=d1=0c

1=d2=2+2 (fusion + copie)c

2=d4=2c1+4+4=16 (rec + fusion + copie)c

3=d8=2c2+8+8=48 (rec + fusion + copie)c

4=d16=2c3+16+16=128 (rec + fusion + copie)c

5=d32=2c4+32+32=320 (rec + fusion + copie)c

6=d64=2c5+64+64=768 (rec + fusion + copie)c

7=d128=2c6+128+128=1792 (rec + fusion + copie)

Algorithmes plus efficaces : Diviser pour régner

19 de 47Complexité du tri par Fusion (1)

Pour simplifier, on suppose que la taille du tableau est une puissance de 2. On noteck=dnle nombre de copies d"éléments siTest de taille n=2k. On trouvec

0=d1=0c

1=d2=2+2 (fusion + copie)c

2=d4=2c1+4+4=16 (rec + fusion + copie)c

3=d8=2c2+8+8=48 (rec + fusion + copie)c

4=d16=2c3+16+16=128 (rec + fusion + copie)c

5=d32=2c4+32+32=320 (rec + fusion + copie)c

6=d64=2c5+64+64=768 (rec + fusion + copie)c

7=d128=2c6+128+128=1792 (rec + fusion + copie)

Algorithmes plus efficaces : Diviser pour régner

19 de 47Complexité du tri par Fusion (1)

Pour simplifier, on suppose que la taille du tableau est une puissance de 2. On noteck=dnle nombre de copies d"éléments siTest de taille n=2k. On trouvec

0=d1=0c

1=d2=2+2 (fusion + copie)c

2=d4=2c1+4+4=16 (rec + fusion + copie)c

3=d8=2c2+8+8=48 (rec + fusion + copie)c

4=d16=2c3+16+16=128 (rec + fusion + copie)c

5=d32=2c4+32+32=320 (rec + fusion + copie)c

6=d64=2c5+64+64=768 (rec + fusion + copie)c

7=d128=2c6+128+128=1792 (rec + fusion + copie)

Algorithmes plus efficaces : Diviser pour régner

20 de 47Complexité du tri par fusion (2)

Proposition

Le nombreckde copies d"éléments effectuées par le tri par fusion d"un tableau den=2kéléments vérifie : c

0=0etck=2(ck1+2k):

c k=2k+1k=2nlog2(n):Preuve par récurrence : vrai pourk=0sick=2k+1kalors c k+1=2(ck+2k+1) =2(2k+1k+2k+1) =2k+2(k+1) Algorithmes plus efficaces : Diviser pour régner

20 de 47Complexité du tri par fusion (2)

Proposition

Le nombreckde copies d"éléments effectuées par le tri par fusion d"un tableau den=2kéléments vérifie : c

0=0etck=2(ck1+2k):

c k=2k+1k=2nlog2(n):Preuve par récurrence : vrai pourk=0sick=2k+1kalors c k+1=2(ck+2k+1) =2(2k+1k+2k+1) =2k+2(k+1) Algorithmes plus efficaces : Diviser pour régner

20 de 47Complexité du tri par fusion (2)

Proposition

Le nombreckde copies d"éléments effectuées par le tri par fusion d"un tableau den=2kéléments vérifie : c

0=0etck=2(ck1+2k):

c k=2k+1k=2nlog2(n):Preuve par récurrence : vrai pourk=0sick=2k+1kalors c k+1=2(ck+2k+1) =2(2k+1k+2k+1) =2k+2(k+1) Algorithmes plus efficaces : Diviser pour régner

21 de 47Complexité du tri par fusion (3)

n n 2 n 2 2. ..n 2 kn 2quotesdbs_dbs26.pdfusesText_32