Dissertations / Theses on the topic 'Matrice partitions'

Cette thèse est consacrée au problème de la comparaison de deux partitions non strictes (floues/probabilistes, possibilistes) d'un même ensemble d'individus en plusieurs clusters. Sa résolution repose sur la définition formelle de mesures de concordance reprenant les principes des mesures historiques développées pour la comparaison de partitions strictes et trouve son application dans des domaines variés tels que la biologie, le traitement d'images, la classification automatique. Selon qu'elles s'attachent à observer les relations entre les individus décrites par chacune des partitions ou à quantifier les similitudes entre les clusters qui composent ces partitions, nous distinguons deux grandes familles de mesures pour lesquelles la notion même d'accord entre partitions diffère, et proposons d'en caractériser les représentants selon un même ensemble de propriétés formelles et informelles. De ce point de vue, les mesures sont aussi qualifiées selon la nature des partitions comparées. Une étude des multiples constructions sur lesquelles reposent les mesures de la littérature vient compléter notre taxonomie. Nous proposons trois nouvelles mesures de comparaison non strictes tirant profit de l'état de l'art. La première est une extension d'une approche stricte tandis que les deux autres reposent sur des approches dite natives, l'une orientée individus, l'autre orientée clusters, spécifiquement conçues pour la comparaison de partitions non strictes. Nos propositions sont comparées à celles de la littérature selon un plan d'expérience choisi pour couvrir les divers aspects de la problématique. Les résultats présentés montrent l'intérêt des propositions pour le thème de recherche qu'est la comparaison de partitions. Enfin, nous ouvrons de nouvelles perspectives en proposant les prémisses d'un cadre qui unifie les principales mesures non strictes orientées individus.

On dit d'un sous-ensemble de NP qu'il présente une dichotomie s'il contient des problèmes qui sont soit résolubles en temps polynomial (dans Ptime), soit difficiles (NP-complets). La classe des problèmes de satisfaction de contraintes (CSP) finis est un sous-ensemble bien connu de NP qui présente une telle dichotomie. La classe de complexité NP n'a pas de dichotomie à moins que P = NP. Pour ces deux classes, il existe des logiques qui leur sont associées. -- NP est capturé par la logique Existentielle du second ordre (ESO) par le théorème de Fagin, c'est-à-dire qu'un problème est dans NP si et seulement s'il est exprimable par une formule ESO.-- CSP est un sous-ensemble de la logique de Feder et Vardi, le fragment monotone, monadique et sans inégalités de SNP, lui-même un fragment syntaxique de ESO (MMSNP); et, pour chaque formule de MMSNP, il existe un problème CSP équivalent via des réductions polynomiales.Ceci implique que la logique ESO, tout comme NP, n'a pas de dichotomie, à contraster avec le fait que MMSNP a une dichotomie tout comme CSP. L'objectif principal de cette thèse est d'étudier les propriétés de dichotomie de sous-ensembles de NP qui contiennent strictement CSP ou MMSNP.Feder et Vardi ont prouvé que si nous omettons une des trois propriétés qui définissent MMSNP, à savoir être monotone, monadique ou omettre les inégalités, alors la logique résultante n'a pas de dichotomie. Comme leurs preuves restent parfois sommaires, nous revisitons ces résultats et fournissons des preuves détaillées. Le fragment guardé et monotone de SNP (GMSNP) est une extension connue de MMSNP qui est obtenue en relâchant la restriction "monadique" de MMSNP. Nous définissons de manière similaire une nouvelle logique appelée MMSNP avec des inégalités gardées, en relâchant la restriction d'être "sans inégalités". Nous prouvons qu'elle est strictement plus expressive que MMSNP et qu'elle possède également une dichotomie.Il existe une logique MMSNP₂ qui étend MMSNP de la même manière que MSO₂ étend la logique monadique du second ordre (MSO). On sait que MMSNP₂ est un fragment de GMSNP et que ces deux classes ont toutes deux une dichotomie ou n'en ont pas. Nous revisitons ce résultat et le renforçons en prouvant que, en ce qui concerne le fait d'avoir une dichotomie, sans perte de généralité, on peut considérer seulement les problèmes MMSNP₂ sur des signatures à un élément, au lieu des problèmes GMSNP sur des signatures finies arbitraires.Nous cherchons à prouver l'existence d'une dichotomie pour les MMSNP₂ en construisant en temps polynomial, pour tout problème MMSNP₂, un problème MMSNP équivalent. Nous rencontrons quelques obstacles pour construire une telle équivalence. Cependant, si nous permettons aux formules MMSNP d'être composées d'un nombre dénombrable de conjonctions négatives, nous prouvons qu'une telle équivalence existe. De plus, la formule MMSNP infinie correspondante a la propriété d'être "régulière". Cette propriété de régularité signifie que, dans un certain sens, cette formule est essentiellement finie. Il est connu que les problèmes MMSNP réguliers peuvent être exprimés par CSP sur des modèles oméga-catégoriques. De plus, il existe une caractérisation de la dichotomie algébrique pour les CSP oméga-catégoriques qui décrivent des problèmes MMSNP. Si l'on parvient à étendre cette caractérisation algébrique sur les problèmes réguliers MMSNP, alors notre résultat fournirait une dichotomie algébrique pour MMSNP₂. (...)
A subset of NP is said to have a dichotomy if it contains problem that are either solvable in P-time or NP-complete. The class of finite Constraint Satisfaction Problems (CSP) is a well-known subset of NP that follows such a dichotomy. The complexity class NP does not have a dichotomy unless P = NP. For both of these classes there exist logics that are associated with them. -- NP is captured by Existential Second-Order (ESO) logic by Fagin's theorem, i.e., a problem is in NP if and only if it is expressible by an ESO sentence.-- CSP is a subset of Feder and Vardi's logic, Monotone Monadic Strict NP without inequalities (MMSNP), and for every MMSNP sentence there exists a P-time equivalent CSP problem. This implies that ESO does not have a dichotomy as well as NP, and that MMSNP has a dichotomy as well as CSP. The main objective of this thesis is to study subsets of NP that strictly contain CSP or MMSNP with respect to the dichotomy existence.Feder and Vardi proved that if we omit one of the three properties that define MMSNP, namely being monotone, monadic or omitting inequalities, then the resulting logic does not have a dichotomy. As their proofs remain sketchy at times, we revisit these results and provide detailed proofs. Guarded Monotone Strict NP (GMSNP) is a known extension of MMSNP that is obtained by relaxing the "monadic" restriction of MMSNP. We define similarly a new logic that is called MMSNP with Guarded inequalities, relaxing the restriction of being "without inequalities". We prove that it is strictly more expressive than MMSNP and that it also has a dichotomy.There is a logic MMSNP₂ that extends MMSNP in the same way as MSO₂ extends Monadic Second-Order (MSO) logic. It is known that MMSNP₂ is a fragment of GMSNP and that these two classes either both have a dichotomy or both have not. We revisit this result and strengthen it by proving that, with respect to having a dichotomy, without loss of generality, one can consider only MMSNP₂ problems over one-element signatures, instead of GMSNP problems over arbitrary finite signatures.We seek to prove the existence of a dichotomy for MMSNP₂ by finding, for every MMSNP₂ problem, a P-time equivalent MMSNP problem. We face some obstacles to build such an equivalence. However, if we allow MMSNP sentences to consist of countably many negated conjuncts, then we prove that such an equivalence exists. Moreover, the corresponding infinite MMSNP sentence has a property of being "regular". This regular property means that, in some sense, this sentence is still finite. It is known that regular MMSNP problems can be expressed by CSP on omega-categorical templates. Also, there is an algebraic dichotomy characterisation for omega-categorical CSPs that describe MMSNP problems. If one manages to extend this algebraic characterisation onto regular MMSNP, then our result would provide an algebraic dichotomy for MMSNP₂.Another potential way to prove the existence of a dichotomy for MMSNP₂ is to mimic the proof of Feder and Vardi for MMSNP. That is, by finding a P-time equivalent CSP problem. The most difficult part there is to reduce a given input structure to a structure of sufficiently large girth. For MMSNP and CSP, it is done using expanders, i.e., structures, where the distribution of tuples is close to a uniform distribution. We study this approach with respect to MMSNP₂ and point out the main obstacles. (...)

