958 resultados para A* search algorithm
Resumo:
In this thesis we are going to analyze the dictionary graphs and some other kinds of graphs using the PagerRank algorithm. We calculated the correlation between the degree and PageRank of all nodes for a graph obtained from Merriam-Webster dictionary, a French dictionary and WordNet hypernym and synonym dictionaries. Our conclusion was that PageRank can be a good tool to compare the quality of dictionaries. We studied some artificial social and random graphs. We found that when we omitted some random nodes from each of the graphs, we have not noticed any significant changes in the ranking of the nodes according to their PageRank. We also discovered that some social graphs selected for our study were less resistant to the changes of PageRank.
Resumo:
In this thesis we study the properties of two large dynamic networks, the competition network of advertisers on the Google and Bing search engines and the dynamic network of friend relationships among avatars in the massively multiplayer online game (MMOG) Planetside 2. We are particularly interested in removal patterns in these networks. Our main finding is that in both of these networks the nodes which are most commonly removed are minor near isolated nodes. We also investigate the process of merging of two large networks using data captured during the merger of servers of Planetside 2. We found that the original network structures do not really merge but rather they get gradually replaced by newcomers not associated with the original structures. In the final part of the thesis we investigate the concept of motifs in the Barabsi-Albert random graph. We establish some bounds on the number of motifs in this graph.
Resumo:
We consider entry-level medical markets for physicians in the United Kingdom. These markets experienced failures which led to the adoption of centralized market mechanisms in the 1960's. However, different regions introduced different centralized mechanisms. We advise physicians who do not have detailed information about the rank-order lists submitted by the other participants. We demonstrate that in each of these markets in a low information environment it is not beneficial to reverse the true ranking of any two acceptable hospital positions. We further show that (i) in the Edinburgh 1967 market, ranking unacceptable matches as acceptable is not profitable for any participant and (ii) in any other British entry-level medical market, it is possible that only strategies which rank unacceptable positions as acceptable are optimal for a physician.
Resumo:
This short article will address the two following issues: the new vision of the Canadian constitutional order entertained by the Supreme Court in the Reference re Secession of Quebec (I) nd the impact of this new vision. upon the fate of Canada (II)
Resumo:
Le prsent mmoire comprend un survol des principales mthodes de rendu en demi-tons, de lanalog screening la recherche binaire directe en passant par lordered dither, avec une attention particulire pour la diffusion derreur. Ces mthodes seront compares dans la perspective moderne de la sensibilit la structure. Une nouvelle mthode de rendu en demi-tons par diffusion derreur est prsente et soumise diverses valuations. La mthode propose se veut originale, simple, autant mme de prserver le caractre structurel des images que la mthode ltat de lart, et plus rapide que cette dernire par deux trois ordres de magnitude. Dabord, limage est dcompose en frquences locales caractristiques. Puis, le comportement de base de la mthode propose est donn. Ensuite, un ensemble minutieusement choisi de paramtres permet de modifier ce comportement de faon pouser les diffrents caractres frquentiels locaux. Finalement, une calibration dtermine les bons paramtres associer chaque frquence possible. Une fois lalgorithme assembl, toute image peut tre traite trs rapidement : chaque pixel est attach une frquence propre, cette frquence sert dindice pour la table de calibration, les paramtres de diffusion appropris sont rcuprs, et la couleur de sortie dtermine pour le pixel contribue en esprance souligner la structure dont il fait partie.
Resumo:
La traduction statistique vise lautomatisation de la traduction par le biais de modles statistiques. Dans ce travail, nous relevons un des grands dfis du domaine : la recherche (Brown et al., 1993). Les systmes de traduction statistique de rfrence, tel Moses (Koehn et al., 2007), effectuent gnralement la recherche en explorant lespace des prfixes par programmation dynamique, une solution coteuse sur le plan computationnel pour ce problme potentiellement NP-complet (Knight, 1999). Nous postulons quune approche par recherche locale (Langlais et al., 2007) peut mener des solutions tout aussi intressantes en un temps et un espace mmoire beaucoup moins importants (Russell et Norvig, 2010). De plus, ce type de recherche facilite lincorporation de modles globaux qui ncessitent des traductions compltes et permet deffectuer des modifications sur ces dernires de manire non-continue, deux tches ardues lors de lexploration de lespace des prfixes. Nos expriences nous rvlent que la recherche locale en traduction statistique est une approche viable, sinscrivant dans ltat de lart.
Resumo:
Cette thse porte sur les problmes de tournes de vhicules avec fentres de temps o un gain est associ chaque client et o l'objectif est de maximiser la somme des gains recueillis moins les cots de transport. De plus, un mme vhicule peut effectuer plusieurs tournes durant l'horizon de planification. Ce problme a t relativement peu tudi en dpit de son importance en pratique. Par exemple, dans le domaine de la livraison de denres prissables, plusieurs tournes de courte dure doivent tre combines afin de former des journes compltes de travail. Nous croyons que ce type de problme aura une importance de plus en plus grande dans le futur avec l'avnement du commerce lectronique, comme les piceries lectroniques, o les clients peuvent commander des produits par internet pour la livraison domicile. Dans le premier chapitre de cette thse, nous prsentons d'abord une revue de la littrature consacre aux problmes de tournes de vhicules avec gains ainsi qu'aux problmes permettant une rutilisation des vhicules. Nous prsentons les mthodologies gnrales adoptes pour les rsoudre, soit les mthodes exactes, les mthodes heuristiques et les mta-heuristiques. Nous discutons enfin des problmes de tournes dynamiques o certaines donnes sur le problme ne sont pas connues l'avance. Dans le second chapitre, nous dcrivons un algorithme exact pour rsoudre un problme de tournes avec fentres de temps et rutilisation de vhicules o l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problme est modlis comme un problme de tournes avec gains. L'algorithme exact est bas sur une mthode de gnration de colonnes couple avec un algorithme de plus court chemin lmentaire avec contraintes de ressources. Pour rsoudre des instances de taille raliste dans des temps de calcul raisonnables, une approche de rsolution de nature heuristique est requise. Le troisime chapitre propose donc une mthode de recherche adaptative grand voisinage qui exploite les diffrents niveaux hirarchiques du problme (soit les journes compltes de travail des vhicules, les routes qui composent ces journes et les clients qui composent les routes). Dans le quatrime chapitre, qui traite du cas dynamique, une stratgie d'acceptation et de refus des nouvelles requtes de service est propose, base sur une anticipation des requtes venir. L'approche repose sur la gnration de scnarios pour diffrentes ralisations possibles des requtes futures. Le cot d'opportunit de servir une nouvelle requte est bas sur une valuation des scnarios avec et sans cette nouvelle requte. Enfin, le dernier chapitre rsume les contributions de cette thse et propose quelques avenues de recherche future.
Resumo:
Les rseaux optiques commutation de rafales (OBS) sont des candidats pour jouer un rle important dans le cadre des rseaux optiques de nouvelle gnration. Dans cette thse, nous nous intressons au routage adaptatif et au provisionnement de la qualit de service dans ce type de rseaux. Dans une premire partie de la thse, nous nous intressons la capacit du routage multi-chemins et du routage alternatif (par dflection) amliorer les performances des rseaux OBS, pro-activement pour le premier et r-activement pour le second. Dans ce contexte, nous proposons une approche base sur lapprentissage par renforcement o des agents placs dans tous les nuds du rseau cooprent pour apprendre, continuellement, les chemins du routage et les chemins alternatifs optimaux selon ltat actuel du rseau. Les rsultats numriques montrent que cette approche amliore les performances des rseaux OBS comparativement aux solutions proposes dans la littrature. Dans la deuxime partie de cette thse, nous nous intressons au provisionnement absolu de la qualit de service o les performances pire-cas des classes de trafic de priorit leve sont garanties quantitativement. Plus spcifiquement, notre objectif est de garantir la transmission sans pertes des rafales de priorit leve lintrieur du rseau OBS tout en prservant le multiplexage statistique et lutilisation efficace des ressources qui caractrisent les rseaux OBS. Aussi, nous considrons lamlioration des performances du trafic best effort. Ainsi, nous proposons deux approches : une approche base sur les nuds et une approche base sur les chemins. Dans lapproche base sur les nuds, un ensemble de longueurs donde est assign chaque nud du bord du rseau OBS pour quil puisse envoyer son trafic garanti. Cette assignation prend en considration les distances physiques entre les nuds du bord. En outre, nous proposons un algorithme de slection des longueurs donde pour amliorer les performances des rafales best effort. Dans lapproche base sur les chemins, le provisionnement absolu de la qualit de service est fourni au niveau des chemins entre les nuds du bord du rseau OBS. cette fin, nous proposons une approche de routage et dassignation des longueurs donde qui a pour but la rduction du nombre requis de longueurs donde pour tablir des chemins sans contentions. Nanmoins, si cet objectif ne peut pas tre atteint cause du nombre limit de longueurs donde, nous proposons de synchroniser les chemins en conflit sans le besoin pour des quipements additionnels. L aussi, nous proposons un algorithme de slection des longueurs donde pour les rafales best effort. Les rsultats numriques montrent que lapproche base sur les nuds et lapproche base sur les chemins fournissent le provisionnement absolu de la qualit de service pour le trafic garanti et amliorent les performances du trafic best effort. En outre, quand le nombre de longueurs dondes est suffisant, lapproche base sur les chemins peut accommoder plus de trafic garanti et amliorer les performances du trafic best effort par rapport lapproche base sur les nuds.
Resumo:
Les habitudes de consommation de substances psychoactives, le stress, lobsit et les traits cardiovasculaires associs seraient en partie relis aux mmes facteurs gntiques. Afin dexplorer cette hypothse, nous avons effectu, chez 119 familles multi-gnrationnelles qubcoises de la rgion du Saguenay-Lac-St-Jean, des tudes dassociation et de liaison pangnomiques pour les composantes gntiques : de la consommation usuelle dalcool, de tabac et de caf, de la rponse au stress physique et psychologique, des traits anthropomtriques relis lobsit, ainsi que des mesures du rythme cardiaque (RC) et de la pression artrielle (PA). 58000 SNPs et 437 marqueurs microsatellites ont t utiliss et lannotation fonctionnelle des gnes candidats identifis a ensuite t ralise. Nous avons dtect des corrlations phnotypiques significatives entre les substances psychoactives, le stress, lobsit et les traits hmodynamiques. Par exemple, les consommateurs dalcool et de tabac ont montr un RC significativement diminu en rponse au stress psychologique. De plus, les consommateurs de tabac avaient des PA plus basses que les non-consommateurs. Aussi, les hypertendus prsentaient des RC et PA systoliques accrus en rponse au stress psychologique et un indice de masse corporelle (IMC) lev, comparativement aux normotendus. Dautre part, lutilisation de tabac augmenterait les taux corporels dpinphrine, et des niveaux levs dpinphrine ont t associs des IMC diminus. Ainsi, en accord avec les corrlations inter-phnotypiques, nous avons identifi plusieurs gnes associs/lis la consommation de substances psychoactives, la rponse au stress physique et psychologique, aux traits relis lobsit et aux traits hmodynamiques incluant CAMK4, CNTN4, DLG2, DAG1, FHIT, GRID2, ITPR2, NOVA1, NRG3 et PRKCE. Ces gnes codent pour des protines constituant un rseau dinteractions, impliques dans la plasticit synaptique, et hautement exprimes dans le cerveau et ses tissus associs. De plus, lanalyse des sentiers de signalisation pour les gnes identifis (P = 0,03) a rvl une induction de mcanismes de Potentialisation Long Terme. Les variations des traits tudis seraient en grande partie lies au sexe et au statut dhypertension. Pour la consommation de tabac, nous avons not que le degr et le sens des corrlations avec lobsit, les traits hmodynamiques et le stress sont spcifiques au sexe et la pression artrielle. Par exemple, si des variations ont t dtectes entre les hommes fumeurs et non-fumeurs (anciens et jamais), aucune diffrence na t observe chez les femmes. Nous avons aussi identifi de nombreux traits relis lobsit dont la corrlation avec la consommation de tabac apparat essentiellement plus lie des facteurs gntiques quau fait de fumer en lui-mme. Pour le sexe et lhypertension, des diffrences dans lhritabilit de nombreux traits ont galement t observes. En effet, des analyses gntiques sur des sous-groupes spcifiques ont rvl des gnes additionnels partageant des fonctions synaptiques : CAMK4, CNTN5, DNM3, KCNAB1 (spcifique lhypertension), CNTN4, DNM3, FHIT, ITPR1 and NRXN3 (spcifique au sexe). Ces gnes codent pour des protines interagissant avec les protines de gnes dtects dans lanalyse gnrale. De plus, pour les gnes des sous-groupes, les rsultats des analyses des sentiers de signalisation et des profils dexpression des gnes ont montr des caractristiques similaires celles de lanalyse gnrale. La convergence substantielle entre les dterminants gntiques des substances psychoactives, du stress, de lobsit et des traits hmodynamiques soutiennent la notion selon laquelle les variations gntiques des voies de plasticit synaptique constitueraient une interface commune avec les diffrences gntiques lies au sexe et lhypertension. Nous pensons, galement, que la plasticit synaptique interviendrait dans de nombreux phnotypes complexes influencs par le mode de vie. En dfinitive, ces rsultats indiquent que des approches bases sur des sous-groupes et des rseaux amlioreraient la comprhension de la nature polygnique des phnotypes complexes, et des processus molculaires communs qui les dfinissent.
Resumo:
Le problme de localisation-routage avec capacits (PLRC) apparat comme un problme cl dans la conception de rseaux de distribution de marchandises. Il gnralisele problme de localisation avec capacits (PLC) ainsi que le problme de tournes de vhicules multiples dpts (PTVMD), le premier en ajoutant des dcisions lies au routage et le deuxime en ajoutant des dcisions lies la localisation des dpts. Dans cette thse on dvelope des outils pour rsoudre le PLRC laide de la programmation mathmatique. Dans le chapitre 3, on introduit trois nouveaux modles pour le PLRC bass sur des ots de vhicules et des ots de commodits, et on montre comment ceux-ci dominent, en termes de la qualit de la borne infrieure, la formulation originale deux indices [19]. Des nouvelles ingalits valides ont t dvelopes et ajoutes aux modles, de mme que des ingalits connues. De nouveaux algorithmes de sparation ont aussi t dvelops qui dans la plupart de cas gnralisent ceux trouvs dans la litterature. Les rsultats numriques montrent que ces modles de ot sont en fait utiles pour rsoudre des instances de petite moyenne taille. Dans le chapitre 4, on prsente une nouvelle mthode de gnration de colonnes base sur une formulation de partition densemble. Le sous-problme consiste en un problme de plus court chemin avec capacits (PCCC). En particulier, on utilise une relaxation de ce problme dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complt par des nouvelles coupes qui permettent de rduire encore davantage le saut dintgralit en mme temps que de dfavoriser lapparition de cycles dans les routes. Ces rsultats suggrent que cette mthode fournit la meilleure mthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle mthode heuristique pour le PLRC. Premirement, on dmarre une mthode randomise de type GRASP pour trouver un premier ensemble de solutions de bonne qualit. Les solutions de cet ensemble sont alors combines de faon les amliorer. Finalement, on dmarre une mthode de type dtruir et rparer base sur la rsolution dun nouveau modle de localisation et raffectation qui gnralise le problme de raffectaction [48].
Resumo:
Thse ralise en cotutelle avec l'Universit d'Avignon.
Resumo:
Nous proposons de construire un atlas numrique 3D contenant les caractristiques moyennes et les variabilits de la morphologie dun organe. Nos travaux seront appliqus particulirement la construction d'un atlas numrique 3D de la totalit de la corne humaine incluant la surface antrieure et postrieure partir des cartes topographiques fournies par le topographe Orbscan II. Nous procdons tout d'abord par normalisation de toute une population de cornes. Dans cette tape, nous nous sommes bass sur l'algorithme de recalage ICP (iterative closest point) pour aligner simultanment les surfaces antrieures et postrieures d'une population de corne vers les surfaces antrieure et postrieure d'une corne de rfrence. En effet, nous avons labor une variante de l'algorithme ICP adapt aux images (cartes) de cornes qui tient compte de changement d'chelle pendant le recalage et qui se base sur la recherche par voisinage via la distance euclidienne pour tablir la correspondance entre les points. Aprs, nous avons procd pour la construction de l'atlas cornen par le calcul des moyennes des lvations de surfaces antrieures et postrieures recales et leurs carts-types associs. Une population de 100 cornes saines a t utilise pour construire l'atlas cornen normal. Pour visualiser latlas, on a eu recours des cartes topographiques couleurs similairement ce quoffrent dj les systmes topographiques actuels. Enfin, des observations ont t ralises sur l'atlas cornen refltant sa prcision et permettant de dvelopper une meilleure connaissance de lanatomie cornenne.
Resumo:
Thse ralise en cotutelle entre l'Universit de Montral et l'Universit de Technologie de Troyes
Resumo:
Utilisant les plus recentes donnees recueillies par le detecteur ATLAS lors de collisions pp a 7 et 8 TeV au LHC, cette these etablira des contraintes severes sur une multitude de modeles allant au-dela du modele standard (MS) de la physique des particules. Plus particulierement, deux types de particules hypothetiques, existant dans divers modeles theoriques et qui ne sont pas presentes dans le MS, seront etudies et sondes. Le premier type etudie sera les quarks-vectoriels (QV) produits lors de collisions pp par lentremise de couplages electrofaibles avec les quarks legers u et d. On recherchera ces QV lorsquils se desintegrent en un boson W ou Z, et un quark leger. Des arguments theoriques etablissent que sous certaines conditions raisonnables la production simple dominerait la production en paires des QV. La topologie particuliere des evenements en production simple des QV permettra alors la mise en oeuvre de techniques doptimisation efficaces pour leur extraction des bruits de fond electrofaibles. Le deuxieme type de particules recherche sera celles qui se desintegrent en WZ lorsque ces bosons de jauges W, et Z se desintegrent leptoniquement. Les etats finaux detectes par ATLAS seront par consequent des evenements ayant trois leptons et de lenergie transverse manquante. La distribution de la masse invariante de ces objets sera alors examinee pour determiner la presence ou non de nouvelles resonances qui se manifesterait par un exces localise. Malgre le fait qua premiere vue ces deux nouveaux types de particules nont que tres peu en commun, ils ont en realite tous deux un lien etroit avec la brisure de symetrie electrofaible. Dans plusieurs modeles theoriques, lexistence hypothetique des QV est propose pour annuler les contributions du quark top aux corrections radiatives de la masse du Higgs du MS. Parallelement, dautres modeles predisent quant a eux des resonances en WZ tout en suggerant que le Higgs est une particule composite, chambardant ainsi tout le sector Higgs du MS. Ainsi, les deux analyses presentees dans cette these ont un lien fondamental avec la nature meme du Higgs, elargissant par le fait meme nos connaissances sur lorigine de la masse intrinseque des particules. En fin de compte, les deux analyses nont pas observe dexces significatif dans leurs regions de signal respectives, ce qui permet detablir des limites sur la section efficace de production en fonction de la masse des resonances.
