The use of GPS probes in traffic management is growing rapidly as the required data collection infrastructure is increasingly in place, with significant number of mobile sensors moving around covering expansive areas of the road network. Many travelers carry with them at least one device with a built-in GPS receiver. Furthermore, vehicles are becoming more and more location aware. Vehicles in commercial fleets are now routinely equipped with GPS. Travel time is important information for various actors of a transport system, ranging from city planning, to day to day traffic management, to individual travelers. They all make decisions based on average travel time or variability of travel time among other factors. AVI (Automatic Vehicle Identification) systems have been commonly used for collecting point-to-point travel time data. Floating car data (FCD) -timestamped locations of moving vehicles- have shown potential for travel time estimation. Some advantages of FCD compared to stationary AVI systems are that they have no single point of failure and they have better network coverage. Furthermore, the availability of opportunistic sensors, such as GPS, makes the data collection infrastructure relatively convenient to deploy. Currently, systems that collect FCD are designed to transmit data in a limited form and relatively infrequently due to the cost of data transmission. Thus, reported locations are far apart in time and space, for example with 2 minutes gaps. For sparse FCD to be useful for transport applications, it is required that the corresponding probes be matched to the underlying digital road network. Matching such data to the network is challenging. This thesis makes the following contributions: (i) a map-matching and path inference algorithm, (ii) a method for route travel time estimation, (iii) a fixed point approach for joint path inference and travel time estimation, and (iv) a method for fusion of FCD with data from automatic number plate recognition. In all methods, scalability and overall computational efficiency are considered among design requirements. Throughout the thesis, the methods are used to process FCD from 1500 taxis in Stockholm City. Prior to this work, the data had been ignored because of its low frequency and minimal information. The proposed methods proved that the data can be processed and transformed into useful traffic information. Finally, the thesis implements the main components of an experimental ITS laboratory, called iMobility Lab. It is designed to explore GPS and other emerging data sources for traffic monitoring and control. Processes are developed to be computationally efficient, scalable, and to support real time applications with large data sets through a proposed distributed implementation. / <p>QC 20150525</p>

Dans les années quatre-vingts dix du siècle dernier, R. W. Thomason a démontréun théorème de concentration pour la K-théorie équivariante algébrique sur lesschémas munis d’une action d’un groupe algébrique G diagonalisable. Comme d’habitude,un tel théorème entraîne une formule des points fixes de type Lefschetz qui permetde calculer la caractéristique d’Euler-Poincaré équivariante d’un G-faisceau cohérent surun G-schéma propre en termes d’une caractéristique sur le sous-schéma des points fixes.Le but de cette thèse est de généraliser les résultats de R.W. Thomason dans le contextede la géométrie d’Arakelov. Dans ce travail, nous considérons les schémas arithmétiquesau sens de Gillet-Soulé et nous tout d’abord démontrons un analogue arithmétiquedu théorème de concentration pour les schémas arithmétiques munis d’une action duschéma en groupe diagonalisable associé à Z/nZ. La démonstration résulte du théorèmede concentration algébrique joint à des arguments analytiques. Dans le dernier chapitre,nous formulons et démontrons deux types de formules de Lefschetz arithmétiques. Cesdeux formules donnent une réponse positive à deux conjectures énoncées par K. Köhler,V. Maillot et D. Rössler. / In the nineties of the last century, R. W. Thomason proved a concentrationtheorem for the algebraic equivariant K-theory on the schemes which are endowed withan action of a diagonalisable group scheme G. As usual, such a concentration theoreminduces a fixed point formula of Lefschetz type which can be used to calculate theequivariant Euler-Poincaré characteristic of a coherent G-sheaf on a proper G-schemein terms of a characteristic on the fixed point subscheme. It is the aim of this thesis togeneralize R. W. Thomason’s results to the context of Arakelov geometry. In this work,we consider the arithmetic schemes in the sense of Gillet-Soulé and we first prove anarithmetic analogue of the concentration theorem for the arithmetic schemes endowedwith an action of the diagonalisable group scheme associated to Z/nZ. The proof is acombination of the algebraic concentration theorem and some analytic arguments. Inthe last chapter, we formulate and prove two kinds of arithmetic Lefschetz formulae.These two formulae give a positive answer to two conjectures made by K. Köhler, V.Maillot and D. Rössler.