Cette thèse est consacrée à l'étude d'identités qu'on observe à l'interface entre le domaine des modèles intégrables en physique statistique et la combinatoire. L'histoire a commencé quand Mills, Robbins et Rumsey étudiaient des Matrices à Signes Alternants (ASM). En 1982, ils proposèrent une formule d'énumération. Pendant qu'ils cherchaient une preuve de cette formule ils découvrirent l'existence d'autres objets comptés par la même formule : les Partitions Planes Totalement Symétriques Auto-Complémentaires (TSSCPP). C'est seulement quelques années plus tard que Zeilberger fut capable de prouver cette égalité, prouvant que les deux objets sont comptés par la même formule. La même année, Kuperberg utilise l'intégrabilité quantique (notion venue de la physique statistique) pour donner une preuve plus simple. En 2001, Razumov et Stroganov conjecturèrent une intrigante relation entre les ASM et l'état fondamental du modèle de spins XXZ (pour Delta=-1/2), lui aussi intégrable. Cette conjecture a été démontrée en 2010 par Cantini et Sportiello. L'objectif principal de ce manuscrit est de comprendre le rôle de l'intégrabilité dans cette histoire, notamment le rôle joué par l'équation de Knizhnik-Zamolodchikov quantique. Grâce à cette équation nous avons été capables de démontrer plusieurs conjectures combinatoires, dont une version raffinée de l'équalité entre le nombre des TSSCPP et des ASM proposée en 1986 par Mills, Robbins et Rumsey et certains propriétés des composantes du vecteur fondamental du modèle XXZ. Est présentée aussi une série de nouvelles conjectures concernant l'état fondamental.

