Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Algorithmique et Programmation Projet Plus petit ancetre commun

3 pages
Algorithmique et Programmation Projet : Plus petit ancetre commun Ecole normale superieure Departement d'informatique 2011-2012 Le probleme du Lowest Common Ancestor (LCA) est le suivant : etant deux noeuds u et v dans un arbre donne, il s'agit de trouver quel est l'ancetre commun a u et a v qui est le plus eloigne possible de la racine. Il existe un algorithme quasi-trivial qui resout la question en temps O (h) ou h designe la hauteur de l'arbre. On pourrait aussi precalculer le resultat pour toutes les paires de sommets, afin de pouvoir repondre en temps constant, mais apres un precalcul en O ( n2 ) , et en utilisant un espace O ( n2 ) . On sait depuis 1984 [3] qu'il est possible de resoudre le probleme en temps constant, si on a pu faire au prealable un precalcul lineaire en la taille de l'arbre. Le but de ce projet est de programmer un algorithme exhibant ces performances. 1 Correspondance avec Range Minimum Queries Le probleme Lowest Common Ancestor est etroitement lie a un autre probleme, Range Minimum Queries. Dans cet autre probleme, on a un tableau A contenant n entiers, et il s'agit de calculer RMQA(i, j) = arg min i≤k≤j A[k] ou arg mink .

  • bloc quelconque

  • zero dans l'ordre du parcours prefixe

  • minimum de l'intervalle

  • probleme du lowest common

  • arbre

  • probleme rmq

  • arbre binaire

  • bloc


Voir plus Voir moins
Algorithmique et Projet : Plus petit
Programmation anceˆtrecommun
Ecolenormalesup´erieure De´partementdinformatique td-algo@di.ens.fr 2011-2012
Leprobl`emeduLowest Common Ancestor (LCA)seoduuenxltseet:´tdanuiesntvauetvdans un arbredonn´e,ilsagitdetrouverquelestlancˆetrecommun`auet`avseiupelt´sulioleqgn´epossibledela racine.Ilexisteunalgorithmequasi-trivialquire´soutlaquestionentempsO(ho)u`hruetlee´nigsuahda delarbre.Onpourraitaussipre´calculerler´esultatpourtouteslespairesdesommets,andepouvoir    2 2 re´pondreentempsconstantr,`measisap´ecaunprneclluOn, et en utilisant un espaceOn. Onsaitdepuis1984[3]quilestpossibleder´esoudreleprobl`emeentempsconstant,sionapufaire aupr´ealableunpr´ecalculeriae´nilen la taille de l’arbre. Le but de ce projet est de programmer un algorithme exhibant ces performances.
1 CorrespondanceavecRange Minimum Queries Leproble`meLowest Common Ancestorutreprobl`eme,metiltne`e´ianuat´esroetRange Minimum Queries. Danscetautreproble`me,onauntableauAcontenantnentiers, et il s’agit de calculer RMQ(i, jmin) = argA[k] A ikj o`uargmink. . .elavaleurdde´esignkpour laquelle le minimum est atteint. En effet, on peut utiliser RMQeoudrr´esruopLCA. pr´ecalcullbcednuoOaeledetrˆeaquhatceenosiup,erbreunuapcruosruE´leriendugrapher´etlustna en partant de la racine (en d’autres termes, on fait un parcours en profondeur de l’arbre, mais on ignorepaslessommetsd´eja`vus).Onstockeleistn´rdenaeudrenco-`emenoA[i], et on stocke sa hauteur dansB[icemmoC.]ioesnufe´seevaresttreteeearˆhaquisfomoenanntt,sedndnecetnaenut la taille deAetBest 2nque)itsuelx´euedatropmiaalsnadtn1.Onnote(cesertndse´emeB di`erentexactementduneunit´e.Ond´enite´galementlapremie`reoccurrencedeidansA: C[i] = arg min{k:A[k] =i} Ge´n´ererlestroistableauxA,BetCse.eemernetntiafialclsnietpmernee´iaillelataarbrdel´ Partie “en-ligne”peiaeredosmmtesnttaEun´enndouetv, il est clair (et on admettra) que leur plus petitancˆetrecommunestvisite´entreuetvsniusleenI.irneul´e´eeEournslatnadtleseuetqcsi `sivde´tieme`ueon-i,alorsC[u]`C[v], et clairementB[`] est minimal dans l’intervalle. On a donc :h i   LCAT(u, v) =ARMQC[u], C[v] B
Si on est capable de calculerRMQen tempsOr´ecalculen1(a)rpe`uspnO(ncestgagn´e.),
2Range Minimum Queriesecav´eprlccaenulO(nlogn) Defac¸onpresqueamusante(maiscestunph´enom`ener´ecurrent),undesingre´dientsclefdelasolution optimaleestunalgorithmesous-optimal.Danscettesectiononveutre´soudreleprobl`emeRMQsur un tableauAden.tseneml´´e   j pre´calculriLeed´dtse´rpelaceelucT[i, j] =RMQi, i+ 21 pourtoutes lesO(logn) valeurs A admissibles dej. Ceci peut se faire en tempsO(nlogn) par programmation dynamique.
1
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