In this thesis we study two different topics, both in the context of semigroup constructions. The first is the investigation of an embedding problem, specifically the problem of whether it is possible to embed any given finitely presentable semigroup into a D-simple finitely presentable semigroup. We consider some well-known semigroup constructions, investigating their properties to determine whether they might prove useful for finding a solution to our problem. We carry out a more detailed study into a more complicated semigroup construction, the Byleen extension, which has been used to solve several other embedding problems. We prove several results regarding the structure of this extension, finding necessary and sufficient conditions for an extension to be D-simple and a very strong necessary condition for an extension to be finitely presentable. The second topic covered in this thesis is relative rank, specifically the sequence obtained by taking the rank of incremental direct powers of a given semigroup modulo the diagonal subsemigroup. We investigate the relative rank sequences of infinite Cartesian products of groups and of semigroups. We characterise all semigroups for which the relative rank sequence of an infinite Cartesian product is finite, and show that if the sequence is finite then it is bounded above by a logarithmic function. We will find sufficient conditions for the relative rank sequence of an infinite Cartesian product to be logarithmic, and sufficient conditions for it to be constant. Chapter 4 ends with the introduction of a new topic, relative presentability, which follows naturally from the topic of relative rank.

Dans cette thèse, nous nous intéressons à plusieurs problèmes liés à la conception de réseaux géométriques et aux plongements isométriques dans le plan.Nous commençons par étudier la généralisation du problème du réseau de Manhattan classique aux plans normés. Étant donné un ensemble de terminaux, nous recherchons le réseau de longueur totale minimum qui connecte chaque paire de terminaux par un plus court chemin dans la métrique définie par la norme. Nous proposons un algorithme d'approximation facteur 2.5 pour ce problème en temps O(mn^3) avec n le nombre de terminaux et m le nombre de directions de la boule unitaire. Le deuxième problème étudié est une version orientée des réseaux de Manhattan dont le but est de construire un réseau orienté de taille minimum dans lequel pour chaque paire de terminaux u, v est relié par un plus court chemin rectilinéaire de u vers v et un autre de v vers u. Nous proposons un algorithme d'approximation facteur 2 pour ce problème en temps O(n^3) où n est le nombre de terminaux.Nous nous intéressons ensuite à la recherche d'un spanner (un sous-graphe approximant les distances) planaire pour les graphes de disques unitaires (UDG) qui modélise les réseaux ad hoc sans fils. Nous présentons un algorithme qui construit un spanner planaire avec un facteur d'étirement constant en terme de distance de graphe pour UDG. Cet algorithme utilise uniquement des propriétés locales et peut donc être implémenté de manière distribuée.Finalement nous étudions le problème de la reconnaissance des espaces plongeables isométriquement dans le plan l_1 pour lequel nous proposons un algorithme en temps optimal O(n^2) pour sa résolution, ainsi que la généralisation de ce problème aux plans normés dont la boule unitaire est un polygone convexe central symétrique. / In this thesis, we study several problems related to the design of geometric networks and isometric embeddings into the plane.We start by considering the generalization of the classical Minimum Manhattan Network problem to all normed planes. We search the minimum network that connects each pair of terminals by a shortest path in this norm. We propose a factor 2.5 approximation algorithm in time O(mn^3), where n is the number of terminals and m is the number of directions of the unit ball.The second problem presented is an oriented version of the minumum Manhattan Network problem, we want to obtain a minimum oriented network such that for each pair u, v of terminals, there is a shortest rectilinear path from u to v and another path from v to u.We describe a factor 2 approximation algorithm with complexity O(n^3) where n is the number of terminals for this problem.Then we study the problem of finding a planar spanner (a subgraph which approximates the distances) of the Unit Disk Graph (UDG) which is used to modelize wireless ad hoc networks. We present an algorithm for computing a constant hop stretch factor planar spanner for all UDG. This algorithm uses only local properties and it can be implemented in distributed manner.Finally, we study the problem of recognizing metric spaces that can be isometrically embbed into the rectilinear plane and we provide an optimal time O(n^2) algorithm to solve this problem. We also study the generalization of this problem to all normed planes whose unit ball is a centrally symmetric convex polygon.

