Thesis (MSc) -- University of Stellenbosch, 2000. / ENGLISH ABSTRACT: A discrete dynamical system is a pair (X, cf;) comprising a non-empty set X and a map cf; : X ---+ X. A study is made of the effect of repeated application of cf; on X, whereby points and subsets of X are classified according to their behaviour under iteration. These subsets include the JULIA and FATOU sets of the map and the sets of periodic and preperiodic points, and many interesting questions arise in the study of their properties. Such questions have been extensively studied in the case of complex dynamics, but much recent work has focussed on non-archimedean dynamical systems, when X is projective space over some field equipped with a non-archimedean metric. This work has uncovered many parallels to complex dynamics alongside more striking differences. In this thesis, various aspects of the theory of non-archimedean dynamics are presented, with particular reference to JULIA and FATOU sets and the relationship between good reduction of a map and the empty JULIA set. We also discuss questions of the finiteness of the sets of periodic points in special contexts. / AFRIKAANSE OPSOMMING: 'n Paar (X, <jJ) bestaande uit 'n nie-leë versameling X tesame met 'n afbeelding <jJ: X -+ X vorm 'n diskrete dinamiese sisteem. In die bestudering van so 'n sisteem lê die klem op die uitwerking op elemente van X van herhaalde toepassing van <jJ op die versameling. Elemente en subversamelings van X word geklasifiseer volgens dinamiese kriteria en op hierdie wyse ontstaan die JULIA en FATOU versamelings van die afbeelding en die versamelings van periodiese en preperiodiese punte. Interessante vrae oor die eienskappe van hierdie versamelings kom na vore. In die geval van komplekse dinamika is sulke vrae reeds deeglik bestudeer, maar onlangse werk is op nie-archimediese dinamiese sisteme gedoen, waar X 'n projektiewe ruimte is oor 'n liggaam wat met 'n nie-archimediese norm toegerus is. Hierdie werk het baie ooreenkomste maar ook treffende verskille met die komplekse dinamika uitgewys. In hierdie tesis word daar ondersoek oor verskeie aspekte van die teorie van nie-archimediese dinamika ingestel, in besonder met betrekking tot die JULIA en FATOU versamelings en die verband tussen goeie reduksie van 'n afbeelding en die leë JULIA versameling. Vrae oor die eindigheid van versamelings van periodiese punte in spesiale kontekste word ook aangebied.

Thesis (MSc)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: Subdivision is an important and e cient tool for rendering smooth curves and surfaces in computer graphics, by repeatedly applying a subdivision (re ning) scheme to a given set of points. In the literature, attention has been mostly restricted to developing binary subdivision schemes. The primary emphasis of this thesis is on ternary subdivision, and in particular on the interpolatory case. We will derive a symmetric ternary interpolatory subdivision scheme for the rendering of curves, satisfying analogous properties to the Dubuc-Deslauriers binary scheme. Explicit construction methods, as well as a corresponding convergence analysis, will be presented. Graphical illustrations of the results will also be provided. / AFRIKAANSE OPSOMMING: Subdivisie bied 'n belangrike en doeltre ende metode om gladde krommes en oppervlakke in rekenaargra ka te genereer. Hierdie metode behels dat 'n subdivisieskema (of verfyningskema) herhaaldelik toegepas word op 'n gegewe versameling punte. In die literatuur word daar hoofsaaklik gefokus op die ont- wikkeling van bin^ere subdivisieskemas. In hierdie tesis word die klem gel^e op tern^ere subdivisieskemas, en in die besonder op interpolerende skemas. Ons sal 'n simmetriese tern^ere interpolerende subdivisieskema, wat analo e eienskappe as di e van die Dubuc-Deslauriers bin^ere skema bevredig, ontwikkel, om krom- mes te lewer. Eksplisiete konstruksiemetodes en ooreenkomstige konvergensie- analise, asook gra ese illustrasies van die resultate, sal getoon word.

