This thesis is divided into two parts. In the first part we describe a new Monte Carlo algorithm for the consistent and unbiased estimation of multidimensional integrals and the efficient sampling from multidimensional densities. The algorithm is inspired by the classical splitting method and can be applied to general static simulation models. We provide examples from rare-event probability estimation, counting, optimization, and sampling, demonstrating that the proposed method can outperform existing Markov chain sampling methods in terms of convergence speed and accuracy. In the second part we present a new adaptive kernel density estimator based on linear diffusion processes. The proposed estimator builds on existing ideas for adaptive smoothing by incorporating information from a pilot density estimate. In addition, we propose a new plug-in bandwidth selection method that is free from the arbitrary normal reference rules used by existing methods. We present simulation examples in which the proposed approach outperforms existing methods in terms of accuracy and reliability.

We study the existence of special points in extremally disconnected compact topological spaces that witness their nonhomogeneity. Via Stone duality, we are looking for ultrafilters on complete Boolean algebras with special combinatorial properties. We introduce the notion of a coherent ultrafilter (coherent P-point, coherently selective). We show that generic existence of such ultrafilters on every complete ccc Boolean algebra of weight not exceeding the continuum is consistent with set theory, and that they witness the nonhomogeneity of the corresponding Stone spaces. We study the properties of the order-sequential property on σ-complete Boolean algebras and its relation to measure-theoretic properties. We ask whether the order-sequential topology can be compact in a nontrivial case, and partially answer the question in a special case of the Suslin algebra associated with a Suslin tree.

This thesis is divided into four chapters. In the first one, all the pre-requisite theory of semigroups and groupoids is introduced, as well as a few new results - such as a short study of ∨-ideals and quotients in distributive semigroups and a non-commutative Loomis-Sikorski Theorem. In the second chapter, we motivate and describe the sofic property for probability measure-preserving groupoids and prove several permanence properties for the class of sofic groupoids. This provides a common ground for similar results in the particular cases of groups and equivalence relations. In particular, we prove that soficity is preserved under finite index extensions of groupoids. We also prove that soficity can be determined in terms of the full group alone, answering a question by Conley, Kechris and Tucker-Drob. In the third chapter we turn to the classical problem of reconstructing a topological space from a suitable structure on the space of continuous functions. We prove that a locally compact Hausdorff space can be recovered from classes of functions with values on a Hausdorff space together with an appropriate notion of disjointness, as long as some natural regularity hypotheses are satisfied. This allows us to recover (and even generalize) classical theorem by Kaplansky, Milgram, Banach-Stone, among others, as well as recent results of the similar nature, and obtain new consequences as well. Furthermore, we extend the techniques used here to obtain structural theorems related to topological groupoids. In the fourth and final chapter, we study dynamical aspects of partial actions of inverse semigroups, and in particular how to construct groupoids of germs and (partial) crossed products and how do they relate to each other. This chapter is based on joint work with Viviane Beuter.

El trabajo de investigación tuvo como objetivo el diseño de un modelo matricial para la construcción del diagrama de Hasse de un Conjunto Parcialmente Ordenado (CPO), que permita su implementación en un lenguaje de programación. Para lograrlo se utilizó la teoría de Relaciones de Orden Parcial, sus propiedades; matrices booleanas, sus operaciones. Este trabajo permitió determinar el diagrama de Hasse de Relaciones de Orden Parcial sin importar la cantidad de elementos del CPO, y lo más importante, permitió automatizar el modelo. / The research work was aimed at the design of a matrix model for the construction of the Hasse diagram of a Partially Ordained Set (CPO), which allows its implementation in a programming language. To achieve this, we used the theory of partial order relations, their properties; Boolean matrices, their operations. This work allowed to determine the Hasse diagram of Partial Order Relations regardless of the number of elements of the CPO, and most importantly, allowed to automate the model.

Orientador: Prof. Dr. Jair Donadelli Jr. / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2014.

Orientador: Prof. Dr. Ronaldo Cristiano Prati / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2014.

