Dissertationen zum Thema „Bases de cycles minimum“

Given an undirected graph G(V,E) and a vertex subset U\subseteq V the U-space is the vector space over GF(2) spanned by the paths with end-points in U and the cycles in G(V,E). We extend Vismara's algorithm to the computation of the union of all minimum length bases of the U-space. (author's abstract)
Series: Preprint Series / Department of Applied Statistics and Data Processing

La thèse présente une nouvelle méthode pour l'analyse et la comparaison de trajectoires de dynamique moléculaire basée sur l'algorithmique de graphes. Nous considérons une trajectoire comme une suite de graphes représentant l'évolution des liaisons chimiques entre les atomes d'une molécule en mouvement.Traditionnellement, l'analyse de dynamique moléculaire repose sur l'énergie potentielle, mais nous avons choisi de nous en abstraire et de proposer une méthode basée sur la topologie des graphes, en particulier celle des cycles. Au cours de l'évolution de la molécule, les cycles et leurs interactions représentent la structure de la molécule. Certains cycles différents peuvent cependant avoir un rôle similaire dans la structure, nous les qualifions alors de polymorphes. Partant de ces cycles polymorphes, nous définissons le polygraphe, un graphe représentatif de la dynamique d'une trajectoire, dans lequel les sommets sont des ensembles de cycles polymorphes.La thèse présente à la fois la méthodologie permettant le calcul et l'utilisation de ce polygraphe, ainsi que l'étude de la complexité des problèmes sous-jacents à sa construction.Dans le même temps, nous proposons plusieurs algorithmes pour répondre aux problèmes posés et obtenir ainsi un polygraphe. Par la suite, nos algorithmes sont évalués afin de définir un protocole de construction du polygraphe à partir d'une suite de graphes constituant une trajectoire.Enfin, nous présentons nos résultats sur l'utilisation du polygraphe pour l'analyse des trajectoires. Le polygraphe permet d'avoir une vue globale, tandis que des sous-polygraphes permettent de représenter la structure en cycles polymorphes de chacun des graphes de la trajectoire. De cette façon, si deux graphes d'une trajectoire ont le même sous-polygraphe alors, leurs structures sont équivalentes et nous pouvons conclure qu'il n'y a pas de différences structurelles majeures entre ces graphes. Nous répétons cela sur tous les graphes de la trajectoire afin de définir des ensembles de graphes qui correspondent à la même structure en cycles polymorphes
The thesis presents a new method for the analysis and comparison of molecular dynamics trajectories based on graph algorithms. We consider a trajectory as a sequence of graphs representing the evolution of chemical bonds between the atoms of a moving molecule.Traditionally, molecular dynamics analysis relies on potential energy, but we chose to abstract from this and propose a method based on graph topology, particularly that of cycles. During the molecule's evolution, the cycles and their interactions represent the structure of the molecule. However, some different cycles can play a similar role in the structure, and we then qualify them as polymorphic. From these polymorphic cycles, we define the polygraph, a representative graph of the trajectory's dynamics, where the vertices are sets of polymorphic cycles.The thesis presents both the methodology for calculating and using this polygraph, as well as the study of the complexity of the underlying problems in its construction.At the same time, we propose several algorithms to address the posed problems and thus obtain a polygraph. Subsequently, our algorithms are evaluated to define a protocol for constructing the polygraph from a sequence of graphs constituting a trajectory.Finally, we present our results on using the polygraph for trajectory analysis. The polygraph provides an overall view, while sub-polygraphs represent the polymorphic cycle structure of each graph in the trajectory. In this way, if two graphs in a trajectory have the same sub-polygraph, then their structures are equivalent, and we can conclude that there are no major structural differences between these graphs. We repeat this for all graphs in the trajectory to define sets of graphs that correspond to the same polymorphic cycle structure