MASTER THESIS Petr Lukeš Emergence of space geometries from quantum entanglement Institute of Theoretical Physics Supervisor of the master thesis: Mgr. Martin Scholtz, Ph.D. Study programme: Physics Study branch: Theoretical physics Prague 2019 Abstract: Connecting the field of Quantum Physics and General Relativity is one of the main interests of contemporary Theoretical Physics. This work attempts to find solution to simplified version of this problem. Firstly entropy is shown to be a good meeting point between the two different theories. Then some of entropy's less intuitive properties are shown, namely its dependence on area, not volume. This relation is studied from both Relativistic and Quantum viewpoint. After- wards there is a short description of a quantum model interpretable as geometry based on the information between its subsystems. Lastly, results of computations within this model are presented.

Le graphe est un concept puissant pour la représentation des relations entre des paires d'entités. Les données ayant une structure de graphes sous-jacente peuvent être trouvées dans de nombreuses disciplines, décrivant des composés chimiques, des surfaces des modèles tridimensionnels, des interactions sociales ou des bases de connaissance, pour n'en nommer que quelques-unes. L'apprentissage profond (DL) a accompli des avancées significatives dans une variété de tâches d'apprentissage automatique au cours des dernières années, particulièrement lorsque les données sont structurées sur une grille, comme dans la compréhension du texte, de la parole ou des images. Cependant, étonnamment peu de choses ont été faites pour explorer l'applicabilité de DL directement sur des données structurées sous forme des graphes. L'objectif de cette thèse est d'étudier des architectures de DL sur des graphes et de rechercher comment transférer, adapter ou généraliser à ce domaine des concepts qui fonctionnent bien sur des données séquentielles et des images. Nous nous concentrons sur deux primitives importantes : le plongement de graphes ou leurs nœuds dans une représentation de l'espace vectorielle continue (codage) et, inversement, la génération des graphes à partir de ces vecteurs (décodage). Nous faisons les contributions suivantes. Tout d'abord, nous introduisons Edge-Conditioned Convolutions (ECC), une opération de type convolution sur les graphes réalisés dans le domaine spatial où les filtres sont générés dynamiquement en fonction des attributs des arêtes. La méthode est utilisée pour coder des graphes avec une structure arbitraire et variable. Deuxièmement, nous proposons SuperPoint Graph, une représentation intermédiaire de nuages de points avec de riches attributs des arêtes codant la relation contextuelle entre des parties des objets. Sur la base de cette représentation, l'ECC est utilisé pour segmenter les nuages de points à grande échelle sans sacrifier les détails les plus fins. Troisièmement, nous présentons GraphVAE, un générateur de graphes permettant de décoder des graphes avec un nombre de nœuds variable mais limité en haut, en utilisant la correspondance approximative des graphes pour aligner les prédictions d'un auto-encodeur avec ses entrées. La méthode est appliquée à génération de molécules / Graph is a powerful concept for representation of relations between pairs of entities. Data with underlying graph structure can be found across many disciplines, describing chemical compounds, surfaces of three-dimensional models, social interactions, or knowledge bases, to name only a few. There is a natural desire for understanding such data better. Deep learning (DL) has achieved significant breakthroughs in a variety of machine learning tasks in recent years, especially where data is structured on a grid, such as in text, speech, or image understanding. However, surprisingly little has been done to explore the applicability of DL on graph-structured data directly.The goal of this thesis is to investigate architectures for DL on graphs and study how to transfer, adapt or generalize concepts working well on sequential and image data to this domain. We concentrate on two important primitives: embedding graphs or their nodes into a continuous vector space representation (encoding) and, conversely, generating graphs from such vectors back (decoding). To that end, we make the following contributions.First, we introduce Edge-Conditioned Convolutions (ECC), a convolution-like operation on graphs performed in the spatial domain where filters are dynamically generated based on edge attributes. The method is used to encode graphs with arbitrary and varying structure.Second, we propose SuperPoint Graph, an intermediate point cloud representation with rich edge attributes encoding the contextual relationship between object parts. Based on this representation, ECC is employed to segment large-scale point clouds without major sacrifice in fine details.Third, we present GraphVAE, a graph generator allowing to decode graphs with variable but upper-bounded number of nodes making use of approximate graph matching for aligning the predictions of an autoencoder with its inputs. The method is applied to the task of molecule generation

