We study reducibility for nowhere-zero flows. A reducibility proof typically consists of showing that some induced subgraphs cannot appear in a minimum counter-example to some conjecture. We derive algebraic proofs of reducibility. We define variables which in some sense count the number of nowhere-zero flows of certain type in a graph and then deduce equalities and inequalities that must hold for all graphs. We then show how to use these algebraic expressions to prove reducibility. In our case, these inequalities and equalities are linear. We can thus use the well developed theory of linear programming to obtain certificates of these proof. We make publicly available computer programs we wrote to generate the algebraic expressions and obtain the certificates.

We study reducibility for nowhere-zero flows. A reducibility proof typically consists of showing that some induced subgraphs cannot appear in a minimum counter-example to some conjecture. We derive algebraic proofs of reducibility. We define variables which in some sense count the number of nowhere-zero flows of certain type in a graph and then deduce equalities and inequalities that must hold for all graphs. We then show how to use these algebraic expressions to prove reducibility. In our case, these inequalities and equalities are linear. We can thus use the well developed theory of linear programming to obtain certificates of these proof. We make publicly available computer programs we wrote to generate the algebraic expressions and obtain the certificates.

No description available.

Cette thèse vise à concevoir des estimateurs non-asymptotiques et robustes pour les systèmes linéaires d’ordre fractionnaire dans un environnement bruité. Elle traite une classe des systèmes linéaires d’ordre fractionnaire modélisée par la dite pseudo représentation d’état avec des conditions initiales inconnues. Elle suppose également que les systèmes étudiés ici peuvent être transformés sous la forme canonique de Brunovsky. Pour estimer le pseudo-état, la forme précédente est transformée en une équation différentielle linéaire d’ordre fractionnaire en prenant en compte les valeurs initiales des dérivées fractionnaires séquentielles de la sortie. Ensuite, en utilisant la méthode des fonctions modulatrices, les valeurs initiales précédentes et les dérivées fractionnaires avec des ordres commensurables de la sortie sont données par des formules algébriques avec des intégrales à l’aide d’une méthode récursive. Ainsi, ces formules sont utilisés pour calculer le pseudo-état dans le cas continu sans bruit. En outre, elle fournit un algorithme pour construire les fonctions modulatrices requises à l’accomplissement de l’estimation. Deuxièmement, inspiré par la méthode des fonctions modulatrices développée pour l’estimation de pseudo-état, cette méthode algébrique basée sur un opérateur est introduite pour estimer la dérivée fractionnée avec un ordre arbitraire fractionnaire de la sortie pour les systèmes considérés. Cet opérateur sert à annuler les valeurs initiales non désirées, puis permet d’estimer la dérivée fractionnaire souhaitée par une nouvelle formule algébrique à l’aide d’une méthode récursive. Troisièmement, l’estimateur du pseudo-état et le différenciateur d’ordre fractionnaire obtenus précédemment sont étudiés respectivement dans le cas discret et bruité. Chacun d’entre eux contient une erreur numérique due à la méthode d’intégration numérique utilisée et au bruit. En particulier, elle fournit une analyse pour diminuer la contribution du bruit au moyen d’une d’erreur bornée qui permet de sélectionner les degrés optimaux des fonctions de modulation à chaque instant. Ensuite, des exemples numériques sont donnés pour mettre en évidence la précision, la robustesse et la propriété non-asymptotique des estimateurs proposés. En outre, les comparaisons avec certaines méthodes existantes et avec un nouvel observateur d’ordre fractionnaire de typeH1sont montrées. Enfin, elle donne des conclusions / This thesis aims to design non-asymptotic and robust estimators for a class of fractional order linear systems in noisy environment. It deals with a class of commensurate fractional order linear systems modeled by the so-called pseudo-state space representation with unknown initial conditions. It also assumed that linear systems under study can be transformed into the Brunovsky’s observable canonical form. Firstly, the pseudo-state of the considered systems is estimated. For this purpose, the Brunovsky’s observable canonical form is transformed into a fractional order linear differential equation involving the initial values of the fractional sequential derivatives of the output. Then, using the modulating functions method, the former initial values and the fractional derivatives with commensurate orders of the output are given by algebraic integral formulae in a recursive way. Thereby, they are used to calculate the pseudo-state in the continuous noise-free case. Moreover, to perform this estimation, it provides an algorithm to build the required modulating functions. Secondly, inspired by the modulating functions method developed for pseudo-state estimation, an operator based algebraic method is introduced to estimate the fractional derivative with an arbitrary fractional order of the output. This operator is applied to cancel the former initial values and then enables to estimate the desired fractional derivative by a new algebraic formula using a recursive way. Thirdly, the pseudo-state estimator and the fractional order differentiator are studied in discrete noisy case. Each of them contains a numerical error due to the used numerical integration method, and the noise error contribution due to a class of stochastic processes. In particular, it provides ananalysis to decrease noise contribution by means of an error bound that enables to select the optimal degrees of the modulating functions at each instant. Then, several numerical examples are given to highlight the accuracy, the robustness and the non-asymptotic property of the proposed estimators. Moreover, the comparisons to some existing methods and a new fractional orderH1-like observer are shown. Finally, conclusions are outlined with some perspectives

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-26T17:27:53Z No. of bitstreams: 1 monicacristinamelquiadesduque.pdf: 697556 bytes, checksum: bf32f50f1172cd3d5154fa9a1bbb5219 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-05-13T12:03:30Z (GMT) No. of bitstreams: 1 monicacristinamelquiadesduque.pdf: 697556 bytes, checksum: bf32f50f1172cd3d5154fa9a1bbb5219 (MD5) / Made available in DSpace on 2017-05-13T12:03:30Z (GMT). No. of bitstreams: 1 monicacristinamelquiadesduque.pdf: 697556 bytes, checksum: bf32f50f1172cd3d5154fa9a1bbb5219 (MD5) Previous issue date: 2013-02-20 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Apresenta-se aqui uma discussão sobre três métodos para o cálculo do propagador de Feynman para alguns modelos em mecânica quântica não relativística. O formalismo de Feynman é apenas um dos vários existentes para a abordagem de problemas na mecânica quântica. O primeiro método é um cálculo da integral de caminho, que é baseado em uma relação de recorrência para a produção de propagadores infinitesimais. Essa relação de recorrência não tem aparecido em discussões anteriores da integral de caminho do oscilador harmônico unidimensional, embora seja inspirada por uma relação similar em um sistema tridimensional. O segundo método foi desenvolvido por Schwinger em 1951 para tratar ações efetivas na eletrodinâmica quântica baseado na solução das equações de movimento do operador de Heisenberg. Com o uso adequado do operador ordenado e subordinadas as condições iniciais produz o propagador. Por fim, o terceiro método, que usa-se de técnicas algébricas baseadas na fatoração do operador evolução temporal usando a fórmula Baker-Campbell-Hausdorff. / Here we present a discussion of three methods to calculate the Feynman propagator for some models in non-relativistic quantum mechanics. The formalism of Feynman is just one of several available for addressing problems in quantum mechanics. The first method is a calculation of the integral path, which is based on a recurrence relation for the production of infinitesimal propagators. This recurrence relation has not appeared in previous discussions of the full path of the one-dimensional harmonic oscillator, although inspired by a similar relationship in a three-dimensional system. The second method was developed by Schwinger in 1951 for treating effective action in quantum electrodynamics based on the solution of the equations of motion of the Heisenberg operator. With the proper use of the operator ordained and subordinated the initial conditions produces the propagator. Finally, the third method, which uses the algebraic techniques are based on factorization of the time evolution operator using the formula Baker-Campbell-Hausdorff.

