Ecole Normale Superieure Departement d'Informatique

Description

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

Sujets

• Problème du voyageur de commerce

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 25
• Langue: Français

Extrait

´ EcoleNormaleSup´erieure D´epartementd’Informatique

Exercice 1

Algorithmique et Programmation Partiel

Notesdecoursautorise´esa`l’exceptiondetoutautredocument

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:dns’eelinnocelbmenutnanetmierrsneeuidelx´eme´stn´el´ement.Notammneutitelopru´dte appartiennentaumeˆmeensemble. –Unionneelbmesnexuedti´eun:r.ulseun L’autreope´rationimportante,Makeunt(enem-lengsicelbetnoenutmesnueiql´´entnaununconstrui, ` ton).Al’aidedesestroisop´erations,beaucoupdeproble`mesdepartitionnementpeuventeˆtrer´esolus.

Afindede´finircesop´erationspluspre´cise´ment,ilfautchoisirunmoyenderepr´esenterlesensembles. L’approcheclassiqueconsistea`s´electionnerun´el´ementparticulier,appel´eleneattnrpe´rsee-p,rrour´ep senterl’ensembletouteentier.De`slors,Find(xlerevnio)erl’denttaenesr´epedelbmesnex.

Nousferonsd´ependre dedeuxparame`tres: UnionetFind.

l’analysedutempsd’ex´ecutiondes nbmonel,´eopd’resontiraMakeet

structures m≥nle

dedonn´eesd’ensemblesdisjoints nombretotald’ope´rationsMake,

1.Proposerunalgorithmesimpleutilisantunestructurededonn´eesd’ensemblesdisjointsquipre- nantenentr´eeungraphenon-oriente´retournelalistedesescomposantesconnexes. 2.Proposerunestructurededonne´essimplepourleproble`medesensemblesdisjoints,utilisant deslisteschaıˆne´es,pourlaquellelesop´erationsMakeetFinds’effectue en temps constant et l’ope´rationUnionenO(mspmetelruce´xe’dnsdaontiderepilecssa’dnueo)atiop´eronnens.D se´quenced’op´erationsMakeetUnionen fonction dem. 3.Montrerqu’enconcat´enanttoujourslalistelapluscourte`alapluslongue,unes´equence d’op´erationsprenduntempsenO(m+nlogn).

Pouruneimplantationplusefficace,nousproposonsderepre´senterlesensemblesparunefamille d’arbresou`chaquenœudcontientune´le´mentetchaquearbrerepr´esenteunsous-ensemble.L’ope´ration Makerateuluesduœno’l,re´p´ecrnaeurerbun`aFindetruopnier(spse`est´notlessuip[∙a`’quus)j] rencontrerlaracinedel’arbreetl’op´erationUnionfait pointer la racine d’un arbre vers la racine de l’autre.

F(i) Nousd´efinissonsre´cursivementunefonctionF:N→NparF(0) = 1 etF(ipour+ 1) = 2i∈N ∗ etnousutiliseronslanotationlogpourrepre´senterlelmhtiragoe´re´tieousdquenisso´efinmmesnoc ∗ l’inverse deF: log(n) = min{i≥0, F(i)≥n}pour toutn∈N.

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´eced’neuqe´senu’d,Make,Unionet Findutilisant cette implantation. 5.De´sormais,dansl’op´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] Lebutdecettequestionestdemontrerqu’unes´equencedemson´eoptiraMake,UnionetFind ∗ parmi lesquellesn´eraesopstionnodtsMakepsce´xe’smetneetuO(mlogn) dans le pire des cas. (a) Ennotanttaille[x’aelrerbraenn´cionelerbmœneddsdunee]x, y compris le nœudxlui rang[x] meˆme,montrerquetaille[x]≥2 . r (b) Montrerque pour tout entierr≥0, 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´noitl’de´eoptiraonFind, notonsX i ese´sreve’snltedesemblstranœud W i ={v∈X i |vest la racine ou un fils de la racine} Y i ={v∈X i \W i |b(v)< b(p[v])} Z i ={v∈X i \X i |b(v) =b(p[v])} i. Montrerqu’il y a au plus 2n/F(t) nœuds de rangt. ii. Montrerque X ∗ #Z i ≤2n((1 + logn)) i iii.End´eduireque X ∗ #X i =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.

SoitA⊆Eunsouulcnisetusnadsesmbseens-ˆeard’ledleinamreconarbntmiuvraG(teraeˆU.enu, v) est diteerusˆpourAsi l’ensembleA∪ {(u, v)}est inclus dans un arbre couvrant minimal deG. Nous avonsalorsl’algorithmege´n´eriquesuivantdecalculd’unarbrecouvrantminimal:

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-ensembleAssteln’id’ˆeareˆraetpay’’dsa 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= (V C , E C ) unecomposanteconnexedanslaforeˆtG A = (V, A). Montrer que si (u, vealriunst)eecetrˆea reliantCnoceexened`uatrecneausantompoG A , 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`aentiastpa’nirapplamiuqtepoidsmindeT? 10. En1956,Krusalithmlgorel’apos´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) alorsajouterl’ar^ete(u, v)l’`aneesbmelE Union(u, v) retournerE Prouverlavalidite´del’algorithmedeKruskaletdonnersacomplexit´e. 11.Supposonsquedansungraphevalu´enonorient´eG= (V, E),otsuelpsiosd’draonssteˆeestd entiers compris entre 1 et|V|.Qutaloelesetpmsrel´xcedse’?skaleKruhmedrotia’gldnletuoi Quesepasse-t-ilsilespoidssontdesentiersborne´sparuneconstante?