James W. Alexander, no artigo[1],mostra que se tivermos um mergulho PL f : \'S POT. 1\' × \'S POT. 1\' \'S POT. 3\', então o fecho de uma das componentes conexas de \'S POT. 3\' f(\'S POT. 1\' × \'S POT. 1\') é homeomorfo a um toro sólido, isto é, homeomorfo a \'S POT. 1\' × \'D POT. 2\'. Este teorema ficou conhecido por Teorema do toro de Alexander. Nesta dissertação, estamos detalhando a demonstração deste teorema feita em[25] que é diferente da demonstração apresentada em [1]. Mais geralmente, para um mergulho diferenciável f : \'S POT. p\' × \'S POT. q\' \'S POT. p + q+1\' , demonstra-se que o fecho de uma das componentes conexasde \'S POT. p +q + 1\' f(\'S POT. p\' × \'S POT. q\') é difeomorfo a \'S POT. p\' × \'D POT. q + 1\' se p q 1 e p + q \'DIFERENTE DE\' 3 ou se p = 2 e q = 1 um dos fechos será homeomorfo a \'S POT. 2\' × \'D POT. 2\' , nesta dissertação estaremos também detalhando estas demonstrações feita em [20] / James W. Alexander shows in[1] that the closure of one of the two connected components of \'S POT. 3\'f( \'S POT. 1 × \'S POT. 1\') is homeomorphic to a solid torus \'S POT. 1\' × \'D POT. 2\' , where f : \'S POT. 1\' ×\' SPOT. 1\' \'S POT. 3\' is a PL embedding. This result became known as Alexanders torus theorem. In this dissertation we are detailing the proof of this theorem made in[25] which is different from the demonstration presented in[1]. More generally, when considering a smooth embeding f : \'S POT. p\' × \'S POT. q\' \' SPOT. p+q+1\' , it is demonstrated that the closure of one of the two connected components \'S POT. p+q+1\' f (\'S POT. p\' × \'S POT. q\' ) is diffeomorphic to \'S POT. p\' × \'D POT. q+1\' if p q 1 and p+q \'DIFFERENT OF\' 3 or if p = 2 and q = 1 one of the closures will be homeomorphic to \'S POT. 2\' × \'D POT. 2\'. In this work we are also detailing the proves made in[20]