Cette thèse est consacrée à l'étude d'identités qu'on observe à l'interface entre le domaine des modèles intégrables en physique statistique et la combinatoire. L'histoire commence quand Mills, Robbins et Rumsey étudiaient des Matrices de Signe Alternant (ASM). En 1982, ils proposèrent une formule d'énumeration. Pendant qu'ils cherchaient une preuve de cette formule ils découvrirent l'existence d'autres objets comptés par la même formule : les Partitions Planes Totalement Symétriques Auto-Complementaires (TSSCPP). C'est seulement quelques années plus tard que Zeilberger fut capable de prouver cet équalité, prouvant que tout les deux objets sont comptés par la même formule. La même année, Kuperberg utilise l'integrabilité quantique (notion venu de la physique statistique) pour donner une preuve plus simple. En 2001, Razumov et Stroganov conjecturèrent une intrigante relation entre les ASM et l'état fondamental du modèle de spins XXZ (pour Delta=-1/2), lui aussi intégrable. Cette conjecture fut démontrée en 2010 par Cantini et Sportiello. L'objectif principal de ce manuscrit est de comprendre le rôle de l'intégrabilité dans cette histoire, notamment, le rôle joué par l'équation Knizhnik-Zamolodchikov quantique. Grâce à cette équation nous avons été capables de démontrer plusieurs conjectures combinatoires, dont une version raffinée de l'équalité entre le nombre des TSSCPP et des ASM proposée en 1986 par Mills, Robbins et Rumsey et certains propriétés des composantes du vecteur fondamental du modèle XXZ. Est présentée aussi une série de nouvelles conjectures concernant l'état fondamental.

Cette thèse se situe dans le domaine de la combinatoire bijective et est consacrée à la construction d’une bijection explicite entre deux familles d’objets combinatoires : les matrices à signes alternants (ASMs) et les partitions planes totalement symétriques auto-complémentaires (TSSCPPs). L’histoire a commencé lorsque Milis, Robbins et Rumsey étudiaient les ASMs et proposèrent une formule d’énumération en 1982. Durant leurs recherches, ils découvrirent l’existence d’autres objets comptés par la même formule : les TSSCPPs. Dix ans plus tard, une preuve non bijective de l’équiénumération de ces deux familles fut donnée par Zeilberger. Pour ce faire, Zeilberger utilise deux sous classes de motif de Gelfand-Tsetlin ; les triangles Gog et les triangles Magog. Pendant ces dernières années les recherches se sont multipliées afin de donner une preuve bijective du théorème de Zeilberger. Citons notamment les travaux de Krattenthaler qui construit une bijection explicite entre les trapézoïdes Gog et Magog à une ligne. L’étape suivante, celle des trapézoïdes à deux lignes, semblait inaccessible. L’objectif de cette thèse est de résoudre ce problème grace à l’utilisation d’un outil fondamental en combinatoire, l’involution de Schiitzenberger. Nous avons pour cela défini des nouvelles statistiques sur les triangles Gog et les triangles Magog et nous montrons expérimentalement que la bijection que nous construisons respecte ces statistiques. Nous présentons également de nouvelles conjectures sur ces statistiques.

We explore two methods for calculating the Taylor Coefficients of the terms of the asymptotic expansion of the partition function of random matrices for specific even potentials. The first of these methods applies to the leading order term. We show that this term has an elementary form in terms of a solution to an algebraic equation. This generates a general formula for the Taylor Coefficients of this term. Next we exploit the relationship between orthogonal polynomials and the Toda Lattice Equations to derive ODE's for the general terms of the expansion of the partition function of random matrices, which leads to a method of calculating the Taylor Coefficients of these functions.

The interplay between spectrum and structure of graphs is the recurring theme of the three more or less independent chapters of this thesis. The first chapter provides a method to relate the eigensolutions of two matrices, one being the principal submatrix of the other, via an arbitrary annihilating polynomial. This is extended to lambda-matrices and to matrices the entries of which are rational functions in one variable. The extension may be interpreted as a possible generalization of other known techniques which aim at reducing the size of a matrix while preserving the spectral information. Several aspects of an application in order to reduce the computational costs of ordinary eigenvalue problems are discussed. The second chapter considers the straightforward extension of the well known concept of equitable partitions to weighted graphs, i.e. complex matrices. It provides a method to divide the eigenproblem into smaller parts corresponding to the front divisor and its complementary factor in an easy and stable way with complexity which is only quadratic in matrix size. The exploitation of several equitable partitions ordered by refinement is discussed and a suggestion is made that preserves hermiticity if present. Some generalizations of equitable partitions are considered and a basic procedure for finding an equitable partition of complex matrices is given. The third chapter deals with isospectral and unitary equivalent graphs. It introduces a construction for unitary equivalent graphs which contains the well known GM-switching as a special case. It also considers an algebra of graph matrices generated by the adjacency matrix that corresponds to the 1-dimensional Weisfeiler-Lehman stabilizer in a way that mimics the correspondence of the coherent closure and the 2-dimensional Weisfeiler-Lehman stabilizer. The algebra contains the degree matrix, the (combinatorial, signless and normalized) Laplacian and the Seidel matrix. An easy construction produces graph pairs that are simultaneously unitary equivalent w.r.t. that algebra.

Neste trabalho, com base em representações por matrizes de duas linhas para alguns tipos de partição (algumas já conhecidas e outras novas), identificamos propriedades sugeridas por classificá-las de acordo com a soma dos elementos de sua segunda linha. Esta soma sempre fornece alguma propriedade da partição relacionada. Se considerarmos versões sem sinal de algumas funções Mock Theta, seu termo geral pode ser interpretado como função geradora para algum tipo de partição com restrições. Para retornar aos coeficientes originais, é possível definir um peso para cada matriz e depois somá-las para contá-los. Uma representação análoga para essas partições nos permite observar propriedades sobre elas, novamente por meio de uma classificação referente à soma dos seu elementos da segunda linha. Esta seriação é feita por meio de tabelas criadas pelo software matemático Maple, as quais nos sugerem padrões e identidades relacionadas com outros tipos de partições conhecidas e, muitas vezes, encontrando uma fórmula fechada para contá-las. Tendo as conjecturas obtidas, elas são provadas por meio de bijeções entre conjuntos ou por contagem.
In this work, based on representations by matrices of two lines for some kind of partition (some already known and other new ones), we identify properties suggested by classifying them according to the sum of its second line. This sum always provides some properties of the related partition. If we consider unsigned versions of some Mock Theta Functions, its general term can be interpreted as generating function for some kind of partition with restrictions. To come back to the original coefficients, you can set a weight for each array and so add them to evaluate the coefficients. An analogous representation for partitions allows us to observe properties, again by classificating them according to the sum of its elements on the second row. This classification is made by means of tables created by mathematical software Maple, which suggest patterns, identities related to other known types of partitions and often, finding a closed formula to count them. Having established conjectured identities, all are proved by bijections between sets or counting methods.