Thesis (MSc)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: This thesis explores two key aspects of wireless ad hoc networks. The first aspect concerns the topic of stimulating cooperation between nodes in a wireless ad hoc network. The functionality of a wireless ad hoc network depends entirely on the willingness of nodes to relay messages on behalf of other nodes. Network functionality depends on ensuring cooperation between nodes, so that each node benefits from continued participation in the network. This suggests an important question: how can cooperation among individual nodes be managed to improve overall wireless ad hoc network performance? The second aspect explored in this thesis concerns the concept of optimal resource utilisation. Wireless ad hoc networks are characterised by limited bandwidth and energy resources, which facilitates deployment in situations in which traditional infrastructure based networks are not practical. This suggests another important question: how can the use of the limited energy and bandwidth resources of wireless ad hoc networks be optimised? This research relies on the concept of a credit-based market economy. Nodes in simulated ad hoc networks use credits to pay for the cost of sending their own traffic and earn credits by forwarding traffic on behalf of other nodes. We show that a credit-based market economy approach can be employed to stimulate and regulate cooperation between nodes in a wireless ad hoc network. We show that this approach can be implemented in a simple decentralised manner and that it has several variants depending on which node is considered to be paying for the service, what the price of each service should be and how we route packets around the network using information derived from the credit-based economy. This thesis demonstrates that several variants of a credit-based scheme can be implemented in a packet based simulator and that these variants result in the stable operation of the network and improve the overall performance. The credit-based mechanisms also show significant improvement to network performance in resource constrained conditions and represent an effective means for optimising limited energy and bandwidth resource. The effectiveness of the credit-based mechanisms increases as the load on the networks increases. / AFRIKAANSE OPSOMMING: Hierdie tesis ondersoek twee belangrike aspekte van draadlose ad hoc-netwerke. Die eerste aspek het betrekking op die onderwerp van 'n stimulerende samewerking tussen die nodusse in 'n draadlose ad hoc-netwerk. Dat die network funksioneer hang daarvan af om samewerking tussen die nodusse te verseker sodat elke nodus voordeel put uit voortgesette deelname in die netwerk. Dit dui op 'n belangrike vraag: Hoe kan die samewerking tussen die individuele nodusse bestuur word om die prestasie van 'n draadlose ad hoc-netwerk te verbeter? Die tweede aspek wat in hierdie tesis ondersoek word, behels die konsep van optimale hulpbronbenutting. Draadlose ad hoc-netwerke word gekenmerk deur beperkte bandwydte- en energie-hulpbronne, wat ontplooiing bewerkstellig in situasies waar tradisionele infrastruktuur-gebaseerde netwerke nie practise moontlik is nie. Dit dui op 'n ander belangrike vraag: Hoe kan die gebruik van die beperkte energie- en bandwydte-hulpbronne van draadlose ad hoc-netwerke optimaal bestuur word? Hierdie navorsing berus op die konsep van 'n krediet-gebaseerde markekonomie. Nodusse in gesimuleerde ad hoc-netwerke gebruik krediete om te betaal vir die versending van hul eie verkeer en nodusse verdien krediete deur die verkeer van ander nodusse aan te stuur. Ons wys dat die benadering van 'n krediet-gebaseerde markekonomie gebruik kan word om die samewerking tussen die nodusse in 'n draadlose ad hoc-netwerk te stimuleer en te reguleer. Ons wys dat hierdie benadering geïmplementeer kan word op 'n eenvoudige gedesentraliseerde wyse. Ons ondersoek verskeie variasies van die benadering, na gelang van watter nodus oorweeg word om vir die diens te betaal, wat die prys van elke diens moet wees en hoe inligting afgelei van die krediet-gebaseerde ekonomie gebruik kan word om pakkies in die netwerk te roeteer. Hierdie tesis toon dat verskeie variante van 'n krediet-gebaseerde skema geïmplementeer kan word in 'n netwerksimulator en dat hierdie variante die stabiele bedryf van en algehele verbetering in die prestasie van die network tot gevolg het. Die krediet-gebaseerde meganismes toon 'n beduidende verbetering in hulpbronbenutting en netwerkprestasie in omgewings met beperkte hulpbronne en verteenwoordig 'n doeltreffende manier om die beperkte energie- en bandwydte-hulpbronne optimaal te benut. Laastens, die doeltreffendheid van die krediet-gebaseerde meganismes word verhoog as die las op die netwerke word verhoog.