In der vorliegenden Arbeit wurden Cluster- und QM/MM-Einbettungsmodelle für geträgerte Vanadiumoxidkatalysatoren auf Siliziumdioxid mit Hilfe von DFT-Rechnungen untersucht. Es wurden Strukturen, Schwingungen und die Stabilität gegenüber Wasser und Sauerstoff unter Reaktionsbedingungen betrachtet. Ferner wurde die Reaktivität bei der Oxidativen Dehydrierung (ODH) von n-Propan zu n-Propen und der Oxidation von Methanol zu Formaldehyd untersucht. Zur Durchführung der Einbettungsrechnung wurde ein angepasstes Shell-Model-Potential verwendet. Bezüglich der Schwingungen zeigte sich, dass sich der Einfluss der Einbettung hauptsächlich auf die Kopplung von Schwingungen beschränkt, aber die Frequenzen kaum verändert werden. Die lokale Struktur um das Vanadiumatom beeinflusst die Vanadylschwingung wenig. Die Stabilitätsberechnungen haben gezeigt, dass die untersuchten Modelle unter Reaktionsbedingungen vorliegen und hydroxylierte Spezies keine Bedeutung haben. Bei der Untersuchung der beiden Reaktionen wird für die Cluster- und die QM/MM-Einbettungsrechnungen jeweils derselbe Mechanismus gefunden. Der Vorteil der Einbettungsrechnungen besteht darin, dass die lokale Struktur um das aktive Zentrum variiert werden kann. Bei der ODH von Propan hat die lokale Struktur einen eher geringen Einfluss auf die Reaktionsenergien, denn die Reaktion verläuft hauptsächlich am Vanadylsauerstoff. Der Übergangszustand des geschwindigkeitsbestimmenden Schrittes liegt bei der Einbettungsrechnung dennoch energetisch höher. Grund ist eine sterische Hinderung durch die Hydroxylgruppen der Oberfläche. Bei der Oxidation von Methanol ist der Einfluss der lokalen Struktur größer, denn die Reaktion verläuft sowohl über den Vanadylsauerstoff als auch über die Brückensauerstoffatome zum Trägermaterial. Für beide Reaktionen wird ein Einfluss der Vanadiumbeladung auf die Reaktionsenergien gefunden. Bei höherer Beladung werden die Reaktionen exothermer. / In this work cluster models and models for QM/MM-embedding for supported vanadia catalysts on silica were studied with help of DFT-calculations. The structures, vibrations and stability towards water and oxygen under reaction conditions were examined. Furthermore the reactivities towards the oxidative dehydrogenation (ODH) of n-propane to n-propene and the oxidation of methanol to formaldehyde were tested. For the embedding an adapted shell-model-potential was employed. Regarding the vibrations it was shown that the influence of the embedding lies mostly in the coupling of vibrations and not in their frequencies. The local structure surrounding the vanadium atom has only minor influence. The stability calculations have shown that the tested model systems exist under reaction conditions while hydroxylated species do not exist. When studying the reactivity of the two reactions always the same mechanism is found for cluster and embedded calculations. The benefit of the embedded calculations is the possibility to vary the local structure surrounding the active center. For the ODH of propane the local structure has only small impact on reaction energies because the reaction takes mainly place at the vanadyl oxygen. The transition state of the rate determining step nevertheless is energetically higher in the embedded calculations due to steric hindrance caused by the hydroxyl groups of the surface. The impact of local structure is more important for the oxidation of methanol since in this case vanadyl oxygen and bridging oxygens to the support are involved in the reaction. For both reactions an influence on reaction energies of the vanadia loading is found. With more loading the reactions becomes more exothermic.

A central operation of users of the text analysis tool Gavagai Explorer is to look through a list of words and arrange them in groups. This thesis explores the use of word clustering to automatically arrange the words in groups intended to help users. A new word clustering algorithm is introduced, which attempts to produce word clusters tailored to be small enough for a user to quickly grasp the common theme of the words. The proposed algorithm computes similarities among words using word embeddings, and clusters them using hierarchical graph clustering. Multiple variants of the algorithm are evaluated in an unsupervised manner by analysing the clusters they produce when applied to 110 data sets previously analysed by users of Gavagai Explorer. A supervised evaluation is performed to compare clusters to the groups of words previously created by users of Gavagai Explorer. Results show that it was possible to choose a set of hyperparameters deemed to perform well across most data sets in the unsupervised evaluation. These hyperparameters also performed among the best on the supervised evaluation. It was concluded that the choice of word embedding and graph clustering algorithm had little impact on the behaviour of the algorithm. Rather, limiting the maximum size of clusters and filtering out similarities between words had a much larger impact on behaviour.