The present thesis analyses the proposal of CubeHash with spe- cial emphasis on the following papers: "Inside the Hypercube" [1], "Sym- metric States and Their Improved Structure" [7] and "Linearisation Frame- work for Collision Attacks" [6]. The CubeHash algorithm is presented in a concise manner together with a proof that the CubeHash round function R : ({0, 1}32 )32 → ({0, 1}32 )32 is a permutation. The results of [1] and [7] con- cerning the CubeHash symmetric states are reviewed, corrected and substan- tiated by proofs. More precisely, working with a definition of D-symmetric state, based on [7], the thesis proves both that for V = Z4 2 and its linear subspace D, there are 22 |V | |D| D-symmetric states and an internal state x is D-symmetric if and only if the state R(x) is D-symmetric. In response to [1], the thesis presents a step-by-step computation of a lower bound for the num- ber of distinct symmetric states, explains why the improved preimage attack does not work as stated and gives a mathematical background for a search for fixed points in R. The thesis further points out that the linearisation method from [6] fails to consider the equation (A ⊕ α) + β = (A + β) ⊕ α (∗), present during the CubeHash iteration phase. Necessary and sufficient conditions for A being a solution to (∗) are...

Neste trabalho inicialmente estudamos o rank da co-homologia do espaço dos pontos fixos de uma \'Z IND.p\' - ação semilivre sobre espaços X~p \' S POT. n\' x \'S POT.n\' e X~p \'S POT.n\' x \'S POT.n\' x \'S POT.n\' , com n>0. Em seguida, estudamos uma extensão para ações de p-grupos sobre espaços X~p \'S POT.n\' X \'S POT.m\', com 0< n \'< OU =\' m. Como parte do material utilizado demos uma descrição do diferencial d1 de uma seqüência espectral que converge para co-homologia equivariante de Tate, bem como uma versão da Fórmula de Künneth para a co-homologia equivariante de Tate. Na parte final, motivado pelo problemas de descrição de espaços de órbita de ações de grupos infinito, calculamos as co-homologias dos grupos virtualmente cíclicos (\'Z IND.a\' X| \' Z IND. b\' )X| Z e [\'Z POT.a\' X|(\'Z IND.b\' X \'Q IND. 2 POT.i\') ]X| Z / In this work is studied the rank of the fixed point set of a semifree action on spaces X~p \'S POT.n\' X \'S POT.n\' and X~p \'S POT.n\' X \'S POT.n\' X \'S POT.n\' , with n>0. We also consider the extension of the result for actions of p-groups on spaces X~p \'SPOT.n\' X \' S POT.m\' , with 0<n \'< OR =\' m. As result of the techniques used, we give a description of the differential d1 of a spectral sequence that converges to Tate equivariant cohomology, as well a version of the Künneth Formule to Tate equivariant cohomology. At the end, motivated by the space form problem for infinite groups we compute the cohomology of the virtually cyclic groups (\'Z IND. a\' X| \'Z IND. b\' )X| Z and [\'Z IND.a\' X|(\'Z IND. b\' X \'Q IND2 POT. i\' )] X| Z

Nas últimas três décadas os phase locked loops (PLLs) totalmente digitais têm recebido muita atenção devido, principalmente, às vantagens que eles oferecem em comparação aos PLLs analógicos. Essas vantagens incluem melhor desempenho, maior velocidade e confiabilidade, tamanho reduzido e menor custo. Os PLLs também são amplamente utilizados em sistemas de comunicações e em outras aplicações digitais. A presente dissertação é uma contribuição no campo dos PLLs digitais adaptativos e otimizados para a sua implementação em hardware. É feito uma análise de suas características dinâmicas e proposta uma nova estrutura de PLL digital capaz de melhorar a resposta da malha em termos de tempo de aquisição e largura de banda. A Malha Síncrona Digital \"Tanlock\" com Estimação de Frequência e Ganho Adaptativo para Convergência Rápida, como é chamada, foi desenvolvida a partir da malha digital \"Tanlock\", utilizando-se teoremas de ponto fixo e mapas contrativos para determinar as condições de ganho que garantam convergência rápida e melhor utilização da largura de banda. Resultados das simulações são comparados com os obtidos teoricamente para avaliar o desempenho da malha proposta. / In the last three decades, fully-digital Phase-Locked-Loops (PLLs) systems have received a lot of attention due to its advantages in comparison with analog PLLs. These advantages include improved transient response, reliability and also reduced size and cost. The PLLs are widely used in communications systems and many other digital applications. This dissertation is a contribution to the field of digital adaptive PLLs optimized to hardware implementation. Here, a new PLL structure is presented; the Frequency Sensing Adaptive TDTL is an improvement to the classic Time-Delay Tanlock structure, alowing fast convergence to the synchronous states, using fixed-point theorems and contractive maps to determine the gain conditions which ensure the rapid convergence and also providing wider bandwidth. The results of simulations are compared with those obtained theoretically in order to assess the loop performance.