Orientador: Prof. Dr. Eduardo Guéron / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional - PROFMAT, Santo André, 2018. / Calculadoras são aparelhos comuns no cotidiano do homem moderno, contudo, os conceitos matemáticos envolvidos em sua concepção ainda são conhecidos por poucos. Durante séculos, a obstinação da humanidade em construir máquinas capazes de computar de forma autônoma resultou tanto no surgimento dos atuais computadores, como também em um magnífico legado de conhecimentos matemáticos agregados a tal conquista. Conteúdos tais como congruências e álgebra booleana suscitaram a revolução dos sistemas informatizados e tem sido amplamente explorados por meio de inúmeras aplicações, nossa trajetória perpassou pela aritmética modular, o teorema de Euler-Fermat e as classes residuais, além de bases numéricas, tópicos de eletrônica digital e funções booleanas, com foco no desenvolvimento de circuitos lógicos e o engendrar de componentes eletrônicos, que configuram a base para idealização e construção de calculadoras que efetuem as operações aritméticas em bases arbitrárias, objetivo preponderante deste trabalho. O esmiuçar das etapas de construção das calculadoras, viabiliza o aprofundamento dos conceitos matemáticos que a fomentaram. A abordagem dos temas supracitados culmina para aprimorar e evidenciar a aplicabilidade da matemática à essência da era moderna. / Calculators are common apparatuses in the everyday of modern man, however, the mathematical concepts involved in its conception are still known by few. For centuries, mankind¿s obstinacy in building machines capable of computing autonomously resulted in both the emergence of current computers and a magnificent legacy of mathematical knowledge added to such achievement. Contents such as congruences and Boolean algebra have aroused the revolution of computerized systems and it has been extensively explored through numerous applications, our trajectory ran through modular arithmetic, Euler-Fermat¿s theorem and residual classes, as well as numerical bases, topics of digital electronics and Boolean functions, focusing on the development of logic circuits and the generation of electronic components, which form the basis for the design and construction of calculators that perform arithmetic operations on arbitrary bases, a preponderant objective of this work. The to detail of the construction steps of the calculators, enables the deepening of the mathematical concepts that fomented it. The approach to the aforementioned themes culminates in improving and evidencing the applicability of mathematics to the essence of the modern era.

Um problema importante na área de Biologia Sistêmica é o de inferência de redes de regulação gênica. Os avanços científicos e tecnológicos nos permitem analisar a expressão gênica de milhares de genes simultaneamente. Por \"expressão gênica\'\', estamos nos referindo ao nível de mRNA dentro de uma célula. Devido a esta grande quantidade de dados, métodos matemáticos, estatísticos e computacionais têm sido desenvolvidos com o objetivo de elucidar os mecanismos de regulação gênica presentes nos organismos vivos. Para isso, modelos matemáticos de redes de regulação gênica têm sido propostos, assim como algoritmos para inferir estas redes. Neste trabalho, focamos nestes dois aspectos: modelagem e inferência. Com relação à modelagem, estudamos modelos existentes para o ciclo celular da levedura (Saccharomyces cerevisiae). Após este estudo, propomos um modelo baseado em redes Booleanas probabilísticas sensíveis ao contexto, e em seguida, um aprimoramento deste modelo, utilizando cadeias de Markov não homogêneas. Mostramos os resultados, comparando os nossos modelos com os modelos estudados. Com relação à inferência, propomos um novo algoritmo utilizando o paradigma de crescimento de semente de genes. Neste contexto, uma semente é um pequeno subconjunto de genes de interesse. Nosso algoritmo é baseado em dois passos: passo de crescimento de semente e passo de amostragem. No primeiro passo, o algoritmo adiciona outros genes à esta semente, seguindo algum critério. No segundo, o algoritmo realiza uma amostragem de redes, definindo como saída um conjunto de redes potencialmente interessantes. Aplicamos o algoritmo em dados artificiais e dados biológicos de células HeLa, mostrando resultados satisfatórios. / A key problem in Systems Biology is the inference of gene regulatory networks. The scientific and technological advancement allow us to analyze the gene expression of thousands of genes, simultaneously. By \"gene expression\'\' we refer to the mRNA concentration level inside a cell. Due to this large amount of data, mathematical, statistical and computational methods have been developed in order to elucidate the gene regulatory mechanisms that take part of every living organism. To this end, mathematical models of gene regulatory networks have been proposed, along with algorithms to infer these networks. In this work, we focus in two aspects: modeling and inference. Regarding the modeling, we studied existing models for the yeast (Saccharomyces cerevisiae) cell cycle. After that, we proposed a model based on context sensitive probabilistic Boolean networks, and then, an improvement of this model, using nonhomogeneous Markov chain. We show the results, comparing our models against the studied models. Regarding the inference, we proposed a new algorithm using the seed growing paradigm. In this context, a seed is a small subset of genes. Our algorithm is based in two main steps: seed growing step and sampling step. In the first step, the algorithm adds genes into the seed, according to some criterion. In the second step, the algorithm performs a sampling process on the space of networks, defining as its output a set of potentially interesting networks. We applied the algorithm on artificial and biological HeLa cells data, showing satisfactory results.