P. Broussous and S. Stevens studierten für die Konstruktion einfacher Typen unitärer p-adischer Gruppen Abbildungen zwischen erweiterten Bruhat-Tits-Gebäuden, die die Moy-Prasad-Filtrierungen respektieren (CLF). Im ersten Teil der Doktorarbeit wird deren Arbeit zu solchen Abbildungen um den Quaternionenalgebrafall erweitert. Genauer, es sei k0 ein p-adischer Körper mit einer von 2 verschiedenen Restcharakteristik und beta ein eine halbeinfache k0-Algebra erzeugendes, k0-rationales Element der Lie-Algebra einer über k0 definierten unitaren Gruppe G=U(h) zu einer epsilon-hermitischen Form h. Es sei H der Zentralisator von beta in G. Es wird bewiesen, dass eine affine H(k0)-equivariante CLF-Abbildung j vom erweiterten Bruhat-Tits-Gebäude B^1(H,k0) nach B^1(G,k0) existiert. Wie von Broussous vermutet, stellt sich in der Doktorarbeit heraus, dass j durch die CLF-Eigenschaft eindeutig bestimmt wird, falls kein Faktor von H k0-isomorph zur isotropen orthogonalen Gruppe vom k0-Rank 1 ist und alle Faktoren unitäre Gruppen sind. Desweiteren wird bei abgeschwächter Äquivarianzeigenschaft bewiesen, dass j als affine und bezüglich dem Zentrum von H^0(k0) equivariante CLF-Abbildung bis auf eine Translation von B^1(H,k0) eindeutig bestimmt ist. Im zweiten Teil wird der von Broussous und M. Grabitz studierte Einbettungstyp mit Hilfe einer CLF-Abbildung entschlüsselt. Wir betrachten einen Schiefkörper von endlichem Index und p-adischem Zentrum F. Die Konstruktion einfacher Typen für GLn(D) nach der Methode von Bushnell und Kutzko bedurfte der Analyse sogenannter Strata, die eine Starrheitseingenschaft erfüllen mussten. Teil eines Stratums ist insbesondere ein Paar (E,a) bestehend aus einer Körpererweiterung E|F in Mn(D) und einer erblichen Ordnung a, welche von E^x normalisiert wird. Broussous und Grabitz klassifizierten diese Paare mit Hilfe von Invarianten. Im zweiten Teil werden diese Invarianten mit Hilfe der Geometrie einer CLF-Abbildung berechnet. / P. Broussous and S. Stevens studied maps between enlarged Bruhat-Tits buildings to construct types for p-adic unitary groups. They needed maps which respect the Moy-Prasad filtrations. That property is called (CLF), i.e. compatibility with the Lie algebra filtrations. In the first part of this thesis we generalise their results on such maps to the Quaternion-algebra case. Let k0 be a p-adic field of residue characteristic not two. We consider a semisimple k0-rational Lie algebra element beta of a unitary group G:=U(h) defined over k0 with a signed hermitian form h. Let H be the centraliser of beta in G. We prove the existence of an affine H(k0)-equivariant CLF-map j from the enlarged Bruhat-Tits building B^1(H,k0) to B^1(G,k0). As conjectured by Broussous the CLF-property determines j, if none of the factors of H is k0-isomorphic to the isotropic orthogonal group of k0-rank one and all factors are unitary groups. Under the weaker assumption that the affine CLF-map j is only equivariant under the center of H^0(k0) it is uniquely determined up to a translation of B^1(H,k0). The second part is devoted to the decoding of embedding types by the geometry of a CLF-map. Embedding types have been studied by Broussous and M. Grabitz. We consider a division algebra D of finite index with a p-adic center F. The construction of simple types for GLn(D) in the Budhnell-Kutzko framework required an investigation of strata which had to fulfil a rigidity property. Giving a stratum especially means to fix a pair (E,a) consisting of a field extension E|F in Mn(D) and a hereditary order a which is stable under conjugation by E^x, in other words we fix an embedding of E^x into the normalizer of a. Broussous and Grabitz classified these pairs with invariants. We describe and prove a way to decode these invariants using the geometry of a CLF-map.