This thesis provides the deliberations about the implementation of Gentleman-Kung systolic array for QR decomposition using Givens Rotations within the context of radar signal processing. The systolic array of Givens Rotations is implemented and analysed using a massively parallel processor array (MPPA), Ambric Am2045. The tools that are dedicated to the MPPA are tested in terms of engineering efficiency. aDesigner, which is built on eclipse environment, is used for programming, simulating and performance analysing. aDesigner has been produced for Ambric chip family. 2 parallel matrix multiplications have been implemented to get familiar with the architecture and tools. Moreover different sized systolic arrays are implemented and compared with each other. For programming, ajava and astruct languages are provided. However floating point numbers are not supported by the provided languages. Thus fixed point arithmetic is used in systolic array implementation of Givens Rotations. Stable and precise numerical results are obtained as outputs of the algorithms. However the analysis results are not reliable because of the performance analysis tools.

Dans la nature existent de nombreux exemples de systèmes dynamiques complexes: systèmes neuronaux, communautés, écosystèmes, réseaux de régulation génétiques, etc. Ces derniers, en particulier, sont de notre intérêt et sont souvent modélisés par des réseaux booléens. Un réseau booléenne peut être considérée comme un digraphe, où les sommets correspondent à des gènes ou de produits de gènes, tandis que les arcs indiquent les interactions entre eux. Une niveau d'expression des gènes est modélisé par des valeurs binaires, 0 ou 1, indiquant deux états de la transcription, soit activité, soit inactivité, respectivement, et ce niveau change dans le temps selon certains fonction locaux d'activation qui dépend des états d'un ensemble de nœuds (les gènes). L'effet conjoint des fonctions d'activation locale définit une fonction de transition globale: ainsi, le autre élément nécessaire dans la description du modèle est fonction de mise à jour, qui détermine quand chaque nœud doit être mis à jour, et donc, comme les fonctions local se combinent dans une fonction globale (en d'autres termes, il doit décrire les temps relative de les activités régulatoires). Comme un réseau booléen avec n sommets a 2 ^ n états globaux, à partir d'un état ​​de départ, et dans un nombre fini de mises à jour, le réseau atteindra un fixe point ou un cycle limite, appelée attracteurs qui sont souvent associées à des phénotypes distincts (états-cellulaire) définis par les patrons d'activité des gènes. Un réseau de régulation Booléenne (REBN) est un réseau Booléen où chaque interaction entre les éléments de la réseau correspond soit à une interaction positif ou d'une interaction négative. Ainsi, le digraphe interaction associée à une REBN est un digraphe signé où un circuit est appelé positif (négatif) si le nombre de ses arcs négative est pair (impair). Dans ce contexte, il y a diverses études sur l'importance du les circuits positif et négatifs dans le comportement dynamique de différents systèmes en Biologie. En effet le point de départ de cette thèse est basée sur un résultat en disant que le nombre maximal de points fixes d'une REBN dépend d'un ensemble de cardinalité minimale qu'intersecte tous les cycles positifs (également dénommés positive feedback vertex set) du digraphe signé associé. D'autre part, un autre aspect important de circuits est leur rôle dans la robustesse des réseaux booléens par rapport différents types de mise à jour déterministe. Dans ce contexte, un élément clé mathématique est le update digraphe qui est un digraphe étiqueté associé à la réseau dont les étiquettes sur les arcs sont définies comme suit: un arc (u,v) est dit être positif si l'état de sommet u est mis à jour en même temps ou après que celle de v, et négative sinon. Ainsi, un cycle dans le digraphe étiqueté est dite positive (négative) si tous ses arcs sont positifs (négatifs). Cela laisse en évidence que parler de "positif" et "négatif" a des significations différentes selon le contex: digraphes signé ou digraphes étiquetés. Ainsi, nous allons voir dans cette thèse, les relations entre les feedback sets et la dynamique des réseaux Booléens à travers l'étude analytique de ces deux fondamentaux objets mathématiques: le digraphe (de connexion) signé et l'update digraphe. / In the nature there exist numerous examples of complex dynamical systems: neural systems, communities, ecosystems, genetic regulatory networks, etc. These latest, in particular are of our interest and are often modeled by Boolean networks. A Boolean network can be viewed as a digraph, where the vertices correspond to genes or gene products, while the arcs denote interactions among them. A gene expression level is modeled by binary values, 0 or 1, indicating two transcriptional states, either active or inactive, respectively, and this level changes in time according to some local activation function which depends on the states of a set of nodes (genes). The joint effect of the local activation functions defines a global transition function; thus, the other element required in the description of the model is an update schedule which determines when each node has to be updated, and hence, how the local functions combine into the global one (in other words, it must describe the relative timings of the regulatory activities). Since a Boolean network with n vertices has 2^n global states, from a starting state, within a finite number of udpates, the network will reach a fixed point or a limit cycle, called attractors that are often associated to distinct phenotypes (cellular states) defined by patterns of gene activity. A regulatory Boolean network (REBN) is a Boolean network where each interaction between the elements of the network corresponds either to a positive or to a negative interaction. Thus, the interaction digraph associated to a REBN is a signed digraph where a circuit is called positive (negative) if the number of its negative arcs is even (odd). In this context, there are diverse studies about the importance of the positive and negative circuits in the dynamical behavior of different systems in Biology. Indeed the starting point of this Thesis is based on a result saying that the maximum number of fixed points of a REBN depends on a minimum cardinality vertex set whose elements intersects to all the positive cycles (also named a positive feedback vertex set) of the associated signed digraph. On the other hand, another important aspect of circuits is their role in the robustness of Boolean networks with respect to different deterministic update schedules. In this context a key mathematical element is the update digraph which is a labeled digraph associated to the network and whose labels on the arcs are defined as follows: an arc (u,v) is said to be positive if the state of vertex u is updated at the same time or after than that of v, and negative otherwise. Hence, a cycle in the labeled digraph is called positive (negative) if all its arcs are positive (negative). This leaves in evidence that talk of "positive" and "negative" has different meanings depending on the contex: signed digraphs or labeled digraphs. Thus, we will see in this thesis, relationships between feedback sets and the dynamics of Boolean networks through the analytical study of these two fundamental mathematical objects: the signed (connection) digraph and the update digraph.

