Department of Mathematical Sciences

Permanent URI for this community

https://scholar.sun.ac.za/handle/10019.1/223

Browse

Now showing 1 - 20 of 533

3 x 3 lemma for star-exact sequences
(INT PRESS BOSTON, INC, 2012) Gran, Marino; Janelidze, Zurab; Rodelo, Diana
ENGLISH ABSTRACT: A regular category is said to be normal when it is pointed and every regular epimorphism in it is a normal epimorphism. Any abelian category is normal, and in a normal category one can deﬁne short exact sequences in a similar way as in an abelian category. Then, the corresponding 3 × 3 lemma is equiv- alent to the so-called subtractivity, which in universal algebra is also known as congruence 0-permutability. In the context of non-pointed regular categories, short exact sequences can be replaced with “exact forks” and then, the corresponding 3 × 3 lemma is equivalent, in the universal algebraic terminology, to congruence 3-permutability; equivalently, regular categories sat- isfying such 3 × 3 lemma are precisely the Goursat categories. We show how these two seemingly independent results can be uniﬁed in the context of star-regular categories recently intro- duced in a joint work of A. Ursini and the ﬁrst two authors.
3D numerical techniques for determining the foot of a continental slope
(Stellenbosch : Stellenbosch University, 2004-12) Pantland, Nicolette Ariana; Van Vuuren, J. H.; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
ENGLISH ABSTRACT: The United Nations Convention on the Law of the Sea (UNCLOS) provides an opportunity for qualifying coastal signatory states to claim extended maritime estate. The opportunity to claim rests on the precept that in certain cases a continental shelf extends beyond the traditionally demarcated two hundred nautical mile (200M) Exclusive Economic Zone (EEZ) mark. In these cases a successful claim results in states having sovereign rights to the living and non-living resources of the seabed and subsoil, as well as the sedentary species, of the area claimed. Where the continental shelf extends beyond the 200M mark, the Foot of the Continental Slope (FoS) has to be determined as one of the qualifying criteria. Article 76 of UNCLOS de nes the FoS as ". . . the point of maximum change in the gradient at its base." Currently Caris Lots is the most widely used software which incorporates public domain data to determine the FoS as a step towards defining the offshore extent of an extended continental shelf. In this software, existing methods to compute the FoS are often subjective, typically involving an operator choosing the best perceived foot point during consideration of a two dimensional profile of the continental slope. These foot points are then joined by straight lines to form the foot line to be used in the desk top study (feasibility study). The purpose of this thesis is to establish a semi-automated and mathematically based three dimensional method for determination of the FoS using South African data as a case study. Firstly, a general background of UNCLOS is given (with emphasis on Article 76), including a brief discussion of the geological factors that influence the characteristics of a continental shelf and thus factors that could influence the determination of the FoS. Secondly, a mathematical method for determination of the surfaces of extremal curvature (on three dimensional data), originally proposed by Vanicek and Ou in 1994, is detailed and applied to two smooth, hypothetical sample surfaces. A discussion of the bathymetric data to be used for application introduces the factors to be taken into account when using extensive survey data as well as methods to process the raw data for use. The method is then applied to two sets of gridded bathymetric data of differing resolution for four separate regions around the South African coast. The ridges formed on the resulting surfaces of maximum curvature are then traced in order to obtain a foot line definition for each region and each resolution. The results obtained from application of the method are compared with example foot points provided by the subjective two dimensional method of computation within the Caris Lots software suite. A comparison of the results for the different resolutions of data is included to provide insight as to the effectiveness of the method with differing spatial coarseness of data. Finally, an indication of further work is provided in the conclusion to this thesis, in the form of a number of recommendations for possible adaptations of the mathematical and tracing methods, and improvements thereof.
3D position estimation of sports players through multi-view tracking
(Stellenbosch : University of Stellenbosch, 2010-12) Vos, Robert (Robbie); Brink, Willie; Herbst, Ben; University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences.
ENGLISH ABSTRACT: Extracting data from video streams and using the data to better understand the observed world allows many systems to automatically perform tasks that ordinarily needed to be completed by humans. One such problem with a wide range of applications is that of detecting and tracking people in a video sequence. This thesis looks speci cally at the problem of estimating the positions of players on a sports eld, as observed by a multi-view camera setup. Previous attempts at solving the problem are discussed, after which the problem is broken down into three stages: detection, 2D tracking and 3D position estimation. Possible solutions to each of the problems are discussed and compared to one another. Motion detection is found to be a fast and e ective solution to the problem of detecting players in a single view. Tracking players in 2D image coordinates is performed by implementing a hierarchical approach to the particle lter. The hierarchical approach is chosen as it improves the computational complexity without compromising on accuracy. Finally 3D position estimation is done by multiview, forward projection triangulation. The components are combined to form a full system that is able to nd and locate players on a sports eld. The overall system that is developed is able to detect, track and triangulate player positions. The components are tested individually and found to perform well. By combining the components and introducing feedback between them the results of the individual components as well as those of the overall system are improved.
A 3D Virtual Environment Development Platform for ASD Therapy Tools
(Stellenbosch : University of Stellenbosch, 2009-12) Chamberlain, Morne Edward; Van Zijl, L.; University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. Computer Science.
ENGLISH ABSTRACT: The aim of this thesis is to develop a generic 3D virtual environment development platform for autism spectrum disorder (ASD) therapy tools. The potential of using computerised therapy tools for ASD therapy is well known. However, the development of such tools is expensive and time-consuming, and is language and culture speci c. This work intends to alleviate these problems. The design of the platform is based on known game engine designs, but adapted for the requirements of ASD therapy tools. It supports standard features such as 3D rendering, animation and audio output. Speci c features, aimed at ASD therapy tools and educational games, included in our engine are: replays, data capturing, remote monitoring over a network and language localisation. We also implemented an input hardware abstraction layer to allow support for non-standard input peripherals in the future, without modifying existing game implementations. Furthermore, to separate the development of games and tools from the engine, we include wrapper libraries in our engine for Lua and Java. We successfully developed our engine and implemented a number of prototype therapy tools and educational games. These implementations confirmed that the engine works as expected. Some of these programs are currently in use at a local primary school.
An adaptive feature-based tracking system
(Stellenbosch : University of Stellenbosch, 2008-03) Pretorius, Eugene; Herbst, B. M.; Hunter, K. M.; University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. Applied Mathematics.
In this paper, tracking tools are developed based on object features to robustly track the object using particle filtering. Automatic on-line initialisation techniques use motion detection and dynamic background modelling to extract features of moving objects. Automatically adapting the feature models during tracking is implemented and tested.
Adaptive occupancy grid mapping with measurement and pose uncertainty
(Stellenbosch : Stellenbosch University, 2012-12) Joubert, Daniek; Herbst, B. M.; Brink, Willie; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
ENGLISH ABSTRACT: In this thesis we consider the problem of building a dense and consistent map of a mobile robot’s environment that is updated as the robot moves. Such maps are vital for safe and collision-free navigation. Measurements obtained from a range sensor mounted on the robot provide information on the structure of the environment, but are typically corrupted by noise. These measurements are also relative to the robot’s unknown pose (location and orientation) and, in order to combine them into a world-centric map, pose estimation is necessary at every time step. A SLAM system can be used for this task. However, since landmark measurements and robot motion are inherently noisy, the pose estimates are typically characterized by uncertainty. When building a map it is essential to deal with the uncertainties in range measurements and pose estimates in a principled manner to avoid overconfidence in the map. A literature review of robotic mapping algorithms reveals that the occupancy grid mapping algorithm is well suited for our goal. This algorithm divides the area to be mapped into a regular lattice of cells (squares for 2D maps or cubes for 3D maps) and maintains an occupancy probability for each cell. Although an inverse sensor model is often employed to incorporate measurement uncertainty into such a map, many authors merely state or depict their sensor models. We derive our model analytically and discuss ways to tailor it for sensor-specific uncertainty. One of the shortcomings of the original occupancy grid algorithm is its inability to convey uncertainty in the robot’s pose to the map. We address this problem by altering the occupancy grid update equation to include weighted samples from the pose uncertainty distribution (provided by the SLAM system). The occupancy grid algorithm has been criticized for its high memory requirements. Techniques have been proposed to represent the map as a region tree, allowing cells to have different sizes depending on the information received for them. Such an approach necessitates a set of rules for determining when a cell should be split (for higher resolution in a local region) and when groups of cells should be merged (for lower resolution). We identify some inconsistencies that can arise from existing rules, and adapt those rules so that such errors are avoided. We test our proposed adaptive occupancy grid algorithm, that incorporates both measurement and pose uncertainty, on simulated and real-world data. The results indicate that these uncertainties are included effectively, to provide a more informative map, without a loss in accuracy. Furthermore, our adaptive maps need far fewer cells than their regular counterparts, and our new set of rules for deciding when to split or merge cells significantly improves the ability of the adaptive grid map to mimic its regular counterpart.
An age structured model for substance abuse dynamics in the Western Cape Province of South Africa
(Stellenbosch : Stellenbosch University, 2017-03) Chinake, Filister; Nyabadza, Farai; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
ENGLISH SUMMARY: The substance abuse problem has escalated in the Western Cape province of South Africa. This has resulted in high rates of gangsterism and other prob- lems associated with substance abuse. The problem has evolved as gangsters have aggressively extended their turf by recruiting school learners to sell drugs within school premises. The e ect is that more age groups are being recruited into abusing substance. In order to reverse the current trends of substance abuse it is imperative that the dynamics of the problem are fully understood. More insight can be gained if age structure was incorporated into the substance abuse models as the processes like initiation, escalation into problematic sub- stance abuse and quitting are in uenced by age. Thus we propose an age structured model of substance abuse. A form of the reproduction number R0 is calculated and the model is shown to be well posed. A suitable nite di er- ence scheme is discussed for the numerical solution of our partial di erential equations. Sensitivity analysis is undertaken using the Latin Hypercube Sam- pling and Partial Rank Correlation Coe cient. Parameters for the model are obtained by tting the model to the age structured data for individuals in the rehabilitation centres. The dynamics of the model are described by the results from the numerical simulations. The model is used to predict the dynamics of substance abuse until the year 2020. Substance abuse is predicted to increase with time and higher incidence of substance abuse expected for the older age groups.
An algebraic framework for reasoning about privacy
(Stellenbosch : University of Stellenbosch, 2016-03) Rajaona, Solofomampionona Forunat; Sanders, J. W.; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Mathematics.
ENGLISH ABSTRACT: In this thesis, we study a formal programming language and algebraic tech-niques to analyse computational systems that considers data confidentiality and hidden computations. The reasoning techniques are based on the refinement of programs (Back and von Wright, Carroll Morgan). The underlying logic is a first-order S 5 n epistemic logic that distinguish b etween o bjects and concepts – of the family of Melvin Fitting’s First Order Intensional Logic. We give a relational semantics and a weakest-precondition semantics to prove the soundness of programming laws. The laws for confidentiality r efinement ex-tends those of Carroll Morgan’s Shadow Knows refinement c alculus, whereas the laws for reasoning about knowledge derives mostly from the Public An-nouncement Logic. As applications for knowledge dynamics, we study the classical puzzles of the Three Wise Men and the Muddy Children by means of the programming laws; and as an application for reasoning about confiden-tiality and anonymity, we give a sketch of formal analysis of the Anonymous Cocaine Auction Protocol.
An algebraic framework for reasoning about security
(Stellenbosch : Stellenbosch University, 2013-03) Rajaona, Solofomampionona Fortunat; Sanders, J. W.; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
ENGLISH ABSTRACT: Stepwise development of a program using refinement ensures that the program correctly implements its requirements. The specification of a system is “refined” incrementally to derive an implementable program. The programming space includes both specifications and implementable code, and is ordered with the refinement relation which obeys some mathematical laws. Morgan proposed a modification of this “classical” refinement for systems where the confidentiality of some information is critical. Programs distinguish between “hidden” and “visible” variables and refinement has to bear some security requirement. First, we review refinement for classical programs and present Morgan’s approach for ignorance pre- serving refinement. We introduce the Shadow Semantics, a programming model that captures essential properties of classical refinement while preserving the ignorance of hidden variables. The model invalidates some classical laws which do not preserve security while it satisfies new laws. Our approach will be algebraic, we propose algebraic laws to describe the properties of ignorance preserving refinement. Thus completing the laws proposed in. Moreover, we show that the laws are sound in the Shadow Semantics. Finally, following the approach of Hoare and He for classical programs, we give a completeness result for the program algebra of ignorance preserving refinement.
Algebraic points in tame expansions of fields
(Stellenbosch : Stellenbosch University, 2021-12) Harrison-Migochi, Andrew; Boxall, Gareth John; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
ENGLISH ABSTRACT: We investigate the behaviour of algebraic points in several expansions of the real, complex and p-adic fields. We build off the work of Eleftheriou, Günaydin and Hieronymi in [17] and [18] to prove a Pila-Wilkie result for a p-adic subanalytic structure with a predicate for either a dense elementary substructure or a dense dcl-independent set. In the process we prove a structure theorem for p-minimal structures with a predicate for a dense independent set. We then prove quantifier reduction results for the complex field with a predicate for the singular moduli and the real field with an exponentially transcendental power function and a predicate for the algebraic numbers using a Schanuel property proved by Bays, Kirby and Wilkie [5]. Finally we adapt a theorem by Ax [2] about exponential fields, key to the proof of the Schanuel property for power functions, to power functions.
American Monte Carlo option pricing under pure jump levy models
(Stellenbosch : Stellenbosch University, 2013-03) West, Lydia; Ouwehand, P. W.; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
ENGLISH ABSTRACT: We study Monte Carlo methods for pricing American options where the stock price dynamics follow exponential pure jump L évy models. Only stock price dynamics for a single underlying are considered. The thesis begins with a general introduction to American Monte Carlo methods. We then consider two classes of these methods. The fi rst class involves regression - we briefly consider the regression method of Tsitsiklis and Van Roy [2001] and analyse in detail the least squares Monte Carlo method of Longsta and Schwartz [2001]. The variance reduction techniques of Rasmussen [2005] applicable to the least squares Monte Carlo method, are also considered. The stochastic mesh method of Broadie and Glasserman [2004] falls into the second class we study. Furthermore, we consider the dual method, independently studied by Andersen and Broadie [2004], Rogers [2002] and Haugh and Kogan [March 2004] which generates a high bias estimate from a stopping rule. The rules we consider are estimates of the boundary between the continuation and exercise regions of the option. We analyse in detail how to obtain such an estimate in the least squares Monte Carlo and stochastic mesh methods. These models are implemented using both a pseudo-random number generator, and the preferred choice of a quasi-random number generator with bridge sampling. As a base case, these methods are implemented where the stock price process follows geometric Brownian motion. However the focus of the thesis is to implement the Monte Carlo methods for two pure jump L évy models, namely the variance gamma and the normal inverse Gaussian models. We first provide a broad discussion on some of the properties of L évy processes, followed by a study of the variance gamma model of Madan et al. [1998] and the normal inverse Gaussian model of Barndor -Nielsen [1995]. We also provide an implementation of a variation of the calibration procedure of Cont and Tankov [2004b] for these models. We conclude with an analysis of results obtained from pricing American options using these models.
An analogue of the Andre-Oort conjecture for products of Drinfeld modular surfaces
(Stellenbosch : Stellenbosch University, 2013-03) Karumbidza, Archie; Breuer, Florian; Keet, A. P.; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
ENGLISH ABSTRACT: This thesis deals with a function eld analog of the André-Oort conjecture. The (classical) André-Oort conjecture concerns the distribution of special points on Shimura varieties. In our case we consider the André-Oort conjecture for special points in the product of Drinfeld modular varieties. We in particular manage to prove the André- Oort conjecture for subvarieties in a product of two Drinfeld modular surfaces under a characteristic assumption.
Analysing ranking algorithms and publication trends on scholarly citation networks
(Stellenbosch : Stellenbosch University, 2014-12) Dunaiski, Marcel Paul; Visser, Willem; Geldenhuys, Jaco; Stellenbosch University. Faculty of Science. Department of Mathematical Sciences.
ENGLISH ABSTRACT: Citation analysis is an important tool in the academic community. It can aid universities, funding bodies, and individual researchers to evaluate scientific work and direct resources appropriately. With the rapid growth of the scientific enterprise and the increase of online libraries that include citation analysis tools, the need for a systematic evaluation of these tools becomes more important. The research presented in this study deals with scientific research output, i.e., articles and citations, and how they can be used in bibliometrics to measure academic success. More specifically, this research analyses algorithms that rank academic entities such as articles, authors and journals to address the question of how well these algorithms can identify important and high-impact entities. A consistent mathematical formulation is developed on the basis of a categorisation of bibliometric measures such as the h-index, the Impact Factor for journals, and ranking algorithms based on Google’s PageRank. Furthermore, the theoretical properties of each algorithm are laid out. The ranking algorithms and bibliometric methods are computed on the Microsoft Academic Search citation database which contains 40 million papers and over 260 million citations that span across multiple academic disciplines. We evaluate the ranking algorithms by using a large test data set of papers and authors that won renowned prizes at numerous Computer Science conferences. The results show that using citation counts is, in general, the best ranking metric. However, for certain tasks, such as ranking important papers or identifying high-impact authors, algorithms based on PageRank perform better. As a secondary outcome of this research, publication trends across academic disciplines are analysed to show changes in publication behaviour over time and differences in publication patterns between disciplines.
Analysis of partner turnover rate and the lifetime number of sexual partners in Cape Town using generalized linear models
(Stellenbosch : Stellenbosch University, 2017-12) Olojede, Christianah Oyindamola; Delva, Wim; Stellenbosch University. Faculty of Science. Department of Mathematical Sciences.
ENGLISH ABSTRACT :A large number of analyses have been carried out to investigate how sexually active people contracted human immunodeficiency virus (HIV) by using common indicators like the number of new sexual partners in a given year and the lifetime number of partners. In this study, the objective is to show that these are not always good indicators because what people report for these two indicators is not accurate nor consistent using generalized linear models such as Poisson and the negative binomial regression models. Generalized linear models are the types of models that allows for the distribution of the response variable to be non-normal. A cross-sectional, sexual behavioural survey was conducted in communities with a high prevalence of HIV in Cape Town, South Africa, in 2011 – 2012. We examined the effects of age and gender on the rate at which sexual partnerships are formed, using count data regression models. The age range of respondents was 16-40 years. The highest number of new sexual relationships formed in a year preceding the survey was 11 and the highest lifetime number of sexual partners was 15. A generalized linear regression model was used to examine the consistency between the reported number of new sexual partners formed in a year preceding the survey and the reported lifetime number of partners. We also assessed the predictive power of these two indicators for the respondent’s HIV status. We found that these indicators are not consistent, and we conclude that they are not good indicators for predicting HIV status.
An analysis of security protocols for lightweight systems
(Stellenbosch : Stellenbosch University, 2022-04) Kamkuemah, Martha Ndeyapeuomagano; Sanders, Jeff; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.
ENGLISH SUMMARY: Security is hard to maintain in distributed systems especially for communicating agents restricted to lightweight computations, as in the Internet of Things, which struggle to implement strong cryptographic security. A methodology is developed for specifying and reasoning algebraically about security in such systems which combines epistemic logic and a state-based formalism. The knowledge modality K is used to define a uthentication a nd s ecrecy i n t erms o f w hat e ach agent knows. Operations are defined a s s tate t ransitions. Having g ained c onfidence in our methodology by applying it to the benchmark case studies Needham-Schroeder and Diffie-Hellman protocols, we then apply it to the contemporary examples Signal and Long-Range Wide-Area Network protocols. A mitigation is proposed and verified for a Long-Range Wide-Area Network.
Analysis of the effects of growth-fragmentation-coagulation in phytoplankton dynamics
(Stellenbosch : Stellenbosch University, 2011-12) Omari, Mohamed; Banasiak, Jacek; Rewitzky, Ingrid; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Mathematics Division.
ENGLISH ABSTRACT: An integro-differential equation describing the dynamical behaviour of phytoplankton cells is considered in which the effects of cell division and aggregation are incorporated by coupling the coagulation-fragmentation equation with growth, and the McKendrick-von Foerster renewal model of an age-structured population. Under appropriate conditions on the model parameters, the associated initial-boundary value problem is shown to be well posed in a physically relevant Banach space using the theory of strongly continuous semigroups of operators, the theory of perturbation of positive semigroups and the semilinear abstract Cauchy problems theory. In particular, we provide sufficient conditions for honesty of the model. Finally, the results on the effects of the growth-fragmentation-coagulation on the overall evolution of the phytoplankton population are summarised.
Analysis of the rolling motion of loaded hoops
(Stellenbosch : University of Stellenbosch, 2008-03) Theron, Willem F. D.; Maritz, M. F.; University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. Applied Mathematics.
This dissertation contains a detailed report on the results of a research project on the behaviour of a dynamical system consisting of a hoop to which a heavy particle is fixed at the rim. This loaded hoop rolls on a rough surface while remaining in the vertical plane. The motion of the hoop consists of various, possibly alternating, phases consisting of rolling without slipping, spinning or skidding motion and in some cases ends by hopping off the surface. A general mathematical model is developed, consisting of a system of second order ordinary differential equations, one for each of the three degrees of freedom. Analytic solutions are obtained in some cases; otherwise numerical solutions are used. Three specific applications of the general model are dealt with. In the first application the problem of massless hoops is investigated. The main emphasis is on the somewhat controversial question of what happens after the normal reaction becomes zero in a position where the particle is still moving downwards. A new result shows that the hoop can continue to move horizontally in a motion defined as skimming. The second application deals with rigid hoops and a large number of detailed results are presented. Classification schemes for the different types of behaviour are introduced and summarised in the form of phase diagrams. Some emphasis is placed on the rather amazing number of different patterns of motion that can be obtained by varying the parameters. In the third application two elastic models are analysed, with the primary purpose of explaining one aspect of the reported behaviour of experimental hoops, namely hopping while the particle is moving downwards. A chapter on experimental models rounds off the project.
Analysis of tree spectra
(Stellenbosch : Stellenbosch University, 2018-12) Dadedzi, Kenneth; Wagner, Stephan; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Mathematics.
ENGLISH ABSTRACT : We study the set of eigenvalues (spectrum) of the adjacency matrix, Laplacian matrix and the distance matrix of trees. In particular, we focus on the distribution of eigenvalues in the spectra of large random trees. The families of random trees considered in this work are simply generated trees and increasing trees. We prove that attaching several copies (two or more) of a tree H to vertices in a tree T “forces" certain real numbers into the adjacency, Laplacian or distance spectrum of the resulting tree. With this construction of forcing subtrees, we prove that the mean proportion of an eigenvalue α in the spectrum of a large random tree is at least the mean number of occurrences of a specific forcing subtree in the large random tree. This gives us explicit lower bounds on the asymptotic mean multiplicity of eigenvalues for different families of random trees. We prove that the mean proportion of an eigenvalue α in the spectrum of the adjacency matrix and Laplacian matrix of a large simply generated tree can be obtained by solving a system of functional equations. We provide an algorithm to solve this system numerically for a given eigenvalue. For instance, using this algorithm, we show that on average approximately 1.4%, 2.1%, 2.5% and 3.3% of the spectrum of a large pruned binary tree, labelled rooted tree, plane tree and pruned ternary tree respectively consist of the eigenvalue 1. Further, we provide explicit formulas for computing the mean proportion of the eigenvalue 0 in the spectrum of a large simply generated tree. We also study the spectra of recursive trees and binary increasing trees. We show that the distribution of the eigenvalue 0 (and other eigenvalues) in these random trees satisfies a central limit theorem. We also compute the mean and variance of the multiplicity of the eigenvalue 0 in the spectrum of a large recursive tree and binary increasing tree. The final chapter deals with related, but somewhat different questions. Given a rooted tree T with leaves v1, v2, . . . , vn, we define the ancestral matrix C(T) of T to be the n × n matrix for which the entry in the i-th row, j-th column is the level (distance from the root) of the first common ancestor of vi and vj . We study properties of this matrix, in particular regarding its spectrum: we obtain several upper and lower bounds for the eigenvalues in terms of other tree parameters. We also find a combinatorial interpretation for the coefficients of the characteristic polynomial of C(T), and show that for dary trees, a specific value of the characteristic polynomial is independent of the precise shape of the tree.
Analytic methods in combinatorial number theory
(Stellenbosch : Stellenbosch University, 2015-12) Baker, Liam Bradwin; Wagner, Stephan; Stellenbosch University. Faculty of Science. Department Mathematical Sciences (Mathematics)
ENGLISH ABSTRACT : Two applications of analytic techniques to combinatorial problems with number-theoretic flavours are shown. The first is an application of the real saddle point method to derive second-order asymptotic expansions for the number of solutions to the signum equation of a general class of sequences. The second is an application of more elementary methods to yield asymptotic expansions for the number of partitions of a large integer into powers of an integer b where each part has bounded multiplicity.
Analytic models of TCP performance
(Stellenbosch : University of Stellenbosch, 2011-10) Kassa, Debassey Fesehaye; Krzesinski, A. E.; University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. Institute for Applied Computer Science.
ENGLISH ABSTRACT: The majority of tra c on the Internet uses the Transmission Control Protocol (TCP) as a transport layer protocol for the end-to-end control of information transfer. Measurement, simulation and analytical models are the techniques and tools that can be used to understand and investigate the Internet and its performance. Measurements can only be used to explore existing network scenario or otherwise become costly and in exible with the growth and complexity of the Internet. Simulation models do not scale with the growth of network capacities and the number of users. Computationally e cient analytical models are therefore important tools for investigating, designing, dimensioning and planning IP (Internet Protocol) networks. Existing analytical models of TCP performance are either too simple to capture the internal dynamics of TCP or are too complex to be used to analyze realistic network topologies with several bottleneck links. The literature shows that the xed point algorithm (FPA) is a very useful way of solving analytical models of Internet performance. This thesis presents fast and accurate analytical models of TCP performance with the FPA used to solve them. Apart from what is observed in experimental literature, no comprehensive proof of the convergence and uniqueness of the FPA is given. In this thesis we show how the FPA of analytical models of reliable Internet protocols such as TCP converges to a unique xed point. The thesis speci es the conditions necessary in order to use the FPA for solving analytical models of reliable Internet protocols. We also develop a general implementation algorithm of the FPA of analytical models of TCP performance for realistic and arbitrary network topologies involving heterogenous TCP connections crossing many bottleneck links. The models presented in this thesis give Internet performance metrics, assuming that only basic network parameters such as the network topology, the number of TCP connections, link capacity, distance between network nodes and router bu er sizes are known. To obtain the performance metrics, TCP and network sub{models are used. A closed network of :=G=1 queues is used to develop each TCP sub-model where each queue represents a state of a TCP connection. An M=M=1=K queue is used for each network sub{model which represents the output interface of an IP router with a bu er capacity of K 􀀀��1 packets. The two sub-models are iteratively solved. We also give closed form expressions for important TCP performance values and distributions. We show how the geometric, bounded geometric and truncated geometric distributions can be used to model reliable protocols such as TCP. We give models of the congestion window cwnd size distribution by conditioning on the slow start threshold ssthresh distribution and vice-versa. We also present models of the probabilities of TCP timeout and triple duplicate ACK receptions. Numerical results based on comparisons against ns2 simulations show that our models are more accurate, simpler and computationally more e cient than another well known TCP model. Our models can therefore be used to rapidly analyze network topologies with several bottlenecks and obtain detailed performance metrics.

Browse

Browsing Department of Mathematical Sciences by Title

Results Per Page

Sort Options