Algorithme de recherche d'un élément dans un tableau Algorithme Entrée Remarque : La recherche dichotomique est récursive terminale Algorithme Définition On dit qu'un tri est en place, s'il utilise un emplacement mémoire constant
Previous PDF | Next PDF |
[PDF] Algorithmique avancée
24 avr 2002 · 2 Complexité et optimalité ; premier algorithme de tri 13 Définition 4 (Définition récursive, algorithme récursif) un comparatif des listes simplement chaînées, doublement chaînées et des tableaux, triés ou non, sur des
[PDF] Cours complet - Structures de données et algorithmes
Quand les appels récursifs se partagent la même structure de données, les Questions `a se poser lors de la définition d'un algorithme : Mon algorithme Tri comparatif : basé sur la comparaison entre les éléments (clés) Algorithmes de tri
[PDF] Techniques Algorithmiques et Programmation - Unité de formation d
25 fév 2021 · recette est un algorithme très très particulier où les entrées sont vides 6 bien qu'en pratique, il n'y a pas de différence entre un programme de complexité trop grande et un Voici un programme récursif calculant k(n) en fonction des k(2i) et donc des k(i) avec i > 0 Cf le tableau comparatif des tris
[PDF] Un algorithme efficace pour la comparaison de deux moyennes
groupe 2, et la différence observée entre les groupes (Do) devrait graviter près des l'algorithme récursif d'énumération, l'un en version Delphi (ou Pascal)
[PDF] Exercices dalgorithmique - CNRS
19 août 2019 · Calculer la différence entre deux heures de la journée : Une version récursive naïve de cette algorithme (invoquant deux fois la fonction fibo) est un rative 8 ⋆⋆ Générer toutes les chaînes de caractères de longueur
[PDF] Algorithmique et application Java - LAMSADE - Université Paris
1 avr 2014 · 2 2 Complexité des algorithmes récursifs Définition 1 La complexité d'un algorithme en fonction du vecteur de paramètres n dépendants
[PDF] Algorithmes de Tris
Algorithme de recherche d'un élément dans un tableau Algorithme Entrée Remarque : La recherche dichotomique est récursive terminale Algorithme Définition On dit qu'un tri est en place, s'il utilise un emplacement mémoire constant
[PDF] Algorithme récursif de coopération de courtiers visant à optimiser l
5 2 2 Algorithme récursif avec évitement d'envois redondants concepts orientés objets qui cachent les différences entre les languages de programmation, ratif signifie que les courtiers sont interrogés par étapes les uns après les autres
[PDF] Calculs ascendants du programme dAckermann - Numdam
La fonction d'Ackermann a été introduite en théorie de la récursivité comme exemple Le principe de l'algorithme de Rice est d'« inverser » la définition récursive, ratifs : transformations syntaxiques, sémantiques locales, sémantiques pro-
[PDF] fonction récursive
[PDF] dynamisme d'une automobile wikipedia
[PDF] automobile in corsa
[PDF] pélican volant de marey (1882)
[PDF] dynamisme d'un cycliste
[PDF] le futurisme mouvement artistique
[PDF] futurisme caractéristiques
[PDF] futurisme définition
[PDF] l5a les clans majeurs pdf
[PDF] l5a pdf
[PDF] l5a 4eme edition pdf
[PDF] pendule élastique vertical
[PDF] l5a 4eme edition pdf download
[PDF] pendule elastique definition
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, dichotomieRecherche 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 : cquotesdbs_dbs44.pdfusesText_44
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 trisTableaux 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-1T[j] <- e
)Complexité :O(taille2) Algorithmes plus efficaces : Diviser pour régner13 de 47Algorithmes plus efficaces :
Diviser pour régner
Algorithmes plus efficaces : Diviser pour régner14 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, pourenfin 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égner14 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, pourenfin 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égner15 de 47Récursivité sur les données :
On sépare les données en deux parties arbitraires, puis on résout lessous-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égner15 de 47Récursivité sur les données :
On sépare les données en deux parties arbitraires, puis on résout lessous-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égner15 de 47Récursivité sur les données :
On sépare les données en deux parties arbitraires, puis on résout lessous-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égner16 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] alorsT[i] <- T1[i1]; i++; i1++
sinonT[i] <- T2[i2]; i++; i2++
si i1 < t1 alors tant que i1 < t1 faireT[i] <- T1[i1]; i++; i1++
sinon tant que i2 < t2 faireT[i] <- T2[i2]; i++; i2++
)Complexité :(t) Algorithmes plus efficaces : Diviser pour régner17 de 47Variantes et applications de la fusion
Opérations ensemblistes sur les tableaux trié :inclusion; intersection, réunion;différence et différencesymé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