The set R of relevant cycles of a graph G is the union of its minimum cycle bases. We introduce a partition of R such that each cycle in a class W can be expressed as a sum of other cycles in W and shorter cycles. It is shown that each minimum cycle basis contains the same number of representatives of a given class W. This result is used to derive upper and lower bounds on the number of distinct minimum cycle bases. Finally, we give a polynomial-time algorithm to compute this partition. (author's abstract)
Series: Preprint Series / Department of Applied Statistics and Data Processing

The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is outlined. (author's abstract)
Series: Preprint Series / Department of Applied Statistics and Data Processing

2-connected outerplanar graphs have a unique minimal cycle basis with length 2|E|-|V|. They are the only Hamiltonian graphs with a cycle basis of this length. (author's abstract)
Series: Preprint Series / Department of Applied Statistics and Data Processing

Afin d’identifier les déterminants moléculaires du polymorphisme de compatibilité dans l’interaction entre le parasite Schistosoma mansoni et l’hôte invertébré mollusque Biomphalaria glabrata, nous avons développé une approche protéomique comparative des souches de parasites compatible et incompatible vis-à-vis de la même souche de mollusque. Cette approche nous a permis d’identifier une nouvelle famille d’antigènes chez S. Mansoni. Ce sont des protéines de type mucines qui sont (i) exprimées spécifiquement dans les stades larvaires interagissant avec le mollusque, (ii) localisées dans la glande apicale et (iii) sécrétées et relarguées avec les produits d’excrétion-sécrétion. De plus, ces protéines de type mucine, présentant un haut degré de polymorphisme, ont été nommé « S. Mansoni Polymorphic Mucin », SmPoMuc. Nous avons ensuite montré que les SmPoMuc sont codées par une famille multigénique qui évolue selon le modèle de « birth and death ». Les gènes codant les SmPoMuc sont transcrits indépendamment, et pour chaque gène, différents transcrits peuvent être obtenus par épissage. De plus, nos résultats suggèrent que ce polymorphisme pourrait avoir des conséquences sur le statut de glycosylation des SmPoMuc. Nos résultats supportent l’idée que S. Mansoni a développé au cours de l’évolution des mécanismes complexes permettant de générer un haut niveau de polymorphisme des SmPoMuc. Par ailleurs, le fait que ce « chaos contrôlé » soit généré à partir d’un nombre limité de gènes est unique par rapport à ce qui a été décrit pour des variants polymorphes exprimés par d’autres parasites
To identify key molecules involved in the compatibility polymorphism in the Schistosoma mansoni / Biomphalaria glabrata model, we developed a comparative proteomics approach for the larval stages that interact with the invertebrate host. The qualitative and quantitative comparison of the proteomes of compatible and incompatible parasite strains led to the identification of a new family of schistosome antigens that share molecular characteristics with highly glycosylated secreted mucins. In particular, they possess a domain containing a variable number of tandem repeats (VNTR). These proteins are (i) only expressed in larval stages interacting with the mollusc, (ii) located in the apical gland of miracidia and sporocysts and (iii) secreted and released in excretion-secretion products. Moreover, we show that these mucin-like proteins display a high degree of polymorphism and that extensive differences are observed between S. Mansoni strains. These different characteristics led us to name this novel molecular family “S. Mansoni Polymorphic Mucins” SmPoMuc. Next, we show that SmPoMuc are coded by a multi-gene family that evolve following the model of “birth and death”. SmPoMuc genes are transcribed in an individual-specific manner, and for each gene, multiple splice variants exist. The incidence of this polymorphism on SmPoMuc glycosylation status was demonstrated. Our data support the view that S. Mansoni has evolved a complex cascade of mechanisms – a “controlled chaos” – based on a relatively low number of genes that provides highly polymorphism to SmPoMuc

Nous étudions les mots de poids minimal des codes correcteurs d'erreurs cycliques. Les fonctions symétriques élémentaires et les fonctions puissances des localisateurs de ces mots vérifient les identités de Newton. Dans le premier chapitre celles-ci sont étudiées comme un système d'équations algébriques, dont les solutions sont étudiées par transformation de Fourier. Dans le chapitre II, le lien est fait avec les codes correcteurs d'erreurs cycliques. Sur quelques exemples, il est montré comment étudier les mots de poids minimal sur la donnée d'une base standard de l'idéal engendré par les équations de Newton. Dans le chapitre III, les relations de Newton sont utilisées d'un point de vue théorique, et des résultats sur les mots de poids minimal de certains codes BCH sont obtenus. Ces calculs se placent dans le contexte de la théorie des corps finis. Dans le chapitre IV, un algorithme est développé pour calculer une base normale sur un corps fini. Un point de vue d'algèbre linéaire est choisi, et d'autres problèmes sont abordés (calcul du polynôme minimal, de la forme de Frobenius d'une matrice, lorsque la factorisation du polynôme caractéristique est connue).

Orientador: Marco Lúcio Bittencourt
Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica
Made available in DSpace on 2018-08-26T18:11:15Z (GMT). No. of bitstreams: 1 Santos_CaioFernandoRodriguesdos_D.pdf: 60307032 bytes, checksum: 4e05fc37f22f1d9206fa3c5665d9bc34 (MD5) Previous issue date: 2015
Resumo: Nesse trabalho apresentamos os procedimentos de construção de bases para o Método de Elementos Finitos (MEF) de alta ordem considerando o procedimento de diagonalização simultânea dos modos internos da matriz de massa e rigidez unidimensionais e a ortogonalização dos modos de contorno usando procedimentos de mínima energia. Nesse caso, os conceitos de ortogonalização de mínima energia são usados como uma maneira eficiente de se construir modos de contorno ortogonais aos modos internos das funções de forma $1D$. Novas funções de forma unidimensionais para o MEF de alta ordem são apresentadas para a construção de bases simultaneamente diagonais de mínima energia para o operador de Helmholtz. Além disso, um procedimento para o cálculo das matrizes de massa e rigidez $2D$ e $3D$, como combinação dos coeficientes unidimensionais das matrizes de massa, rigidez e mista é apresentado para elementos quadrilaterais e hexaédricos distorcidos em problemas de projeção, Poisson, estado plano e estado geral em problemas de elasticidade linear. O uso de procedimentos via matrizes unidimensionais permite obter um speedup significativo em comparação com o procedimento padrão, para malhas distorcidas e não distorcidas. Com esse procedimento, é possível armazenar apenas as funções de forma unidimensionais e suas derivadas calculadas nos pontos de integração unidimensionais gerando uma redução no consumo de memória. O desempenho das bases propostas foi verificado através de testes numéricos e os resultados comparados com aqueles usando a base padrão com polinômios de Jacobi. Características como esparsidade, condicionamento numérico e número de iterações usando o método dos gradientes conjugados com precondicionador diagonal também são investigados. Além disso, investigamos o uso da matriz de massa local, utilizando bases simultaneamente diagonais de mínima energia, como pré-condicionador. Os resultados foram comparados com o uso do precondicionador diagonal e SSOR (Symmetric Successive Over Relaxation)
Abstract: In this work we present construction procedures of bases for the high-order finite element method (FEM) considering a procedures for the simultaneous diagonalization of the internal modes of the one-dimensional mass and stiffness matrices and orthogonalization of the boundary modes using minimum energy procedure. The concepts of minimum energy orthogonalization are used efficiently to construct one-dimensional boundary modes orthogonal to the internal modes of the shape functions. New one-dimensional bases for the high-order FEM are presented for the construction of the simultaneously diagonal and minimum energy basis for the Helmholtz norm. Furthermore, we present a calculation procedure for the $2D$ and $3D$ mass and stiffness matrices, as the combination of one-dimensional coefficients of the mass, stiffness and Jacobian matrices. This procedure is presented for quadrilateral and hexahedral distorted elements in projection, Poisson, plane state and general linear elasticity problems. The use of the one-dimensional matrices procedure allows a significant speedup compared to the standard procedure for distorted and undistorted meshes. Also, this procedure stores only one-dimensional shape functions and their derivatives calculated using one-dimensional integration points, which generates a reduction in memory consumption. The performance of the proposed bases was verified by numerical tests and the results are compared with those using the standard basis using Jacobi polynomials. Sparsity patterns, condition numbers and number of iterations using the conjugate gradient methods with diagonal preconditioner are also investigated. Furthermore, we investigated the use of the local mass matrix using simultaneously diagonal and minimum energy bases as preconditioner to solve the system of equations. The results are compared with the diagonal preconditioner and Symmetric Successive Over Relaxation (SSOR)
Doutorado
Mecanica dos Sólidos e Projeto Mecanico
Doutor em Engenharia Mecânica

Dans cette thèse, nous nous intéressons à plusieurs aspects des systèmes de racines des algèbres de Lie simples. Dans un premier temps, nous étudions les coordonnées des vecteurs propres des matrices de Cartan. Nous commençons par généraliser les travaux de physiciens qui ont montré que les masses des particules dans la théorie des champs de Toda affine sont égales aux coordonnées du vecteur propre de Perron -- Frobenius de la matrice de Cartan. Puis nous adoptons une approche différente, puisque nous utilisons des résultats de la théorie des singularités pour calculer les coordonnées des vecteurs propres de certains systèmes de racines. Dans un deuxième temps, en s'inspirant des idées de Givental, nous introduisons les matrices de Cartan q-déformées et étudions leur spectre et leurs vecteurs propres. Puis, nous proposons une q-déformation des équations de Toda et construisons des 1-solitons solutions en adaptant la méthode de Hirota, d'après les travaux de Hollowood. Enfin, notre intérêt se porte sur un ensemble de transformations agissant sur l'ensemble des bases ordonnées de racines comme le groupe de tresses. En particulier, nous étudions les bases distinguées, qui forment l'une des orbites de cette action, et des matrices que nous leur associons
In this thesis, our goal is to study various aspects of root systems of simple Lie algebras. In the first part, we study the coordinates of the eigenvectors of the Cartan matrices. We start by generalizing the work of physicists who showed that the particle masses of the affine Toda field theory are equal to the coordinates of the Perron -- Frobenius eigenvector of the Cartan matrix. Then, we adopt another approach. Namely, using the ideas coming from the singularity theory, we compute the coordinates of the eigenvectors of some root systems. In the second part, inspired by Givental's ideas, we introduce q-deformations of Cartan matrices and we study their spectrum and their eigenvectors. Then, we propose a q-deformation of Toda's equations et compute 1-solitons solutions, using the Hirota's method and Hollowood's work. Finally, our interest is focused on a set of transformations which induce an action of the braid group on the set of ordered root basis. In particular, we study an orbit for this action, the set of distinguished basis and some associated matrices

C'est sous l'impulsion des travaux fondateurs de Schumpeter que l'innovation se positionne au coeur de l'analyse économique. Depuis ces travaux fondateurs, trop peu d'innovation studies se sont toutefois consacrées aux usages du brevet dans la longue durée. Partant de là, cette thèse a pour ambition première de fournir, outre des renseignements empiriques de bonne qualité et de nouvelles séries statistiques, une lecture renouvelée, d'inspiration cliométrique, des brevets dans leurs dimensions structurelles et spatiales. Notre premier apport est de présenter l'organisation d'une nouvelle base de données sur l'évolution de longue période des brevets dans 40 pays du XVIIe siècle à 1945 et dans plus de 150 pays de 1945 à nos jours. Nous montrons, par la suite, que des événements certes rares, mais particulièrement significatifs, ont conditionné les pulsations de l'histoire économique des brevets. Les guerres, la promulgation de lois, l'ouverture ou la fermeture d'offices, mais aussi des effets purement statistiques ont, sur le très long terme, normé, à travers le dépôt et la délivrance des séries étudiées, l'existence des systèmes de brevets. En prolongement, nous déterminons, à travers une analyse spectrale et co-spectrale, la périodicité de nos séries de brevets. Enfin, nous livrons un éclairage plus contemporain, en termes de convergence, sur les dynamiques structurelles et surtout spatiales en oeuvre dans les systèmes de brevets des pays européens
At the behest of Schumpeter's seminal works, innovation is now positioned at the heart of economic analysis. However, since these pioneering works, not enough innovation studies have been devoted to the uses of patent over time. Starting from this assertion, the present thesis aims first and foremost at providing - in addition to good quality empirical information and new statistical series - a new interpretation of patents in their structural and spatial dimensions, based on a cliometric approach. Our first contribution is to present the organisation of a new database on the evolution over a long period of time of patents in 40 countries from the XVIIth century up to 1945 and in over 150 countries from 1945 to the present time. We show in a second step that rare but nevertheless significant events conditioned the heartbeat of the economic history of patents. Wars, the promulgation of laws, the opening or closing of offices, but also purely statistical effects standardized over the long term the existence of patent systems through the application and granting of the series under study. Furthermore we determine the periodicity of our patent series using a spectral and co-spectral analysis. Finally we propose a more contemporary insight - in terms of convergence - into structural and more specifically spatial dynamics at work in the European countries patent systems

Made available in DSpace on 2016-06-02T19:33:10Z (GMT). No. of bitstreams: 1 LIMA_Tania_2013.pdf: 544878 bytes, checksum: 3ab61a445786d45aa5a0f88a548b8b74 (MD5) Previous issue date: 2013-06-10
This research sought to understand the Brazilian youth unemployment in the period 2003 - 2011. The aim of this study is to verify if the business cycles and changes in the minimum wage have been affecting youth unemployment, considering the control of socioeconomic variables. In order to develop such analyses, this study has considered linear panel data as one estimation method and dynamic panel as the other method. In addition, the current research has been considered the four initial interviews contained in PME database. The results of the study show that the youth unemployment rate has been affected by economic cycles, wages and socioeconomic variables, like proportion of labor force non-white , formal sector and metropolitan region that the individual belongs to. Concerning the dynamic character, the previous level of youth unemployment and economic cycles are the main factors affecting the variability of youth unemployment rate. It is worth mentioning that the present study splits the youth group into two subcategories, "teens" and "young-adults", aiming at verifying whetherthe cycles and wages have been impacting in a similar fashion. Thus, the results show that the two distinct subcategories demonstrate different sensitiveness, making room for the creationof different public policies.
A presente pesquisa buscou compreender o desemprego juvenil brasileiro no período 2003 - 2011. O objetivo do presente estudo consiste em verificar se os ciclos econômicos e as mudanças no salário-mínimo afetam o desemprego juvenil, controlado por variáveis socioeconômicas. Para dada análise utilizou-se os métodos de estimação painel linear e painel dinâmico, sendo consideradas as quatro entrevistas iniciais da base de dados da PME (Pesquisa Mensal de Empregos). Os resultados do estudo apontaram que a taxa de desemprego juvenil é afetada em nível pelos ciclos econômicos, salário e variáveis socioeconômicas, tais como proporção da força de trabalho não branca, carteira assinada e a região metropolitana que o indivíduo pertencia. No tocante ao caráter dinâmico, nota-se que o nível do desemprego juvenil passado e a variável de ciclo econômico são os principais fatores a afetarem a taxa de desemprego dos jovens. Vale ressaltar que a presente pesquisa dividiu o grupo juvenil em duas subcategorias, adolescentes e jovem-adulto , no intuito de verificar se ciclos e salários impactavam da mesma forma. Sendo assim, observou-se que as duas subcategorias apresentam sensibilidades distintas, dando espaço para escopos de políticas públicas diferenciados.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
In this work, we present a special class of linear codes: parameterized affine codes. We show that these codes are easy to construct and that given a parameterized affine code one can easily obtain an equivalent projective parameterized code equivalent to it. We also studied some topics which served as the theoretical foundations for the work, such as the theory of Groebner Bases, the footprint of an ideal and some topics of algebraic geometry and commutative algebra. This work has as main goal to obtain the basic parameters (length, dimension and minimum distance) of parameterized codes related and also to relate them to the projective parameterized codes, as done in [7]. We finish by applying the theory of Groebner Bases to the footprint of a certain ideal in order to obtain the basic parameters of the parameterized code over an affine torus.
Neste trabalho apresentamos uma classe especial de códigos lineares: os códigos parametrizados afins. Mostramos que esses códigos são de fácil construção e que, dado um código parametrizado afim, pode-se facilmente obter um código parametrizado projetivo equivalente a ele. Também estudamos algumas teorias que nos serviram como base teórica tais como: a teoria de Bases de Groebner e a Pegada de um ideal e alguns tópicos de geometria algébrica e álgebra comutativa. Este trabalho tem por objetivo principal obter os parâmetros básicos (comprimento, dimensão e distância mínima) dos códigos parametrizados afins e relacioná-los com os códigos parametrizados projetivos, assim como na referência [7]. Encerramos aplicando a teoria de Bases de Groebner a Pegada de um ideal para obter os parâmetros básicos do código parametrizado no toro afim.
Mestre em Matemática

This article intends to analyze treatment and functions assigned to the penalty by our Peruvian Constitution and the way this legal institution is conducted at the prescribed basic penalty level (imposed by the legislator ineach type of criminal offence), the specific penalty level (imposed by the judge according to its individual characteristics in each case) and at the penitentiary enforcement level. Finally recommends some considerations for carrying out a possible legislative reform in accordance with a criminal policy plan within our constitutional framework.
El presente trabajo busca efectuar un análisis en torno al tratamiento y las funciones que nuestra Constitución política asigna a la pena, y la manera como dicha institución se desarrolla en nuestro país con respectoa la pena abstracta (la impuesta por el legislador en cada tipo penal), la pena concreta (la impuesta por el juez luego de una individualización en cada casoconcreto), y su ejecución en el ámbito penitenciario. Finaliza proponiendo algunas consideraciones para una eventual reforma legislativa conforme conun plan de política criminal que se encuentre dentro del marco constitucional.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
In this work we present the determination of the second Hamming weight of generalized Reed- Muller codes in most cases (see Teorema 4.6). Our main reference is [13], although we have also used results from [3] and [5]. In the first chapter we describe finite fields e we show how they can be constructed. In chapter 2 we present the basics of coding theory. We define what are error correcting codes, the Hamming metric, the parameters of a code, the equivalence of codes through the concept of isometry, and we briefly present generalized Reed-Muller codes and their parameters. In chapter 3 we present some results from Grobner bases theory and the definition of Affine Cartesian codes, which generalize the generalized Reed-Muller codes. we use tools from Grobner bases theory to determine the dimension and the minimum distance of Affine Cartesian codes. We finish our work in chapter 4, with the determination of the second Hamming weight for generalized Reed-Muller codes in most cases.
Nesse trabalho apresentamos o cálculo do segundo peso de Hamming de códigos de Reed-Muller generalizados na maioria dos casos (v. Teorema 4.6). Nossa referência principal sera [13], embora tenhamos utilizado também resultados de [3] e [5]. No primeiro capítulo descrevemos os corpos finitos e mostramos como podem ser construídos. No capítulo 2 apresentamos os conceitos básicos da teoria de códigos. Nele, definimos o que são os códigos corretores de erros, a métrica de Hamming, os parâmetros de um código, a equivalência de códigos através da noção de isometria, bem como uma breve apresentação dos códigos de Reed-Muller generalizados e seus parâmetros. No capítulo 3 sao apresentados alguns resultados da teoria de Bases de Grobner e a definição dos Códigos Cartesianos Afins, que são uma generalização dos códigos de Reed-Muller generalizados. Usamos ferramentas da teoria de bases de Grobner para determinar a dimensão e distância mínima de Códigos Cartesianos Afins. Para finalizar nosso trabalho, no capítulo 4 determinamos o segundo peso de Hamming do Código de Reed-Muller generalizado na maioria dos casos.
Mestre em Matemática

Les travaux de cette thèse s’inscrivent dans la théorie principalement développée par Judea Pearl sur les diagrammes causaux; des modèles graphiques qui permettent de dériver toutes les quantités causales d’intérêt formellement et intuitivement. Nous traitons le problème de l’inférence de réseau causal à partir uniquement de données d’observation, c’est-à-dire sans aucune intervention de la part de l’expérimentateur. En particulier, nous proposons d’améliorer les méthodes existantes pour les rendre plus aptes à analyser des données issues du monde réel, en nous affranchissant le plus possible des contraintes sur les distributions des données, et en les rendant plus interprétables. Nous proposons une extension de MIIC, une approche basée sur les contraintes et la théorie de l’information pour retrouver la classe d’équivalence du graphe causal à partir d’observations. Notre contribution est un algorithme de discrétisation optimale basé sur le principe de description minimale pour simultanément estimer la valeur de l’information mutuelle (et multivariée) et évaluer sa significativité entre des échantillons de variables de n’importe quelle nature : continue, catégorique ou mixte. Nous mettons à profit ces développements pour analyser des jeux de données mixtes d'intérêt clinique (dossiers médicaux de patients atteints de troubles cognitifs; ou du cancer du sein) ou biologique (réseaux de régulation génique de cellules précurseur hématopoïétiques)
The work in this thesis follows the theory primarily developed by Judea Pearl on causal diagrams; graphical models that allow all causal quantities of interest to be derived formally and intuitively. We address the problem of causal network inference from observational data alone, i.e., without any intervention from the experimenter. In particular, we propose to improve existing methods to make them more suitable for analyzing real-world data, by freeing them as much as possible from constraints on data distributions, and by making them more interpretable. We propose an extension of MIIC, a constraint-based information-theoretic approach to recover the equivalence class of the causal graph from observations. Our contribution is an optimal discretization algorithm based on the minimum description length principle to simultaneously estimate the value of mutual (and multivariate) information and evaluate its significance between samples of variables of any nature: continuous, categorical or mixed. We use these developments to analyze mixed datasets of clinical (medical records of patients with cognitive disorders; or breast cancer and being treated by neoadjuvant chemotherapy) or biological interest (gene regulation networks of hematopoietic stem and precursor cells)

碩士
國立臺灣大學
資訊工程學研究所
96
We give the first known optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O(n)-space compact representation Z(C) for a minimum cycle basis C of G. Each cycle in C can be computed from Z(C) in O(1) time per edge.

碩士
國立中央大學
數學研究所
100
The purpose of this thesis is to survey known results on minimum strictly fundamental cycle basis. It is hoped that our survey will facilitate future research in the study of minimum strictly fundamental cycle basis. Proofs of some existing results are provided if we could not get the old papers containing them. In this thesis, we also provide some new results.

碩士
國立臺灣科技大學
電機工程系
91
With the advance of computer and networking techniques, distributed computing has emerged as an important paradigm for many computing tasks. The scale and complexity of distributed systems are rapidly growing, so the probability that some processes may fail is becoming a critical factor for system performance. If the distributed system is equipped with fault-tolerance ability, we may save a lot of resources and, as a result, make the efficiency of the system much better. For a long-term executing task, rollback-recovery is an efficient fault-tolerance mechanism. In this paper, we propose a novel rollback-recovery mechanism. It alleviates many drawbacks of the previous mechanisms. Our scheme introduces a temporary logic ring which is formed among the set of the processes. The ring is used to circulate a control token on which message logging information is carried so that only a minimal set of the processes need to take checkpoints. As the processes run asynchronously in our mechanism, the overhead of the system is light during the normal operation. No synchronization is needed for our scheme; each processes can decide when to take their checkpoints by themselves. The task of garbage collection is fairly simple as only a single global checkpoint need be maintained at any time. When an error occurs, we need only rollback to the previous checkpoint.

碩士
國立暨南國際大學
資訊工程學系
95
Tournaments have many interesting research topic in the field of graph theory. Brualdi and Li have proved that the number of 3-cycles of minimum tournaments formed by the minimum score sequence is n – 3。 In this thesis, we discuss the relation between a minimum tournament and its spanning tree. We propose an algorithm for finding all 3-cycles of minimum tournaments and prove that its time complexity is O(m + n), where n is the number of nodes and m is the total number of out-degrees in the tournaments.

碩士
國立臺灣大學
資訊工程學研究所
103
Let G be an n-node simple directed planar graph with nonnegative edge weights. We study the fundamental problems of computing (1) a global cut of G with minimum weight and (2) a cycle of G with minimum weight. The best previously known algorithm for the former problem, running in O(n log3 n) time, can be obtained from the algorithm of Lacki, Nussbaum, Sankowski, and Wulff-Nilsen for single-source all-sinks maximum flows. The best previously known result for the latter problem is the O(n log3 n)-time algorithm of Wulff-Nilsen. By exploiting duality between the two problems in planar graphs, we solve both problems in O(n log n log log n) time via a divide-and-conquer algorithm that finds a shortest non-degenerate cycle. The kernel of our result is an O(n log log n)-time algorithm for computing shortest noncrossing paths among nodes well ordered on a common face of a directed plane graph, which is extended from the algorithm of Italiano, Nussbaum, Sankowski, and Wulff-Nilsen for an undirected plane graph.

Avec les récents développements obtenus grâce aux modèles globaux magnétohydrodynamiques en trois dimensions de la convection solaire, il est désormais possible de simuler des champs magnétiques structurés à grande échelle et présentant des inversions de polarité bien synchronisées dans chaque hémisphère. Ces modèles qui n'incluent, pour la plupart, aucune modélisation de la surface du Soleil génèrent donc leur dynamo avec l'action de la force électromotrice turbulente (FEM) et de la rotation différentielle uniquement. À partir de cette FEM, différentes techniques peuvent être utilisées pour extraire les coefficients de transport turbulent. Notamment, différents auteurs ont obtenu un tenseur alpha (coefficient du premier ordre) dont les 9 composantes présentent des amplitudes du même ordre, remettant en doute l'approximation faite dans le cas des modèles dynamo de type alphaOmega qui ne tient en compte qu’une de composante du tenseur. À partir d'un code d'analyse par décomposition en valeurs singulières pour évaluer les coefficients du tenseur alpha, nous avons généralisé la procédure pour extraire 18 des composantes du tenseur de deuxième ordre (tenseur beta). Les tenseurs alpha et beta obtenus par cette nouvelle procédure tel qu'appliquée aux sorties du modèle global EULAG-MHD, sont similaires aux tenseurs alpha et beta équivalant obtenus en utilisant l'approximation « Second Order Correlation Approximation ». À l'aide des coefficients de transport turbulent du premier ordre introduit dans un modèle dynamo en champ moyen, nous avons ensuite étudié certaines solutions magnétiques présentant des doubles dynamos. Cette analyse avait pour but de comparer les résultats obtenus par ce modèle simplifié caractérisé par la FEM provenant de EULAG-MHD aux résultats de EULAG-MHD directement. Cette preuve de concept nous a permis de démontrer que l'oscillation observée dans le champ magnétique en surface de EULAG-MHD pouvait provenir de l'action inductive d'une seconde dynamo. Une oscillation biennale est également observée dans plusieurs indices d'activité solaire dont l'origine n'est toujours pas établie. Il est évident que les deux modèles décrits ci-haut et le Soleil opèrent dans des régimes physiques différents. Toutefois, malgré leurs différences, le fait qu'il soit relativement facile de produire une seconde dynamo dans EULAG-MHD et dans le modèle en champ moyen indique que l'action inductive de la FEM peut facilement générer deux dynamos. Finalement, dans le but d'étudier les périodes de grands minima, phénomène encore non reproduit par les modèles globaux, nous avons ajouté une rétroaction magnétique sur l'écoulement azimutal au modèle dynamo cinématique en champ moyen décrit ci-haut. En analysant les solutions de ce modèle dynamo de type alpha2Omega non cinématique, nous avons pu reproduire la tendance observée jusqu'ici uniquement dans les modèles de type alphaOmega selon laquelle le nombre de nombre de Prandtl magnétique contrôle le rapport des périodes générées. De plus, en analysant une solution sur 50 000 ans présentant des périodes de grands minima et maxima non périodiques, nous avons obtenu une distribution de temps de séparation des grands minima presque exponentielle, caractéristique observée dans les reconstructions de l'activité solaire. La rotation différentielle associée à ces périodes de grands minima présente un niveau de fluctuation de 1% par rapport au profil moyen. Ce niveau de fluctuation est d'ailleurs comparable avec les reconstructions historiques de la rotation différentielle en surface obtenues lors du grand minimum de Maunder.
The recent developments achieved by tri-dimensionals magnetohydrodynamic (3D-MHD) global simulations of solar convection allow us to generate an organized large-scale magnetic fields with well-synchronized hemispheric polarity reversal. Because the vast majority of these simulations do not include a modelization of the Sun's surface layer, the generation of their dynamo is thus solely due to the action of the turbulent electromotive force (EMF) in conjunction with differential rotation. From this EMF, different methods can be used to extract the turbulent transport coefficients. In particular, various authors found a full 9 component alpha-tensor (first order coefficients) where all the components are of the same order of magnitude. This finding calls into question the alphaOmega approximation made by the vast majority of mean field dynamo models. We generalized a first order (alpha-tensor) singular value decomposition (SVD) analysis procedure to extract the 18 additional components of the second order tensor (beta-tensor). The alpha and beta tensors obtained by this new procedure as applied to the EULAG-MHD outputs, are similar to the equivalent alpha and beta tensors obtained using the second order correlation approximation (SOCA). By introducing the first order turbulent transport coefficients in a mean field dynamo model, we study the magnetic solutions where double dynamo modes were observed. This analysis allows us to compare the mean field dynamo solutions produced with the EMF, as extracted from EULAG-MHD, with the real magnetic output of EULAG-MHD. This proof of concept demonstrated that the quasi-biennal oscillation observed in the surface toroidal magnetic field in EULAG-MHD can be produced by the inductive action of a secondary dynamo. A similar quasi-biennal oscillation signal is also observed in multiple proxies of the solar activity whose origin is still not confirmed. Although the physical set of properties under which the two numerical models described above operate are different from the Sun, the fact that both models can reproduce a secondary dynamo shows us that the inductive action of the EMF can easily produce two dynamos. Finally, in order to study epochs of grand minima that still cannot be reproduced in global 3D-MHD simulations of convection, we added a magnetic feedback on the mean azimutal flow in our kinematic mean field model. This non-kinematic alpha2Omega model was able to reproduce the tendency of the Prandtl number (Pm) to control the ratio of the modulation period. More specifically, we found an inverse relation between Pm and the ratio of the main magnetic cycle period to the grand minima occurrence period. Moreover, by analyzing a simulation of a length of 50,000 years, where aperiodic periods of grand minima and maxima are observed, we found a waiting time distribution (WTD) of the grand minima close to an exponential, a characteristic also observed in the reconstruction of the solar activity. Finally, the level of fluctuation in the surface differential rotation associated with epochs of grand minima is ~1%. This level of fluctuation was also observed in historical reconstructions of the surface differential rotation during the Maunder minimum.