The aim of this thesis is to bring together two areas of the graph theory. We first give a brief exposition of graph homomorphisms and related notions that directs to the definition of the replacement operation by using an appropriate replacement graph. The tree-depth is investigated as one of considerable chara- cteristics of each graph. Finally we focus on category representations in the category Graph of all finite graphs and Graphk of all finite graphs with tree-depth at most k.

Le Cloud est devenu une plate-forme très répandue pour le déploiement d'applications distribuées. Beaucoup d'entreprises peuvent sous-traiter leurs infrastructures d'hébergement et, ainsi, éviter des dépenses provenant d'investissements initiaux en infrastructure et de maintenance.Des petites et moyennes entreprises, en particulier, attirés par le modèle de coûts sur demande du Cloud, ont désormais accès à des fonctionnalités comme le passage à l'échelle, la disponibilité et la fiabilité, qui avant le Cloud étaient presque réservées à de grandes entreprises.Les services du Cloud peuvent être offerts aux utilisateurs de plusieurs façons. Dans cette thèse, nous nous concentrons sur le modèle d'Infrastructure sous Forme de Service. Ce modèle permet aux utilisateurs d’accéder à des ressources de calcul virtualisés sous forme de machine virtuelles (MVs).Pour installer une application distribuée, un client du Cloud doit d'abord définir l'association entre son application et l'infrastructure. Il est nécessaire de prendre en considération des contraintesde coût, de ressource et de communication pour pouvoir choisir un ensemble de MVs provenant d'opérateurs de Cloud publiques et privés le plus adaptés. Cependant, étant donné la quantité exponentiel de configurations, la définition manuelle de l'association entre application et infrastructure peut être un challenge dans des scénarios à large échelle ou ayant des contraintes importantes de temps. En effet, ce problème est une généralisation du problème de calcul de homomorphisme de graphes, qui est NP-complet.Dans cette thèse, nous adressons le problème de calculer des placements initiaux et de reconfiguration pour des applications distribuées sur potentiellement de multiples Clouds. L'objectif est de minimiser les coûts de location et de migration en satisfaisant des contraintes de ressources et communications. Pour cela, nous proposons des heuristiques performantes capables de calculer des placements de bonne qualité très rapidement pour des scénarios à petite et large échelles. Ces heuristiques, qui sont basées sur des algorithmes de partition de graphes et de vector packing, ont été évaluées en les comparant avec des approches de l'état de l'art comme des solveurs exactes et des méta-heuristiques. Nous montrons en utilisant des simulations que les heuristiques proposées arrivent à calculer des solutions de bonne qualité en quelques secondes tandis que des autres approches prennent des heures ou jours pour les calculer. / The Cloud has become a very popular platform for deploying distributed applications. Today, virtually any credit card holder can have access to Cloud services. There are many different ways of offering Cloud services to customers. In this thesis we especially focus on theInfrastructure as a Service (IaaS), a model that, usually, proposes virtualized computing resources to costumers in the form of virtual machines (VMs). Thanks to its attractive pay-as-you-use cost model, it is easier for customers, specially small and medium companies, to outsource hosting infrastructures and benefit of savings related to upfront investments and maintenance costs. Also, customers can have access to features such as scalability, availability, and reliability, which previously were almost exclusive for large companies. To deploy a distributed application, a Cloud customer must first consider the mapping between her application (or its parts) to the target infrastructure. She needs to take into consideration cost, resource, and communication constraints to select the most suitable set of VMs, from private and public Cloud providers. However, defining a mapping manually may be a challenge in large-scale or time constrained scenarios since the number of possible configuration explodes. Furthermore, when automating this process, scalability issues must be taken into account given that this mapping problem is a generalization of the graph homomorphism problem, which is NP-complete.In this thesis we address the problem of calculating initial and reconfiguration placements for distributed applications over possibly multiple Clouds. Our objective is to minimize renting and migration costs while satisfying applications' resource and communication constraints. We concentrate on the mapping between applications and Cloud infrastructure. Using an incremental approach, we split the problem into three different parts and propose efficient heuristics that can compute good quality placements very quickly for small and large scenarios. These heuristics are based on graph partition and vector packing heuristics and have been extensively evaluated against state of the art approaches such as MIP solvers and meta-heuristics. We show through simulations that the proposed heuristics manage to compute solutions in a few seconds that would take many hours or days for other approaches to compute.

Dans cette thèse, nous nous intéressons à differentes colorations des sommets d’un graphe et aux homomorphismes de graphes. Nous nous intéressons plus spécialement aux graphes planaires et aux graphes peu denses. Nous considérons la coloration propre des sommets, la coloration acyclique, la coloration étoilée, lak-forêt-coloration, la coloration fractionnaire et la version par liste de la plupart de ces concepts.Dans le Chapitre 2, nous cherchons des conditions suffisantes de 3-liste colorabilité des graphes planaires. Ces conditions sont exprimées en termes de sous-graphes interdits et nos résultats impliquent plusieurs résultats connus.La notion de la coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud, et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. Dans le Chapitre 3, on obtient des conditions suffisantes pour qu’un graphe planaire admette une k-coloration acyclique par liste avec k 2 f3; 4; 5g.Dans le Chapitre 4, nous montrons que tout graphe subcubique est 6-étoilé coloriable.D’autre part, Fertin, Raspaud et Reed ont montré que le graphe de Wagner ne peut pas être 5-étoilé-coloriable. Ce fait implique que notre résultat est optimal. De plus, nous obtenons des nouvelles bornes supérieures sur la choisissabilité étoilé d’un graphe planaire subcubique de maille donnée.Une k-forêt-coloration d’un graphe G est une application ¼ de l’ensemble des sommets V (G) de G dans l’ensemble de couleurs 1; 2; ¢ ¢ ¢ ; k telle que chaque classede couleur induit une forêt. Le sommet-arboricité de G est le plus petit entier ktel que G a k-forêt-coloration. Dans le Chapitre 5, nous prouvons une conjecture de Raspaud et Wang affirmant que tout graphe planaire sans triangles intersectants admet une sommet-arboricité au plus 2.Enfin, au Chapitre 6, nous nous concentrons sur le problème d’homomorphisme des graphes peu denses dans le graphe de Petersen. Plus précisément, nous prouvons que tout graphe sans triangles ayant un degré moyen maximum moins de 5=2 admet un homomorphisme dans le graphe de Petersen. En outre, nous montrons que la borne sur le degré moyen maximum est la meilleure possible. / In this thesis, we are interested in various vertex coloring and homomorphism problems of graphs with special emphasis on planar graphs and sparsegraphs. We consider proper vertex coloring, acyclic coloring, star coloring, forestcoloring, fractional coloring and the list version of most of these concepts.In Chapter 2, we consider the problem of finding sufficient conditions for a planargraph to be 3-choosable. These conditions are expressed in terms of forbiddensubgraphs and our results extend several known results.The notion of acyclic list coloring of planar graphs was introduced by Borodin,Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that everyplanar graph is acyclically 5-choosable. In Chapter 3, we obtain some sufficientconditions for planar graphs to be acyclically k-choosable with k 2 f3; 4; 5g.In Chapter 4, we prove that every subcubic graph is 6-star-colorable. On theother hand, Fertin, Raspaud and Reed showed that the Wagner graph cannot be5-star-colorable. This fact implies that our result is best possible. Moreover, weobtain new upper bounds on star choosability of planar subcubic graphs with givengirth.A k-forest-coloring of a graph G is a mapping ¼ from V (G) to the set f1; ¢ ¢ ¢ ; kgsuch that each color class induces a forest. The vertex-arboricity of G is the smallestinteger k such that G has a k-forest-coloring. In Chapter 5, we prove a conjecture ofRaspaud and Wang asserting that every planar graph without intersecting triangleshas vertex-arboricity at most 2.Finally, in Chapter 6, we focus on the homomorphism problems of sparse graphsto the Petersen graph. More precisely, we prove that every triangle-free graph withmaximum average degree less than 5=2 admits a homomorphism to the Petersengraph. Moreover, we show that the bound on the maximum average degree in ourresult is best possible.

Cette thèse est consacrée à une classe de groupes, appelés groupes de Kac-Moody, qui généralise de façon naturelle les groupes de Lie semi-simples, ou plus précisément, les groupes algébriques réductifs, dans un contexte infini-dimensionnel. On s'intéresse plus particulièrement au problème d'isomorphismes pour ces groupes, en vue d'obtenir un analogue infini-dimensionnel de la célèbre théorie des homomorphismes 'abstraits' de groupes algébriques simples, due à Armand Borel et Jacques Tits.<p><p>Le problème d'isomorphismes qu'on étudie s'avère être un cas particulier d'un problème plus général, qui consiste à caractériser les homomorphismes de groupes algébriques vers les groupes de Kac-Moody, dont l'image est bornée. Ce problème peut à son tour s'énoncer comme un problème de rigidité pour les actions de groupes algébriques sur les immeubles, via l'action naturelle d'un groupe de Kac-Moody sur une paire d'immeubles jumelés. Les résultats partiels, relatifs à ce problème de rigidité, que nous obtenons, nous permettent d'apporter une solution complète au problème d'isomorphismes pour les groupes de Kac-Moody déployés.<p>En particulier, on obtient un résultat de dévissage pour les automorphismes de ces objets. Celui-ci fournit à son tour une description complète de la structure du groupe d'automorphismes d'un groupe de Kac-Moody déployé sur un corps de caractéristique~$0$.<p><p>Nos arguments permettent également de traiter de façon analogue certaines formes anisotropes de groupes de Kac-Moody complexes, appelées formes unitaires. On montre en particulier que la topologie Hausdorff naturelle que portent ces formes est un invariant de leur structure de groupe abstrait. Ceci généralise un résultat bien connu de H. Freudenthal pour les groupes de Lie compacts.<p><p>Enfin, l'on s'intéresse aux homomorphismes de groupes de Kac-Moody à image fini-dimensionnelle, et l'on démontre la non-existence de tels homomorphismes à noyau central, lorsque le domaine est un groupe de Kac-Moody de type indéfini sur un corps infini. Ceci réduit un problème ouvert, dit problème de linéarité pour les groupes de Kac-Moody, au cas de corps de base finis. / Doctorat en sciences, Spécialisation mathématiques / info:eu-repo/semantics/nonPublished

<p>Neka je A neprazan skup i L = (L;&middot;) proizvoljna mreža sa nulom i jedinicom. Svako preslikavanje A&macr; : A &iexcl;! L zovemo rasplinuti podskup od A. Uobičajeno je da se rasplinute podgrupe defini&scaron;u na grupi. U radu su fazi podgrupe definisane na polugrupi kao i na rasplinutoj podpolugrupi. Jedan od glavnih rezultata je teorema o particiji rasplinutih kompletno regularnih polugrupa. Takođe su definisane rasplinute kongruencije i rasplinute&nbsp;jednakosti na rasplinutim podalgebrama neke algebre i ispitane njihove osobine. Uvedeni su pojmovi: podalgebre rasplinute podalgebre, rasplinutog homomorfizma rasplinute podalgebre na rasplinutu podalgebru i direktnog proizvoda rasplinutih podalgebri. Jedan od važnijih rezultata je teorema koja je uop&scaron;tenje teoreme Birkhoff-a na rasplinutim strukturama.</p> / <p>Let A be nonemptu set, and let L = (L; 6) be a lattice with 0 and 1. The mapping A&macr; : A ! L is called fuzzy subset of A. It is usual to define fuzzy subgroup on the group. In this work fuzzy semigroups are defined on the semigroup and on the fuzzy subsemigroup, too. As a main result is theorem about partition fuzzy completlu regular semigroup. Also, fuzzy congruences are defined, and fuzzy equolites on fuzzy subalgebras of an algebra and their propertes are investigated. We introduced some new notions: subalgebras of fuzzy subalgebras, fuzzy homomorphism of fuzzy subalgebra, and direct product of fuzzy subalgebras. One of the most important result is extension of Birkhoff&rsquo;s theorem on fuzzy structures.</p>

No description available.

Ce mémoire étudie l'algorithme d'amplification de l'amplitude et ses applications dans le domaine de test de propriété. On utilise l'amplification de l'amplitude pour proposer le plus efficace algorithme quantique à ce jour qui teste la linéarité de fonctions booléennes et on généralise notre nouvel algorithme pour tester si une fonction entre deux groupes abéliens finis est un homomorphisme. Le meilleur algorithme quantique connu qui teste la symétrie de fonctions booléennes est aussi amélioré et l'on utilise ce nouvel algorithme pour tester la quasi-symétrie de fonctions booléennes. Par la suite, on approfondit l'étude du nombre de requêtes à la boîte noire que fait l'algorithme d'amplification de l'amplitude pour amplitude initiale inconnue. Une description rigoureuse de la variable aléatoire représentant ce nombre est présentée, suivie du résultat précédemment connue de la borne supérieure sur l'espérance. Suivent de nouveaux résultats sur la variance de cette variable. Il est notamment montré que, dans le cas général, la variance est infinie, mais nous montrons aussi que, pour un choix approprié de paramètres, elle devient bornée supérieurement. / This thesis studies the quantum amplitude amplification algorithm and some of its applications in the field of property testing. We make use of the amplitude amplification algorithm to design an algorithm testing the linearity of Boolean functions which is more efficient than the previously best known quantum algorithm. We then generalize this new algorithm to test if a function between two finite abelian groups is a homomorphism. We improve on the previously best known algorithm for testing the symmetry of Boolean functions and use this new algorithm to test the quasi-symmetry of Boolean functions. Next, we further the study of the query complexity of the amplitude amplification algorithm for unknown initial amplitude. We give a rigorous description of the random variable representing the number of queries made by the algorithm and present the previously known result on its expected value upper bound. We then provide new results on the variance of this random variable. It is shown that, in the general case, the variance cannot be bounded above. We show, however, that it can be bounded for an appropriate choice of parameters.