Thesis(MSc)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: The pricing of plain vanilla options, including early exercise options, such as Bermudan and American options, forms the basis for the calibration of financial models. As such, it is important to be able to price these options quickly and accurately. Empirical studies suggest that asset dynamics have jump components which can be modelled by exponential Lévy processes. As such models often have characteristic functions available in closed form, it is possible to use Fourier transform methods, and particularly, the Fast Fourier Transform, to price such options efficiently. In this dissertation we investigate and implement four such methods, dubbed the Carr- Madan method, the convolution method, the COS method and the Fourier spacetime stepping method. We begin by pricing European options using these Fourier methods in the Black-Scholes, Variance Gamma and Normal Inverse Gaussian models. Thereafter, we investigate the pricing of Bermudan and American options in the Black-Scholes and Variance Gamma models. Throughout, we compare the four Fourier pricing methods for accuracy and computational efficiency. / AFRIKAANSE OPSOMMING: Die prysbepaling van gewone vanilla opsies, insluitende opsies wat vroeg uitgeoefen kan word, soos Bermuda-en Amerikaanse opsies, is grondliggend vir die kalibrering van finansiële modelle. Dit is daarom belangrik dat die pryse van sulke opsies vinnig en akkuraat bepaal kan word. Empiriese studies toon aan dat batebewegings sprongkomponente besit, wat gemodelleer kan word met behulp van exponensiëele Lévyprosesse. Aangesien hierdie modelle dikwels karakteristieke funksies het wat beskikbaar is in geslote vorm, is dit moontlik om Fourier-transform metodes, en in besonders die vinnige Fourier-transform, te gebruik om opsiepryse doeltreffend te bepaal. In hierdie proefskrif ondersoek en implementeer ons vier sulke metodes, genaamd die Carr-Madan metode, die konvolusiemetode, die COS-metode en die Fourier ruimte-tydstap metode. Ons begin deur die pryse van Europese opsies in die Black-Scholes, Gammavariansie (Engels: Variance gamma) en Normaal Invers Gauss (Engels: Normal Inverse Gaussian)-modelle te bepaal met behulp van die vier Fourier-metodes. Daarna ondersoek ons die prysbepaling van Bermuda-en Amerikaanse opsies in die Black-Scholes en Gammavariansiemodelle. Deurlopend vergelyk ons die vier Fourier-metodes vir akkuraatheid en berekeningsdoeltreffendheid.

Thesis (MSc)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: Major works done in Function Field Arithmetic show a strong analogy between the ring of integers Z and the ring of polynomials over a nite eld Fq[T]. While an algorithm has been discovered to factor integers using elliptic curves, the discovery of Drinfeld modules, which are analogous to elliptic curves, made it possible to exhibit an algorithm for factorising polynomials in the ring Fq[T]. In this thesis, we introduce the notion of Drinfeld modules, then we demonstrate the analogy between Drinfeld modules and Elliptic curves. Finally, we present an algorithm for factoring polynomials over a nite eld using Drinfeld modules. / AFRIKAANSE OPSOMMING: 'n Groot deel van die werk wat reeds in funksieliggaam rekenkunde voltooi is toon 'n sterk verband tussen die ring van heelgetalle, Z; en die ring van polinome oor 'n eindige liggaam, F[T]: Terwyl daar alreeds 'n algoritme, wat gebruik maak van elliptiese kurwes, ontwerp is om heelgetalle te faktoriseer, het die ontdekking van Drinfeld modules, wat analoog is aan elliptiese kurwes, dit moontlik gemaak om 'n algoritme te konstrueer om polinome in die ring F[T] te faktoriseer. In hierdie tesis maak ons die konsep van Drinfeld modules bekend deur sekere aspekte daarvan te bestudeer. Ons gaan voort deur 'n voorbeeld te voorsien wat die analoog tussen Drinfeld modules en elliptiese kurwes illustreer. Uiteindelik, deur gebruik te maak van Drinfeld modules, bevestig ons hierdie analoog deur die algoritme vir die faktorisering van polinome oor eindige liggame te veskaf.

Thesis (MSc)--Stellenbosch University, 2013. / 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. / AFRIKAANSE OPSOMMING: Stapsgewyse ontwikkeling van ’n program met behulp van verfyning verseker dat die program voldoen aan die vereistes. Die spesifikasie van ’n stelsel word geleidelik ”verfyn” wat lei tot ’n implementeerbare kode, en word georden met ‘n verfyningsverhouding wat wiskundige wette gehoorsaam. Morgan stel ’n wysiging van hierdie klassieke verfyning voor vir stelsels waar die vertroulikheid van sekere inligting van kritieke belang is. Programme onderskei tussen ”verborgeën ”sigbare” veranderlikes en verfyning voldoen aan ’n paar sekuriteitsvereistes. Eers hersien ons verfyning vir klassieke programme en verduidelik Morgan se benadering tot onwetendheid behoud. Ons verduidelik die ”Shadow Semantics”, ’n programmeringsmodel wat die noodsaaklike eienskappe van klassieke verfyning omskryf terwyl dit die onwetendheid van verborge veranderlikes laat behoue bly. Die model voldoen nie aan n paar klassieke wette, wat nie sekuriteit laat behoue bly nie, en dit voldoen aan nuwe wette. Ons benadering sal algebraïese wees. Ons stel algebraïese wette voor om die eienskappe van onwetendheid behoudende verfyning te beskryf, wat dus die wette voorgestel in voltooi. Verder wys ons dat die wette konsekwent is in die ”Shadow Semantics”. Ten slotte, na aanleiding van die benadering in vir klassieke programme, gee ons ’n volledigheidsresultaat vir die program algebra van onwetendheid behoudende verfyning.