Orientador: Manoel Ferreira Borges Neto / Banca: Sandra Regina Monteiro Masalskiene / Banca: Antonio Luís Venezuela / Resumo: O presente trabalho tem por objetivo abordar aspectos fundamentais da teoria de imersão proposta por John Nash em 1954, na qual foi mostrado que uma variedade continua com derivada continuação nua C1, pode ser imersa em espaços euclidianos de 2n dimensões. Faz-se importante citar que ao longo do trabalho serão destacados aspectos inovadores do Teorema de Nash, tais como a não necessidade da hipótese de analitici-dade conforme havia sido usada anteriormente por Janet-Cartan, além do aspecto da perturbação que permite construir qualquer outra variedade imersa por uma sequência de deformações infinitesimais. São discutidos também extensões do Teorema de Nash, sobretudo os trabalhos de Greene e de Gunther, e aplicações do método perturbativo de Nash nas Teorias unificadoras da física. / Abstract: The present work has for objective to approach basic aspects of the immersion theory proposal for John Nash in 1954, in which it was shown that a continuous variety with continuous derivative C1, can be immersed in Euclidean spaces of 2n dimensions. One becomes important to cite that throughout the work innovative aspects of the The- orem of Nash will be detached, such as the necessity of the hypothesis of in agreement analiticidade had not been used previously for Janet-Cartan, beyond the aspect of the disturbance that allows to construct any another immersed variety for a sequência of infinitesimal deformations. Extensions of the Theorem of Nash are also argued, over all the works of Greene and Gunther, and applications of the perturbativo method of Nash in the unifying Theories of the physics. / Mestre

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-12-12T11:28:20Z No. of bitstreams: 1 Romulo Reis de Oliveira_DIS.pdf: 1719302 bytes, checksum: 005f38fa0c94cb6b97ce5f6ad6ec70ed (MD5) / Approved for entry into archive by Sheila Dias (sheila.dias@pucrs.br) on 2018-12-14T11:26:14Z (GMT) No. of bitstreams: 1 Romulo Reis de Oliveira_DIS.pdf: 1719302 bytes, checksum: 005f38fa0c94cb6b97ce5f6ad6ec70ed (MD5) / Made available in DSpace on 2018-12-14T11:50:26Z (GMT). No. of bitstreams: 1 Romulo Reis de Oliveira_DIS.pdf: 1719302 bytes, checksum: 005f38fa0c94cb6b97ce5f6ad6ec70ed (MD5) Previous issue date: 2015-04-24 / Hybrid synchrony virtual networks arose by combining network virtualization, which allows the co-existence of several virtual networks in the same shared physical substrate, providing infrastructure in a flexible and economic way, with partial synchrony network architecture, which is relevant in distributed systems in order to build reliable systems. One of the main challenges in network virtualization is the efficient mapping of virtual resources in the substrate network, since it is a NP-Hard complexity problem. When considering the synchrony of virtual and physical resources it becomes more difficult to map, making it unfeasible to calculate the optimal solution in real environments. Thus, heuristic approaches are necessary for finding semi-optimal solutions faster. In this work, four heuristics for mapping hybrid synchrony virtual networks are adapted. In order to evaluate these heuristics, two sets of experiments were executed. In the first set is compared the optimal solutions with their respective semi-optimal solutions, the results show the heuristics? efficiency are better when the virtual network requests are smaller, furthermore there were some semi-optimal solution mapping costs equivalent to the optimal solution mapping cost. The second set of experiments evaluates the heuristics performance using a physical substrate closer to real context and a larger number of virtual network requests. The results of this second set of experiments demonstrate that even with a larger number of virtual requests and a larger substrate, the solutions were computed in acceptable time. / As redes virtuais de sincronia h?brida surgiram da combina??o entre a virtualiza??o de redes, a qual permite a coexist?ncia de v?rias redes virtuais no mesmo substrato f?sico compartilhado fornecendo infraestrutura de maneira flex?vel e econ?mica, e arquitetura de redes com sincronia parcial, essa relevante em sistemas distribu?dos para construir sistemas confi?veis. Um dos principais desafios em virtualiza??o de redes ? o mapeamento eficiente dos recursos virtuais na rede de substrato, pois ? um problema de complexidade NP-Dif?cil. Ao considerar a sincronia dos recursos virtuais e f?sicos, se torna mais dif?cil efetuar esse mapeamento, inviabilizando o c?lculo da solu??o ?tima em ambientes reais. Sendo assim, abordagens heur?sticas s?o necess?rias para encontrar solu??es semi-?timas de maneira mais r?pida. Neste trabalho s?o adaptadas quatro abordagens heur?sticas para efetuar o mapeamento de redes virtuais de sincronia h?brida. Para avaliar o desempenho dessas heur?sticas foram efetuados dois conjuntos de experimentos. No primeiro conjunto de experimentos s?o comparadas as solu??es ?timas e as respectivas solu??es semi-?timas, os resultados indicaram que a efici?ncia das heur?sticas s?o melhores quando as requisi??es de redes virtuais s?o menores, al?m disso houveram alguns custos de solu??es semi-?timas equivalentes ao custo de mapeamento da solu??o ?tima. O segundo conjunto de experimento avalia o desempenho das heur?sticas utilizando um substrato de rede mais pr?ximo do contexto real e um maior n?mero de requisi??es de redes virtuais. Os resultados desse segundo experimento demonstram que mesmo com um n?mero maior de requisi??es de redes virtuais e um substrato maior, as solu??es foram calculadas em tempo aceit?vel.