[PDF] Cours 2. Partie 2: Introduction à lalgorithmique. Dichotomie. Un peu





Previous PDF Next PDF



Algorithmique Trier et Trouver

On essaye avec i au milieu du tableau. Page 7. Recherche dans un tableau dichotomie. 6 de 47. Recherche dichotomique.



Recherche dichotomique

tableau de façon ordonnée. Une première façon de rechercher une valeur dans un tableau est d'effectuer ... On dit que l'on procède par dichotomie du.



Cours 2. Partie 2: Introduction à lalgorithmique. Dichotomie. Un peu

Aujourd'hui. Recherche dans un tableau. Dichotomie. Trier. Tri par sélection. Tri `a bulles. Tri par insertion. Tri par fusion.



Recherche dichotomique dans un tableau [re04] Exercice

On cherche `a construire un algorithme permettant de savoir `a quel endroit se trouve une valeur x. On suppose que x est dans le tableau. Écrivez une fonction 



Recherche dichotomique dans un tableau dentiers

13 sept. 2000 int iTableau[]={12



Algorithmes appliqués à des intervalles Dichotomie et intégration

dans un tableau trié. Les questions de précision du calcul sont en lien avec la partie 1.b. Recherche par dichotomie du zéro d'une fonction continue.



M´ethodes par dichotomie et algorithmes gloutons

reconnaitre un cas o `u une approche par dichotomie est envisageable. • savoir coder en Python un algorithme de recherche dichotomique dans un tableau trié.



F1 : Méthode dencadrement dune solution par dichotomie : Le

On souhaite donner un encadrement à 10?2 près de x0 à l'aide de l'algorithme de dichotomie. Compléter le tableau suivant et donner un encadrement de x0 .



EA3 Complexité en temps de lalgorithme de dichotomie

Etant donné un tableau T et un élément x si x n'appartient pas à T



Juin 2009 1) QCM (8 points) a) La recherche par dichotomie dans

Juin 2009. Université d'Orléans. Master MIAGE 1. 1) QCM (8 points) a) La recherche par dichotomie dans un tableau trié de taille n se fait en . . . étapes.

Cours 2. Partie 2: Introduction a

l'algorithmique.

Dichotomie. Un peu de tris

Olivier Bournez

bournez@lix.polytechnique.fr

LIX, Ecole Polytechnique

2011-12 Algorithmique

1

Aujourd'hui

Recherche dans un tableau

Dichotomie

Trier

Tri par selection

Tri a bulles

Tri par insertion

Tri par fusion2

Rechercher un element

Le problemeRECHERCHE

I On se donne une liste d'entiers naturelsT[1];T[2];;T[n].

IOn se donnexun entier.

IOn doit determiner six=T[i] pour un certain entieri. 3 int [] T= new int[100]; int x; int r = Dans(T,x); int Dans(int [] T, int x) { for (int j=0; j< T.length; j++) { if (T[j] == x) return true;} return false; }Nombre de comparaisons (hors variable de boucle)

1C(n)n.

n= nombre d'entiers dans le tableau. 4

Bornes extr^emes

C(n) = 1 pour un tableau qui debute parx.C(n) =npour un tableau qui ne contient pasx.C(n)2O(n).En moyenne:

I si on suppose que le tableau contient une permutation de

1;2;;n, et que chaque permutation est choisie de facon

uniforme, en moyenne n+12 5

Digression: pourquoi?

calcul sur les moyennesSi on suppose que les entrees sont les listes permutations de f1;2;;ng, et qu'elles sont equiprobables,

ComplexiteMoyenneA(n) =Esperanced=taille(d)=n[k]

=Pn i=1iP(k=i)Puisque les permutations sont equiprobables,

Proba(k=i) = 1=n.

ComplexiteMoyenneA(n) =Pn

i=1i1n =n(n+1)2n=n+12 (joli exercice) Pour l'algorithme iteratif pourMAX, ComplexiteMoyenneA(n) en aectations entre variables entieres est en (logn) (de l'ordre deHn= 1 +12 ++1n 6

Optimal?

A tout algorithme qui fonctionne par comparaisons, on peut associer un arbre de decision.Si cet arbre possede moins densommets, on peut trouver un tableauTsur lequel l'algorithme repond de facon non correcte.Il faut donc au moinsncomparaisons.... (sans autres hypotheses sur les donnees). 7

Aujourd'hui

Recherche dans un tableau

Dichotomie

Trier

Tri par selection

Tri a bulles

Tri par insertion

Tri par fusion8

Rechercher un element dans un tableau trie

Le problemeRECHERCHE

I

On se donne une liste d'entiers naturelsTRIEE

T[0]T[2] T[n1]:

I

On se donnexun entier.

IOn doit determiner six=T[i] pour un certain entieri. 9

Le jeu prefere de Pierrick

Papachoisit un entierminiIoptimale? Combien de question est il necessaire dans le pire des cas?

16 = 2222 = 24:

128 = 2222222 = 27:

10

Strategie de la dichotomie

Strategie de la dichotomie:

I prendre systematiquementd= (min+max)=2.

Iactualiserminetmax.

11

Retour sur recherche: arbre des possibilites

Dessin de l'algorithme naif.

Dessin de l'arbre de decision pour la dichotomie pour par exemplen= 16.Remarque: I Tout algorithme qui fonctionne par comparaisons peut se representer par un arbre de decision. 12

Recherche par dichotomie: version recursive

static

b ooleantrouve(int[] T,intv,intmin,intmax){if(minmax)/ /v idereturnf alse;intmid = (min + max) / 2;if(T[mid] == v)returnt rue;elsei f(T[mid] > v)returntrouve(T, v, min, mid);elser eturntrouve(T, v, mid + 1, max);}13

Version non-recursive

Elimination d'une recursion terminale...

I aucun traitement a executer apres chacun des appels qu'elle

contient.staticb ooleantrouve(int[] T,intv,intmin,intmax){while(min < max) {intmid = (min + max) / 2;if(T[mid] == v)returnt rue;elsei f(T[mid] > v) max=mid;elsemin=mid+1;}

}14

Cet algorithme fonctionne

Il faut prouver que:

1. l ap rocedureter minetou jours 2. s 'ile xisteun en tieriavecT[i] =v, alors l'algorithme repond vrai. 3. s il' algorithmer epondvr ai,a lorsi ly a u nen tieriavec T[i] =v.Dernier point evident, car quand l'algorithme repond vrai, cette propriete est vraie.Pour le premier point, on montre que la suitemaxmin decroit strictement.Pour le second point, preuve par recurrence surk, le numero de l'etape. 15

Analyse

Complexite:

I Si 2k1n<2k, une recherche fructueuse utilise entre 1 et

2kcomparaisons.

INombre de comparaisons est donc enO(blog2nc) =O(log2n).Optimal: I a tout algorithme par comparaison, on peut associer un arbre:

Il doit avoir au moinsnsommets.

Sa hauteur est donc au moins de l'ordre deblog2nc. Il a donc au moins une execution avecblog2ncinstructions.

Il ne peut donc pas ^etre de complexite mieux que

blog2nc=O(log2n). 16

Aujourd'hui

Recherche dans un tableau

Dichotomie

Trier

Tri par selection

Tri a bulles

Tri par insertion

Tri par fusion17

Pourquoi trier?

Trier est une operation naturelle.

Travailler sur des donnees triees est parfois plus ecace. I

Exemple:

Rechercher un element dans un tableau anelements:O(n). Rechercher un element dans un tableau trie anelements:

O(logn) (par dichotomie).

Trier devient interessant des que le nombre de recherches est en (Complexite(tri)=n).18

Pourquoi trier?

Trier est une operation naturelle.

Travailler sur des donnees triees est parfois plus ecace. I

Exemple:

Rechercher un element dans un tableau anelements:O(n). Rechercher un element dans un tableau trie anelements:

O(logn) (par dichotomie).

Trier devient interessant des que le nombre de recherches est en (Complexite(tri)=n).18

Aujourd'hui

Recherche dans un tableau

Dichotomie

Trier

Tri par selection

Tri a bulles

Tri par insertion

Tri par fusion19

Principe

Sur un tableau de n elements (numerotes de 0 an1), le principe du tri par selection est le suivant : I rechercher le plus petit element du tableau, et l'echanger avec l'element d'indice 0; Irechercher le second plus petit element du tableau, et l'echanger avec l'element d'indice 1 ; Icontinuer de cette facon jusqu'a ce que le tableau soit entierement trie. 20 procedure tri_selection(tableau t, entier n) pour i de 0 a n - 2 min := i pour j de i + 1 a n - 1 si t[j] < t[min], alors min := j si min <> i, alors echanger t[i] et t[min] 21

Correct

Invariant de boucle: \ a la n de l'etape i,

1. l etab leauest un ep ermutationdu ta bleaui nitial 2. e tl esi p remiers elementsdu ta bleauco ncident avec les i premiers elements du tableau trie. 22

Complexite

Eectue

(n1)+(n2)++1 = 1+2++(n1) =n(n1)=2 comparaisons.Soit enO(n2).Non-optimal.

Inter^et: peu d'echanges :

I n1 echanges dans le pire cas, qui est atteint par exemple lorsqu'on trie la sequence 2,3,...,n,1 ; n(1=2 ++ 1=n)'nlnnen moyenne, c'est-a-dire si les elements sont deux a deux distincts et que toutes leurs permutations sont equiprobables (en eet, l'esperance du nombre d'echanges a l'etape i est (ni)=(ni+ 1)); Iaucun si l'entree est deja triee.Ce tri est donc interessant lorsque les elements sont aisement comparables, mais co^uteux a deplacer dans la structure. 23

Aujourd'hui

Recherche dans un tableau

Dichotomie

Trier

Tri par selection

Tri a bulles

Tri par insertion

Tri par fusion24

Tri a bulles

1. L 'ideecon siste acomp arerd eux elementsa djacents,e t al es echanger s'ils ne sont pas dans l'ordre. 2. L orsqu'onr ealiseun p assage,on ra ngel ep lusgr and elementquotesdbs_dbs19.pdfusesText_25
[PDF] Tableau de Facture ? Complété en Mathématique

[PDF] tableau de ferraillage pdf

[PDF] tableau de financement cours et exercices

[PDF] tableau de financement emplois ressources

[PDF] tableau de financement exemple

[PDF] tableau de financement explication

[PDF] tableau de financement partie 1

[PDF] tableau de financement partie 2

[PDF] tableau de financement pdf

[PDF] tableau de formation de resultat pdf

[PDF] Tableau de Johannes Gumpp

[PDF] tableau de joseph steib

[PDF] Tableau de Joseph Vernet

[PDF] Tableau de l'évolution chronologique du pont

[PDF] Tableau de la Joconde