Ecole Normale Superieure Departement d'Informatique

Publié par

Niveau: Supérieur
Ecole Normale Superieure 2007-2008 Departement d'Informatique Algorithmique et Programmation Partiel Notes de cours autorisees a l'exception de tout autre document Exercice 1 Premiere Partie : structures de donnees pour le probleme des ensembles disjointes. Etant donne un ensemble, il est souvent utile de le partitionner en un certain nombre de sous-ensembles disjoints. Une structure de donnees pour le probleme des ensembles disjoints est une structure de donnees qui maintient une telle partition. Un algorithme union-find est un algorithme qui fournit deux operations essentielles sur une telle structure : – Find : determine l'ensemble contenant un element. Notamment utile pour determiner si deux elements appartiennent au meme ensemble. – Union : reunit deux ensemble en un seul. L'autre operation importante, Make, construit un ensemble contenant un unique element (un single- ton). A l'aide de ses trois operations, beaucoup de problemes de partitionnement peuvent etre resolus. Afin de definir ces operations plus precisement, il faut choisir un moyen de representer les ensembles. L'approche classique consiste a selectionner un element particulier, appele le representant, pour repre- senter l'ensemble toute entier. Des lors, Find(x) renvoie le representant de l'ensemble de x. Nous ferons dependre l'analyse du temps d'execution des structures de donnees d'ensembles disjoints de deux parametres : n, le nombre d'operations Make et m ≥ n le nombre total d'operations Make, Union et Find.

  • temps constant

  • arbre

  • poids

  • probleme du voyageur de commerce

  • arbres couvrants du graphe