Cette thèse porte sur le partitionnement parallèle de graphes et essentiellement sur son application à la renumérotation de matrices creuses. Nous utilisons pour résoudre ce problème un schéma multi-niveaux dont nous avons parallélisé les phases de contraction et d'expansion. Nous avons ainsi introduit pour la phase de contraction un nouvel algorithme de gestion des conflits d'appariements distants, tout en améliorant les algorithmes déjà existants en leur associant une phase de sélection des communications les plus utiles. Concernant la phase d'expansion, nous avons introduit la notion de graphe bande qui permet de diminuer de manière très conséquente la taille du problème à traiter par les algorithmes de raffinement. Nous avons généralisé l'utilisation de ce graphe bande aux implantations séquentielles et parallèles de notre outil de partitionnement SCOTCH. Grâce à la présence du graphe bande, nous avons proposé une utilisation nouvelle des algorithmes génétiques dans le cadre de l'expansion en les utilisant comme heuristiques parallèles de raffinement de la partition.

La conversion de la biomasse lignocellulosique en biocarburants et molécules biosourcées produit des matrices liquides complexes thermosensibles qui couvrent une large gamme de polarités et de masses moléculaires. Les outils analytiques développés dans la littérature donnent une description partielle de ces matrices oxygénées. Pour en comprendre la réactivité et mieux guider le développement des procédés de conversion, une meilleure caractérisation est nécessaire. L’objectif de cette thèse est de démontrer l’apport d’une dimension de fractionnement pertinente en amont de techniques séparatives pour accéder à la caractérisation à l’échelle moléculaire d’échantillons ex-biomasse. Une déformulation complète et structurée par familles chimiques est visée, sans perte ni modification des composés. Deux voies de fractionnement ont été investiguées : (1) fractionnement par solubilité à l’aide de l’extraction liquide-liquide (LLE) et de la chromatographie de partage centrifuge (CPC) et (2) fractionnement par taille avec la chromatographie d’exclusion stérique (SEC). Ces techniques se veulent complémentaires à une analyse par chromatographie liquide à polarité de phase inversée avec détection par spectroscopie ultraviolet-visible et spectrométrie de masse haute résolution (RPLC-UV/HRMS). Des méthodes de fractionnement LLE, CPC et SEC ont été développées sur molécules modèles afin d’identifier les mécanismes et la sélectivité chimique mis en jeu. Des cartographies 2D inédites ont ainsi été obtenues, assurant un gain important en pouvoir résolutif et une structuration nouvelle des chromatogrammes en comparaison à l’approche RPLC-UV/HRMS. Dans un second temps, le potentiel des couplages SECxRPLC-UV/HRMS et CPCxRPLC-UV/HRMS pour la description de matrices complexes a été illustré via l’étude de deux échantillons issus d’expérimentations en unités pilotes et de compositions chimiques très différentes, représentant deux voies possibles de transformation (biochimique et thermochimique) de biomasse lignocellulosique. La complémentarité entre les approches de séparation mises au point a ainsi permis de doubler le nombre de pics détectés tout en bénéficiant de l’organisation chimique des composés. Cette aide précieuse à l’identification a été renforcée par les informations structurales délivrées via les différents modes de détection, en particulier l’HRMS. La compréhension de la structuration des cartographies 2D a été présentée et discutée afin de proposer la stratégie la plus adaptée pour déformuler complètement un échantillon en s’appuyant sur la mesure de descripteurs pertinents. Enfin, l’une des approches développée dans cette thèse a été mise en œuvre pour l’isolement sélectif et l’élucidation structurale de molécules clefs au sein d’une matrice complexe à l’aide d’expériences en fragmentation MS et spectroscopie de résonance magnétique nucléaire (RMN)
The conversion of lignocellulosic biomass into biofuels and biosourced molecules produces complex thermosensitive liquid matrices which cover a wide range of polarity and molecular weight. Analytical tools developed in the literature only give a partial description of these oxygenated matrices. To understand the reactivity of these samples and optimize the development of conversion processes, a better characterization is required. The objective of this thesis is to demonstrate the interest of a relevant fractionation step prior to separation techniques to help the molecular characterization of biomass samples. The reverse engineering proposed for the sample is desired complete and chemically controlled (without loss or sample modification). Two fractionation pathways were investigated: (1) solubility fractionation with liquid-liquid extraction (LLE) and centrifugal partition chromatography (CPC) and (2) size fractionation with size exclusion chromatography (SEC). These techniques intend to be complementary to reversed-phase liquid chromatography hyphenated to ultraviolet-visible spectroscopy detection and high resolution mass spectrometry (RPLC-UV/HRMS). LLE, CPC and SEC methods were developed on model molecules to understand mechanisms involved and control the chemical selectivity. 2D contour plots were obtained, improving the resolving power and structuring chromatograms in comparison with RPLC-UV/HRMS. Then, SECxRPLC-UV/MS and CPCxRPLC-UV/MS hyphenations were applied to describe two complex samples from different substrates produced on experimental pilot units from two possible conversion pathways of lignocellulosic biomass (biochemical and thermochemical). The complementarity of separation modes allows to double the number of peaks detected, benefiting from the chemical organization of compounds. This constitute a support to identification also enhanced by multi-detection which provide additional structural information on compound detected, especially HRMS. Chemical organization in 2D contour plots were presented and discussed to propose the most adapted strategy to fully fractionate a sample based on the measurement of relevant descriptors. Finally, one of the fractionation approach developed in this thesis was used to isolate and structurally elucidate key molecules of a complex sample through MS fragmentation experiments and nuclear magnetic resonance spectroscopy (NMR)

