IN101 - cours 05 - 15 octobre 2010

De
Publié par

IN 101 - Cours 057 octobre 2011pr´esent´e parMatthieu FiniaszUn probleme concretRecherche de collisionspLe paradoxe des anniversaires dit que 365 ´el`eves sont suffisants(en moyenne) pour avoir une collision d’anniversaire,deux ´el`eves ayant leur anniversaire le mˆeme jour._Comment fait-on pour efficacement trouver ces “paires” d’´el`eves?1Un probleme concretRecherche de collisionspLe paradoxe des anniversaires dit que 365 ´el`eves sont suffisants(en moyenne) pour avoir une collision d’anniversaire,deux ´el`eves ayant leur anniversaire le mˆeme jour._Comment fait-on pour efficacement trouver ces “paires” d’´el`eves?M´ethode simple :on remplit un tableau avec les n dates d’anniversaire,on compare chaque ´el´ement `a tous les autres du tableau2complexit´e enΘ(n )._Peut-on faire mieux?2Un probleme concretRecherche de collisionspLe paradoxe des anniversaires dit que 365 ´el`eves sont suffisants(en moyenne) pour avoir une collision d’anniversaire,deux ´el`eves ayant leur anniversaire le mˆeme jour._Comment fait-on pour efficacement trouver ces “paires” d’´el`eves?M´ethode simple :on remplit un tableau avec les n dates d’anniversaire,on compare chaque ´el´ement `a tous les autres du tableau,2complexit´e enΘ(n )._Peut-on faire mieux? OUI_on trie le tableau,on le parcourt en regarant si 2 voisins sont ´egaux,complexit´e enΘ(nlogn)._3Commenttrier un tableauLe triDescription du problemeOn se donne un tableau de n ´el´ements (des entiers ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 29
Nombre de pages : 43
Voir plus Voir moins
IN
¸ ¸ ´
7
-
o
’QaTU
ctobre
persenet
-5“ HiDa
par
´ 5
2011
iFNi5Uz
p
UNRTQ=DLMDAQNATD1DAHDTAHD CD AQLLiUiQNU
Leparadoxedesanniversairesditque365el`evessontsusants , (enmoyenne)pouravoirunecollision d’annive saire r deuxele`vesayantleuranniversaireleme^mejour.
_
Comment
fait-on
pour
ecacement
trouver
ces
\paires"
del`eves
?1
UNLiQLDADCAHDTAH1DDTANQADMDL=QTRUiUNQ?:2?
Comment fait-on pourecacementve`led"seriap\esrcesouvetr
Methodesimple , onremplituntableauaveclescasreeriadsvinndate on compare chaqueedsertuasuaelbatuntmelleusto`a _ complexiet en (c2).
p Leparadoxedesanniversairesditque365el`evessontsusants (enmoyenne)pouravoirunecollision d’anniversaire , deuxele`vesayantleuranniversaireleme^mejour. _
Peut-on faire mieux
?:
p Leparadoxedesanniversairesditque365el`evessontsusants , (enmoyenne)pouravoirunecollision d’anniversaire deuxele`vesayantleuranniversaireleme^mejour. _
3
Methodesimple onremplituntableauaveclescadetnnvidsaireersa , , on compare chaqueeabutauletnemlleusto`asdreutsa complexieten(c2. ) _
Comment fait-on pourecacementuoevcrsep\iaer"sdel`evesrt
_ Peut-on faire mieux ? OUI , ontrie le tableau onleparcourtenregarantsi2voisinssontegaux, complexietenclogc). _ (
DTAH1DAHATDDAQNLMDTR=QNUNQiUUADCDiLLQ
QMMDN“TiDT aN “5=LD5a
D(UATiRiQNaCTRQ,D=
On se donne un tableau decelments (des entiers par exemple) et unerelation d’ordre totale. one ectueuntri par comparaisonutilisant uniquement , lacomplexietestlenombredecomparaisons.
Les algorithmesenteelexicomptuneesonriatneml
Lesmeilleursalgorithmesontunecomplexieten

 c2.
(clog(c).
En autorisant plus que des comparaisons on peut parfois faire(c). ,
LDMD4Ti
:x:iT5vDL=5LDa0UDaSQMDbRLDiNiiCD QNU
QMRLDbiDC5NULDRiTDA5U Tempsdecalculdanslepirecaspourlesenteresdetaillecee x
QMRLDbiDMQcDNND Temps de calcul moyen sur toutes les enteres de taille
5
( max,(x). , c) = {x,jxj=cg
c.
X ( ( (x. ,ac) =ecx),) , jxj=c
( ec)utseidenirtsbutiondeprobabiltieuslrsenerteiltadeesle
cee x
3T9){}}DRAH5T5Mı¸TNQaATDH5A5M`NAQRTaiNUDiR5TN2iTiQ{{
01
} h361\%)] 0 had,
00 00
0iov*f=gb[fcg_bc[hh"idh* 1idh&[&\ah,d 2>cf "[0), [-b, [%%) 3had 0 h361[], 4\ 0 [-), 5kM[_= ""\ >0 ()& " 6h,]\163h0])%\163 7\-,
h361\] > had
L’elmentistrangeemrapselii 1 premierseinttmre`dase(j)esl ou^teaupirei een moi inesrerunelment c yenn2, complexietenc2nversementtrie)dalenserip(saclbatiuae , complexietmoyenne en c2 aussi.
h36&idhb)
6:
3Ti5 =aLLDU
Liedeestdefaireremonterlesgrandseenm`ats nlataduulbael on parcourt le tableau en comparant l’elmentiaui et on+ 1 , lesinversesiencessaire _, , a`la nduparcoursledernierelment est le plus grand apr`esiparcours lesiplus grandsent`atssomenl.aln on faitc uocrtesratalaelbstueitre.1ap
Complexiet:one ectue(c compa- ) () parcours comportant c raisons`achaquefois , letria`bullesaunecomplexietde c2dans le pire cas et en moyenne.
, Pourameliorerunpeulesperformancesonarer^teletrid`esque lundesparcoursninverseaucunelments. Ce tri ne fait que(c.eriaelbatnuta`jedupara)comssurison
7
3TiEaUiQN 2iA5 M5TAHD RQaTN`A5 M5TAHD RQaT N

Inesrerunemenlnsuntsdalbattuaeeiru^oc(tec) , fusionner deux tableaux de taillec2ico^uteauss(c).
Oncherche`aerduireleproble`me , on coupe le tableau en deux , ontriechaquemoitei on fusionne.
:
Lecuo^ttotalestceluidesfusions chaquefusioncuo^te(g e), lecuo^ttotalet(clog( , sc) dans le pire cas et en moyenne.
:8
3TiEaUiQN FaUiQNCDUUQaU-5=LD5ab
Oncommenceparrecopier\dosa`dos"les2tableaux(cou^t

c) ( ,
puisonparcourtparlesdeuxboutsenavancantdupluspetitoc^et `achaquefois(cou^t(c) aussi).
9
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.