Publié le : mardi 29 mai 2012
Lecture(s) : 22
Source : di.ens.fr
Nombre de pages : 6
Voir plus Voir moins
´ EcoleNormaleSup´erieure D´epartementdInformatique
Exercice 1
Algorithmique et Programmation Partiel
Notesdecoursautorise´esa`lexceptiondetoutautredocument
2007-2008
Premie`rePartie:structuresdedonn´eespourleproble`medesensemblesdisjointes.
´ Etantdonne´unensemble,ilestsouventutiledelepartitionnerenuncertainnombredesous-ensembles disjoints.Unestructurededonne´espourleniojstneesdesedssibmell`emprobest une structure de donn´eesquimaintientunetellepartition.Unalgorithmeunion-findest un algorithme qui fournit deuxop´erationsessentiellessurunetellestructure: Findrmte´e:dnseelinnocelbmenutnanetmierrsneeuidelx´eme´stn´el´ement.Notammneutitelopru´dte appartiennentaumeˆmeensemble. Unionneelbmesnexuedti´eun:r.ulseun Lautreope´rationimportante,Makeunt(enem-lengsicelbetnoenutmesnueiql´´entnaununconstrui, ` ton).Alaidedesestroisop´erations,beaucoupdeproble`mesdepartitionnementpeuventeˆtrer´esolus.
Andede´nircesop´erationspluspre´cise´ment,ilfautchoisirunmoyenderepr´esenterlesensembles. Lapprocheclassiqueconsistea`s´electionnerun´el´ementparticulier,appel´eleneattnrpe´rsee-p,rrour´ep senterlensembletouteentier.De`slors,Find(xlerevnio)erldenttaenesr´epedelbmesnex.
Nousferonsd´ependre dedeuxparame`tres: UnionetFind.
lanalysedutempsdex´ecutiondes nbmonel,´eopdresontiraMakeet
structures mnle
dedonn´eesdensemblesdisjoints nombretotaldope´rationsMake,
1.Proposerunalgorithmesimpleutilisantunestructurededonn´eesdensemblesdisjointsquipre-nantenentr´eeungraphenon-oriente´retournelalistedesescomposantesconnexes. 2.Proposerunestructurededonne´essimplepourleproble`medesensemblesdisjoints,utilisant deslisteschaıˆne´es,pourlaquellelesop´erationsMakeetFinds’effectue en temps constant et lope´rationUnionenO(mspmetelruce´xednsdaontiderepilecssadnueo)atiop´eronnens.D se´quencedop´erationsMakeetUnionen fonction dem. 3.Montrerquenconcat´enanttoujourslalistelapluscourte`alapluslongue,unes´equence dop´erationsprenduntempsenO(m+nlogn).
Pouruneimplantationplusecace,nousproposonsderepre´senterlesensemblesparunefamille darbresou`chaquenœudcontientune´le´mentetchaquearbrerepr´esenteunsous-ensemble.Lope´ration Makerateuluesduœnol,re´p´ecrnaeurerbun`aFindetruopnier(spse`est´notlessuip[a`quus)j] rencontrerlaracinedelarbreetlop´erationUnionfait pointer la racine d’un arbre vers la racine de l’autre.
F(i) Nousd´enissonsre´cursivementunefonctionF:NNparF(0) = 1 etF(ipour+ 1) = 2iN etnousutiliseronslanotationlogpourrepre´senterlelmhtiragoe´re´tieousdquenisso´enmmesnoc l’inverse deF: log(n) = min{i0, F(i)n}pour toutnN.
4.Danschaquenœud,nousmaintenonsa`jourunrangqui sera une approximation du logarithme de la taille du sous-arbre : Make(x) p[x] :=x rang[x] := 0 Find(x) six=p[x]alors retournerp[x] sinon retournerFind(p[x]) Union(x,y) 0 0 x:=Find(x) ;y:=Find(y) 0 0 sirang[x]> rang[y] 0 0 alorsp[y] :=x 0 0 sinonp[x] :=y 0 0 sirang[x] =rang[y] 0 0 alorsrang[y] :=rang[y] + 1 Donnerlacomplexite´,enfonctiondemet denonsratiop´ecedneuqe´senud,Make,Unionet Findutilisant cette implantation. 5.De´sormais,danslop´erationFind, nous ferons pointer chaque nœud de la route directe sur la racine de l’arbre. Find(x) six6=p[x]alorsp[x] :=Find(p[x]) retournerp[x] Lebutdecettequestionestdemontrerquunes´equencedemson´eoptiraMake,UnionetFind parmi lesquellesn´eraesopstionnodtsMakepsce´xesmetneetuO(mlogn) dans le pire des cas. (a) Ennotanttaille[xaelrerbraenn´cionelerbmœneddsdunee]x, y compris le nœudxlui rang[x] meˆme,montrerquetaille[x]2 . r (b) Montrerque pour tout entierr0, il existe au plusn/de rang2 nœudsr. (c) Nouspartitionnons les rangs des nœuds en plusieursblocs: le rangrse trouvant dans le bloc log (r) pour toutr∈ {0, . . . ,blognc}et nous notonsb(v) le bloc correspondant au rang d’un nœudv. Pour laie`-xeemuce´noitlde´eoptiraonFind, notonsXiese´srevesnltedesemblstranœud Wi={vXi|vest la racine ou un fils de la racine} Yi={vXi\Wi|b(v)< b(p[v])} Zi={vXi\Xi|b(v) =b(p[v])} i. Montrerqu’il y a au plus 2n/F(t) nœuds de rangt. ii. Montrerque X #Zi2n((1 + logn)) i iii.End´eduireque X #Xi=O(mlog (n)) i (d) Conclure
Deuxie`mepartie:arbrescouvrantsminimauxetalgorithmedeKruskal.
´ Etantdonn´eungraphenonoriente´etconnexe,unarbre couvrantde ce graphe est un sous-ensemble qui est un arbre et qui connecte tous les sommets ensemble.Unarbre couvrant de poids minimald’un graphevalu´eestunarbrecouvrantdontlepoidsestleminimumparmitouslesarbrescouvrantsdu graphe.
SoitAEunsouulcnisetusnadsesmbseens-ˆeardledleinamreconarbntmiuvraG(teraeˆU.enu, v) est diteerusˆpourAsi l’ensembleA∪ {(u, v)}est inclus dans un arbre couvrant minimal deG. Nous avonsalorslalgorithmege´n´eriquesuivantdecalculdunarbrecouvrantminimal:
A:=tant queAne forme pas un arbre couvrant minimal fairechoisiruneare^tes^ure(u, v)pourA A=A∪ {(u, v)} retournerA 6. Proposerun invariant pour cet algorithme et prouver sa terminaison. 7. Unecoupeest une partition (S, V\E) deVU.enraeˆettraverseune coupe (S, V\S) si elle part deSet arrive enV\S. Une coupe respecte un sous-ensembleAsstelnidˆeareˆraetpaydsa deAaverse.Uquilatrsetenraeˆetclairesi elle traverse la coupe et est de poids minimal. Soit un sous-ensembleAdeEqui est inclus dans un arbre couvrant minimal, soit (S, V\S) une coupe qui respecteAet soit (u, v)unearˆeteclairertre(quuopecalrepuonoM.u, v)ˆtusrees pourA. 8. Soitun sous-ensembleAdeEqui est inclus dans un arbre couvrant minimal, et soitC= (VC, EC) unecomposanteconnexedanslaforeˆtGA= (V, A). Montrer que si (u, vealriunst)eecetrˆea reliantCnoceexened`uatrecneausantompoGA, alors (u, vuor)esˆstepurA. 9. Soit(u, vrangsuanldmanimiehp)unearˆetedepoidsG. Montrer que (u, vnt`artieappanu) arbre couvrant deG. ´ Etantdonne´ungrapheGet un arbre couvrant minimalTpourGruaee-ˆteltixesieturepn, (u, v) deG`aentiastpanirapplamiuqtepoidsmindeT? 10. En1956,Krusalithmlgorelapos´paor:tnaviuse E:=pour chaque sommetvdeG faireMake(v) trierlesar^etesdeGpar ordre croissant de poids pourchaqueare^te(u, v)deGprise par ordre de poids croissant faire siFind(u)6=Find(v) alorsajouterlar^ete(u, v)l`aneesbmelE Union(u, v) retournerE Prouverlavalidite´delalgorithmedeKruskaletdonnersacomplexit´e. 11.Supposonsquedansungraphevalu´enonorient´eG= (V, E),otsuelpsiosddraonssteˆeestd entiers compris entre 1 et|V|.Qutaloelesetpmsrel´xcedse?skaleKruhmedrotiagldnletuoi Quesepasse-t-ilsilespoidssontdesentiersborne´sparuneconstante?
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi