La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

Du même publieur

´ 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?
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin