71 |
Computing the Gromov hyperbolicity constant of a discrete metric spaceIsmail, Anas 07 1900 (has links)
Although it was invented by Mikhail Gromov, in 1987, to describe some family of groups[1], the notion of Gromov hyperbolicity has many applications and interpretations in different fields. It has applications in Biology, Networking, Graph Theory, and many other areas of research. The Gromov hyperbolicity constant of several families of graphs and geometric spaces has been determined. However, so far, the only known algorithm for calculating the Gromov hyperbolicity constant δ of a discrete metric space is the brute force algorithm with running time O (n4) using the four-point condition. In this thesis, we first introduce an approximation algorithm which calculates a O (log n)-approximation of the hyperbolicity constant δ, based on a layering approach, in time O(n2), where n is the number of points in the metric space. We also calculate the fixed base point hyperbolicity constant δr for a fixed point r using a (max, min)−matrix multiplication algorithm by Duan in time O(n2.688)[2]. We use this result to present a 2-approximation algorithm for calculating the hyper-bolicity constant in time O(n2.688). We also provide an exact algorithm to compute the hyperbolicity constant δ in time O(n3.688) for a discrete metric space. We then present some partial results we obtained for designing some approximation algorithms to compute the hyperbolicity constant δ.
|
72 |
The Topswop ForestDesheng, Zhang January 2021 (has links)
In this thesis, we will define the topswop forest and study the properties of the forest. We will show the number of trees and leaves in the forest. We will also do an experiment to show there is more than an exponential growth between the number of nodes of each tree and the number of elements in the permutation. The experiment also shows that the tallest tree doesn’t always contain the identity permutation. In the later section, we derive a linear lower bound for the topswop problem by studying a specific family of permutation.
|
73 |
A Learning Model for Discrete MathematicsWallace, Christopher 01 December 2008 (has links)
In this paper we introduce a new model which we apply to Discrete Mathematics, but could be applied to other courses as well. The model uses homework, lectures and quizzes. The key factor and design is centered on the quizzes which are given daily. We also discuss how lectures and homework question sessions can be shortened slightly to allow for twenty-five minute quizzes without sacrificing content. The model assumes a course which meets two days a week lecture, each of which is ninety minutes with no recitations. A three hour lecture could also be applied to this model.
|
74 |
Free-Form Deformation for Computer-Aided Engineering Analysis and DesignLadner, Amy Lynn 11 August 2007 (has links)
Toward support of the use of geometry in advanced simulation, a freeorm deformation (FFD) tool was designed, developed, and tested using object oriented (OO) techniques. The motivation for creating this FFD tool in-house was to provide engineers and researchers a cost efficient, quick, and easy way to computationally manipulate models without having to start from scratch while readily seeing the resulting geometry. The FFD tool was built using the OO scripting language, Python, the OO GUI toolkit, Qt, and the graphics toolkit, OpenGL. The tool produced robust and intuitive results for two-dimensional shapes especially when multiple point manipulation was utilized. The use of ?grouping? control points also provided the user the ability to maintain certain desired shape features such as straight lines and corners. This in-house FFD tool could be useful to engineers due to the ability to customize source code.
|
75 |
Control of multiplicative discrete-time systemsEl-Bialy, Ahmed Mohamed January 1990 (has links)
No description available.
|
76 |
Design and Evaluation of a Discrete Wavelet Transform Based Multi-Signal ReceiverChiang, Tony 11 July 2006 (has links)
No description available.
|
77 |
Driver Behaviour Clustering Using Discrete PDFs and Modified Markov AlgorithmKartashev, K., Doikin, Aleksandr, Campean, Felician, Uglanov, Alexey, Abdullatif, Amr R.A., Zhang, Q., Angiolini, E. 09 October 2021 (has links)
No / This paper presents a novel approach for probabilistic clustering, motivated
by a real-world problem of modelling driving behaviour. The main aim is
to establish clusters of drivers with similar journey behaviour, based on a large
sample of historic journeys data. The proposed approach is to establish similarity
between driving behaviours by using the Kullback-Leibler and Jensen-Shannon
divergence metrics based on empirical multi-dimensional probability density functions.
A graph-clustering algorithm is proposed based on modifications of the
Markov Cluster algorithm. The paper provides a complete mathematical formulation,
details of the algorithms and their implementation in Python, and case study
validation based on real-world data.
|
78 |
Computational Circle Packing: Geometry and Discrete Analytic Function TheoryOrick, Gerald Lee 01 May 2010 (has links)
Geometric Circle Packings are of interest not only for their aesthetic appeal but also their relation to discrete analytic function theory. This thesis presents new computational methods which enable additional practical applications for circle packing geometry along with providing a new discrete analytic interpretation of the classical Schwarzian derivative and traditional univalence criterion of classical analytic function theory. To this end I present a new method of computing the maximal packing and solving the circle packing layout problem for a simplicial 2-complex along with additional geometric variants and applications. This thesis also presents a geometric discrete Schwarzian quantity whose value is associated with the classical Schwarzian derivative. Following Hille, I present a characterization of circle packings as the ratio of two linearly independent solutions of a discrete difference equation taking the discrete Schwarzian as a parameter. This characterization then gives a discrete interpretation of the classical univalence criterion of Nehari in the circle packing setting.
|
79 |
COMBINATORIAL OPTIMIZATION APPROACHES TO DISCRETE PROBLEMSLIU, MIN JING 10 1900 (has links)
<p>As stressed by the Society for Industrial and Applied Mathematics (SIAM): Applied mathematics, in partnership with computational science, is essential in solving many real-world problems. Combinatorial optimization focuses on problems arising from discrete structures such as graphs and polyhedra. This thesis deals with extremal graphs and strings and focuses on two problems: the Erdos' problem on multiplicities of complete subgraphs and the maximum number of distinct squares in a string.<br />The first part of the thesis deals with strengthening the bounds for the minimum proportion of monochromatic t cliques and t cocliques for all 2-colourings of the edges of the complete graph on n vertices. Denote by k_t(G) the number of cliques of order t in a graph G. Let k_t(n) = min{k_t(G)+k_t(\overline{G})} where \overline{G} denotes the complement of G of order n. Let c_t(n) = {k_t(n)} / {\tbinom{n}{t}} and c_t be the limit of c_t(n) for n going to infinity. A 1962 conjecture of Erdos stating that c_t = 2^{1-\tbinom{t}{2}} was disproved by Thomason in 1989 for all t > 3. Tighter counterexamples have been constructed by Jagger, Stovicek and Thomason in 1996, by Thomason for t < 7 in 1997, and by Franek for t=6 in 2002. We present a computational framework to investigate tighter upper bounds for small t yielding the following improved upper bounds for t=6,7 and 8: c_6 \leq 0.7445 \times 2^{1- \tbinom{6}{2}}, c_7\leq 0.6869\times 2^{1- \tbinom{7}{2}}, and c_8 \leq 0.7002\times 2^{1- \tbinom{8}{2}}. The constructions are based on a large but highly regular variant of Cayley graphs for which the number of cliques and cocliques can be expressed in closed form. Considering the quantity e_t=2^{\tbinom{t}{2}-1} c_t, the new upper bound of 0.687 for e_7 is the first bound for any e_t smaller than the lower bound of 0.695 for e_4 due to Giraud in 1979.<br />The second part of the thesis deals with extremal periodicities in strings: we consider the problem of the maximum number of distinct squares in a string. The importance of considering as key variables both the length n and the size d of the alphabet is stressed. Let (d,n)-string denote a string of length n with exactly d distinct symbols. We investigate the function \sigma_d(n) = max {s(x) | x} where s(x) denotes the number of distinct primitively rooted squares in a (d,n)-string x. We discuss a computational framework for computing \sigma_d(n) based on the notion of density and exploiting the tightness of the available lower bound. The obtained computational results substantiate the hypothesized upper bound of n-d for \sigma_d(n). The structural similarities with the approach used for investigating the Hirsch bound for the diameter of a polytope of dimension d having n facets is underlined. For example, the role played by (d,2d)-polytope was presented in 1967 by Klee and Walkup who showed the equivalency between the Hirsch conjecture and the d-step conjecture.</p> / Doctor of Philosophy (PhD)
|
80 |
Analysis of Discrete Fractional Operators and Discrete Fractional Rheological ModelsUyanik, Meltem 01 May 2015 (has links)
This thesis is comprised of two main parts: Monotonicity results on discrete fractional operators and discrete fractional rheological constitutive equations. In the first part of the thesis, we introduce and prove new monotonicity concepts in discrete fractional calculus. In the remainder, we carry previous results about fractional rheological models to the discrete fractional case. The discrete method is expected to provide a better understanding of the concept than the continuous case as this has been the case in the past. In the first chapter, we give brief information about the main results. In the second chapter, we present some fundamental definitions and formulas in discrete fractional calculus. In the third chapter, we introduce two new monotonicity concepts for nonnegative or nonpositive valued functions defined on discrete domains, and then we prove some monotonicity criteria based on the sign of the fractional difference operator of a function. In the fourth chapter, we emphasize the rheological models: We start by giving a brief introduction to rheological models such as Maxwell and Kelvin-Voigt, and then we construct and solve discrete fractional rheological constitutive equations. Finally, we finish this thesis by describing the conclusion and future work.
|
Page generated in 0.0592 seconds