Spelling suggestions: "subject:"algorithme A*"" "subject:"lalgorithme A*""
251 |
Algorithmic Contributions to Computational Molecular BiologyVialette, Stéphane 01 June 2010 (has links) (PDF)
Nous présentons ici nos résultats de recherche depuis 2001 sur l'algorithmique des graphes linéaires, la recherche de motif (avec ou sans topologie) dans les graphes, et la génomique comparative.
|
252 |
Diagnostic et suivi d'état embarqués -- Une étude algorithmique.Fabien, Aratbi-Perrot 01 July 2011 (has links) (PDF)
La problématique de cette thèse a été d'étudier les systèmes pouvant (se) diagnostiquer en vue de (se) reconfigurer dans le contexte de l'amélioration de l'autonomie des systèmes spatiaux. Pour cela, nous nous sommes intéressés aux agents fondés sur un modèle du système, concept étudié en Intelligence Artificielle. Nous avons utilisé ce concept dans un but de suivi d'état, tout en prenant en compte les défauts pouvant affecter le système, effectuant ainsi la tâche de diagnostic dynamique. Pour cela, les aspects concernant les défauts du système ont été intégrés dans le modèle. Le suivi d'état est la tâche qui met à jour un état de croyance concernant le système. Nous l'avons analysé sous un angle algorithmique dans le but de répondre aux contraintes de faibles ressources de calcul présentes à bord des systèmes spatiaux. Nous avons étudié les algorithmes de suivi qui opèrent sur des modèles logiques, tels que ceux écrits en logique propositionnelle ou dans le langage des réseaux de contraintes, et sur des modèles probabilistes, tels que les réseaux Bayésiens dynamiques. Cette étude a permis de cibler le phénomène d'enchevêtrement qui rend exponentiel la représentation de l'état de croyance. Notre contribution consiste à proposer une approche algorithmique qui utilise un algorithme de recherche en profondeur d'abord dans un espace de recherche Et/Ou. Dans cet espace, le phénomène d'enchevêtrement a pu être analysé sous un nouvel angle. Nous avons proposé une solution au phénomène d'enchevêtrement en définissant, sous la forme de trois règles de calcul, un système cohérent et complet dans la théorie des ensembles. Nous avons ensuite défini des structures de données servant de représentation compacte de l'état de croyance. Ces structures de données sont appelées arbres symboliques. Nous concluons par une généralisation et des perspectives dans le domaine algorithmique et les mathématiques.
|
253 |
Étude d'algorithmes de restauration d'images sismiques par optimisation de forme non linéaire et application à la reconstruction sédimentaireGilardet, Mathieu 19 December 2013 (has links) (PDF)
Nous présentons une nouvelle méthode pour la restauration d'images sismiques. Quand on l'observe, une image sismique est le résultat d'un système de dépôt initial qui a été transformé par un ensemble de déformations géologiques successives (flexions, glissement de la faille, etc) qui se sont produites sur une grande période de temps. L'objectif de la restauration sismique consiste à inverser les déformations pour fournir une image résultante qui représente le système de dépôt géologique tel qu'il était dans un état antérieur. Classiquement, ce procédé permet de tester la cohérence des hypothèses d'interprétations formulées par les géophysiciens sur les images initiales. Dans notre contribution, nous fournissons un outil qui permet de générer rapidement des images restaurées et qui aide donc les géophysiciens à reconnaître et identifier les caractéristiques géologiques qui peuvent être très fortement modifiées et donc difficilement identifiables dans l'image observée d'origine. Cette application permet alors d'assister ces géophysiciens pour la formulation d'hypothèses d'interprétation des images sismiques. L'approche que nous introduisons est basée sur un processus de minimisation qui exprime les déformations géologiques en termes de contraintes géométriques. Nous utilisons une approche itérative de Gauss-Newton qui converge rapidement pour résoudre le système. Dans une deuxième partie de notre travail nous montrons différents résultats obtenus dans des cas concrets afin d'illustrer le processus de restauration d'image sismique sur des données réelles et de montrer comment la version restaurée peut être utilisée dans un cadre d'interprétation géologique.
|
254 |
Régression isotonique itéréeJégou, Nicolas 23 November 2012 (has links) (PDF)
Ce travail se situe dans le cadre de la régression non paramétrique univariée. Supposant la fonction de régression à variation bornée et partant du résultat selon lequel une telle fonction se décompose en la somme d'une fonction croissante et d'une fonction décroissante, nous proposons de construire et d'étudier un nouvel estimateur combinant les techniques d'estimation des modèles additifs et celles d'estimation sous contraintes de monotonie. Plus précisément, notreméthode consiste à itérer la régression isotonique selon l'algorithme backfitting. On dispose ainsià chaque itération d'un estimateur de la fonction de régression résultant de la somme d'une partiecroissante et d'une partie décroissante.Le premier chapitre propose un tour d'horizon des références relatives aux outils cités à l'instant. Le chapitre suivant est dédié à l'étude théorique de la régression isotonique itérée. Dans un premier temps, on montre que, la taille d'échantillon étant fixée, augmenter le nombre d'itérations conduit à l'interpolation des données. On réussit à identifier les limites des termes individuels de la somme en montrant l'égalité de notre algorithme avec celui consistant à itérer la régressionisotonique selon un algorithme de type réduction itérée du biais. Nous établissons enfin la consistance de l'estimateur.Le troisième chapitre est consacré à l'étude pratique de l'estimateur. Comme augmenter le nombre d'itérations conduit au sur-ajustement, il n'est pas souhaitable d'itérer la méthode jusqu'à la convergence. Nous examinons des règles d'arrêt basées sur des adaptations de critères usuellement employés dans le cadre des méthodes linéaires de lissage (AIC, BIC,...) ainsi que des critères supposant une connaissance a priori sur le nombre de modes de la fonction de régression. Il en ressort un comportement intéressant de la méthode lorsque la fonction de régression possède des points de rupture. Nous appliquons ensuite l'algorithme à des données réelles de type puces CGH où la détection de ruptures est d'un intérêt crucial. Enfin, une application à l'estimation des fonctions unimodales et à la détection de mode(s) est proposée
|
255 |
Une approche formelle pour l'optimisation de systèmes à événements discretsCardillo Albarran, Juan 05 February 2004 (has links) (PDF)
Cette thèse est centrée sur l'optimisation de systèmes dynamiques a événements discrets sur un domaine fini. Deux approches fondamentales de l'optimisation sont considérées : le principe du minimum et la programmation dynamique. Dans chaque cas une méthode de calcul formel est développée pour l'optimisation d'une forme polynomiale sur un domaine de définition fini. Le résultat de l'approche basée sur le principe du minimum est établi sons la forme d'un théorème dans lequel la condition (nécessaire) d'optimalité est définie en terme d'une inégalité variationnelle sons une forme séparable par rapport aux étapes (instants). Celle-ci est explicitement fonction de la variable de commande à linstant courant, (commande courante), de la forme paramétrée de celle-ci et de l'état du système auquel peuvent s'ajouter des paramètres exogènes impliqués dans le modèle d'évolution. La résolution de cette inégalité variationnelle paramétrique est développée selon une procédure de type Min-Max avec une minimisation par rapport aux commandes courantes et une maximisation par rapport aux autres commandes. L'algorithme correspondant est désigné par le symbole SCDO (Symbolic Computation for Discrete Optimisation). L'approche basée sur la programmation dynamique exploite le caractère paramétrique de cette méthode de décomposition. L'intégration de l'algorithme SCDO dans les deux phases de ce processus d'optimisation permet ici encore d'exprimer la séquence de commandes optimales sous une forme explicite de l'état du système et des autres paramètres exogènes. Dans ce mémoire, nous considérons également le principe de relaxation pour transformer le problème discret en un problème continu de résolution classique. Ainsi, pour une famille particulière de processus discrets linéaires par rapport à l'état et de fonction de coût concave, nous obtenons une condition de type principe du minimum, équivalente pour l'optimum relaxé et l'optimum de problème original. Dans le cas de fonctions de coût linéaires, la condition obtenue est celle du principe du minimum classique.
|
256 |
Etude des propriétés physiques des aérosols de la moyenne et haute atmosphère à partir d'une nouvelle analyse des observations du GOMOS-ENVISAT pour la période 2002-2006Salazar, Veronica 13 December 2010 (has links) (PDF)
L'étude des aérosols de la stratosphère est primordiale pour modéliser précisément le bilan radiatif terrestre, et pour évaluer l'influence des particules sur le cycle de destruction de l'ozone. Depuis la découverte de la couche de Junge, ce domaine de recherche connaît différents décors, du plus important contenu en aérosols du dernier siècle après l'éruption du Mont Pinatubo en 1991, à un rétablissement vers les faibles niveaux atteints dans les années 2000, qui permet l'étude des particules autres que celles d'origine volcanique. Cependant, à ce jour, le degré de connaissance est faible quant à la distribution spatiale et verticale de ces aérosols dans la moyenne et haute stratosphère. Leur détection présente plusieurs difficultés: les particules ont une grande variété d'origines, compositions, tailles et formes, et leurs faibles épaisseurs optiques rendent indispensables des résultats précis. Un algorithme d'inversion développé au LPC2E a été adapté à l'analyse des données de niveau 1b de l'instrument GOMOS à bord d'ENVISAT, qui emploie la technique d'occultation stellaire, et fournit une bonne (mais irrégulière) couverture géographique et temporelle des mesures; un critère de sélection est d'ailleurs nécessaire du fait de l'utilisation de sources lumineuses de propriétés différentes. La méthode mise au point est validée pour l'étude de l'extinction induite par les aérosols; une climatologie globale est alors établie pour la période allant d'août 2002 à juillet 2006, et indique la présence permanente de particules dans l'ensemble du globe, jusqu'à environ 45 km d'altitude. La variabilité temporelle de l'extinction montre une augmentation progressive du contenu moyen depuis 2002 aux latitudes tropicales dans la basse stratosphère, et a permis d'évaluer l'effet de l'oscillation quasi-biennale et d'étudier d'autres variations saisonnières. La dépendance spectrale permet de déduire certaines spécificités concernant la taille et la nature des aérosols, majoritairement des particules sulfatées, mais également des suies en provenance de la troposphère et des particules d'origine interplanétaire.
|
257 |
Contribution aux méthodes hybrides d'optimisation heuristique : Distribution et application à l'interopérabilité des systèmes d'informationEl Hami, Norelislam 23 June 2012 (has links) (PDF)
Les travaux présentés dans ce mémoire proposent une nouvelle méthode d'optimisation globale dénommée MPSO-SA. Cette méthode hybride est le résultat d'un couplage d'une variante d'algorithme par Essaim de particules nommé MPSO (Particle Swarm Optimization) avec la méthode du recuit simulé nommé SA (Simulted Annealing). Les méthodes stochastiques ont connu une progression considérable pour la résolution de problèmes d'optimisation. Parmi ces méthodes, il y a la méthode Essaim de particules (PSO° qui est développée par [Eberhart et Kennedy (1995)]. Quant à la méthode recuit simulé (SA), elle provient du processus physique qui consiste à ordonner les atomes d'un cristal afin de former une structure cristalline parfaite. Pour illustrer les performances de la méthode MPSO-SA proposée, une comparaison avec MPSO et SA est effectuée sur des fonctions tests connues dans la littérature. La métode MPSO-SA est utilisée pour la résolution des problèmes réels interopérabilité des systèmes d'information, ainsi qu'aux problèmes d'optimisation et de fiabilité des structures mécaniques.
|
258 |
Mesures de similarité pour cartes généraliséesCombier, Camille 28 November 2012 (has links) (PDF)
Une carte généralisée est un modèle topologique permettant de représenter implicitementun ensemble de cellules (sommets, arêtes, faces , volumes, . . .) ainsi que l'ensemblede leurs relations d'incidence et d'adjacence au moyen de brins et d'involutions. Les cartes généralisées sont notamment utilisées pour modéliser des images et objets3D. A ce jour il existe peu d'outils permettant l'analyse et la comparaison de cartes généralisées.Notre objectif est de définir un ensemble d'outils permettant la comparaisonde cartes généralisées.Nous définissons tout d'abord une mesure de similarité basée sur la taille de la partiecommune entre deux cartes généralisées, appelée plus grande sous-carte commune.Nous définissons deux types de sous-cartes, partielles et induites, la sous-carte induitedoit conserver toutes les involutions tandis que la sous-carte partielle autorise certaines involutions à ne pas être conservées. La sous-carte partielle autorise que les involutionsne soient pas toutes conservées en analogie au sous-graphe partiel pour lequelles arêtes peuvent ne pas être toutes présentes. Ensuite nous définissons un ensembled'opérations de modification de brins et de coutures pour les cartes généralisées ainsiqu'une distance d'édition. La distance d'édition est égale au coût minimal engendrépar toutes les successions d'opérations transformant une carte généralisée en une autrecarte généralisée. Cette distance permet la prise en compte d'étiquettes, grâce à l'opérationde substitution. Les étiquettes sont posées sur les brins et permettent d'ajouter del'information aux cartes généralisées. Nous montrons ensuite, que pour certains coûtsnotre distance d'édition peut être calculée directement à partir de la plus grande souscartecommune.Le calcul de la distance d'édition est un problème NP-difficile. Nous proposons unalgorithme glouton permettant de calculer en temps polynomial une approximation denotre distance d'édition de cartes. Nous proposons un ensemble d'heuristiques baséessur des descripteurs du voisinage des brins de la carte généralisée permettant de guiderl'algorithme glouton, et nous évaluons ces heuristiques sur des jeux de test générésaléatoirement, pour lesquels nous connaissons une borne de la distance.Nous proposons des pistes d'utilisation de nos mesures de similarités dans le domainede l'analyse d'image et de maillages. Nous comparons notre distance d'éditionde cartes généralisées avec la distance d'édition de graphes, souvent utilisée en reconnaissancede formes structurelles. Nous définissons également un ensemble d'heuristiquesprenant en compte les étiquettes de cartes généralisées modélisant des images etdes maillages. Nous mettons en évidence l'aspect qualitatif de notre appariement, permettantde mettre en correspondance des zones de l'image et des points du maillages.
|
259 |
Fabrication de nanoaimants pour le contrôle rapide d'un spin électronique dans une boîte quantique doubleBureau-Oxton, Chloé January 2014 (has links)
Un ordinateur quantique est un ordinateur formé de bits quantiques (qubits) qui tire profit des propriétés quantiques de la matière. Un grand intérêt est porté au développement d’un tel ordinateur depuis qu’il a été montré que le calcul quantique permettrait d’effectuer certains types de calculs exponentiellement plus rapidement qu’avec les meilleurs algorithmes connus sur un ordinateur classique. D’ailleurs, plusieurs algorithmes ont déjà été suggérés pour résoudre efficacement des problèmes tels que la factorisation de grands nombres premiers et la recherche dans des listes désordonnées.
Avant d’en arriver à un ordinateur quantique fonctionnel, certains grands défis doivent être surmontés. Un de ces défis consiste à fabriquer des qubits ayant un temps d’opération nettement inférieur au temps de cohérence (temps durant lequel l’état du qubit est conservé). Cette condition est nécessaire pour parvenir à un calcul quantique fiable. Pour atteindre cet objectif, de nombreuses recherches visent à augmenter le temps de cohérence en choisissant judicieusement les matériaux utilisés dans la fabrication des qubits en plus d’imaginer de nouvelles méthodes d’utiliser ces dispositifs pour diminuer la durée des opérations.
Une manière simple d’implémenter un qubit est de piéger quelques électrons dans l’espace et d’utiliser l’état de spin de cet ensemble d’électrons pour encoder les états du qubit. Ce type de dispositif porte le nom de qubit de spin. Les boîtes quantiques (BQs) latérales fabriquées sur des substrats de GaAs/AlGaAs sont un exemple de qubit de spin et sont les dispositifs étudiés dans ce mémoire.
En 2007, Pioro-Ladrière et al. ont suggéré de placer un microaimant à proximité d’une BQ pour créer un gradient de champ magnétique non-uniforme et permettre d’effectuer des rotations de spin à l’aide d’impulsions électriques rapides. Ce mémoire présente comment modifier la géométrie de ces microaimants pour obtenir un plus grand gradient de champ magnétique dans la BQ. Une nouvelle technique de contrôle de spin menant à des rotations de spin et de phase plus rapides sera aussi détaillée. Enfin, il sera montré que le département de physique de l’Université de Sherbrooke possède tous les outils nécessaires pour implémenter cette méthode.
|
260 |
Algorithmes de classification répartis sur le cloudDurut, Matthieu 28 September 2012 (has links) (PDF)
Les thèmes de recherche abordés dans ce manuscrit ont trait à la parallélisation d'algorithmes de classification non-supervisée (clustering) sur des plateformes de Cloud Computing. Le chapitre 2 propose un tour d'horizon de ces technologies. Nous y présentons d'une manière générale le Cloud Computing comme plateforme de calcul. Le chapitre 3 présente l'offre cloud de Microsoft : Windows Azure. Le chapitre suivant analyse certains enjeux techniques de la conception d'applications cloud et propose certains éléments d'architecture logicielle pour de telles applications. Le chapitre 5 propose une analyse du premier algorithme de classification étudié : le Batch K-Means. En particulier, nous approfondissons comment les versions réparties de cet algorithme doivent être adaptées à une architecture cloud. Nous y montrons l'impact des coûts de communication sur l'efficacité de cet algorithme lorsque celui-ci est implémenté sur une plateforme cloud. Les chapitres 6 et 7 présentent un travail de parallélisation d'un autre algorithme de classification : l'algorithme de Vector Quantization (VQ). Dans le chapitre 6 nous explorons quels schémas de parallélisation sont susceptibles de fournir des résultats satisfaisants en terme d'accélération de la convergence. Le chapitre 7 présente une implémentation de ces schémas de parallélisation. Les détails pratiques de l'implémentation soulignent un résultat de première importance : c'est le caractère en ligne du VQ qui permet de proposer une implémentation asynchrone de l'algorithme réparti, supprimant ainsi une partie des problèmes de communication rencontrés lors de la parallélisation du Batch K-Means.
|
Page generated in 0.0578 seconds