Dans cette thèse, nous nous intéressons à la résolution du problème de la satisfiabilité propositionnelle (SAT). Ce problème fondamental en théorie de la complexité est aujourd'hui utilisé dans de nombreux domaines comme la planification, la bio-informatique, la vérification de matériels et de logiciels. En dépit d'énormes progrès observés ces dernières années dans la résolution pratique du problème SAT, il existe encore une forte demande d'algorithmes efficaces pouvant permettre de résoudre les problèmes difficiles. C'est dans ce contexte que se situent les différentes contributions apportées par cette thèse. Ces contributions s'attellent principalement autour de deux composants clés des solveurs SAT : l'apprentissage de clauses et les heuristiques de choix de variables de branchement. Premièrement, nous proposons une méthode de résolution permettant d'exploiter les fonctions booléennes cachées généralement introduites lors de la phase d'encodage CNF pour réduire la taille des clauses apprises au cours de la recherche. Ensuite, nous proposons une approche de résolution basée sur le principe d'intensification qui indique les variables sur lesquelles le solveur devrait brancher prioritairement à chaque redémarrage. Ce principe permet ainsi au solveur de diriger la recherche sur la sous-formule booléenne la plus contraignante et de tirer profit du travail de recherche déjà accompli en évitant d'explorer le même sous-espace de recherche plusieurs fois. Dans une troisième contribution, nous proposons un nouveau schéma d'apprentissage de clauses qui permet de dériver une classe particulière de clauses Bi-Assertives et nous montrons que leur exploitation améliore significativement les performances des solveurs SAT CDCL issus de l'état de l'art. Finalement, nous nous sommes intéressés aux principales stratégies de gestion de la base de clauses apprises utilisées dans la littérature. En effet, partant de deux stratégies de réduction simples : élimination des clauses de manière aléatoire et celle utilisant la taille des clauses comme critère pour juger la qualité d'une clause apprise, et motiver par les résultats obtenus à partir de ces stratégies, nous proposons plusieurs nouvelles stratégies efficaces qui combinent le maintien de clauses courtes (de taille bornée par k), tout en supprimant aléatoirement les clauses de longueurs supérieures à k. Ces nouvelles stratégies nous permettent d'identifier les clauses les plus pertinentes pour le processus de recherche. / In this thesis, we focus on propositional satisfiability problem (SAT). This fundamental problem in complexity theory is now used in many application domains such as planning, bioinformatic, hardware and software verification. Despite enormous progress observed in recent years in practical SAT solving, there is still a strong demand of efficient algorithms that can help to solve hard problems. Our contributions fit in this context. We focus on improving two of the key components of SAT solvers: clause learning and variable ordering heuristics. First, we propose a resolution method that allows to exploit hidden Boolean functions generally introduced during the encoding phase CNF to reduce the size of clauses learned during the search. Then, we propose an resolution approach based on the intensification principle that circumscribe the variables on which the solver should branch in priority at each restart. This principle allows the solver to direct the search to the most constrained sub-formula and takes advantage of the previous search to avoid exploring the same part of the search space several times. In a third contribution, we propose a new clause learning scheme that allows to derive a particular Bi-Asserting clauses and we show that their exploitation significantly improves the performance of the state-of-the art CDCL SAT solvers. Finally, we were interested to the main learned clauses database reduction strategies used in the literature. Indeed, starting from two simple strategies : random and size-bounded reduction strategies, and motivated by the results obtained from these strategies, we proposed several new effective ones that combine maintaing short clauses (of size bounded by k), while deleting randomly clauses of size greater than k. Several other efficient variants are proposed. These new strategies allow us to identify the most important learned clauses for the search process.

[pt] Operações booleanas em modelagem 3D são usadas para criar novos modelos ou para modificá-los. Na maioria dos tipos de representação de objetos 3D, estas operações são bastante complexas. Nos últimos anos tem sido muito explorado um novo tipo de modelagem, a modelagem por pontos, que apresenta muitas vantagens em relação às outras representações como maior simplicidade e eficiência. Dois trabalhos exploram as operações booleanas na modelagem por pontos, o trabalho de Adams e Dutré e o trabalho de Pauly et. al. Dada a grande importância deste novo tipo de modelagem e do uso de operações booleanas, esta dissertação apresenta uma introdução à modelagem por pontos, implementa o algoritmo proposto em Adams e Dutré com algumas melhorias e o compara com o método de Pauly et. al. / [en] Boolean operations are used to create or modify models. These operations in the majority of 3D object representations are very complex. In the last years a significant trend in computer graphics has been the shift towards point sampled 3D models due to their advantages over other representations, such as simplicity and efficiency. Two recent works present algorithms to perform interactive boolean operations on point-based models: the work by Adams and Dutré and the work by Pauly et. Al.. Due to great importance of this novel representation and of the use of boolean operations, the present work makes an introduction to point-based representation, implements the algorithm proposed by Adams and Dutré with some improvements, and compares this implementation with the work by Pauly et. al..