Rozprawy doktorskie na temat „Combinatorial statistics”
Kliknij ten link, aby zobaczyć inne rodzaje publikacji na ten temat: Combinatorial statistics.
Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych
Sprawdź 50 najlepszych rozpraw doktorskich naukowych na temat „Combinatorial statistics”.
Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.
Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.
Przeglądaj rozprawy doktorskie z różnych dziedzin i twórz odpowiednie bibliografie.
1
Ning, Michael Zhu. "Relational combinatorial optimisation". Thesis, University of Oxford, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.284507.
Pełny tekst źródła
2
Olsen, McCabe J. "HILBERT BASES, DESCENT STATISTICS, AND COMBINATORIAL SEMIGROUP ALGEBRAS". UKnowledge, 2018. https://uknowledge.uky.edu/math_etds/52.
Pełny tekst źródłaStreszczenie:
The broad topic of this dissertation is the study of algebraic structure arising from polyhedral geometric objects. There are three distinct topics covered over three main chapters. However, each of these topics are further linked by a connection to the Eulerian polynomials.
Chapter 2 studies Euler-Mahonian identities arising from both the symmetric group and generalized permutation groups. Specifically, we study the algebraic structure of unit cube semigroup algebra using Gröbner basis methods to acquire these identities. Moreover, this serves as a bridge between previous methods involving polyhedral geometry and triangulations with descent bases methods arising in representation theory.
In Chapter 3, the aim is to characterize Hilbert basis elements of certain 𝒔-lecture hall cones. In particular, the main focus is the classification of the Hilbert bases for the 1 mod 𝑘 cones and the 𝓁-sequence cones, both of which generalize a previous known result. Additionally, there is much broader characterization of Hilbert bases in dimension ≤ 4 for 𝒖-generated Gorenstein lecture hall cones.
Finally, Chapter 4 focuses on certain algebraic and geometric properties of 𝒔-lecture hall polytopes. This consists of partial classification results for the Gorenstein property, the integer-decomposition property, and the existence of regular, unimodular triangulations.
3
Quinn, Kathleen Anne Sara. "Combinatorial structures with applications to information theory". Thesis, Royal Holloway, University of London, 1991. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.261791.
Pełny tekst źródła
4
Marett, Richard Colin. "Neighbourhood search techniques for multi-objective combinatorial problems". Thesis, Lancaster University, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.296889.
Pełny tekst źródła
5
McShine, Lisa Maria. "Random sampling of combinatorial structures". Diss., Georgia Institute of Technology, 2000. http://hdl.handle.net/1853/28771.
Pełny tekst źródła
6
Williams, Trevor K. "Combinatorial Games on Graphs". DigitalCommons@USU, 2017. https://digitalcommons.usu.edu/etd/6502.
Pełny tekst źródłaStreszczenie:
Combinatorial games are intriguing and have a tendency to engross students and lead them into a serious study of mathematics. The engaging nature of games is the basis for this thesis. Two combinatorial games along with some educational tools were developed in the pursuit of the solution of these games.
The game of Nim is at least centuries old, possibly originating in China, but noted in the 16th century in European countries. It consists of several stacks of tokens, and two players alternate taking one or more tokens from one of the stacks, and the player who cannot make a move loses. The formal and intense study of Nim culminated in the celebrated Sprague-Grundy Theorem, which is now one of the centerpieces in the theory of impartial combinatorial games. We study a variation on Nim, played on a graph. Graph Nim, for which the theory of Sprague-Grundy does not provide a clear strategy, was originally developed at the University of Colorado Denver. Graph Nim was first played on graphs of three vertices.
The winning strategy, and losing position, of three vertex Graph Nim has been discovered, but we will expand the game to four vertices and develop the winning strategies for four vertex Graph Nim.
Graph Theory is a markedly visual field of mathematics. It is extremely useful for graph theorists and students to visualize the graphs they are studying. There exists software to visualize and analyze graphs, such as SAGE, but it is often extremely difficult to learn how use such programs. The tools in GeoGebra make pretty graphs, but there is no automated way to make a graph or analyze a graph that has been built. Fortunately GeoGebra allows the use of JavaScript in the creation of buttons which allow us to build useful Graph Theory tools in GeoGebra. We will discuss two applets we have created that can be used to help students learn some of the basics of Graph Theory.
The game of thrones is a two-player impartial combinatorial game played on an oriented complete graph (or tournament) named after the popular fantasy book and TV series. The game of thrones relies on a special type of vertex called a king. A king is a vertex, k, in a tournament, T, which for all x in T either k beats x or there exists a vertex y such that k beats y and y beats x. Players take turns removing vertices from a given tournament until there is only one king left in the resulting tournament. The winning player is the one which makes the final move. We develop a winning position and classify those tournaments that are optimal for the first or second-moving player.
7
Niese, Elizabeth M. "Combinatorial Properties of the Hilbert Series of Macdonald Polynomials". Diss., Virginia Tech, 2010. http://hdl.handle.net/10919/26702.
Pełny tekst źródłaStreszczenie:
The original Macdonald polynomials $P_\mu$ form a basis for the vector space of symmetric
functions which specializes to several of the common bases such as the monomial, Schur, and
elementary bases. There are a number of different types of Macdonald polynomials obtained
from the original $P_\mu$ through a combination of algebraic and plethystic transformations one
of which is the modified Macdonald polynomial $\widetilde{H}_\mu$. In this dissertation, we study a certain
specialization $\widetilde{F}_\mu(q,t)$ which is the coefficient of $x_1x_2 ... x_N$ in $\widetilde{H}_\mu$ and also the Hilbert series
of the Garsia-Haiman module $M_\mu$. Haglund found a combinatorial formula expressing $\widetilde{F}_\mu$ as
a sum of $n!$ objects weighted by two statistics. Using this formula we prove a $q,t$-analogue of
the hook-length formula for hook shapes. We establish several new combinatorial operations
on the fillings which generate $\widetilde{F}_\mu$. These operations are used to prove a series of recursions
and divisibility properties for $\widetilde{F}_\mu$.Ph. D.
8
Hites, Romina. "Robustness and preferences in combinatorial optimization". Doctoral thesis, Universite Libre de Bruxelles, 2005. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210905.
Pełny tekst źródłaStreszczenie:
In this thesis, we study robust combinatorial problems with interval data. We introduce several new measures of robustness in response to the drawbacks of existing measures of robustness. The idea of these new measures is to ensure that the solutions are satisfactory for the decision maker in all scenarios, including the worst case scenario. Therefore, we have introduced a threshold over the worst case costs, in which above this threshold, solutions are no longer satisfactory for the decision maker. It is, however, important to consider other criteria than just the worst case.Therefore, in each of these new measures, a second criteria is used to evaluate the performance of the solution in other scenarios such as the best case one.
We also study the robust deviation p-elements problem. In fact, we study when this solution is equal to the optimal solution in the scenario where the cost of each element is the midpoint of its corresponding interval.
Then, we finally formulate the robust combinatorial problem with interval data as a bicriteria problem. We also integrate the decision maker's preferences over certain types of solutions into the model. We propose a method that uses these preferences to find the set of solutions that are never preferred by any other solution. We call this set the final set.
We study the properties of the final sets from a coherence point of view and from a robust point of view. From a coherence point of view, we study necessary and sufficient conditions for the final set to be monotonic, for the corresponding preferences to be without cycles, and for the set to be stable.
Those that do not satisfy these properties are eliminated since we believe these properties to be essential. We also study other properties such as the transitivity of the preference and indifference relations and more. We note that many of our final sets are included in one another and some are even intersections of other final sets. From a robust point of view, we compare our final sets with different measures of robustness and with the first- and second-degree stochastic dominance. We show which sets contain all of these solutions and which only contain these types of solutions. Therefore, when the decision maker chooses his preferences to find the final set, he knows what types of solutions may or may not be in the set.
Lastly, we implement this method and apply it to the Robust Shortest Path Problem. We look at how this method performs using different types of randomly generated instances.
Doctorat en sciences, Orientation recherche opérationnelle
info:eu-repo/semantics/nonPublished
9
Talebi, Mazraeh Shahi Mohammad Sadegh. "Minimizing Regret in Combinatorial Bandits and Reinforcement Learning". Doctoral thesis, KTH, Reglerteknik, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-219970.
Pełny tekst źródłaStreszczenie:
This thesis investigates sequential decision making tasks that fall in the framework of reinforcement learning (RL). These tasks involve a decision maker repeatedly interacting with an environment modeled by an unknown finite Markov decision process (MDP), who wishes to maximize a notion of reward accumulated during her experience. Her performance can be measured through the notion of regret, which compares her accumulated expected reward against that achieved by an oracle algorithm always following an optimal behavior. In order to maximize her accumulated reward, or equivalently to minimize the regret, she needs to face a trade-off between exploration and exploitation. The first part of this thesis investigates combinatorial multi-armed bandit (MAB) problems, which are RL problems whose state-space is a singleton. It also addresses some applications that can be cast as combinatorial MAB problems. The number of arms in such problems generically grows exponentially with the number of basic actions, but the rewards of various arms are correlated. Hence, the challenge in such problems is to exploit the underlying combinatorial structure.For these problems, we derive asymptotic (i.e., when the time horizon grows large) lower bounds on the regret of any admissible algorithm and investigate how these bounds scale with the dimension of the underlying combinatorial structure. We then propose several algorithms and provide finite-time analyses of their regret. The proposed algorithms efficiently exploit the structure of the problem, provide better performance guarantees than existing algorithms, and significantly outperform these algorithms in practice. The second part of the thesis concerns RL in an unknown and discrete MDP under the average-reward criterion. We develop some variations of the transportation lemma that could serve as novel tools for the regret analysis of RL algorithms. Revisiting existing regret lower bounds allows us to derive alternative bounds, which motivate that the local variance of the bias function of the MDP, i.e., the variance with respect to next-state transition laws, could serve as a notion of problem complexity for regret minimization in RL. Leveraging these tools also allows us to report a novel regret analysis of the KL-UCRL algorithm for ergodic MDPs. The leading term in our regret bound depends on the local variance of the bias function, thus coinciding with observations obtained from our presented lower bounds. Numerical evaluations in some benchmark MDPs indicate that the leading term of the derived bound can provide an order of magnitude improvement over previously known results for this algorithm.QC 20171215
10
Devlin, Agatha. "A study of parallel algorithms for the solution of some combinatorial optimization problems on a distributed array of processors". Thesis, Queen's University Belfast, 1995. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.282129.
Pełny tekst źródła
11
March, William B. "Multi-tree algorithms for computational statistics and phyiscs". Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/49116.
Pełny tekst źródłaStreszczenie:
The Fast Multipole Method of Greengard and Rokhlin does the seemingly impossible: it approximates the quadratic scaling N-body problem in linear time. The key is to avoid explicitly computing the interactions between all pairs of N points. Instead, by organizing the data in a space-partitioning tree, distant interactions are quickly and efficiently approximated. Similarly, dual-tree algorithms, which approximate or eliminate parts of a computation using distance bounds, are the fastest algorithms for several fundamental problems in statistics and machine learning -- including all nearest neighbors, kernel density estimation, and Euclidean minimum spanning tree construction.
We show that this overarching principle -- that by organizing points spatially, we can solve a seemingly quadratic problem in linear time -- can be generalized to problems involving interactions between sets of three or more points and can provide orders-of-magnitude speedups and guarantee runtimes that are asymptotically better than existing algorithms. We describe a family of algorithms, multi-tree algorithms, which can be viewed as generalizations of dual-tree algorithms. We support this thesis by developing and implementing multi-tree algorithms for two fundamental scientific applications: n-point correlation function estimation and Hartree-Fock theory.
First, we demonstrate multi-tree algorithms for n-point correlation function estimation. The n-point correlation functions are a family of fundamental spatial statistics and are widely used for understanding large-scale astronomical surveys, characterizing the properties of new materials at the microscopic level, and for segmenting and processing images. We present three new algorithms which will reduce the dependence of the computation on the size of the data, increase the resolution in the result without additional time, and allow probabilistic estimates independent of the problem size through sampling. We provide both empirical evidence to support our claim of massive speedups and a theoretical analysis showing linear scaling in the fundamental computational task. We demonstrate the impact of a carefully optimized base case on this computation and describe our distributed, scalable, open-source implementation of our algorithms.
Second, we explore multi-tree algorithms as a framework for understanding the bottleneck computation in Hartree-Fock theory, a fundamental model in computational chemistry. We analyze existing fast algorithms for this problem, and show how they fit in our multi-tree framework. We also show new multi-tree methods, demonstrate that they are competitive with existing methods, and provide the first rigorous guarantees for the runtimes of all of these methods. Our algorithms will appear as part of the PSI4 computational chemistry library.
12
Tang, Yu. "Combinatorial properties of uniform designs and their applications in the constructions of low-discrepancy designs". HKBU Institutional Repository, 2005. http://repository.hkbu.edu.hk/etd_ra/595.
Pełny tekst źródła
13
Tomczuk, Randal Wade. "Autocorrelation and decomposition methods in combinational logic design". Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1996. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/nq21952.pdf.
Pełny tekst źródła
14
Sportiello, Andrea. "Combinatorial methods in Statistical Field Theory : Trees, loops, dimers and orientations vs. Potts and non-linear σ-models". Doctoral thesis, Scuola Normale Superiore, 2010. http://hdl.handle.net/11384/85875.
Pełny tekst źródła
15
Calvet, Liñán Laura. "From metaheuristics to learnheuristics: Applications to logistics, finance, and computing". Doctoral thesis, Universitat Oberta de Catalunya, 2017. http://hdl.handle.net/10803/667118.
Pełny tekst źródłaStreszczenie:
Un gran nombre de processos de presa de decisions en sectors estratègics com el transport i la producció representen problemes NP-difícils. Sovint, aquests processos es caracteritzen per alts nivells d'incertesa i dinamisme. Les metaheurístiques són mètodes populars per a resoldre problemes d'optimització difícils en temps de càlcul raonables. No obstant això, sovint assumeixen que els inputs, les funcions objectiu, i les restriccions són deterministes i conegudes. Aquests constitueixen supòsits forts que obliguen a treballar amb problemes simplificats. Com a conseqüència, les solucions poden conduir a resultats pobres. Les simheurístiques integren la simulació a les metaheurístiques per resoldre problemes estocàstics d'una manera natural. Anàlogament, les learnheurístiques combinen l'estadística amb les metaheurístiques per fer front a problemes en entorns dinàmics, en què els inputs poden dependre de l'estructura de la solució. En aquest context, les principals contribucions d'aquesta tesi són: el disseny de les learnheurístiques, una classificació dels treballs que combinen l'estadística / l'aprenentatge automàtic i les metaheurístiques, i diverses aplicacions en transport, producció, finances i computació.Un gran número de procesos de toma de decisiones en sectores estratégicos como el transporte y la producción representan problemas NP-difíciles. Frecuentemente, estos problemas se caracterizan por altos niveles de incertidumbre y dinamismo. Las metaheurísticas son métodos populares para resolver problemas difíciles de optimización de manera rápida. Sin embargo, suelen asumir que los inputs, las funciones objetivo y las restricciones son deterministas y se conocen de antemano. Estas fuertes suposiciones conducen a trabajar con problemas simplificados. Como consecuencia, las soluciones obtenidas pueden tener un pobre rendimiento. Las simheurísticas integran simulación en metaheurísticas para resolver problemas estocásticos de una manera natural. De manera similar, las learnheurísticas combinan aprendizaje estadístico y metaheurísticas para abordar problemas en entornos dinámicos, donde los inputs pueden depender de la estructura de la solución. En este contexto, las principales aportaciones de esta tesis son: el diseño de las learnheurísticas, una clasificación de trabajos que combinan estadística / aprendizaje automático y metaheurísticas, y varias aplicaciones en transporte, producción, finanzas y computación.
A large number of decision-making processes in strategic sectors such as transport and production involve NP-hard problems, which are frequently characterized by high levels of uncertainty and dynamism. Metaheuristics have become the predominant method for solving challenging optimization problems in reasonable computing times. However, they frequently assume that inputs, objective functions and constraints are deterministic and known in advance. These strong assumptions lead to work on oversimplified problems, and the solutions may demonstrate poor performance when implemented. Simheuristics, in turn, integrate simulation into metaheuristics as a way to naturally solve stochastic problems, and, in a similar fashion, learnheuristics combine statistical learning and metaheuristics to tackle problems in dynamic environments, where inputs may depend on the structure of the solution. The main contributions of this thesis include (i) a design for learnheuristics; (ii) a classification of works that hybridize statistical and machine learning and metaheuristics; and (iii) several applications for the fields of transport, production, finance and computing.
16
Al-Khaledi, Zaid T. "Serial Testing for Detection of Multilocus Genetic Interactions". UKnowledge, 2019. https://uknowledge.uky.edu/statistics_etds/37.
Pełny tekst źródłaStreszczenie:
A method to detect relationships between disease susceptibility and multilocus genetic interactions is the Multifactor-Dimensionality Reduction (MDR) technique pioneered by Ritchie et al. (2001). Since its introduction, many extensions have been pursued to deal with non-binary outcomes and/or account for multiple interactions simultaneously. Studying the effects of multilocus genetic interactions on continuous traits (blood pressure, weight, etc.) is one case that MDR does not handle. Culverhouse et al. (2004) and Gui et al. (2013) proposed two different methods to analyze such a case. In their research, Gui et al. (2013) introduced the Quantitative Multifactor-Dimensionality Reduction (QMDR) that uses the overall average of response variable to classify individuals into risk groups. The classification mechanism may not be efficient under some circumstances, especially when the overall mean is close to some multilocus means. To address such difficulties, we propose a new algorithm, the Ordered Combinatorial Quantitative Multifactor-Dimensionality Reduction (OQMDR), that uses a series of testings, based on ascending order of multilocus means, to identify best interactions of different orders with risk patterns that minimize the prediction error. Ten-fold cross-validation is used to choose from among the resulting models. Regular permutations testings are used to assess the significance of the selected model. The assessment procedure is also modified by utilizing the Generalized Extreme-Value distribution to enhance the efficiency of the evaluation process. We presented results from a simulation study to illustrate the performance of the algorithm. The proposed algorithm is also applied to a genetic data set associated with Alzheimer's Disease.
17
Jarman, Ben. "Essays in optimal auction design". University of Sydney, 2008. http://hdl.handle.net/2123/4627.
Pełny tekst źródłaStreszczenie:
Doctor of Philosophy (Economics)Auctions are an ancient economic institution. Since Vickrey (1961), the development of auction theory has lead to an extremely detailed description of the often desirable characteristics of these simple selling procedures, in the process explaining their enduring popularity. Given the pervasiveness of auctions, the question of how a seller should engineer the rules of these mechanisms to maximize her own profits is a central issue in the organization of markets. The seminal paper of Myerson (1981) shows that when facing buyers with Independent Private Values (IPVs) a standard auction with a specifically selected reserve price (or prices) is optimal, that is, maximizes a seller's expected profits among all conceivable selling mechanisms. In this model, it is assumed that the buyers have perfect information as to the existence of gains from trade. We shall argue that the consequences of this assumption for the design of the optimal auction are not well understood, which motivates our analysis. The three essays of this thesis relax the `known seller valuation' assumption by examining the optimal auction program when the seller (and principal) holds private information representing her reservation value for the good. In the first essay we provide an original technique for comparing ex ante expected profits across mechanisms for a seller facing N>1 potential buyers when all traders hold private information. Our technique addresses mechanisms that cannot be ranked point-by-point through their allocation rules using the Revenue Equivalence Theorem. We find conditions such that the seller's expected profits increase in the slope of each buyer's allocation probability function. This provides new intuition for the fact that a principal does not benefit from holding private information under risk neutrality. Monopoly pricing induces steep probability functions so the seller/principal benefits from announcing a fixed price, and implicitly her private information. An application is presented for the well known k double auction of the bilateral trade literature. In the second and third essays of this thesis, we extend the above framework to allow for informational externalities. Specifically, we allow for the situation in which the seller's private information represents a common value component in buyers' valuations. Thus the seller's private information (say regarding the quality of the good) is of interest to bidders independently of any strategic effects. In recent work Cai, Riley and Ye (2007) have demonstrated that a seller who holds private information about the quality of a good faces an extra consideration in designing an auction; the reserve price signals information to bidders. In a separating equilibrium signalling is costly in the sense that reserves are higher than would be optimal under complete information. We examine the returns to the seller in an English auction from using different types of secret reserve regimes. We find that immediate disclosure of a reserve is preferable to announcement after the auction in the form of a take-it-or-leave-it offer to the winning bidder. Sale occurs less often during the auction for a given reserve price strategy under secret reserve regimes, which increases the incentive for the seller to report more favourable information though the reserve price offer. Separating equilibria involving later announcement therefore generate even lower expected profits to the seller (signalling is more costly) than under immediate disclosure. In the third essay we compare the benchmark signalling equilibrium of immediate disclosure to a screening regime which we call the Right of Refusal. In this extreme form of a secret reserve the seller never announces the reserve price, she simply accepts or rejects the auction price. We find that the Right of Refusal dominates immediate disclosure if the seller's valuation is a sufficient statistic for the private information of interest. Thus a seller with market-relevant private preference information can benefit from not exercising monopoly price setting power. The result also provides conditions under which a competitive screening equilibrium is more efficient than a signalling mechanism. Broadly speaking, screening is better when the common value aspect in the preferences of the informed and uninformed parties are `aligned', and potential gains from trade to the uninformed party are significant. We believe this conclusion to be of particular interest to the design of privatization schemes.
18
Thapper, Johan. "Combinatorial Considerations on Two Models from Statistical Mechanics". Licentiate thesis, Linköping : Matematiska institutionen, Linköpings universitet, 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-10141.
Pełny tekst źródła
19
Polettini, Matteo <1982>. "Geometric and Combinatorial Aspects of NonEquilibrium Statistical Mechanics". Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2012. http://amsdottorato.unibo.it/4305/1/polettini_matteo_tesi.pdf.
Pełny tekst źródłaStreszczenie:
Non-Equilibrium Statistical Mechanics is a broad subject. Grossly speaking, it deals with systems which have not yet relaxed to an equilibrium state, or else with systems which are in a steady non-equilibrium state, or with more general situations. They are characterized by external forcing and internal fluxes, resulting in a net production of entropy which quantifies dissipation and the extent by which, by the Second Law of Thermodynamics, time-reversal invariance is broken. In this thesis we discuss some of the mathematical structures involved with generic discrete-state-space non-equilibrium systems, that we depict with networks in all analogous to electrical networks. We define suitable observables and derive their linear regime relationships, we discuss a duality between external and internal observables that reverses the role of the system and of the environment, we show that network observables serve as constraints for a derivation of the minimum entropy production principle. We dwell on deep combinatorial aspects regarding linear response determinants, which are related to spanning tree polynomials in graph theory, and we give a geometrical interpretation of observables in terms of Wilson loops of a connection and gauge degrees of freedom. We specialize the formalism to continuous-time Markov chains, we give a physical interpretation for observables in terms of locally detailed balanced rates, we prove many variants of the fluctuation theorem, and show that a well-known expression for the entropy production due to Schnakenberg descends from considerations of gauge invariance, where the gauge symmetry is related to the freedom in the choice of a prior probability distribution. As an additional topic of geometrical flavor related to continuous-time Markov chains, we discuss the Fisher-Rao geometry of nonequilibrium decay modes, showing that the Fisher matrix contains information about many aspects of non-equilibrium behavior, including non-equilibrium phase transitions and superposition of modes. We establish a sort of statistical equivalence principle and discuss the behavior of the Fisher matrix under time-reversal. To conclude, we propose that geometry and combinatorics might greatly increase our understanding of nonequilibrium phenomena.
20
Polettini, Matteo <1982>. "Geometric and Combinatorial Aspects of NonEquilibrium Statistical Mechanics". Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2012. http://amsdottorato.unibo.it/4305/.
Pełny tekst źródłaStreszczenie:
Non-Equilibrium Statistical Mechanics is a broad subject. Grossly speaking, it deals with systems which have not yet relaxed to an equilibrium state, or else with systems which are in a steady non-equilibrium state, or with more general situations. They are characterized by external forcing and internal fluxes, resulting in a net production of entropy which quantifies dissipation and the extent by which, by the Second Law of Thermodynamics, time-reversal invariance is broken. In this thesis we discuss some of the mathematical structures involved with generic discrete-state-space non-equilibrium systems, that we depict with networks in all analogous to electrical networks. We define suitable observables and derive their linear regime relationships, we discuss a duality between external and internal observables that reverses the role of the system and of the environment, we show that network observables serve as constraints for a derivation of the minimum entropy production principle. We dwell on deep combinatorial aspects regarding linear response determinants, which are related to spanning tree polynomials in graph theory, and we give a geometrical interpretation of observables in terms of Wilson loops of a connection and gauge degrees of freedom. We specialize the formalism to continuous-time Markov chains, we give a physical interpretation for observables in terms of locally detailed balanced rates, we prove many variants of the fluctuation theorem, and show that a well-known expression for the entropy production due to Schnakenberg descends from considerations of gauge invariance, where the gauge symmetry is related to the freedom in the choice of a prior probability distribution. As an additional topic of geometrical flavor related to continuous-time Markov chains, we discuss the Fisher-Rao geometry of nonequilibrium decay modes, showing that the Fisher matrix contains information about many aspects of non-equilibrium behavior, including non-equilibrium phase transitions and superposition of modes. We establish a sort of statistical equivalence principle and discuss the behavior of the Fisher matrix under time-reversal. To conclude, we propose that geometry and combinatorics might greatly increase our understanding of nonequilibrium phenomena.
21
Morabito, David L. "Statistical mechanics of neural networks and combinatorial opimization problems /". Online version of thesis, 1991. http://hdl.handle.net/1850/11089.
Pełny tekst źródła
22
Briend, Simon. "Inference of the past of random structures and other random problems". Electronic Thesis or Diss., université Paris-Saclay, 2024. http://www.theses.fr/2024UPASM013.
Pełny tekst źródłaStreszczenie:
Cette thèse est décomposée en trois parties disjointes. Les deux premières parties se concentrent sur des modèles de graphes aléatoires croissants de manière dynamique. Dans la première partie, nous inférons des informations sur le passé d'un graphe à partir d'une unique observation dudit graphe. Nous commençons par le problème de la recherche de racine, où l'objectif est de trouver un ensemble de confiance pour la racine. Nous proposons une méthode pour les L-dags uniformes et analysons ses performances. À notre connaissance, il s'agit de la première méthode réalisant une archéologie du graphe dans des graphes généraux. Nous étendons ensuite naturellement la question de la recherche de racine à celle de la sériation. Étant donné un instantané d'un graphe, est-il possible de récupérer son ordre complet ? Nous présentons une méthode et une garantie statistique sur sa qualité dans le cas des arbres récursifs uniformes et des arbres d'attachement préférentiel linéaire. Pour conclure la section sur l'archéologie de graphe, nous étudions un problème de broadcasting, où l'on ne tente pas de retrouver la racine du graphe mais son état. Dans de tels problèmes, la racine se voit attribuer un bit, qui est ensuite propagé de manière bruité lors de la croissance du réseau. Dans les L-dags, nous étudions un vote par majorité pour estimer le bit de la racine et identifions trois régimes, dépendants du niveau de bruit. Dans la deuxième partie, nous étudions l'arbre d'amitié aléatoire, qui est un modèle d'arbre récursif aléatoire avec redirection complète. Dans ce modèle apparaît un phénomène de rich-get-richer, mais à la différence du modèle d'attachement préférentiel celui ci découle d'un processus d'attachement local. Nous prouvons des conjectures sur la distribution des degrés, le diamètre et la structure locale. Enfin, nous plongeons dans le monde de l'apprentissage automatique théorique et de l'analyse de données. Nous étudions une approximation aléatoire de la profondeur de Tukey. La profondeur de Tukey est un outil puissant pour la visualisation des données et peut être considérée comme une extension des quantiles en dimension plus élevée (ils coïncident en dimension 1). Son calcul exact est NP-difficile, et nous étudions les performances d'une approximation aléatoire dans le cas de données échantillonnées à partir d'une distribution log-concaveThis thesis is decomposed in three disjoint parts. The first two parts delve into dynamically growing networks. In the first part, we infer information about the past from a snapshot of the graph. We start by the problem of root finding, where the goal is to find confidence set for the root. We propose a method for uniform L-dags and analyse its performance. It is, to the best of our knowledge, the first method achieving network archaeology in general graphs. Then, we naturally extend the question of root finding to the one of seriation. Given a snapshot of a graph, is it possible to retrieve its whole ordering? We present a method and statistical guarantee of its quality in the case of uniform random recursive trees and linear preferential attachment tree. To conclude the network archaeology section, we study the root bit finding problem, where one does not try to infer the position of the root but its state. In such problems, the root is assigned a bit and is then propagated through a noisy channel during network growth. In the L-dag, we study majority voting to infer the bit of the root and we identify three different regimes depending on the noise level. In the second part of this thesis, we study the so called friendship tree, which is a random recursive tree model with complete redirection. This model display emerging properties, but unlike in the preferential attachment model they stem from a local attachment rule. We prove conjectures about degree distribution, diameter and local structure. Finally, we delve into the world of theoretical machine learning and data analysis. We study a random approximation of the Tukey depth. The Tukey depth is a powerful tool for data visualization and can be thought of as an extension of quantiles in higher dimension (they coincide in dimension 1). Its exact computation is NP-hard, and we study the performances of a classical random approximation in the case of data sets sampled from log-concave distribution
23
Rava, Andrea Basilio. "Quantum approximate optimization algorithm: combinatorial problems and classical statistical models". Master's thesis, Alma Mater Studiorum - Università di Bologna, 2021. http://amslaurea.unibo.it/23113/.
Pełny tekst źródłaStreszczenie:
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm for solving combinatorial optimization problems. Since most of combinatorial optimization problems may be thought as particular instances of Ising Hamiltonians, the study of the QAOA is very relevant from the physical point of view for its potential applications in describing physical systems. In the QAOA a quantum state is prepared and, through 2p parameterized quantum evolutions, a final state which represents an extreme of cost function and encodes the approximate solution of the problem is obtained. The 2p parameters are determined through a classical parameter optimization process. In this work we apply QAOA to two different problems, the Max Cut and the random bond Ising Model (RBIM). For both problems we perform an analysis of the optimization efficiency, verifying that the quality of the approximation increases with p. For the Max Cut we perform a further analysis of the p=1 case for which we obtain an analytical expression for the cost function and make observations regarding the choice of the initial parameters in the optimization procedure. For the RBIM, for different disordered configurations we obtain the ground states energies and magnetizations for different lattice sizes and different level p of the optimisation. We observe that, even if the magnetisation is obtained for small lattice sizes, its behaviour suggests the presence of a transition separating a ferromagnetic from a paramagnetic phase.
24
DI, GIOACCHINO ANDREA. "EUCLIDEAN CORRELATIONS IN COMBINATORIAL OPTIMIZATION PROBLEMS: A STATISTICAL PHYSICS APPROACH". Doctoral thesis, Università degli Studi di Milano, 2019. http://hdl.handle.net/2434/693073.
Pełny tekst źródłaStreszczenie:
In this thesis I discuss combinatorial optimization problems, from the statistical physics perspective. The starting point are the motivations which brought physicists together with computer scientists and mathematicians to work on this beautiful and deep topic. I give some elements of complexity theory, and I motivate why the point of view of statistical physics, although different from the one adopted in standard complexity theory, leads to many interesting results, as well as new questions. I discuss the connection between combinatorial optimization problems and spin glasses. Finally, I briefly review some topics of large deviation theory, as a way to go beyond average quantities. As a concrete example of this, I show how the replica method can be used to explore the large deviations of a well-known toy model of spin glasses, the p-spin spherical model. In the second chapter I specialize in Euclidean combinatorial optimization problems. In particular, I explain why these problems, when embedded in a finite dimensional Euclidean space, are difficult to deal with. I analyze several problems (the matching and assignment problems, the traveling salesman problem, and the 2-factor problem) in one dimension to explain a quite general technique to deal with one dimensional Euclidean combinatorial optimization problems. Whenever possible, and in a detailed way for the traveling-salesman problem case, I also discuss how to proceed in two (and also more) dimensions. In the last chapter I outline a promising approach to tackle hard combinatorial optimization problems: quantum computing. After giving a quick overview of the paradigm of quantum computation (and its differences with respect to the classical one), I discuss in detail the application of the so-called quantum annealing algorithm to a specific case of the matching problem, also by providing a comparison between the performance of a recent quantum annealer machine (the D-Wave 2000Q) and a classical super-computer equipped with an heuristic algorithm (an implementation of parallel tempering). Finally, I draw the conclusions of my work and I suggest some interesting directions for future studies.
25
Beeler, Robert A. "How to Count: An Introduction to Combinatorics and Its Applications". Digital Commons @ East Tennessee State University, 2015. https://dc.etsu.edu/etsu_books/179.
Pełny tekst źródłaStreszczenie:
Providing a self-contained resource for upper undergraduate courses in combinatorics, this text emphasizes computation, problem solving, and proof technique. In particular, the book places special emphasis the Principle of Inclusion and Exclusion and the Multiplication Principle. To this end, exercise sets are included at the end of every section, ranging from simple computations (evaluate a formula for a given set of values) to more advanced proofs. The exercises are designed to test students' understanding of new material, while reinforcing a working mastery of the key concepts previously developed in the book. Intuitive descriptions for many abstract techniques are included. Students often struggle with certain topics, such as generating functions, and this intuitive approach to the problem is helpful in their understanding. When possible, the book introduces concepts using combinatorial methods (as opposed to induction or algebra) to prove identities. Students are also asked to prove identities using combinatorial methods as part of their exercises. These methods have several advantages over induction or algebra.https://dc.etsu.edu/etsu_books/1199/thumbnail.jpg
26
Mustafa, Nabil. "Approximations of Points: Combinatorics and Algorithms". Habilitation à diriger des recherches, Université Paris-Est, 2013. http://tel.archives-ouvertes.fr/tel-01062825.
Pełny tekst źródłaStreszczenie:
At the core of successful manipulation and computation over large geometric data is the notion of approximation, both structural and computational. The focus of this thesis will be on the combinatorial and algorithmic aspects of approximations of point-set data P in d-dimensional Euclidean space. It starts with a study of geometric data depth where the goal is to compute a point which is the 'combinatorial center' of P. Over the past 50 years several such measures of combinatorial centers have been proposed, and we will re-examine several of them: Tukey depth, Simplicial depth, Oja depth and Ray-Shooting depth. This can be generalized to approximations with a subset, leading to the notion of epsilon-nets. There we will study the problem of approximations with respect to convexity. Along the way, this requires re-visiting and generalizing some basic theorems of convex geometry, such as the Caratheodory's theorem. Finally we will turn to the algorithmic aspects of these problems. We present a polynomial-time approximation scheme for computing hitting-sets for disks in the plane. Of separate interest is the technique, an analysis of local-search via locality graphs. A further application of this technique is then presented in computing independent sets in intersection graphs of rectangles in the plane.
27
Oliveira, Saullo Haniell Galvão de 1988. "On biclusters aggregation and its benefits for enumerative solutions = Agregação de biclusters e seus benefícios para soluções enumerativas". [s.n.], 2015. http://repositorio.unicamp.br/jspui/handle/REPOSIP/259072.
Pełny tekst źródłaStreszczenie:
Orientador: Fernando José Von ZubenDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação
Made available in DSpace on 2018-08-27T03:28:44Z (GMT). No. of bitstreams: 1 Oliveira_SaulloHaniellGalvaode_M.pdf: 1171322 bytes, checksum: 5488cfc9b843dbab6d7a5745af1e3d4b (MD5) Previous issue date: 2015
Resumo: Biclusterização envolve a clusterização simultânea de objetos e seus atributos, definindo mo- delos locais de relacionamento entre os objetos e seus atributos. Assim como a clusterização, a biclusterização tem uma vasta gama de aplicações, desde suporte a sistemas de recomendação, até análise de dados de expressão gênica. Inicialmente, diversas heurísticas foram propostas para encontrar biclusters numa base de dados numérica. No entanto, tais heurísticas apresen- tam alguns inconvenientes, como não encontrar biclusters relevantes na base de dados e não maximizar o volume dos biclusters encontrados. Algoritmos enumerativos são uma proposta recente, especialmente no caso de bases numéricas, cuja solução é um conjunto de biclusters maximais e não redundantes. Contudo, a habilidade de enumerar biclusters trouxe mais um cenário desafiador: em bases de dados ruidosas, cada bicluster original se fragmenta em vá- rios outros biclusters com alto nível de sobreposição, o que impede uma análise direta dos resultados obtidos. Essa fragmentação irá ocorrer independente da definição escolhida de co- erência interna no bicluster, sendo mais relacionada com o próprio nível de ruído. Buscando reverter essa fragmentação, nesse trabalho propomos duas formas de agregação de biclusters a partir de resultados que apresentem alto grau de sobreposição: uma baseada na clusteriza- ção hierárquica com single linkage, e outra explorando diretamente a taxa de sobreposição dos biclusters. Em seguida, um passo de poda é executado para remover objetos ou atributos indesejados que podem ter sido incluídos como resultado da agregação. As duas propostas foram comparadas entre si e com o estado da arte, em diversos experimentos, incluindo bases de dados artificiais e reais. Essas duas novas formas de agregação não só reduziram significa- tivamente a quantidade de biclusters, essencialmente defragmentando os biclusters originais, mas também aumentaram consistentemente a qualidade da solução, medida em termos de precisão e recuperação, quando os biclusters são conhecidos previamente
Abstract: Biclustering involves the simultaneous clustering of objects and their attributes, thus defin- ing local models for the two-way relationship of objects and attributes. Just like clustering, biclustering has a broad set of applications, ranging from an advanced support for recom- mender systems of practical relevance to a decisive role in data mining techniques devoted to gene expression data analysis. Initially, heuristics have been proposed to find biclusters, and their main drawbacks are the possibility of losing some existing biclusters and the inca- pability of maximizing the volume of the obtained biclusters. Recently efficient algorithms were conceived to enumerate all the biclusters, particularly in numerical datasets, so that they compose a complete set of maximal and non-redundant biclusters. However, the ability to enumerate biclusters revealed a challenging scenario: in noisy datasets, each true bicluster becomes highly fragmented and with a high degree of overlapping, thus preventing a direct analysis of the obtained results. Fragmentation will happen no matter the boundary condi- tion adopted to specify the internal coherence of the valid biclusters, though the degree of fragmentation will be associated with the noise level. Aiming at reverting the fragmentation, we propose here two approaches for properly aggregating a set of biclusters exhibiting a high degree of overlapping: one based on single linkage and the other directly exploring the rate of overlapping. A pruning step is then employed to filter intruder objects and/or attributes that were added as a side effect of aggregation. Both proposals were compared with each other and also with the actual state-of-the-art in several experiments, including real and artificial datasets. The two newly-conceived aggregation mechanisms not only significantly reduced the number of biclusters, essentially defragmenting true biclusters, but also consistently in- creased the quality of the whole solution, measured in terms of Precision and Recall when the composition of the dataset is known a priori
Mestrado
Engenharia de Computação
Mestre em Engenharia Elétrica
28
Wingkono, Gracy A. "Combinatorial Technique for Biomaterial Design". Thesis, Georgia Institute of Technology, 2004. http://hdl.handle.net/1853/7264.
Pełny tekst źródłaStreszczenie:
Combinatorial techniques have changed the paradigm of materials research by allowing a faster data acquisition in complex problems with multidimensional parameter space. The focus of this thesis is to demonstrate biomaterials design and characterization via preparation of two dimensional combinatorial libraries with chemically-distinct structured patterns. These are prepared from blends of biodegradable polymers using thickness and temperature gradient techniques.
The desired pattern in the library is chemically-distinct cell adhesive versus non-adhesive micro domains that improve library performance compared to previous implementations that had modest chemical differences. Improving adhesive contrast should minimize the competing effects of chemistry versus physical structure. To accomplish this, a method of blending and crosslinking cell adhesive poly(季aprolactone) (PCL) with cell non-adhesive poly(ethylene glycol) (PEG) was developed. We examine the interaction between MC3T3-E1 osteoblast cells and PCL-PEG libraries of thousands of distinct chemistries, microstructures, and roughnesses.
These results show that cells grown on such patterned biomaterial are sensitive to the physical distribution and phases of the PCL and PEG domains.
We conclude that the cells adhered and spread on PCL regions mixed with PEG-crosslinked non-crystalline phases. Tentatively, we attribute this behavior to enhanced physical, as well as chemical, contrast between crystalline PCL and non-crystalline PEG.
29
Borrotti, Matteo <1981>. "An evolutionary approach to the design of experiments for combinatorial optimization with an application to enzyme engineering". Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2011. http://amsdottorato.unibo.it/3422/1/Matteo_Borrotti_tesi.pdf.
Pełny tekst źródłaStreszczenie:
In a large number of problems the high dimensionality of the search space, the vast number of variables and the economical constrains limit the ability of classical techniques to reach the optimum of a function, known or unknown. In this thesis we investigate the possibility to combine approaches from advanced statistics and optimization algorithms in such a way to better explore the combinatorial search space and to increase the performance of the approaches. To this purpose we propose two methods: (i) Model Based Ant Colony Design and (ii) Naïve Bayes Ant Colony Optimization. We test the performance of the two proposed solutions on a simulation study and we apply the novel techniques on an appplication in the field of Enzyme Engineering and Design.
30
Borrotti, Matteo <1981>. "An evolutionary approach to the design of experiments for combinatorial optimization with an application to enzyme engineering". Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2011. http://amsdottorato.unibo.it/3422/.
Pełny tekst źródłaStreszczenie:
In a large number of problems the high dimensionality of the search space, the vast number of variables and the economical constrains limit the ability of classical techniques to reach the optimum of a function, known or unknown. In this thesis we investigate the possibility to combine approaches from advanced statistics and optimization algorithms in such a way to better explore the combinatorial search space and to increase the performance of the approaches. To this purpose we propose two methods: (i) Model Based Ant Colony Design and (ii) Naïve Bayes Ant Colony Optimization. We test the performance of the two proposed solutions on a simulation study and we apply the novel techniques on an appplication in the field of Enzyme Engineering and Design.
31
Streib, Amanda Pascoe. "Markov chains at the interface of combinatorics, computing, and statistical physics". Diss., Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/43628.
Pełny tekst źródłaStreszczenie:
The fields of statistical physics, discrete probability, combinatorics, and theoretical computer science have converged around efforts to understand random structures and algorithms. Recent activity in the interface of these fields has enabled tremendous breakthroughs in each domain and has supplied a new set of techniques for researchers approaching related problems. This thesis makes progress on several problems in this interface whose solutions all build on insights from multiple disciplinary perspectives.
First, we consider a dynamic growth process arising in the context of DNA-based self-assembly. The assembly process can be modeled as a simple Markov chain. We prove that the chain is rapidly mixing for large enough bias in regions of Z^d. The proof uses a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias, where the bias can vary depending on the location of the tile, which arises in the nanotechnology application. Moreover, we use intuition from statistical physics to construct a choice of the biases for which the Markov chain M_mon requires exponential time to converge.
Second, we consider a related problem regarding the convergence rate of biased permutations that arises in the context of self-organizing lists. The Markov chain M_nn in this case is a nearest-neighbor chain that allows adjacent transpositions, and the rate of these exchanges is governed by various input parameters. It was conjectured that the chain is
always rapidly mixing when the inversion probabilities are positively biased, i.e., we put nearest neighbor pair x
32
Rohwer, Christian Matthias. "Combinatorics and dynamics in polymer knots". Thesis, Stellenbosch : Stellenbosch University, 2014. http://hdl.handle.net/10019.1/86706.
Pełny tekst źródłaStreszczenie:
Thesis (PhD)--Stellenbosch University, 2014.ENGLISH ABSTRACT: In this dissertation we address the conservation of topological states in polymer knots. Topological constraints are frequently included into theoretical descriptions of polymer systems through invariants such as winding numbers and linking numbers of polynomial invariants. In contrast, our approach is based on sequences of manipulations of knots that maintain a given knot's topology; these are known as Reidemeister moves. We begin by discussing basic properties of knots and their representations. In particular, we show how the Reidemeister moves may be viewed as rules for dynamics of crossings in planar projections of knots. Thereafter we consider various combinatoric enumeration procedures for knot configurations that are equivalent under chosen topological constraints. Firstly, we study a reduced system where only the zeroth and first Reidemeister moves are allowed, and present a diagrammatic summation of all contributions to the associated partition function. The partition function is then calculated under basic simplifying assumptions for the Boltzmann weights associated with various configurations. Secondly, we present a combinatoric scheme for enumerating all topologically equivalent configurations of a polymer strand that is wound around a rod and closed. This system has the constraint of a fixed winding number, which may be viewed in terms of manipulations that obey a Reidemeister move of the second kind of the polymer relative to the rod. Again configurations are coupled to relevant statistical weights, and the partition function is approximated. This result is used to calculate various physical quantities for confined geometries. The work in that chapter is based on a recent publication, "Conservation of polymer winding states: a combinatoric approach", C.M. Rohwer, K.K. Müller-Nedebock, and F.-E. Mpiana Mulamba, J. Phys. A: Math. Theor. 47 (2014) 065001. The remainder of the dissertation is concerned with a dynamical description of the Reidemeister moves. We show how the rules for crossing dynamics may be addressed in an operator formalism for stochastic dynamics. Differential equations for densities and correlators for crossings on strands are calculated for some of the Reidemeister moves. These quantities are shown to encode the relevant dynamical constraints. Lastly we sketch some suggestions for the incorporation of themes in this dissertation into an algorithm for the simulated annealing of knots.
AFRIKAANSE OPSOMMING: In hierdie tesis ondersoek ons die behoud van topologiese toestande in knope. Topologiese dwangvoorwaardes word dikwels d.m.v. invariante soos windingsgetalle, skakelgetalle en polinomiese invariante in die teoretiese beskrywings van polimere ingebou. In teenstelling hiermee is ons benadering gebaseer op reekse knoopmanipulasies wat die topologie van 'n gegewe knoop behou - die sogenaamde Reidemeisterskuiwe. Ons begin met 'n bespreking van die basiese eienskappe van knope en hul daarstellings. Spesi ek toon ons dat die Reidemeisterskuiwe beskryf kan word i.t.v. reëls vir die dinamika van kruisings in planêre knoopprojeksies. Daarna beskou ons verskeie kombinatoriese prosedures om ekwivalente knoopkon gurasies te genereer onderhewig aan gegewe topologiese dwangvoorwaardes. Eerstens bestudeer ons 'n vereenvoudigde sisteem waar slegs die nulde en eerste Reidemeisterskuiwe toegelaat word, en lei dan 'n diagrammatiese sommasie van alle bydraes tot die geassosieerde toestandsfunksie af. Die partisiefunksie word dan bereken onderhewig aan sekere vereenvoudigende aannames vir die Boltzmanngewigte wat met die verskeie kon- gurasies geassosieer is. Tweedens stel ons 'n kombinatoriese skema voor om ekwivalente kon gurasies te genereer vir 'n polimeer wat om 'n staaf gedraai word. Die beperking tot 'n vaste windingsgetal in hierdie sisteem kan daargestel word i.t.v. 'n Reidemeister skuif van die polimeer t.o.v. die staaf. Weereens word kon gurasies gekoppel aan relevante statistiese gewigte en die partisiefunksie word benader. Verskeie siese hoeveelhede word dan bereken vir beperkte geometrie e. Die werk in di e hoofstuk is gebaseer op 'n onlangse publikasie, "Conservation of polymer winding states: a combinatoric approach", C.M. Rohwer, K.K. Müller-Nedebock, and F.-E. Mpiana Mulamba, J. Phys. A: Math. Theor. 47 (2014) 065001. Die res van die tesis handel oor 'n dinamiese beskrywing van die Reidemeisterskuiwe. Ons toon hoe die re els vir kruisingsdinamika beskryf kan word i.t.v. 'n operatorformalisme vir stochastiese dinamika. Di erensiaalvergelykings vir digthede en korrelatore vir kruisings op stringe word bereken vir sekere Reidemeisterskuiwe. Daar word getoon dat hierdie hoeveelhede die relevante dinamiese beperkings respekteer. Laastens maak ons 'n paar voorstelle vir hoe idees uit hierdie tesis geï nkorporeer kan word in 'n algoritme vir die gesimuleerde vereenvoudiging van knope.
33
Lee, Jonathan David. "Probabilistic combinatorics in factoring, percolation and related topics". Thesis, University of Cambridge, 2015. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.709255.
Pełny tekst źródła
34
Martin, Russell Andrew. "Paths, sampling, and markov chain decomposition". Diss., Georgia Institute of Technology, 2001. http://hdl.handle.net/1853/29383.
Pełny tekst źródła
35
Han, Bin. "Gamma positivity in enumerative combinatorics". Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1115/document.
Pełny tekst źródłaStreszczenie:
La positivité gamma d’une suite combinatoire unifie à la fois l’unimodalité et la symétrie de cette suite. Trouver des nouvelles familles d’objets dont les polynômes énumératives ont une positivité gamma est un défi et un sujet important en combinatoire et géométrie. Il a attiré beaucoup d’attention ces derniers temps en raison de la conjecture de Gal, qui affirme que le gamma-vecteur a des coefficients positifs pour n’importe quel polytope simple. Souvent, le h-polynôme pour les polytopes simpliciaux de signification combinatoire peut être donné en tant que fonction génératrice sur un ensemble d’objets combinatoires apparentés par rapport à une statistique telle que le nombre des descentes, dont les polynômes énumératifs sur les permutations sont des polynômes Eulériens. Ce travail traite des propriétés gamma de plusieurs polynômes énumératifs de permutations tels que les polynômes Eulériens et les polynômes de Narayana. Cette thèse contient cinq chapitresThe gamma positivity of a combinatorial sequence unifies both unimodality and symmetry. Finding new family of objets whose enumerative sequences have gamma positivity is a challenge and important topic in recent years. it has received considerable attention in recent times because of Gal’s conjecture, which asserts that the gamma-vector has nonnegative entries for any flag simple polytope. Often times, the h-polynomial for simplicial polytopes of combinatorial signification can be given as a generating function over a related set of combinatorial objects with respect to some statistic like the descent numbers, whose enumerative polynomials on permutations are Eulerian polynomials.This work deals with the gamma properties of several enumerative polynomials of permutation such as Eulerian polynomials and Narayana polynomials. This thesis contains five chapters
36
Farr, Graham E. "Topics in computational complexity". Thesis, University of Oxford, 1986. http://ora.ox.ac.uk/objects/uuid:ad3ed1a4-fea4-4b46-8e7a-a0c6a3451325.
Pełny tekst źródła
37
Boberg, Jonas. "Counting Double-Descents and Double-Inversions in Permutations". Thesis, Mälardalens högskola, Akademin för utbildning, kultur och kommunikation, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-54431.
Pełny tekst źródłaStreszczenie:
In this paper, new variations of some well-known permutation statistics are introduced and studied. Firstly, a double-descent of a permutation π is defined as a position i where πi ≥ 2πi+1. By proofs by induction and direct proofs, recursive and explicit expressions for the number of n-permutations with k double-descents are presented. Also, an expression for the total number of double-descents in all n-permutations is presented. Secondly, a double-inversion of a permutation π is defined as a pair (πi,πj) where i<j but πi ≥ 2πj. The total number of double-inversions in all n-permutations is presented.
38
Mohan, Sidharth. "Consensus, Correlation And Combinatorics Based Approaches In Engineering And Exploring Triosephosphate Isomerase Stability". The Ohio State University, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=osu1503054678218166.
Pełny tekst źródła
39
Riggle, Matthew. "Runs of Identical Outcomes in a Sequence of Bernoulli Trials". TopSCHOLAR®, 2018. https://digitalcommons.wku.edu/theses/2451.
Pełny tekst źródłaStreszczenie:
The Bernoulli distribution is a basic, well-studied distribution in probability. In this thesis, we will consider repeated Bernoulli trials in order to study runs of identical outcomes. More formally, for t ∈ N, we let Xt ∼ Bernoulli(p), where p is the probability of success, q = 1 − p is the probability of failure, and all Xt are independent. Then Xt gives the outcome of the tth trial, which is 1 for success or 0 for failure. For n, m ∈ N, we define Tn to be the number of trials needed to first observe n consecutive successes (where the nth success occurs on trial XTn ). Likewise, we define Tn,m to be the number of trials needed to first observe either n consecutive successes or m consecutive failures.
We shall primarily focus our attention on calculating E[Tn] and E[Tn,m]. Starting with the simple cases of E[T2] and E[T2,2], we will use a variety of techniques, such as counting arguments and Markov chains, in order to derive the expectations. When possible, we shall also provide closed-form expressions for the probability mass function, cumulative distribution function, variance, and other values of interest. Eventually we will work our way to general formulas for E[Tn] and E[Tn,m]. We will also derive formulas for conditional averages, and discuss how famous results from probability such as Wald’s Identity apply to our problem. Numerical examples will also be given in order to supplement the discussion and clarify the results.
40
Noel, Jonathan A. "Extremal combinatorics, graph limits and computational complexity". Thesis, University of Oxford, 2016. https://ora.ox.ac.uk/objects/uuid:8743ff27-b5e9-403a-a52a-3d6299792c7b.
Pełny tekst źródłaStreszczenie:
This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Qm in Qd. Specifically, we show that for m ≥ 2 fixed and d large there exists a subgraph G of Qd of bounded average degree such that G does not contain a copy of Qm but, for every G' such that G ⊊ G' ⊆ Qd, the graph G' contains a copy of Qm. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists ε > 0 such that for all k and for n sufficiently large there is a collection of at most 2(1-ε)k subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, Pálvölgyi and Patkós. We also prove that there exists a constant c ∈ (0,1) such that the smallest such collection is of cardinality 2(1+o(1))ck for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Qm in Qd. That is, we determine the minimum number of edges in a spanning subgraph G of Qd such that the edges of E(Qd)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Qm. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A0 of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A0 percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r ≥ 2, every percolating set in Qd has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollobás and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset 𝒱(q,n) consisting of all subspaces of 𝔽qnordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in 𝒱(q,n) and a bound on the size of the largest antichain in a p-random subset of 𝒱(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (εi)∞i=1 tending to zero such that, for all i ≥ 1, every weak εi-regular partition of W has at least exp(εi-2/25log∗εi-2) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lovász and Szegedy. For positive integers p,q with p/q ❘≥ 2, a circular (p,q)-colouring of a graph G is a mapping V(G) → ℤp such that any two adjacent vertices are mapped to elements of ℤp at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 ≤ p/q < 4 and is PSPACE-complete for p/q ≥ 4.
41
Kam-Thong, Tony Verfasser], i Klaus-Robert [Akademischer Betreuer] [Müller. "Massive parallelization of combinatorial statistical genetics analyses porting machine learning methods on general purpose graphics processing units (GPU) / Tony Kam-Thong. Betreuer: Klaus Robert Müller". Berlin : Universitätsbibliothek der Technischen Universität Berlin, 2012. http://d-nb.info/102553879X/34.
Pełny tekst źródła
42
Kang, Ross J. "Improper colourings of graphs". Thesis, University of Oxford, 2008. http://ora.ox.ac.uk/objects/uuid:a93d8303-0eeb-4d01-9b77-364113b81a63.
Pełny tekst źródłaStreszczenie:
We consider a generalisation of proper vertex colouring of graphs, referred to as improper colouring, in which each vertex can only be adjacent to a bounded number t of vertices with the same colour, and we study this type of graph colouring problem in several different settings. The thesis is divided into six chapters. In Chapter 1, we outline previous work in the area of improper colouring. In Chapters 2 and 3, we consider improper colouring of unit disk graphs -- a topic motivated by applications in telecommunications -- and take two approaches, first an algorithmic one and then an average-case analysis. In Chapter 4, we study the asymptotic behaviour of the improper chromatic number for the classical Erdos-Renyi model of random graphs. In Chapter 5, we discuss acyclic improper colourings, a specialisation of improper colouring, for graphs of bounded maximum degree. Finally, in Chapter 6, we consider another type of colouring, frugal colouring, in which no colour appears more than a bounded number of times in any neighbourhood. Throughout the thesis, we will observe a gradient of behaviours: for random unit disk graphs and "large" unit disk graphs, we can greatly reduce the required number of colours relative to proper colouring; in Erdos-Renyi random graphs, we do gain some improvement but only when t is relatively large; for acyclic improper chromatic numbers of bounded degree graphs, we discern an asymptotic difference in only a very narrow range of choices for t.
43
Hahn-Klimroth, Maximilian Grischa [Verfasser], Amin [Akademischer Betreuer] Coja-Oghla, Yury [Akademischer Betreuer] Person, Amin [Gutachter] Coja-Oghlan i Uriel [Gutachter] Feige. "Large discrete structures : statistical inference, combinatorics and limits / Maximilian Grischa Hahn-Klimroth ; Gutachter: Amin Coja-Oghlan, Uriel Feige ; Amin Coja-Oghla, Yury Person". Frankfurt am Main : Universitätsbibliothek Johann Christian Senckenberg, 2021. http://d-nb.info/1239730039/34.
Pełny tekst źródła
44
Samimi, Peyman. "Combinatorial Assessment of the Influence of Composition and Exposure Time on the Oxidation Behavior and Concurrent Oxygen-induced Phase Transformations of Binary Ti-x Systems". Thesis, University of North Texas, 2015. https://digital.library.unt.edu/ark:/67531/metadc801898/.
Pełny tekst źródłaStreszczenie:
The relatively low oxidation resistance and subsequent surface embrittlement have often limited the use of titanium alloys in elevated temperature structural applications. Although extensive effort is spent to investigate the high temperature oxidation performance of titanium alloys, the studies are often constrained to complex technical titanium alloys and neither the mechanisms associated with evolution of the oxide scale nor the effect of oxygen ingress on the microstructure of the base metal are well-understood. In addition lack of systematic oxidation studies across a wider domain of the alloy composition has complicated the determination of composition-mechanism-property relationships. Clearly, it would be ideal to assess the influence of composition and exposure time on the oxidation resistance, independent of experimental variabilities regarding time, temperature and atmosphere as the potential source of error. Such studies might also provide a series of metrics (e.g., hardness, scale, etc) that could be interpreted together and related to the alloy composition. In this thesis a novel combinatorial approach was adopted whereby a series of compositionally graded specimens, (Ti-xMo, Ti-xCr, Ti-xAl and Ti-xW) were prepared using Laser Engineered Net Shaping (LENS™) technology and exposed to still-air at 650 °C. A suite of the state-of-the-art characterization techniques were employed to assess several aspects of the oxidation reaction as a function of local average composition including: the operating oxidation mechanisms; the structure and composition of the oxides; the oxide adherence and porosity; the thickness of the oxide layers; the depth of oxygen ingress; and microstructural evolution of the base material just below the surface but within the oxygen-enriched region. The results showed that for the Ti-Mo, Ti-Al and Ti-W systems a parabolic oxidation rate law is obeyed in the studied composition-time domain while Ti-Cr system experiences a rapid breakaway oxidation regime at low solute concentrations. The only titanium oxide phase present in the scale for all the binary systems was identified as rutile (TiO2) and formation of multiphase oxide scales TiO2+Al2O3 in Ti-Al system and TiO2+TiCr2 in Ti-Cr system was observed. A thermodynamic framework has been used to rationalize the oxygen-induced subsurface microstructural transformations including: homogeneous precipitation of nano-scaled β particles and discontinuous precipitation of +β phases in Ti-Mo and Ti-W system, evolution of TiCr2 intermetallic phase in Ti-Cr system and ordering phase transformation in Ti-Al system.
45
Warnke, Lutz. "Random graph processes with dependencies". Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:71b48e5f-a192-4684-a864-ea9059a25d74.
Pełny tekst źródłaStreszczenie:
Random graph processes are basic mathematical models for large-scale networks evolving over time. Their systematic study was pioneered by Erdös and Rényi around 1960, and one key feature of many 'classical' models is that the edges appear independently. While this makes them amenable to a rigorous analysis, it is desirable, both mathematically and in terms of applications, to understand more complicated situations. In this thesis the main goal is to improve our rigorous understanding of evolving random graphs with significant dependencies. The first model we consider is known as an Achlioptas process: in each step two random edges are chosen, and using a given rule only one of them is selected and added to the evolving graph. Since 2000 a large class of 'complex' rules has eluded a rigorous analysis, and it was widely believed that these could give rise to a striking and unusual phenomenon. Making this explicit, Achlioptas, D'Souza and Spencer conjectured in Science that one such rule yields a very abrupt (discontinuous) percolation phase transition. We disprove this, showing that the transition is in fact continuous for all Achlioptas process. In addition, we give the first rigorous analysis of the more 'complex' rules, proving that certain key statistics are tightly concentrated (i) in the subcritical evolution, and (ii) also later on if an associated system of differential equations has a unique solution. The second model we study is the H-free process, where random edges are added subject to the constraint that they do not complete a copy of some fixed graph H. The most important open question for such 'constrained' processes is due to Erdös, Suen and Winkler: in 1995 they asked what the typical final number of edges is. While Osthus and Taraz answered this in 2000 up to logarithmic factors for a large class of graphs H, more precise bounds are only known for a few special graphs. We close this gap for the cases where a cycle of fixed length is forbidden, determining the final number of edges up to constants. Our result not only establishes several conjectures, it is also the first which answers the more than 15-year old question of Erdös et. al. for a class of forbidden graphs H.
46
Rasnick, Rebecca. "Generalizations of the Arcsine Distribution". Digital Commons @ East Tennessee State University, 2019. https://dc.etsu.edu/etd/3565.
Pełny tekst źródłaStreszczenie:
The arcsine distribution looks at the fraction of time one player is winning in a fair coin toss game and has been studied for over a hundred years. There has been little further work on how the distribution changes when the coin tosses are not fair or when a player has already won the initial coin tosses or, equivalently, starts with a lead. This thesis will first cover a proof of the arcsine distribution. Then, we explore how the distribution changes when the coin the is unfair. Finally, we will explore the distribution when one person has won the first few flips.
47
Ekiz, Funda. "Cagan Type Rational Expectations Model on Time Scales with Their Applications to Economics". TopSCHOLAR®, 2011. http://digitalcommons.wku.edu/theses/1126.
Pełny tekst źródłaStreszczenie:
Rational expectations provide people or economic agents making future decision with available information and past experiences. The first approach to the idea of rational expectations was given approximately fifty years ago by John F. Muth. Many models in economics have been studied using the rational expectations idea. The most familiar one among them is the rational expectations version of the Cagans hyperination model where the expectation for tomorrow is formed using all the information available today. This model was reinterpreted by Thomas J. Sargent and Neil Wallace in 1973. After that time, many solution techniques were suggested to solve the Cagan type rational expectations (CTRE) model. Some economists such as Muth [13], Taylor [26] and Shiller [27] consider the solutions admitting an infinite moving-average representation. Blanchard and Kahn [28] find solutions by using a recursive procedure. A general characterization of the solution was obtained using the martingale approach by Broze, Gourieroux and Szafarz in [22], [23]. We choose to study martingale solution of CTRE model. This thesis is comprised of five chapters where the main aim is to study the CTRE model on isolated time scales.
Most of the models studied in economics are continuous or discrete. Discrete models are more preferable by economists since they give more meaningful and accurate results. Discrete models only contain uniform time domains. Time scale calculus enables us to study on m-periodic time domains as well as non periodic time domains. In the first chapter, we give basics of time scales calculus and stochastic calculus. The second chapter is the brief introduction to rational expectations and the CTRE model. Moreover, many other solution techniques are examined in this chapter. After we introduce the necessary background, in the third chapter we construct the CTRE Model on isolated time scales. Then we give the general solution of this model in terms of martingales. We continue our work with defining the linear system and higher order CTRE on isolated time scales. We use Putzer Algorithm to solve the system of the CTRE Model. Then, we examine the existence and uniqueness of the solution of the CTRE model. In the fourth chapter, we apply our solution algorithm developed in the previous chapter to models in Finance and stochastic growth models in Economics.
48
Mohan, Rathish. "Algorithmic Optimization of Sensor Placement on Civil Structures for Fault Detection and Isolation". University of Cincinnati / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1353156107.
Pełny tekst źródła
49
Sadeghi, Kayvan. "Graphical representation of independence structures". Thesis, University of Oxford, 2012. http://ora.ox.ac.uk/objects/uuid:86ff6155-a6b9-48f9-9dac-1ab791748072.
Pełny tekst źródłaStreszczenie:
In this thesis we describe subclasses of a class of graphs with three types of edges, called loopless mixed graphs (LMGs). The class of LMGs contains almost all known classes of graphs used in the literature of graphical Markov models. We focus in particular on the subclass of ribbonless graphs (RGs), which as special cases include undirected graphs, bidirected graphs, and directed acyclic graphs, as well as ancestral graphs and summary graphs. We define a unifying interpretation of independence structure for LMGs and pairwise and global Markov properties for RGs, discuss their maximality, and, in particular, prove the equivalence of pairwise and global Markov properties for graphoids defined over the nodes of RGs. Three subclasses of LMGs (MC, summary, and ancestral graphs) capture the modified independence model after marginalisation over unobserved variables and conditioning on selection variables of variables satisfying independence restrictions represented by a directed acyclic graph (DAG). We derive algorithms to generate these graphs from a given DAG or from a graph of a specific subclass, and we study the relationships between these classes of graphs. Finally, a manual and codes are provided that explain methods and functions in R for implementing and generating various graphs studied in this thesis.
50
Kelley, Logan. "The Quantum Dialectic". Scholarship @ Claremont, 2011. http://scholarship.claremont.edu/pitzer_theses/4.
Pełny tekst źródłaStreszczenie:
A philosophic account of quantum physics. The thesis is divided into two parts. Part I is dedicated to laying the groundwork of quantum physics, and explaining some of the primary difficulties. Subjects of interest will include the principle of locality, the quantum uncertainty principle, and Einstein's criterion for reality. Quantum dilemmas discussed include the double-slit experiment, observations of spin and polarization, EPR, and Bell's theorem. The first part will argue that mathematical-physical descriptions of the world fall short of explaining the experimental observations of quantum phenomenon. The problem, as will be argued, is framework of the physical descriptive schema. Part I includes in-depth discussions of mathematical principles. Part II will discuss the Copenhagen interpretation as put forth by its founders. The Copenhagen interpretation will be expressed as a paradox: The classical physical language cannot describe quantum phenomenon completely and with certainty, yet this language is the only possible method of articulating the physical world. The paradox of Copenhagen will segway into Kant's critique of metaphysics. Kant's understanding of causality, things-in-themselves, and a priori synthetic metaphysics. The thesis will end with a conclusion of the quantum paradox by juxtaposing anti-materialist Martin Heidegger with quantum founder Werner Heisenberg. Our conclusion will be primarily a discussion of how we understand the world, and specifically how our understanding of the world creates potential for truth.