Thesis (MSc)--Stellenbosch University, 2013. / Please refer to full text to view abstract.

Thesis (MSc)--Stellenbosch University, 2013. / ENGLISH ABSTRACT: The main objective of our study is enumerating spanning trees (G) and perfect matchings PM(G) on graphs G and lattices L. We demonstrate two methods of enumerating spanning trees of any connected graph, namely the matrix-tree theorem and as a special value of the Tutte polynomial T(G; x; y). We present a general method for counting spanning trees on lattices in d 2 dimensions. In particular we apply this method on the following regular lattices with d = 2: rectangular, triangular, honeycomb, kagomé, diced, 9 3 lattice and its dual lattice to derive a explicit formulas for the number of spanning trees of these lattices of finite sizes. Regarding the problem of enumerating of perfect matchings, we prove Cayley’s theorem which relates the Pfaffian of a skew symmetric matrix to its determinant. Using this and defining the Pfaffian orientation on a planar graph, we derive explicit formula for the number of perfect matchings on the following planar lattices; rectangular, honeycomb and triangular. For each of these lattices, we also determine the bulk limit or thermodynamic limit, which is a natural measure of the rate of growth of the number of spanning trees (L) and the number of perfect matchings PM(L). An algorithm is implemented in the computer algebra system SAGE to count the number of spanning trees as well as the number of perfect matchings of the lattices studied. / AFRIKAANSE OPSOMMING: Die hoofdoel van ons studie is die aftelling van spanbome (G) en volkome afparings PM(G) in grafieke G en roosters L. Ons beskou twee metodes om spanbome in ’n samehangende grafiek af te tel, naamlik deur middel van die matriks-boom-stelling, en as ’n spesiale waarde van die Tutte polinoom T(G; x; y). Ons behandel ’n algemene metode om spanbome in roosters in d 2 dimensies af te tel. In die besonder pas ons hierdie metode toe op die volgende reguliere roosters met d = 2: reghoekig, driehoekig, heuningkoek, kagomé, blokkies, 9 3 rooster en sy duale rooster. Ons bepaal eksplisiete formules vir die aantal spanbome in hierdie roosters van eindige grootte. Wat die aftelling van volkome afparings aanbetref, gee ons ’n bewys van Cayley se stelling wat die Pfaffiaan van ’n skeefsimmetriese matriks met sy determinant verbind. Met behulp van hierdie stelling en Pfaffiaanse oriënterings van planare grafieke bepaal ons eksplisiete formules vir die aantal volkome afparings in die volgende planare roosters: reghoekig, driehoekig, heuningkoek. Vir elk van hierdie roosters word ook die “grootmaat limiet” (of termodinamiese limiet) bepaal, wat ’n natuurlike maat vir die groeitempo van die aantaal spanbome (L) en die aantal volkome afparings PM(L) voorstel. ’n Algoritme is in die rekenaaralgebra-stelsel SAGE geimplementeer om die aantal spanboome asook die aantal volkome afparings in die toepaslike roosters af te tel.

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: Wireless ad hoc networks are increasingly used in today’s life in various areas ranging from environmental monitoring to the military. For technical reasons, they are severely limited in terms of battery power, communication capacity and computation capability. Research has been carried out to deal with these limitations using different approaches. A theoretical treatment of the subject is topology control whose basic task is to design network topologies with special properties that make them energy-efficient and interference-optimal. We study, implement and compare the XTC and CBTC algorithms in terms of interference reduction, length stretch factor and maximum degree. These two algorithms have two features that are absent in almost all competitive topology control algorithms which are practicality and maintaining connectivity. Both algorithms show good performance in terms of interference reduction and maintaining a good length stretch factor. Regarding CBTC, we prove that it is a power spanner. We show through extensive simulation that the degree distribution of wireless ad hoc networks modelled by the log-normal model is binomial if the average degree is not high. We find that there is no fixed threshold for the average degree at which the distribution is distorted and no longer binomial. We show through simulation that the node density which ensures the absence of isolated nodes is a tight lower bound for the node density which ensures connectivity. The implication of this result is that connectivity is ensured with high probability if the minimum node degree is equal to 1. Finally we show through simulation that the log-normal model is not a realistic representation of wireless ad hoc networks if the environmental parameter is at least 6. This result is important because there are no available measurements to determine the range of the environmental parameter for typical frequencies used in wireless ad hoc networks. / AFRIKAANSE OPSOMMING: Koordlose ad hoc netwerke word toenemend gebruik in vandag se lewe op verskillende gebiede wat wissel van die omgewing monitor tot militêregebruik. Vir tegniese redes is hulle ernstig beperk in terme van battery krag, kommunikasie kapasiteit en berekeningsvermoë. Navorsing vanuit verkillende benaderings word gedoen om met hierdie beperkings te deel. ’n Teoretiese benadering tot onderwerp is topologie beheer. Die basiese taak is om netwerktopologieë met spesiale eienskappe wat hulle energie-doeltreffend en interferensieoptimaal maak te ontwerp. Ons bestudeer, implementeer en vergelyk die XTC en CBTC algoritmes in terme van interferensie vermindering, lengte rek faktor en maksimum graad. Beide hierdie algoritmes het twee eienskappe wat afwesig is in byna al die mededingende topologie beheer algoritmes: hulle is prakties en handhaf verbindings. Beide algoritmes toon goeie prestasie in terme van interferensie verminder en die handhawing van ’n goeie lengte rek faktor. Ten opsigte van CBTC bewys ons dat dit ’n “power spanner” is. Ons wys deur middel van uitgebreide simulasie dat die graad verdeling van die koordlose ad hoc netwerke wat deur die log-normale model gemodelleer kan word binomiaal is as die gemiddelde graad nie hoog is nie. Ons vind dat daar geen vaste drempel is vir die gemiddelde graad waarby die verdeling vervorm en nie meer binomiaal is nie. Ons wys deur simulasie dat die node digtheid wat die afwesigheid van geïsoleerde nodusse verseker ’n streng ondergrens vir die node digtheid wat konnektiviteit verseker is. Die implikasie van hierdie resultaat is dat ‘n konneksie verseker word as die minimum node graad gelyk is aan 1. Ten slotte wys ons deur simulasie dat die log-normale model nie ’n realistiese voorstelling van koordlose ad hoc netwerke is wanneer die “environmental parameter” groter is as 6 nie. Hierdie resultaat is belangrik, want daar is geen beskikbare metings om die grense van hierdie parameter vir ’n tipiese frekwensie gebruik in koordlose ad hoc netwerke te bepaal nie.

Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: A greedy tree is constructed from a given degree sequence using a simple greedy algorithm that assigns the highest degree to the root, the second, the third, . . . , -highest degree to the root’s neighbours, etc. This particular tree is the solution to numerous extremal problems among all trees with given degree sequence. In this thesis, we collect results for some distancebased graph invariants, the number of subtrees and the spectral radius in which greedy trees play a major role. We show that greedy trees are extremal for the aforementioned graph invariants by means of two different approaches, one using level greedy trees and majorization, while the other one is somewhat more direct. Finally, we prove some new results on greedy trees for additive parameters with specific toll functions. / AFRIKAANSE OPSOMMING: ’n Gulsige boom word vanuit ’n gegewe graadry deur middel van ’n eenvoudige gulsige algoritme gebou, wat die hoogste graad aan die wortel toewys, die tweede-, derde-, . . . , -hoogste graad aan die wortel se bure, ens. Hierdie spesifieke boom is die oplossing van ’n groot aantal ekstremale probleme onder al die bome met gegewe graadry. In hierdie tesis beskou ons ’n versameling van resultate oor afstand-gebaseerde grafiekinvariante, die aantal subbome en die spektraalstraal waarin gulsige bome ’n belangrike rol speel. Ons bewys dat gulsige bome ekstremaal vir die bogenoemde grafiekinvariante is deur van twee verskillende tegnieke gebruik te maak: een met behulp van vlak-gulsige bome en majorering, en ’n ander metode wat effens meer direk is. Laastens bewys ons sommige nuwe resultate oor gulsige bome vir additiewe parameters met spesifieke tolfunksies.