La chromatographie bidimensionnelle préparative suscite de plus en plus d'intérêt dans l'élucidation d'échantillons complexes car elle permet de collecter un grand nombre de molécules à haute pureté et quantitée récupérée. Bien que la chromatographie liquide (LC) soit souvent choisie en deuxième dimension, la chromatographie de partage centrifuge (CPC) à de multiples avantages qui en font une technique de choix pour la première dimension. Dans le but de purifier plusieurs molécules d’intérêt dans les matrices végétales, le couplage «comprehensive» CPCxLC représente une technique à fort potentiel. Après avoir expliqué son intérêt et les enjeux liés à la séparation préparative en mode «comprehensive», le développement d’une telle séparation est étudiée selon trois axes. Tout d’abord, une purification de deux molécules d’intérêt dans la plante Edelweiss est réalisée à l’échelle industrielle grâce à la réalisation de cartographies 2D au laboratoire. Cette application permet de montrer l’intérêt du couplage et de mettre en évidence les verrous liés aux conditions de transfert total des fractions en deuxième dimension. Dans une deuxième partie, la séparation CPCxLC en mode « comprehensive » est développée avec le transfert total de l’échantillon en deuxième dimension pour la purification de cinq composés cibles présents dans la plante Edelweiss. Les points clés de la séparation CPCxLC, à savoir le temps d’échantillonnage et le transfert en deuxième dimension, sont étudiés au regard du couplage LCxLC afin de garantir une qualité de séparation permettant la récupération totale des composés. Enfin, la troisième partie consiste à la mise en place d’une méthodologie de sélection des systèmes CPCxLC basée sur l’évaluation quantitative du potentiel des systèmes bidimensionnels à apporter de la distance entre les pics. Cette procédure de sélection est développée sur l’échantillon Cyclopia genistoides avec l’objectif d’isoler huit composés cibles
Preparative two-dimensional chromatography is gaining interest in the elucidation of complex samples as it allows the collection of a large number of molecules with high recovered purity and quantity. While the second dimension is often selected to be liquid chromatography (LC), centrifugal partition chromatography (CPC) is a technique with multiple advantages representing a suitable first dimension. In order to purify several molecules of interest in plant matrices, the comprehensive CPCxLC represents a technique with high potential. After explaining its interest and the issues related to the preparative separation in comprehensive mode, the development of such a separation is studied according to three axes. Firstly, a purification of two targeted molecules in Edelweiss plant is carried out at industrial scale thanks to the realization of 2D-contour plot. This application allows to expose the interest of the separation and to highlight the locks related to the conditions of total transfer of the fractions in second dimension. In a second part, the comprehensive CPCxLC separation is developed with the total transfer of the sample in second dimension applied to the purification of five target compounds from Edelweiss plant. The key points of the CPCxLC separation, namely the sampling time and the second dimension transfer, are studied with regard to the LCxLC separation in order to ensure a separation quality allowing the total recovery of the compounds. Finally, the third part consists in the implementation of a CPCxLC system selection methodology based on the quantitative evaluation of the potential of two-dimensional systems to generate distance between peaks. This selection procedure is developed on the sample Cyclopia genistoides with the objective of isolating eight target compounds

