No description available.

Je présente dans ce mémoire mes travaux sur les limites d'échelle de grandes structures aléatoires. Il s'agit de décrire les structures combinatoires dans la limite des grandes tailles en prenant un point de vue objectif dans le sens où on cherche des limites des objets, et non pas seulement de paramètres caractéristiques (même si ce n'est pas toujours le cas dans les résultats que je présente). Le cadre général est celui des structures critiques pour lesquelles on a typiquement des distances caractéristiques polynomiales en la taille, et non concentrées. Sauf exception, ces structures ne sont en général pas adaptées aux applications informatiques. Elles sont cependant essentielles de part l'universalité de leurs propriétés asymptotiques, prouvées ou attendues. Je parle en particulier d'arbres uniformément choisis, de graphes aléatoires, d'arbres couvrant minimaux et de partitions récursives de domaines du plan:<br/> <strong>Arbres aléatoires uniformes.</strong> Il s'agit ici de mieux comprendre un objet limite essentiel, l'arbre continu brownien (CRT). Je présente quelques résultats de convergence pour des modèles combinatoires ''non-branchants'' tels que des arbres sujets aux symétries et les arbres à distribution de degrés fixée. Je décris enfin une nouvelle décomposition du CRT basée sur une destruction partielle.<br/> <strong>Graphes aléatoires.</strong> J'y décris la construction algorithmique de la limite d'échel-le des graphes aléatoires du modèle d'Erdös--Rényi dans la zone critique, et je fais le lien avec le CRT et donne des constructions de l'espace métrique limite. <strong>Arbres couvrant minimaux.</strong> J'y montre qu'une connection avec les graphes aléatoires permet de quantifier les distances dans un arbre convrant aléatoire. On obtient non seulement l'ordre de grandeur de l'espérance du diamètre, mais aussi la limite d'échelle en tant qu'espace métrique mesuré. Partitions récursives. Sur deux exemples, les arbres cadrant et les laminations du disque, je montre que des idées basées sur des théorèmes de point fixe conduisent à des convergences de processus, où les limites sont inhabituelles, et caractérisées par des décompositions récursives.

We introduce numerical methods for the analysis of random dynamical systems. The subdivision and the continuation algorithm are powerful tools which will be demonstrated for a system from ship dynamics. With our software package we are able to show that the well known safe basin is a moving fractal set. We will also give a numerical approximation of the attracting invariant set (which contains a local attractor) and its evolution.

The art of reconstructing a real-world scene digitally has been on the mind of researchers for decades. Recently, it has attracted more and more attention from companies seeing a chance to bring this kind of technology to the market. Digital reconstruction of buildings in particular is a niche that has both potential and room for improvement. With this background, this thesis will present the design and evaluation of a pipeline made to find and correct approximately flat surfaces in architectural scenes. The scenes are 3D-reconstructed triangle meshes based on RGB images. The thesis will also comprise an evaluation of a few different components available for doing this, leading to a choice of best components. The goal is to improve the visual quality of the reconstruction. The final pipeline is designed with two blocks - one to detect initial plane seeds and one to refine the detected planes. The first block makes use of a multi-label energy formulation on the graph that describes the reconstructed surface. Penalties are assigned to each vertex and each edge of the graph based on the vertex labels, effectively describing a Markov Random Field. The energy is minimized with the help of the alpha-expansion algorithm. The second block uses heuristics for growing the detected plane seeds, merging similar planes together and extracting deviating details. Results on several scenes are presented, showing that the visual quality has been improved while maintaining accuracy compared with ground truth data. / Konsten att digitalt rekonstruera en verklig miljö har länge varit intressant för forskare. Nyligen har området även tilldragit sig mer och mer uppmärksamhet från företag som ser en möjlighet att föra den här typen av teknik till produkter på marknaden. I synnerhet är digital rekonstruktion av byggnader en nisch som har både stor potential och möjlighet till förbättring. Med denna bakgrund så presenterar detta examensarbete designen för och utvärderingen av en pipeline som skapats för att detektera och rätta till approximativt platta regioner i arkitektoniska miljöer. Miljöerna är 3D-rekonstruerade triangelmeshar skapade från RGB-bilder. Examensarbetet omfattar även utvärdering av olika komponenter för att uppnå detta, som avslutas med att de mest lämpliga komponenterna presenteras. Målet i korthet är att förbättra den visuella kvaliteten av en rekonstruerad modell. Den slutgiltiga pipelinen består av två övergripande block - ett för att detektera initiala plan och ett för att förbättra de funna planen. Det första blocket använder en multi-label energiformulering på grafen som beskriver den rekonstruerade ytan. Straffvärden tilldelas varje vertex och varje båge i grafen baserade på varje vertex label. På så sätt beskriver grafen ett Markov Random Field. Energin är sedan minimerad med alpha-expansion-algoritmen. Det andra blocket använder heuristiker för att låta planen växa, slå ihop närliggande plan och för att extrahera avvikande detaljer. Resultat på flera miljöer presenteras också för att påvisa att den visuella kvaliteten har förbättrats utan att rekonstruktionens noggrannhet har försämrats jämfört med ground truth-data.

Random access schemes are primarily used for data transmission in the uplink of cellular networks. Every user in a random access network is programmed to follow a predetermined transmit control policy that is designed to achieve optimal network performance. This approach, however, is not very efficient in cellular networks where channel conditions vary from time to time. Employing a fixed transmission policy may not guarantee optimal performance. To alleviate this problem, recently, channel aware random access schemes have been proposed wherein information available at the physical (PHY) layer is utilized at the higher layers to maximize network throughput. Such a cross-layer approach naturally has its share of challenges and problems. The objective of the proposed research is to study the effect of multicarrier diversity on channel aware random access schemes. First, we describe two generic random access schemes - channel aware multicarrier random access (CAMCRA) and no selection random access (NS-RA) for multicarrier networks. The former is based on judicious carrier selection and exploits multicarrier diversity while the latter does not perform carrier selection. For illustration purposes, we consider the well-known Aloha protocol and study the effect of channel state imperfection on the overall network throughput. We show that networks employing the NS-RA scheme are extremely sensitive to channel measurement errors. More precisely, the asymptotic average throughput of the NS-RA scheme under uncertain channel conditions is zero. The CAMCRA scheme, however, is very robust to channel estimation errors and maintains the same order of throughput.

Complex networks is a vibrant research field and has received much attention over the last decade. Central to this area is the question of how networks around us are constructed. The essential notion of network research is that these systems are assembled in a decentralised way, thus no central agent is planning the network beforehand. Despite this lack of central coordination, many networks present intriguing universalities, such as broad degree distributions, in the form of power-laws. The subject of study in this thesis is a class of networks that are constructed by a node intrinsic variable, called fitness. The way these networks grow could be called a rich-get-richer mechanism. The fitter a node is, the more likely it is to acquire new connections inside the network. Several aspects that are directly connected to these networks are explored in this thesis. In the first part, the properties of growing networks that are driven by fitness are investigated and it is shown that the introduction of growth leads to a topological structure that is different from its static counterpart. In the subsequent chapter, percolation on fitness driven networks is studied. The results give insights into possible mechanisms that can stabilise systems. Furthermore, the theory can be used to identify vulnerable structures around us. In the following chapter, the world trade network is discussed. This numerical investigation highlights possible improvements to the methodology to make statistical analysis more robust. That chapter is followed by an analysis of time-varying networks. Time-varying networks represent an interesting construct that allows a formulation of stochastic processes on the same time-scale as the evolution of the network itself. This possibility is highly relevant to the investigation of epidemics, for instance. In the last chapter, a study of a system of clusters and their self-organised formation is presented.

No description available.

published_or_final_version / abstract / Statistics and Actuarial Science / Doctoral / Doctor of Philosophy

New tools are available for reconstructing the attractor basins of discrete dynamical networks where state-space is linked according the network's dynamics. In this thesis the computer software "Discrete Dynamics Lab" is applied to examine simple networks ranging from cellular automata (CA) to random Boolean networks (RBN), that have been widely applied as idealised models of physical and biological systems, to search for general principles underlying their dynamics. The algorithms and methods for generating pre-images for both CA and RBN, and reconstructing and representing attractor basins are described, and also considered in the mathematical context of random directed graphs. RBN and CA provide contrasting notions of self-organisation. RBN provide models of hierarchical categorisation in biology, for example memory in neural and genomic networks. CA provide models at the lower level of emergent complex pattern. New measures and results are presented on CA attractor basins and how they relate to measures on local dynamics and the Z parameter, characterising ordered to "complex" to chaotic behaviour. A method is described for classifying CA rules by an entropy-variance measure which allows glider rules and related complex rules to be found automatically giving a virtually unlimited sample for further study. The dynamics of RBN and intermediate network architectures are examined in the context of memory, where categorisation occurs at the roots of subtrees as well as at attractors. Learning algorithms are proposed for "sculpting" the basin of attraction field. RBN are proposed as a possible neural network model, and also discussed as a model of genomic regulatory networks, where cell types have been explained as attractors

Jitter is defined as timing uncertainties of digital signals at their intended ideal positions in time. While it undermines valuable clock budget and limits the maximum clock frequency in I/O circuitry, it is one of the most difficult parameters to measure accurately due to the small value and randomness. This thesis proposes a random jitter RMS measurement method using AND and OR operations, which targets BIST applications. This thesis is organized as follows. Chapter 1 introduces the motivation of the proposed work. It includes a comparison between two major approaches to jitter measurement. Chapter 2 explains the proposed random jitter estimation method in detail. Chapter 3 describes circuit implementations with design considerations. Chapter 4 demonstrates estimation results from circuit level simulation runs. Chapter 5 discusses the source of error in the jitter estimation and concludes. / text