Chapitre 2 Exemples dalgorithmes itératifs et récursifs
Algorithme 1: Euclide forme récursive. Entrée: Deux entiers relatifs : a
Algorithmique et programmation avancée
définition par récurrence 3) Récursivité et itération. Tout algorithme récursif peut être ... Choisir entre itératif et récursif. Version récursive.
LIFAP2 : ALGORITHMIQUE ET PROGRAMMATION RECURSIVE
Algorithme itératif / récursif L'exécution d'un algorithme ne doit pas impliquer ... comparaison entre le premier élément de la liste (ici 3).
Algorithmique Trier et Trouver
Entrée : un tableau tab de taille taille et un élément e. Algorithme (RechDichoIt recherche dichotomique itérative) ... différence et différence.
Algorithmique Récursivité
On appelle récursive toute fonction ou procédure qui s'appelle elle même. Algorithme Fact. Entrée : un entier positif N. Sortie : factorielle de N si N = 0
Trois algorithmes de calcul des nombres de Fibonacci
Exercice 1 (Algorithme récursif) Soit l'algorithme suivant : si n = 0 ou n = 1 alors Exercice 2 (Algorithme itératif) Soit l'algorithme suivant :.
livre-algorithmes EXo7.pdf
Arithmétique – Algorithmes récursifs . ci-dessus) avec par définition tan?i = 10?i. ... Écrire une version itérative de l'algorithme d'Euclide.
Algorithmes récursifs: une introduction pragmatique pour un
27 oct. 2019 retourner fact. Algorithme 1 : FactorielleItérative : calcule itérativement la valeur de n!. Essayons-nous à la même démarche avec l'équation (2) ...
Algorithmique & programmation en langage C - vol.1 - Archive
1 févr. 2019 COMPARAISON ITÉRATIF/RÉCURSIF . ... d'ores et déjà d'établir l'indépendance entre un algorithme et sa mise en œuvre c'est à dire.
Première partie : Algorithmique avancée pour les graphes
Algorithme 5 : Parcours en profondeur récursif d'un graphe La différence entre les trois algorithmes réside dans la stratégie utilisée pour décider de ...
[PDF] LIFAP2 : ALGORITHMIQUE ET PROGRAMMATION RECURSIVE
Algorithme itératif / récursif Langage commun entre la machine et nous : comparaison entre le premier élément de la liste (ici 3) et min (ici -2)
[PDF] Spécificités des algorithmes itératifs et récursifs - CNRS
4 oct 2022 · Complexité des algorithmes itératifs : – Utilisation des règles révisées dans les slides 103 et 104 • Complexité des algorithmes récursifs
[PDF] Chapitre 2 Exemples dalgorithmes itératifs et récursifs
Algorithme 1: Euclide forme récursive Entrée: Deux entiers relatifs : a b; Sortie: Un entier pgcd de a et b; Fonction PGCD(a b);
[PDF] Algorithmique et programmation avancée
Tout algorithme récursif peut être transformé en un algorithme itératif équivalent : c'est la dérécursivation La méthode à suivre dépend du type de récursivité
[PDF] Algorithmique Récursivité
Moyen simple et élégant de résoudre certain problème Définition On appelle récursive toute fonction ou procédure qui s'appelle elle même Algorithme Fact
[PDF] cours 2:Complexité des algorithmes récursifs - Esentn
Algorithmes récursifs Définition La récursivité est le fait pour une méthode de s'appeler elle même On parle alors de méthode récursive
[PDF] Récursivité
3 fév 2020 · Une procédure (ou une fonction) est dite récursive si elle contient au moins un énoncé d'appel direct ou non à elle-même dans son corps
Différence entre récursivité et itération - WayToLearnX
14 juil 2018 · La principale différence entre récursion et itération est que la récursivité est un processus toujours appliqué à une fonction
[PDF] ALGORITHMIQUE II
Un algorithme (ou fonction) est dit récursif s'il est défini en fonction de lui-même ? Exemples ? Fonction puissance(x : réel n : entier) : réel
[PDF] Récursivité - LACL
- ´Ecrire deux fonctions C l'une utilisant un algorithme itératif l'autre un algorithme récursif permettant de calculer l'entier naturel n étant donné en
Quelle est la différence entre un programme itératif et un programme récursif ?
Un programme est dit récursif lorsqu'une entité s'appelle elle-même. Un programme est appelé itératif lorsqu'il y a une boucle (ou répétition).Comment transformer un algorithme récursif en itératif ?
Tout algorithme récursif peut être transformé en un algorithme itératif équivalent : c'est la dérécursivation. La méthode à suivre dépend du type de récursivité de l'algorithme. Un algorithme est dit récursif terminal s'il ne contient aucun traitement après un appel récursif.Quand Dit-on qu'un algorithme est récursif ?
L'algorithme est récursif parce qu'il s'invoque lui-même. En effet, pour construire toutes les permutations de belle Marquise -- vos beaux yeux -- me font mourir -- d'amour, il faut construire toutes les permutations de vos beaux yeux -- me font mourir -- d'amour.- En informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini.
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égner18 de 47Tri par fusion (MergeSort)
Algorithme (TriFusion)Entrée :TableauxTde taillet,0minmaxTriFusion(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égner19 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 trouvec0=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égner19 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 trouvec0=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égner19 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 trouvec0=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égner19 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 trouvec0=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égner19 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 trouvec0=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égner19 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 trouvec0=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égner19 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 trouvec0=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égner19 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 trouvec0=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égner20 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 : c0=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égner20 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[PDF] fonction récursive
[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
[PDF] l5a 4 edition pdf
