231 |
A study on the expressive power of some fragments of the modal µ-calculusFacchini, Alessandro 03 December 2010 (has links)
Dans ce travail nous étudions la complexité de certains fragments du mu-calcul selon deux points de vue: l’un syntaxique et l’autre topologique. Dans la première partie nous adoptons le point de vue syntaxique afin d'étudier le comportement du mu-calcul sur des classes restreintes de modèles. Parmi d'autres résultats, nous montrons en particulier que sur les modèles transitifs toute propriété définissable par une formule du mu-calcul est définissable par une formule sans alternance de points fixes. Pour ce qui concerne la perspective topologique, nous montrons d'abord que sur les modèles transitifs la logique modale correspond au fragment borélien du mu-calcul. Ensuite nous donnons une description effective des hiérarchies de Borel et de Wadge d'un sous-fragment sans alternance de cette logique sur les arbres binaires et vérifions que pour ce fragment les points de vue topologique et syntaxique coïncident. / In this work we study the complexity of some fragments of the modal mu-calculus from two points of view: the syntactical and the topological. In the first part of the dissertation we adopt the syntactical point of view in order to study the behavior of this formalism on some restricted classes of models. Among other results, we show that on transitive transition systems, every mu-formula is logically equivalent to an alternation free formula. For what concerns the topological point of view, we first prove that on transitive models, the modal logic is exactly the Borel fragment of the modal mu-calculus. Then we provide an effective description of the Borel and Wadge hierarchies of a sub-fragment of the alternation free fragment of the mu-calculus on binary trees. Finally we verify that for this fragment the syntactical point of view and topological point of view coincide.
|
232 |
Calcul en n-dimensions sur GPUBergeron, Arnaud 04 1900 (has links)
Le code source de la libraire développée accompagne ce dépôt dans l'état où il était à ce moment. Il est possible de trouver une version plus à jour sur github (http://github.com/abergeron). / Le calcul scientifique sur processeurs graphiques (GPU) est en plein essor depuis un certain temps, en particulier dans le domaine de l'apprentissage machine.
Cette thèse présente les efforts pour établir une structure de données de table au multidimensionnel de manière efficace sur GPU.
Nous commençons par faire une revue de ce qui est actuellement similaire dans le domaine et des désavantages d'avoir une multitude d'approches.
Nous nous intéresserons particulièrement aux calculs fait à partir du langage Python.
Nous décrirons des techniques intéressantes telles que la réduction d'ordre et le calcul asynchrone automatique.
Pour terminer nous présenterons l'utilisation du module développé dans le cadre de cette thèse. / Scientific computing on GPU (graphical processing units) is on the rise, specifically in machine learning.
This thesis presents the implementation of an efficient multidimensional array on the GPU.
We will begin by a review of what currently implements similar functionality and the disadvantage of a fragmented approach.
We will focus on packages that have a Python interface.
We will explain techniques to optimize execution such as order reduction and automatic asynchronous computations.
Finally, we will present the functionality of the module developed for this thesis.
|
233 |
A survey of graph and subgraph isomorphism problemsLei, Yaohui January 2003 (has links)
Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.
|
234 |
Le calcul parallèle des plus courts chemins temporelsPépin, Jean-Nicolas January 2003 (has links)
Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.
|
235 |
Programmes de génération et machines de Turing algébriquesPilette, Simon January 2006 (has links)
Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.
|
236 |
Étude numérique des mécanismes d'autodiffusion dans les semiconducteursEl-Mellouhi, Fedwa January 2006 (has links)
Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.
|
237 |
Sur une stratégie multi-échelle d'analyse des grands délaminages en dynamique transitoire / Towards the multiscale analysis of large delamination in dynamicsDupleix-Couderc, Chloé 14 April 2011 (has links)
Les matériaux composites sont largement utilisés dans les structures aéronautiques. Les travaux présentés ici visent à mettre en place une méthode de calcul permettant de prédire les délaminages dans ces structures stratifiées soumises à des chargements dynamiques tout en assurant des coûts de calculs compatibles dans un contexte industriel. Une méthode de décomposition de domaine en dynamique est d’abord utilisée, afin de coupler des modélisations et des pas de temps de calcul différents. Une modélisation fine est utilisée uniquement dans les zones en cours de dégradation. Une représentation macroscopique du stratifié par des éléments de coque 3D est développée et employée dans le reste de la structure. Les coûts de calcul sont ainsi réduits tout en assurant une bonne précision des résultats. Pour éviter un remaillage avec l’avancée du délaminage, une approche multi-échelle en temps et en espace est ensuite proposée. Un maillage global de coque 3D de l'ensemble de la structure est défini. Des maillages utilisant une représentation fine du matériau sont utilisés localement. Des pas de temps adaptés sont utilisés dans les deux types de maillage. / The part of composite materials in aeronautic structures is increasing due to their specific properties and the mass reduction they enable. Accurate numerical simulations are thus needed in order to design these structures, particularly to verify if they could resist dynamic charges such as soft bodies impact. Nevertheless, using a refined model to represent phenomenon such as delamination leads to computing time and dofs number incompatible with an industrial context. The aim of the present work is to propose a multi-scale method in space and time to solve dynamic impact problems on laminate structures. A domain decomposition method for dynamic problems is first used to couple different kinds of models and time discretisations. A refined model for the laminate is used in the degradating areas only - elsewhere, a coarser representation using 3D-shell elements is used. This approach reduced the cost of the simulation giving accurate results. To avoid a remeshing due to delamination propagation within the structure, a multi-scale method is then proposed. A global 3D shell elements mesh for the whole structure is defined. Local meshes based on a refined representation of the laminates are used only if required. Coupling between global and local representation is done using velocity field.
|
238 |
Adressing scaling challenges in comparative genomics / Adresser les défis de passage à l'échelle en génomique comparéeGolenetskaya, Natalia 09 September 2013 (has links)
La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations n-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques. / Comparative genomics is essentially a form of data mining in large collections of n-ary relations between genomic elements. Increases in the number of sequenced genomes create a stress on comparative genomics that grows, at worse geometrically, for every increase in sequence data. Even modestly-sized labs now routinely obtain several genomes at a time, and like large consortiums expect to be able to perform all-against-all analyses as part of these new multi-genome strategies. In order to address the needs at all levels it is necessary to rethink the algorithmic frameworks and data storage technologies used for comparative genomics.To meet these challenges of scale, in this thesis we develop novel methods based on NoSQL and MapReduce technologies. Using a characterization of the kinds of data used in comparative genomics, and a study of usage patterns for their analysis, we define a practical formalism for genomic Big Data, implement it using the Cassandra NoSQL platform, and evaluate its performance. Furthermore, using two quite different global analyses in comparative genomics, we define two strategies for adapting these applications to the MapReduce paradigm and derive new algorithms. For the first, identifying gene fusion and fission events in phylogenies, we reformulate the problem as a bounded parallel traversal that avoids high-latency graph-based algorithms. For the second, consensus clustering to identify protein families, we define an iterative sampling procedure that quickly converges to the desired global result. For both of these new algorithms, we implement each in the Hadoop MapReduce platform, and evaluate their performance. The performance is competitive and scales much better than existing solutions, but requires particular (and future) effort in devising specific algorithms.
|
239 |
Towards a software architecture for generic image processing / Vers une architecture logicielle pour le traitement d'images génériqueLevillain, Roland 15 November 2011 (has links)
Dans le cadre du génie logiciel en traitement d'images (TDI), nous nous intéressons à la notion de réutilisabilité des algorithmes. Dans de nombreux outils logiciels, l'implémentation d'un algorithme est souvent dépendante du type des données traitées. Au sens le plus général, les formes que peuvent prendre les images numériques discrètes sont nombreuses (image 2D classiques, volumes 3D, graphes non réguliers, complexes cellulaires, etc.) conduisant à une explosion combinatoire du nombre théorique d'implémentations. La programmation générique (PG) est un cadre adapté au développement d'outils logiciels réutilisables. Nous présentons un paradigme de programmation basé sur la PG conçu pour la création de logiciels scientifiques tels ceux dédiés au TDI. Cette approche concilie réutilisabilité, puissance d'expression, extensibilité et performance. Nous proposons ensuite une architecture logicielle pour le TDI basée sur ce paradigme de programmation, s'appuyant sur une bibliothèque générique de TDI. Les fondations de ce cadre définissent des concepts fondamentaux du TDI, qui permettent l'écriture d'algorithmes réutilisables sur de nombreux types d'images. Nous présentons enfin une stratégie pour construire des outils haut niveau au dessus de cette bibliothèque tels que des ponts vers des langages dynamiques ou des interfaces graphiques. Ce mécanisme est conçu pour préserver la généricité et la performance des outils logiciels sous-jacents, tout en permettant un usage plus simple et plus flexible de ceux-ci / In the context of software engineering for image processing (IP), we consider the notion of reusability of algorithms. In many software tools, an algorithm's implementation often depends on the type of processed data. In a broad definition, discrete digital images may have various forms : classical 2D images, 3D volumes, non-regular graphs, cell complexes, and so on : thus leading to a combinatorial explosion of the theoretical number of implementations. Generic programming (GP) is a framework suited to the development of reusable software tools. We present a programming paradigm based on GP designed for the creation of scientific software such as IP tools. This approach combines the benefits of reusability, expressive power, extensibility, and efficiency. We then propose a software architecture for IP using this programming paradigm based on a generic IP library. The foundations of this framework define essential IP concepts, enabling the development of algorithms compatible with many image types. We finally present a strategy to build high-level tools on top of this library, such as bridges to dynamic languages or graphical user interfaces. This mechanism has been designed to preserve the genericity and efficiency of the underlying software tools, while making them simpler to use and more flexible
|
240 |
Modélisation et étude numérique de quelques écoulements de fluides complexes en micro-fluidiqueDambrine, Julien 07 December 2009 (has links)
Ce document est consacré à l’étude de quelques écoulements de fluides complexes appliquée à la micro-fluidique. Deux études indépendantes sont effectuées : d’une part l’étude des mélanges de fluides Newtoniens dans des micro-canaux fins, et d’autre part l’étude d’écoulements de Micelles géantes (fluides non-Newtoniens). Dans chaque étude on traite tout d’abord des modèles en détail, puis on effectue une étude numérique des modèles en question. Dans la première partie nous traiterons de l’hydrodynamique de mélanges de fluides de différentes viscosités en régime de Stokes. Nous dériverons alors un modèle réduit de type Reynolds à partir du modèle complet de Stokes. Cette réduction de modèle est particulièrement adaptée à des écoulements dans des micro-canaux dont le rapport d’aspect largeur/hauteur est important. Les modèles obtenus au final peuvent être 2D ou bien 2.5D (2D pour la pression 3D pour le mélange) selon que l’on souhaite ou non prendre en compte les variations de viscosité dans la direction ”?ne”. De plus, les conditions aux limites en haut et au fond du canal pour le modèle complet (canal à reliefs, motifs de matériaux glissants) apparaissent dans le modèle réduit comme de simples coefficients de résistance à l’écoulement. Un résultat d’existence de solution est donné pour le modèle 2D. Une méthode numérique est alors donnée pour approcher ces modèles. Cette méthode numérique est basée sur une discrétisation des équations sur une grille cartésienne, ce qui permet une résolution rapide des systèmes linéaires obtenus après discrétisation. Deux études numériques sont alors menées, tout d’abord une étude de l’inter-diffusion de deux fluides dont les viscosités sont différentes dans des expériences dites de ”co-flow”, puis une autre étude sur des écoulements mono-fluides pour des canaux à reliefs et à surfaces glissantes utilisant des modèles 2.5D adaptées. La deuxième partie de ce document est consacrée à l’étude d’écoulements micro-fluidiques de micelles géantes en solution. Ce type particulier de fluide a tendance à former spontanément dans l’écoulement des phases dont les propriétés mécaniques peuvent être très différentes. (...) Cette étude a permis en particulier de déterminer le rôle exact de la diffusion dans le modèle. Une deuxième étude concernant des écoulements 3D dans des jonctions micro-fluidiques en T a permis de mieux comprendre les phénomènes étranges observés sur la répartition des débits dans les branches de sortie de ces jonctions. / Abstract
|
Page generated in 0.0557 seconds