Made available in DSpace on 2014-06-11T19:23:39Z (GMT). No. of bitstreams: 0 Previous issue date: 2005-08-29Bitstream added on 2014-06-13T18:07:17Z : No. of bitstreams: 1 oliveira_kpm_me_ilha.pdf: 4592597 bytes, checksum: 54231cd87b58b957eaaa00ebf38e513b (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho trata da elaboração de um aplicativo computacional em Visual Basic capaz de gerar malhas estruturadas e não estruturadas sobre domínios bidimensionais multiplamente conexos. Esta geração deverá ocorrer de modo bastante automático com pouca intervenção do usuário, a qual será efetuada através de uma interface gráfica amigável. Para armazenamento das malhas definiu-se uma estrutura de dados de fácil compatibilidade com aplicativos computacionais baseados no método dos elementos finitos para solução de problemas do tipo convectivo-difusivo. Os tipos de células (elementos finitos) que foram implementadas são: células triangulares lineares e células quadrilaterais quadráticas. Adicionalmente gerou-se malhas bidimensionais para solução de problemas clássicos do tipo convectivo-difusivo, utilizando-se códigos de elementos finitos já desenvolvidos por pesquisadores do grupo de pesquisa. / The mesh generation is needed in many applications of numerical methods such as finite difference, finite volume and finite element methods. In this work the algebraic method has been applied to generate 2D structured and unstructured mesh of quadrilateral and triangular elements by using Visual Basic. Both linear and quadratic elements can be generated. The connectivity, the nodes coordinates and contour nodes can be saved in an automatic way for a posterior use in, for example, a solver of finite element methods. A friendly interface has been developed for easy usage by users. Some tests have been done in applications of convective-diffusive fluid flows problems using solvers previously constructed, based on finite elements methods to demonstrate the capabilities of the mesh generator.

Resumo: Este trabalho trata da elaboração de um aplicativo computacional em Visual Basic capaz de gerar malhas estruturadas e não estruturadas sobre domínios bidimensionais multiplamente conexos. Esta geração deverá ocorrer de modo bastante automático com pouca intervenção do usuário, a qual será efetuada através de uma interface gráfica amigável. Para armazenamento das malhas definiu-se uma estrutura de dados de fácil compatibilidade com aplicativos computacionais baseados no método dos elementos finitos para solução de problemas do tipo convectivo-difusivo. Os tipos de células (elementos finitos) que foram implementadas são: células triangulares lineares e células quadrilaterais quadráticas. Adicionalmente gerou-se malhas bidimensionais para solução de problemas clássicos do tipo convectivo-difusivo, utilizando-se códigos de elementos finitos já desenvolvidos por pesquisadores do grupo de pesquisa. / Abstract: The mesh generation is needed in many applications of numerical methods such as finite difference, finite volume and finite element methods. In this work the algebraic method has been applied to generate 2D structured and unstructured mesh of quadrilateral and triangular elements by using Visual Basic. Both linear and quadratic elements can be generated. The connectivity, the nodes coordinates and contour nodes can be saved in an automatic way for a posterior use in, for example, a solver of finite element methods. A friendly interface has been developed for easy usage by users. Some tests have been done in applications of convective-diffusive fluid flows problems using solvers previously constructed, based on finite elements methods to demonstrate the capabilities of the mesh generator. / Orientador: João Batista Aparecido / Coorientador: João Batista Campos Silva / Banca: Amarildo Tabone Paschoalini / Banca: Carlos Roberto Ribeiro / Mestre

<p dir="ltr">A bath of free electrons interacting with a local quantum impurity leads to various exotic non-Fermi liquid behaviors, such as the non-integer effective ground state degeneracy of the impurity and the correction to the zero temperature conductance, which is temperature to the power of a fractional number. The former indicates emergent anyons, which are the key ingredients for achieving topological protected quantum computations. The latter can be used for experimentally probing non-Fermi liquid physics. It was recently proposed that a Coulomb blockaded M-Majorana island coupled to normal metal leads realizes a novel type of Kondo effect where the effective impurity “spin” transforms under the orthogonal group SO(M). Inspired by the multichannel generalization of the original Kondo model, we introduce a physically motivated N-channel generalization of this topological Kondo model whose impurity spin stems from the non-local topological ground state degeneracy of the island. This multichannel topological Kondo model supports Z3 parafermion and Fibonacci anyon (not supported by one-channel topological Kondo model) but may be limited to experiments because it is unstable to channel anisotropy. Therefore, we propose a Majorana-free meso- scopic setup which implements the Kondo effect of the symplectic Lie group and can harbor emergent anyons (including Majorana fermions, Fibonacci anyons, and Z3 parafermions) even in the absence of perfect channel symmetry. Besides, I comment on the future work such as the strong tunneling case that is beyond the topological Kondo regime and the two-impurity Kondo physics.</p>

La réduction des informations redondantes et/ou non-pertinentes dans la description de données est une étape importante dans plusieurs domaines scientifiques comme les statistiques, la vision par ordinateur, la fouille de données ou l’apprentissage automatique. Dans ce manuscrit, nous abordons la réduction de la taille des signatures des images par une méthode issue de l’Analyse Formelle de Concepts (AFC), qui repose sur la structure du treillis des concepts et la théorie des treillis. Les modèles de sac de mots visuels consistent à décrire une image sous forme d’un ensemble de mots visuels obtenus par clustering. La réduction de la taille des signatures des images consiste donc à sélectionner certains de ces mots visuels. Dans cette thèse, nous proposons deux algorithmes de sélection d’attributs (mots visuels) qui sont utilisables pour l’apprentissage supervisé ou non. Le premier algorithme, RedAttSansPerte, ne retient que les attributs qui correspondent aux irréductibles du treillis. En effet, le théorème fondamental de la théorie des treillis garantit que la structure du treillis des concepts est maintenue en ne conservant que les irréductibles. Notre algorithme utilise un graphe d’attributs, le graphe de précédence, où deux attributs sont en relation lorsque les ensembles d’objets à qui ils appartiennent sont inclus l’un dans l’autre. Nous montrons par des expérimentations que la réduction par l’algorithme RedAttsSansPerte permet de diminuer le nombre d’attributs tout en conservant de bonnes performances de classification. Le deuxième algorithme, RedAttsFloue, est une extension de l’algorithme RedAttsSansPerte. Il repose sur une version approximative du graphe de précédence. Il s’agit de supprimer les attributs selon le même principe que l’algorithme précédent, mais en utilisant ce graphe flou. Un seuil de flexibilité élevé du graphe flou entraîne mécaniquement une perte d’information et de ce fait une baisse de performance de la classification. Nous montrons par des expérimentations que la réduction par l’algorithme RedAttsFloue permet de diminuer davantage l’ensemble des attributs sans diminuer de manière significative les performances de classification. / In several scientific fields such as statistics, computer vision and machine learning, redundant and/or irrelevant information reduction in the data description (dimension reduction) is an important step. This process contains two different categories : feature extraction and feature selection, of which feature selection in unsupervised learning is hitherto an open question. In this manuscript, we discussed about feature selection on image datasets using the Formal Concept Analysis (FCA), with focus on lattice structure and lattice theory. The images in a dataset were described as a set of visual words by the bag of visual words model. Two algorithms were proposed in this thesis to select relevant features and they can be used in both unsupervised learning and supervised learning. The first algorithm was the RedAttSansPerte, which based on lattice structure and lattice theory, to ensure its ability to remove redundant features using the precedence graph. The formal definition of precedence graph was given in this thesis. We also demonstrated their properties and the relationship between this graph and the AC-poset. Results from experiments indicated that the RedAttsSansPerte algorithm reduced the size of feature set while maintaining their performance against the evaluation by classification. Secondly, the RedAttsFloue algorithm, an extension of the RedAttsSansPerte algorithm, was also proposed. This extension used the fuzzy precedence graph. The formal definition and the properties of this graph were demonstrated in this manuscript. The RedAttsFloue algorithm removed redundant and irrelevant features while retaining relevant information according to the flexibility threshold of the fuzzy precedence graph. The quality of relevant information was evaluated by the classification. The RedAttsFloue algorithm is suggested to be more robust than the RedAttsSansPerte algorithm in terms of reduction.