Les parcours en largueur lexicographiques ont ete introduits en 1976 pour reconnaitre les graphes triangules. Depuis des proprietes interessantes de ce parcours ont ete mises en evidence (notamment pour la reconnaissance des graphes d'intervalles). Pour mieux comprendre ces parcours, nous avons, dans un premier temps, etudie leur application d'origine : la reconnaissance des graphes triangules. Nous obtenons une generalisation des algorithmes de reconnaissance des graphes triangules. Nous en deduisons une unique preuve de ces algorithmes. Nous mettons ensuite en evidence des proprietes diametrales des parcours en largeur lexicographiques pour deux classes de graphes : les graphes triangules et les graphes sans triplet asteroide. Nous montrons que, deux parcours permettent de trouver un sommet dont l'excentricite differe du diametre d'au plus 1. Les parcours en largeur lexicographiques peuvent etre compris comme un processus d'affinage de partition. Cette technique est utilisee dans de nombreuses applications : tri de chaines de caracteres, minimisation d'automates finis deterministes, orientation transitive d'un graphe, reconnaissance des graphes d'intervalles nous proposons une structure de donnees et un algorithme generique pour toutes ces applications. Ainsi nous mettons en evidence des liens entre ces problemes et pouvons esperer de nouveaux resultats algorithmiques.

The research work presented in this thesis concern to the stability analysis of linear time-delay systems with low-order controllers. This thesis is divided into three parts.The first part of the thesis focus on the study of linear SISO (single-input/single-output) systems with input/output delays, where the feedback loop is closed with a controller of PID-type. Inspired by the geometrical approach developed by Gu et al. we propose an analytical method to find the stability regions of all stabilizing controllers of PID-type for the time-delay system. Based on this same approach, we propose an algorithm to calculate the degree of fragility of a given controller of PID- type (PI, PD and PID).The second part of the thesis focuses on the stability analysis of linear systems under an NCS (Networked System Control) based approach. More precisely, we first focus in the stabilization problem by taking into account the induced network delays and the effects induced by the sampling period. To carry out such an analysis we have adopted an eigenvalue perturbation-based approach.Finally, in the third part of the thesis we tackle certain problems concerning to the behavior of the zeros of a certain class of sampled-data SISO systems. More precisely, given a continuous-time system, we obtain the sampling intervals guaranteeing the invariance of the number of unstable zeros in each interval. To perform such an analysis, we adopt an eigenvalue perturbation-based approach.

Etude theorique des divers aspects des phenomenes critiques bidimensionnels par des methodes essentiellement analytiques: transformation en modeles de champ libre, exploitation de la symetrie conforme. Determination des valeurs exactes d'exposants critiques, et des expressions des fonctions de partition et des fonctions de correlation. Test d'un certain nombre de resultats par des calculs de matrice de transfert ou des simulations de monte carlo

A semigroup is simply a set with an associative binary operation; computational semigroup theory is the branch of mathematics concerned with developing techniques for computing with semigroups, as well as investigating semigroups with the help of computers. This thesis explores both sides of computational semigroup theory, across several topics, especially in the finite case. The central focus of this thesis is computing and describing maximal subsemigroups of finite semigroups. A maximal subsemigroup of a semigroup is a proper subsemigroup that is contained in no other proper subsemigroup. We present novel and useful algorithms for computing the maximal subsemigroups of an arbitrary finite semigroup, building on the paper of Graham, Graham, and Rhodes from 1968. In certain cases, the algorithms reduce to computing maximal subgroups of finite groups, and analysing graphs that capture information about the regular I-classes of a semigroup. We use the framework underpinning these algorithms to describe the maximal subsemigroups of many families of finite transformation and diagram monoids. This reproduces and greatly extends a large amount of existing work in the literature, and allows us to easily see the common features between these maximal subsemigroups. This thesis is also concerned with direct products of semigroups, and with a special class of semigroups known as Rees 0-matrix semigroups. We extend known results concerning the generating sets of direct products of semigroups; in doing so, we propose techniques for computing relatively small generating sets for certain kinds of direct products. Additionally, we characterise several features of Rees 0-matrix semigroups in terms of their underlying semigroups and matrices, such as their Green's relations and generating sets, and whether they are inverse. In doing so, we suggest new methods for computing Rees 0-matrix semigroups.

Thesis (Ph. D.)--University of Wisconsin--Madison, 1999.
Typescript. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 74-77).

The interplay between spectrum and structure of graphs is the recurring theme of the three more or less independent chapters of this thesis. The first chapter provides a method to relate the eigensolutions of two matrices, one being the principal submatrix of the other, via an arbitrary annihilating polynomial. This is extended to lambda-matrices and to matrices the entries of which are rational functions in one variable. The extension may be interpreted as a possible generalization of other known techniques which aim at reducing the size of a matrix while preserving the spectral information. Several aspects of an application in order to reduce the computational costs of ordinary eigenvalue problems are discussed. The second chapter considers the straightforward extension of the well known concept of equitable partitions to weighted graphs, i.e. complex matrices. It provides a method to divide the eigenproblem into smaller parts corresponding to the front divisor and its complementary factor in an easy and stable way with complexity which is only quadratic in matrix size. The exploitation of several equitable partitions ordered by refinement is discussed and a suggestion is made that preserves hermiticity if present. Some generalizations of equitable partitions are considered and a basic procedure for finding an equitable partition of complex matrices is given. The third chapter deals with isospectral and unitary equivalent graphs. It introduces a construction for unitary equivalent graphs which contains the well known GM-switching as a special case. It also considers an algebra of graph matrices generated by the adjacency matrix that corresponds to the 1-dimensional Weisfeiler-Lehman stabilizer in a way that mimics the correspondence of the coherent closure and the 2-dimensional Weisfeiler-Lehman stabilizer. The algebra contains the degree matrix, the (combinatorial, signless and normalized) Laplacian and the Seidel matrix. An easy construction produces graph pairs that are simultaneously unitary equivalent w.r.t. that algebra.

