IN101 - cours 05 - 15 octobre 2010

Matthieu Finiasz

Description

Un probl`eme concretRecherche de collisions√Le paradoxe des anniversaires dit que 365 ´el`eves sont suffisants(en moyenne) pour avoir une collision d’anniversaire,IN 101 - Cours 05deux ´el`eves ayant leur anniversaire le mˆeme jour.7 octobre 2011Comment fait-on pour efficacement trouver ces “paires” d’´el`eves?pr´esent´eparMatthieu FiniaszUn probl`eme concret Un probl`eme concretRecherche de collisions Recherche de collisions√ √Le paradoxe des anniversaires dit que 365 ´el`eves sont suffisants Le paradoxe des anniversaires dit que 365 ´el`eves sont suffisants(en moyenne) pour avoir une collision d’anniversaire, (en moyenne) pour avoir une collision d’anniversaire, deux ´el`eves ayant leur anniversaire le mˆeme jour. deux ´el`eves ayant leur anniversaire le mˆeme jour.Comment fait-on pour efficacement trouver ces “paires” d’´el`eves? Comment fait-on pour efficacement trouver ces “paires” d’´el`eves?M´ethode simple : M´ethode simple :on remplit un tableau avec les n dates d’anniversaire, on remplit un tableau avec les n dates d’anniversaire,on compare chaque ´el´ement `a tous les autres du tableau on compare chaque ´el´ement `a tous les autres du tableau,2 2complexit´eenΘ(n ). complexit´eenΘ(n ). Peut-on faire mieux? Peut-on faire mieux? OUIon trie le tableau,on le parcourt en regarant si 2 voisins sont ´egaux,complexit´eenΘ(nlogn).Le triDescription du probl`emeOn se donne un tableau de n ´el´ements (des entiers par exemple) etune relation ...

Informations

• Publié par: Oslu
• Nombre de lectures: 37
• Langue: Français

Extrait

IN 101 - Cours 05 7 octobre 2011

pre´sent´epar Matthieu Finiasz

Unproble`meconcret Recherche de collisions √ Leparadoxedesanniversairesditque365e´l`evessontsuffisants (en moyenne) pour avoir unecollision d’anniversaire,  ˆeemelirsaerivnnarueltnayaseve`ldeux´eru.emoj

Comment fait-on pourefficacementrouvts“paerced”´’riseev?slee` Me´thodesimple: on remplit un tableau avec lesndates d’anniversaire, oncomparechaque´el´ementa`touslesautresdutableau 2  oceenxit´mpleΘ(n).

Peut-on faire mieux ?

Unproble`meconcret Recherche de collisions √ Leparadoxedesanniversairesditque365´ele`vessontsuffisants (en moyenne) pour avoir unecollision d’anniversaire,  e`ev´xledueniveuranntlesayauojemeˆmeleriasrr.

Comment fait-on pourefficacementevuosecriap“”serd’´el`eves?tr

Unprobl`emeconcret Recherche de collisions √ Leparadoxedesanniversairesditque365´ele`vessontsuffisants (en moyenne) pour avoir unecollision d’anniversaire,  irelemˆemejour.ltnaaruevinnasrede´euxevl`ayes

Comment fait-on pourefficacement’´”desirpas“ceervuortev?slee` M´ethodesimple: on remplit un tableau avec lesndates d’anniversaire, oncomparechaque´ele´ment`atouslesautresdutableau, 2  molpxetien´ecΘ(n).

Peut-on faire mieux ?  OUI ontrie le tableau, onleparcourtenregarantsi2voisinssonte´gaux,  eplmioxc´teenΘ(nlogn).

Comment trier un tableau

Complexite´variable Quelquesd´efinitions

Complexit´edanslepirecas Tempsdecalculdanslepirecaspourlesentr´eesdetaillen:fi´xee

T(n) = maxT(x). { x, | x | =n }

Complexite´moyenne Tempsdecalculmoyensurtouteslesentre´esdetaillene:fix´e  T m (n) =p n (x)T(x). x, | x | =n (p n rpednoittilibabonetues)buristdiedatliel´esurlesentr´eesn.

Le tri Descriptionduproble`me