<p>This thesis provides the deliberations about the implementation of Gentleman-Kung systolic array for QR decomposition using Givens Rotations within the context of radar signal </p><p>processing. The systolic array of Givens Rotations is implemented and analysed using a massively parallel processor array (MPPA), Ambric Am2045. The tools that are dedicated to the MPPA are tested in terms of engineering efficiency. aDesigner, which is built on eclipse environment, is used for programming, simulating and performance analysing. aDesigner has been produced for Ambric chip family. 2 parallel matrix multiplications have been implemented </p><p>to get familiar with the architecture and tools. Moreover different sized systolic arrays are implemented and compared with each other. For programming, ajava and astruct languages are provided. However floating point numbers are not supported by the provided languages. </p><p>Thus fixed point arithmetic is used in systolic array implementation of Givens Rotations. Stable and precise numerical results are obtained as outputs of the algorithms. However the analysis </p><p>results are not reliable because of the performance analysis tools.</p>

<p>This thesis provides the deliberations about the implementation of Gentleman-Kung systolic array for QR decomposition using Givens Rotations within the context of radar signal processing. The systolic array of Givens Rotations is implemented and analysed using a massively parallel processor array (MPPA), Ambric Am2045. The tools that are dedicated to the MPPA are tested in terms of engineering efficiency. aDesigner, which is built on eclipse environment, is used for programming, simulating and performance analysing. aDesigner has been produced for Ambric chip family. 2 parallel matrix multiplications have been implemented to get familiar with the architecture and tools. Moreover different sized systolic arrays are implemented and compared with each other. For programming, ajava and astruct languages are provided. However floating point numbers are not supported by the provided languages. Thus fixed point arithmetic is used in systolic array implementation of Givens Rotations. Stable </p><p>and precise numerical results are obtained as outputs of the algorithms. However the analysis results are not reliable because of the performance analysis tools.</p>

<p>The success of the current Internet relies to a large extent on a cooperation between the users and the network. The network signals its current state to the users by marking or dropping packets. The users then strive to maximize the sending rate without causing network congestion. To achieve this, the users implement a flow-control algorithm that controls the rate at which data packets are sent into the Internet. More specifically, the <i>Transmission Control Protocol (TCP)</i> is used by the users to adjust the sending rate in response to changing network conditions. TCP uses the observation of packet loss events and estimates of the round trip time (RTT) to adjust its sending rate. </p><p>In this thesis we investigate and propose stochastic models for TCP. The models are used to estimate network performance like throughput, link utilization, and packet loss rate. The first part of the thesis introduces the TCP protocol and contains an extensive TCP modeling survey that summarizes the most important TCP modeling work. Reviewed models are categorized as renewal theory models, fixed-point methods, fluid models, processor sharing models or control theoretic models. The merits of respective category is discussed and guidelines for which framework to use for future TCP modeling is given. </p><p>The second part of the thesis contains six papers on TCP modeling. Within the renewal theory framework we propose single source TCP-Tahoe and TCP-NewReno models. We investigate the performance of these protocols in both a DropTail and a RED queuing environment. The aspects of TCP performance that are inherently depending on the actual implementation of the flow-control algorithm are singled out from what depends on the queuing environment.</p><p>Using the fixed-point framework, we propose models that estimate packet loss rate and link utilization for a network with multiple TCP-Vegas, TCP-SACK and TCP-Reno on/off sources. The TCP-Vegas model is novel and is the first model capable of estimating the network's operating point for TCP-Vegas sources sending on/off traffic. All TCP and network models in the contributed research papers are validated via simulations with the network simulator <i>ns-2</i>. </p><p>This thesis serves both as an introduction to TCP and as an extensive orientation about state of the art stochastic TCP models.</p>