Flavour is widely accepted as a major determinant of consumer satisfaction, so factors that influence flavour quality are of great interest to both food scientists and the manufacturing industry globally. Volatile organic compounds (VOC) play an important role in characterising the unique flavour profile of foods. However non-volatile matrix solutes are capable of selectively binding these compounds and modifying their availability for perception during consumption. The impact of carbohydrates and lipids has been extensively studied which has led to a comprehensive understanding of the principles governing their interaction with flavour volatiles. Proteins, in comparison, remain poorly understood. This is due mainly to their structural diversity and resulting range of available binding mechanisms which can change in response to environmental conditions such as those encountered during food processing. Myofibrillar proteins are compositionally significant components of skeletal muscle tissue and play a critical role in defining the textural properties of processed meat products including burgers and sausages. To determine their influence on flavour, a series of model solutions were analysed and partition coefficients Kg-m calculated to enable changes in compound volatility to be measured. Eleven different flavour volatiles were evaluated, including a number of plant derived bioactive compounds not previously considered in binding studies. Partition coefficients were measured using static headspace-gas chromatography (SH-GC) methods partnered with indirect phase ratio variation (PRV) techniques. The retention effect of myofibrillar proteins was quantified by reporting the percentage change in Kg-m following the introduction of protein extract into the system. Myofibrillar proteins were obtained from a series of extractions of pork loin fillet with sodium phosphate buffer. The process yielded 58.6 mg/g of muscle which accounted for an approximate recovery rate of 60% of total available proteins. Subsequent instrumental analysis confirmed that at 35°C, a 2 mg/mL protein extract was capable of binding all volatile compounds, to various degrees, reducing their volatility, or headspace concentration, and therefore the availability of each compound for sensory perception. The greatest effect was recorded for isomers citral and neral, with 55.9% and 59.1% retention reported respectively, followed by ethyl hexanote which gave 36.7% retention. Thymol and carvacrol followed closely, with 28.6% and 33.7% retention respectively. Data collected throughout the study strongly indicates that myofibrillar proteins interact predominantly via weak reversible associations that are enhanced with increasing levels of flavour compound hydrophobicity. Both SH-GC and PRV are commonly utilised in flavour interaction investigations and are known to have areas of limitation that must be considered throughout application. During instrumental method development however, a significant obstacle was encountered which had not been documented previously. After considerable method development, it was concluded that mass spectrometer (MS) detectors are not suitable for use in PRV trials due to the repeated injection of headspace water vapour into the system. This damaged MS components and limited the ionisation of analytes required for their detection.
Thesis (MPhil) -- University of Adelaide, School of Agriculture, Food & Wine, 2016