The purpose of this work is to analyse the analogue of prime modules in commutative case – strongly prime modules over rings in non-commutative case. Strongly prime modules over rings, two-sided and one-sided strongly prime ideals in the rings are examined in the work. Concepts and theorems related to this topic are analysed in the paper. These problems are solved: • Taking the homomorphism of the ring R into ring of endomorphisms of the Abelian group we get all the modules over the ring R. • Annihilators of the nonzero elements of the module over commutative ring coincide and are the prime ideal. • In non-commutative case module is strongly prime only in the case when annihilators its nonzero elements are equivalent. • Finite Cartesian product of strongly prime modules, in which annihilators of the nonzero elements are equivalent, is a strongly prime module.

Ce mémoire étudie l'algorithme d'amplification de l'amplitude et ses applications dans le domaine de test de propriété. On utilise l'amplification de l'amplitude pour proposer le plus efficace algorithme quantique à ce jour qui teste la linéarité de fonctions booléennes et on généralise notre nouvel algorithme pour tester si une fonction entre deux groupes abéliens finis est un homomorphisme. Le meilleur algorithme quantique connu qui teste la symétrie de fonctions booléennes est aussi amélioré et l'on utilise ce nouvel algorithme pour tester la quasi-symétrie de fonctions booléennes. Par la suite, on approfondit l'étude du nombre de requêtes à la boîte noire que fait l'algorithme d'amplification de l'amplitude pour amplitude initiale inconnue. Une description rigoureuse de la variable aléatoire représentant ce nombre est présentée, suivie du résultat précédemment connue de la borne supérieure sur l'espérance. Suivent de nouveaux résultats sur la variance de cette variable. Il est notamment montré que, dans le cas général, la variance est infinie, mais nous montrons aussi que, pour un choix approprié de paramètres, elle devient bornée supérieurement. / This thesis studies the quantum amplitude amplification algorithm and some of its applications in the field of property testing. We make use of the amplitude amplification algorithm to design an algorithm testing the linearity of Boolean functions which is more efficient than the previously best known quantum algorithm. We then generalize this new algorithm to test if a function between two finite abelian groups is a homomorphism. We improve on the previously best known algorithm for testing the symmetry of Boolean functions and use this new algorithm to test the quasi-symmetry of Boolean functions. Next, we further the study of the query complexity of the amplitude amplification algorithm for unknown initial amplitude. We give a rigorous description of the random variable representing the number of queries made by the algorithm and present the previously known result on its expected value upper bound. We then provide new results on the variance of this random variable. It is shown that, in the general case, the variance cannot be bounded above. We show, however, that it can be bounded for an appropriate choice of parameters.

<p>In this thesis local methods are made available as a tool to study the<br />unary parts of clones (or, equivalently, the weak Krasner algebras). Using the<br />language of model theory and Galois connections we develop a link between<br />homomorphism-homogeneous relational structures and local methods, via the<br />notion of endolocality. The theoretical results that are obtained are used to develop<br />a systematic theory for the classification of homomorphism-homogeneous<br />relational structures.</p> / <p>U ovoj tezi su razvijene lokalne metode koje se mogu koristiti za izu-<br />ˇcavanje unarnih delova klonova (ili, ekvivalentno, slabih Krasnerovih algebri).<br />Koriˇs&acute;cenjem jezika teorije modela i Galoovih veza uspostavljen je odnos izmedu<br />homomorfizam-homogenih relacionih struktura i lokalnih metoda, preko pojma<br />endolokalnosti. Dobijeni teoretski rezultati su upotrebljeni za razvoj sistematske<br />teorije za klasifikaciju homomorfizam-homogenih struktura.</p>