On se donne un tableau denaperexpmele)´etl´ements(desentiers unerelation d’ordre totale≤. on effectue untri par comparaison, utilisant uniquement≤ lacomplexite´estlenombredecomparaisons.

  2 Lesalgorithmes´ele´mentairesontunecomplexit´eenΘn. Lesmeilleursalgorithmesontunecomplexite´enΘ(nlog(n)).

En autorisant plus que des comparaisons, on peut parfois faireΘ(n).

Tri par insertion Si¸camarchepourn,c¸amarchepourn+1

1 voidinsertion_sort(int*tab,intn) { 2 inti,j,tmp; 3 for (i=1; i<n; i++) { 4 tmp = tab[i]; 5 j = i-1; 6 while ((j >= 0) && (tab[j] > tmp)) { tab[j+1] = tab[j]; 7 8 j--; 9 } 10 tab[j+1] = tmp; } 11 } 12

L’´el´ementiesiltsareapmrgne´i−tri´es):1pmires´ere´letnem´d(sa`je i ins´ererune´l´ementcoˆuteaupireien moyenne ,   2 2 complexite´enΘnipersneladnvereauitablcas()e´i,emesrttn   2 complexit´emoyenneenΘnaussi.

Oncommenceparrecopier“dos`ados”les2tableaux(couˆtΘ(n)),

Tri fusion Fusion des sous-tableaux

p(p+r)/2r-1 1 5 4 9 7 3 6 2

Tri rapide Quicksort

1 4 5 9 7 6 3 2

Pourame´liorerunpeulesperformances,onarreˆteletride`sque l’undesparcoursn’inverseaucun´el´ements. Ce tri ne fait queΘ(ntri´ej`aaud´able.eoc)armpsoaisunsntru

Tre`srapide,peuteˆtrefaiten place:   2 complexit´edanslepirecasΘn, complexite´enmoyenneΘ(nlog(n)).

2 3 6 7

1 4 5 9

Oncherche`are´duireleprobl`eme: on coupe le tableau en deux, ontriechaquemoiti´e, on fusionne.

Inse´rerun´el´ementsdansuntableautri´ecoˆuteΘ(n), n fusionnerdeuxtableauxdetaillecouˆteaussiΘ(n). 2

puisonparcourtparlesdeuxboutsenavan¸cantdupluspetitcoˆt´e a`chaquefois(coˆutΘ(n) aussi).

L’ide´eestdefaireremonterlesgrands´el´ements`alafindutableau onparcourtletableauencomparantl’´el´ementiauiet on+ 1 lesinversesin´ecessaire,  `al,sruocrapudnfialsttepllegrusd,anrederein´le´neme apr`esiparcours lesiplusgrands´eln.sstneme´fiala`tno on faitn−´e.ttricoar1plttaruesuasebael Complexit´e:oneffectueΘ(n) parcours comportantΘ(n) compa- raisons`achaquefois,   2 letria`bullesaunecomplexite´deΘndans le pire cas et en moyenne.

4 5 9 7 6 i j

1 2 3 4

Tri fusion n Si¸camarchepour,c¸amarchepourn 2

1 voidquick_sort(int*tab,intp,intr) { 2 if (r-p > 1) { 3 intq =partition(tab,p,r); 4 quick_sort(tab,p,q); 5 quick_sort(tab,q+1,r); 6 } 7 }

5 9 7 6 i j

1 2 3

Trire´cursifbase´surunpartitionnement: on choisit unpivot, onpermutelese´le´mentsdutableau  gransles,puiivotlspep,iubetuua´dtstipeesl,ds on trie les petits entre eux et les grands entre eux.

7 3 6 2

7 3

6 2

7

2

3

1 5

3 7

2 6

Tria`bulles

4 9

4 9

9

Lecouˆttotalestceluidesfusions: chaquefusioncoˆuteΘ(r−p), lecouˆttotalestΘ(nlog(n)), dans le pire cas et en moyenne.

1 5 4 9

4

1 2 3 4 5 6 7 9

2 3 6 7

1

5

1 5

1 4 5 9

6

La fonctionpartitioneffectuer−p−1 comparaisons.

1 intpartition(int*tab,intp,intr) { 2 intx = tab[p]; 3 intq = p; 4 inti,tmp; 5 for (i=p+1; i<r; i++) { 6 if (tab[i] <= x) { 7 q++; 8 tmp = tab[q]; 9 tab[q] = tab[i]; 10 tab[i] = tmp; 11 } 12 } 13 tmp = tab[q]; 14 tab[q] = tab[p]; tab[p] = tmp; 15 16 return q; 17 }

En moyenne

n

Tableau trié

n

Complexit´es

compare´es En pratique

Tableau inversement trié

n

Tri rapide Tri par insertion Tri fusion

Algorithme Tri par insertion Tri`abulles Tri rapide Tri fusion

Cas le pire   2 Θn   2 Θn Θ(nlog(n))

Complexite´scompare´es Asymptotiquement

En moyenne   2 Θn Θ(nlog(n)) Θ(nlog(n))

Application L’algorithme “quickselect”

Pourtrouverlam´ediane(ouleke´em´eleu’tntnd):auleabi`em- n onpeuttrierletableauetprendrel’´el´ement, 2  cˆotueΘ(nlogn). maiscelan’estpasn´ecessaire...

On s’inspire du tri rapide : on conserve la ligne :intq = partition(tab,p,r); aulieude2appelsre´cursifs,onn’enfaitqu’un n n queq<o ,  selon 2 uq> 2 onnefaitqu’unepartiedutri,leminimumn´ecessaire, n n n  esnetlaelixocpmyone´tmen... = 2+ + + + n=Θ(n). 2 4 8