Chromatography is one of the most studied methods, due to its simplicity, versatility and high reproducibility, to separate and purify molecules that can have therapeutic, industrial and biotechnological interest. In recent years, the development of new chromatographic matrices has been continuously increased in order to afford rapid and efficient separations and decrease the use of resources. Gellan gum is a natural anionic exopolysaccharide and, in the presence of divalent cations, has the ability to form thermos-reversible strong gels resistant to temperature and extreme acidic conditions. In this work, it was proposed the preparation of gellan gum microbeads to be used as a stable chromatographic stationary phase. In order to produce the matrix, a low-cost water-in-oil emulsion technique was adopted. To obtain optimal conditions to the bead formulation, experimental design was applied, which allowed the optimization of the experimental conditions and to produce microbeads with the smallest diameter possible. Due to the negative charge of gellan gum, it was possible to study the interactions established with three model proteins (BSA, a-chymotrypsin and lysozyme) and with a therapeutic complex protein, SCOMT. In the model protein assays, MES buffer with pH 6.2 was used, which conferred negative charge to BSA and positive charge to a-chymotrypsin and lysozyme, due to its isoelectric points. Thus, BSA did not bind to the matrix while the other two proteins were retained to the gellan gum, being eluted with an increase of ionic strength. Regarding to prepurified SCOMT sample, a buffer with pH 4.0 was used under equilibrium conditions, conferring positive charge to the protein, thus, it also interacted with the column and was majorly eluted by pH manipulation (by changing the buffer pH to 6.4), allowing the elimination of some protein contaminants. Dynamic binding capacity assay of the gellan gum microbeads was made, in order to characterize this support as a novel chromatographic matrix. The values of DBC of the gellan gum stationary phase to 10 % and 50 % of breakthrough were 2.43 mg/mL and 4.73 mg/mL, respectively. These DBC values are satisfactory when compared to commercial resins used in affinity chromatography, taking into account that protein interaction only occurred at the gellan bead surface. These results indicated that gellan gum microbeads obtained by waterin- oil emulsion technique can be used as an innovative and promising chromatographic support due to its gelling ability and versatility to interact with different biomolecules.
A cromatografia é um dos métodos mais usados para a separação e purificação de diferentes biomoléculas terapêuticas. É uma técnica que tem sido muito explorada, ao longo dos últimos anos, nas áreas da indústria farmacêutica e biotecnológica para a obtenção de proteínas e ácidos nucleicos com elevado grau de pureza. Os suportes cromatográficos têm sido alvo de grandes desenvolvimentos a fim de encontrar uma matriz que reúna as características ideais como porosidade, estabilidade química e física, elevada eficiência de transferência de massa, baixo custo de produção associado, biocompatibilidade, hidrofilicidade, boa capacidade de manutenção do fluxo e capacidade de reutilização após vários ensaios cromatográficos. A goma de gelana é um polímero polissacárido natural linear que tem uma vasta gama de aplicações em diversas áreas, desde a indústria alimentar (agente espessante e gelificante), cosmética (loções, cremes, maquilhagem, etc), indústria biotecnológica (como um substituinte do agar), indústria farmacêutica (sistema de entrega direcionada de fármacos e microencapsulações) e medicina (construção de “scaffolds” para regeneração de tecidos). Devido às suas propriedades como versatilidade, biocompatibilidade, biodegradabilidade e elevada estabilidade, a gelana tem atraído grande interesse por parte do mercado e tem ganho crescente importância entre as diferentes indústrias. A gelana possui a capacidade de, em determinadas condições e na presença de catiões divalentes, sofrer uma alteração conformacional formando uma forte rede tridimensional devido às interações entre a gelana, os iões e as moléculas de água dando origem a um gel termoreversível, resistente a altas temperaturas e a extremas condições ácidas. Tendo em conta as características apresentadas, o presente trabalho teve como objetivo otimizar a formulação de uma matriz cromatográfica pela técnica de emulsão água-em-óleo a fim de ser usada em diversos processos cromatográficos. A inovação deste projeto tem como base a produção de microesferas através de um método de emulsão água-em-óleo, usando dois líquidos imiscíveis, a água e um óleo alimentar vegetal. Trata-se de uma técnica que não requer o uso de instrumentos complexos, é de fácil manuseamento, tem baixo custo associado e permite o fácil controlo dos parâmetros associados a este processo. A preparação das esferas foi feita de acordo com os seguintes parâmetros: concentração da goma de gelana (1 % - 2,5 %), velocidade de agitação (250 rpm – 750 rpm) e temperatura (20 ºC – 100 ºC). Considerando que todos estes fatores afetam a estabilidade e estrutura das microesferas, foram feitas várias formulações utilizando um desenho experimental, estratégia que permitiu obter as condições ótimas no sentido de se produzirem micropartículas com o mínimo diâmetro possível. As condições ótimas fornecidas pelo desenho foram 1,41 % de concentração de gelana, 749,47 rpm de velocidade de agitação e 99,20 ºC para obter microesferas com um tamanho de 277,08 µm. Para a formulação deste suporte cromatográfico, foi necessário a presença de catiões divalentes numa solução de reforço, para onde as esferas foram transferidas a fim de aumentar a estabilidade. O catião escolhido foi o bário, que devido ao seu grande tamanho iónico é considerado bastante eficaz na gelificação da gelana, pois contribui largamente para a formação da estável e rígida rede tridimensional. Além disso, o bário também permitiu a formação de esferas uniformes de tamanho reduzido com um pequeno ratio de inchaço. Para a validação do modelo fornecido pelo software do desenho experimental, foi necessário efetuar cinco réplicas de dois pontos previstos dados pelo programa. A visualização das esferas produzidas foi feita através de microscopia ótica que permitiu a medição dos diâmetros das micropartículas e através de microscopia eletrónica de varrimento, que tornou possível a análise estrutural das esferas num estado liofilizado, bem como a análise topográfica e morfológica da sua superfície. Além disso, esta última metodologia também permitiu avaliar a porosidade das esferas, de onde foi constatado a ausência de canais interiores, sugerindo que qualquer interação estabelecida com a matriz de goma de gelana se dê apenas na sua superfície. Aproveitando a natureza aniónica do polímero de gelana e o facto de não ter que ser funcionalizada com ligandos como os suportes cromatográficos comerciais, foi possível explorar diferentes interações com as proteínas modelo albumina sérica bovina (BSA), a-quimotripsina e lisozima, bem como com um extracto parcialmente purificado da proteína catecol-O-metiltransferase humana na isoforma solúvel (hSCOMT). Nos ensaios com as proteínas modelo, o tampão usado foi o MES a pH 6.2, o que conferiu carga negativa à BSA e cargas positivas à a-quimotripsina e lisozima devido aos seus pontos isoelétricos. Assim, a BSA não ligou à matriz tendo sido eluída após a injeção da amostra na coluna, ainda com a passagem do tampão sem sal, enquanto as outras duas proteínas interagiram devido à oposição de cargas, tendo sido eluídas com o aumento da força iónica. Quanto à amostra pré-purificada de SCOMT, foi usado um tampão de pH 4.0 nas condições de equilíbrio, o que conferiu carga positiva a esta proteína. Esta condição permitiu a interação desta proteina com a coluna, tendo sido maioritariamente eluída através da manipulação do pH (alterando o pH do tampão para 6.4), permitindo assim a eliminação de algumas proteínas contaminantes presentes na amostra. A fim de se caracterizar melhor esta nova matriz cromatográfica, foi determinada a capacidade dinâmica de ligação utilizando uma estratégia de saturação da coluna com uma solução de lisozima 0,5 mg/mL a 1 mL/min. Os valores obtidos na capacidade de ligação das microesferas de goma de gelana a 10 % e 50 % da curva de saturação foram 2,43 mg/mL e 4,73 mg/mL, respetivamente. Comparando com outras matrizes cromatográficas comerciais e tendo em conta que apenas a área de superfície das microesferas de gelana é funcional, estes valores estão dentro do esperado. Estes estudos permitiram concluir que a estabilidade da matriz cromatográfica de gelana foi incrementada com o desenvolvimento deste projecto de mestrado e que permitiu a interação com proteínas de várias naturezas, através de estratégias de eluição com manipulação de força iónica e pH. Em suma, os dados apresentados manifestam uma versatilidade da gelana em interagir com diferentes biomoléculas e, devido à sua capacidade de gelificação, foi possível a elaboração deste inovador e promissor suporte cromatográfico para a cromatografia de troca catiónica, a partir de microesferas da goma de gelana.