Recentemente, Barak et al. (2004) exibiram construções de extratores e dispersores determinísticos (funções computáveis em tempo polinomial) com parâmetros melhores do que era anteriormente possível. Introduziremos os conceitos envolvidos em tal trabalho e mencionaremos suas aplicações; em particular, veremos como é possível obter cotas muito melhores para o problema Ramsey bipartido (um problema bem difícil) utilizando as construções descritas no artigo. Também apresentamos resultados originais para melhorar tais construções. Tais idéias são inspiradas no trabalho de Anup Rao (2005) e utilizam o recente êxito de Jean Bourgain (2005) em obter extratores que quebram a \"barreira 1/2\". / Recently, Barak et al. (2004) constructed explicit deterministic extractors and dispersers (these are polynomial-time computable functions) with much better parameters than what was known before. We introduce the concepts involved in such a construction and mention some of its applications; in particular, we describe how it is possible to obtain much better bounds for the bipartite Ramsey problem (a very hard problem) using the machinery developed in that paper. We also present some original results that improve on these constructions. They are inspired by the work of Anup Rao (2005) and uses the recent breakthrough of Jean Bourgain (2005) in obtaining 2-source extractors that break the \"1/2-barrier\".

Neste trabalho consideramos um problema da Antropologia. A modelagem de sociedades e casamentos de indivíduos é feita com grafos mistos e encontrar caminhos disjuntos é uma questão central no problema. O problema é NP-completo e, quando visto como um problema parametrizado, ele é W[1]-difícil. Alguns subproblemas que surgem durante o processo de obter uma solução para o problema, envolvem caminhos disjuntos e podem ser resolvidos em tempo polinomial. Implementamos algoritmos polinomiais que são usados em uma ferramenta desenvolvida para solucionar o problema na Antropologia considerado. Nossa solução funcionou bem para as sociedades fornecidas pelos nossos parceiros. / In this work we consider a problem from the Anthropology. The model of the societies and the marriages of individuals is done with mixed graphs and to find disjoint paths is a central question in the problem. The problem is NP-complete and W[1]-hard when it is considered a parameterized problem. Some subproblems that arise during the process to obtain a solution for the problem, involve disjoint paths and can be solved in polynomial time. We implemented some polynomial algorithms that are used in a tool developed to solve the problem in the Anthropology considered. Our solution worked well for the societies provided by our partners.

La localisation et cartographie simultanées connue, communément, sous le nom de SLAM (Simultaneous Localization And Mapping) est un processus qui permet à un robot explorant un environnement inconnu de reconstruire une carte de celui-ci tout en se localisant, en même temps, sur cette carte. Dans ce travail de thèse, nous nous intéressons au SLAM par optimisation de graphe. Celui-ci utilise un graphe pour représenter et résoudre le problème de SLAM. Une optimisation de graphe consiste à trouver une configuration de graphe (trajectoire et carte) qui correspond le mieux aux contraintes introduites par les mesures capteurs. L'optimisation de graphe présente une forte complexité algorithmique et requiert des ressources de calcul et de mémoire importantes, particulièrement si l'on veut explorer de larges zones. Cela limite l'utilisation de cette méthode dans des systèmes embarqués temps-réel. Les travaux de cette thèse contribuent à l'atténuation de la complexité de calcul du SLAM par optimisation de graphe. Notre approche s’appuie sur deux axes complémentaires : la représentation mémoire des données et l’implantation sur architectures hétérogènes embarquées. Dans le premier axe, nous proposons une structure de données incrémentale pour représenter puis optimiser efficacement le graphe. Dans le second axe, nous explorons l'utilisation des architectures hétérogènes récentes pour accélérer le SLAM par optimisation de graphe. Nous proposons, donc, un modèle d’implantation adéquat aux applications embarquées en mettant en évidence les avantages et les inconvénients des architectures évaluées, à savoir SoCs basés GPU et FPGA. / Simultaneous Localization And Mapping is the process that allows a robot to build a map of an unknown environment while at the same time it determines the robot position on this map.In this work, we are interested in graph-based SLAM method. This method uses a graph to represent and solve the SLAM problem. A graph optimization consists in finding a graph configuration (trajectory and map) that better matches the constraints introduced by the sensors measurements. Graph optimization is characterized by a high computational complexity that requires high computational and memory resources, particularly to explore large areas. This limits the use of graph-based SLAM in real-time embedded systems. This thesis contributes to the reduction of the graph-based computational complexity. Our approach is based on two complementary axes: data representation in memory and implementation on embedded heterogeneous architectures. In the first axis, we propose an incremental data structure to efficiently represent and then optimize the graph. In the second axis, we explore the use of the recent heterogeneous architectures to speed up graph-based SLAM. We propose an efficient implementation model for embedded applications. We highlight the advantages and disadvantages of the evaluated architectures, namely GPU-based and FPGA-based System-On-Chips.

A standard problem in mathematical finance is the calculation of the price of some financial derivative such as various types of options. Since there exists analytical solutions in only a few cases it will often boil down to estimating the price with Monte Carlo simulation in conjunction with some numerical discretization scheme. The upside of using what we can call standard Monte Carlo is that it is relative straightforward to apply and can be used for a wide variety of problems. The downside is that it has a relatively slow convergence which means that the computational cost or complexity can be very large. However, this slow convergence can be improved upon by using Multilevel Monte Carlo instead of standard Monte Carlo. With this approach it is possible to reduce the computational complexity and cost of simulation considerably. The aim of this thesis is to introduce the reader to the Multilevel Monte Carlo method with applications to European and Asian call options in both the Black-Scholes-Merton (BSM) model and in the Heston model. To this end we first cover the necessary background material such as basic probability theory, estimators and some of their properties, the stochastic integral, stochastic processes and Ito’s theorem. We introduce stochastic differential equations and two numerical discretizations schemes, the Euler–Maruyama scheme and the Milstein scheme. We define strong and weak convergence and illustrate these concepts with examples. We also describe the standard Monte Carlo method and then the theory and implementation of Multilevel Monte Carlo. In the applications part we perform numerical experiments where we compare standard Monte Carlo to Multilevel Monte Carlo in conjunction with the Euler–Maruyama scheme and Milsteins scheme. In the case of a European call in the BSM model, using the Euler–Maruyama scheme, we achieved a cost O(ε-2(log ε)2) to reach the desired error in accordance with theory in comparison to the O(ε-3) cost for standard Monte Carlo. When using Milsteins scheme instead of the Euler–Maruyama scheme it was possible to reduce the cost in terms of the number of simulations needed to achieve the desired error even further. By using Milsteins scheme, a method with greater order of strong convergence than Euler–Maruyama, we achieved the O(ε-2) cost predicted by the complexity theorem compared to the standard Monte Carlo cost of order O(ε-3). In the final numerical experiment we applied the Multilevel Monte Carlo method together with the Euler–Maruyama scheme to an Asian call in the Heston model. In this case, where the coefficients of the Heston model do not satisfy a global Lipschitz condition, the study of strong or weak convergence is much harder. The numerical experiments suggested that the strong convergence was slightly slower compared to what was found in the case of a European call in the BSM model. Nevertheless, we still achieved substantial savings in computational cost compared to using standard Monte Carlo.

In cellular communication systems, the estimation of Doppler spread has a wide range of applications such as handoff, channel assignment scheme, adaptivetransmission, power control, etc. A great quantity of Doppler spread estimation algorithms have been proposed in the literature. But there has been few investigations which gives a comprehensive comparison of these algorithms. Therefore, it is of great signicance to compare and evaluate the performance of the existing algorithms in the same simulation framework. In this report, the uplink of WCDMA is considered. Four different types of Doppler spread estimation algorithms are evaluated and compared in a link level baseband simulator. The performance and the ability to implement are considered as the metrics for evaluation. Both Rayleigh and Rician fading channel model are applied, and the effect of speed, signal to noise ratio, Rician factor and the angle of arrived line of sight component are also tested. Moreover, the computational complexity is analysed to evaluate the practical value for implementation. / Estimatering av en mobils hastighet i form av Dopplerspridning har ett brett spektrum av tillmpningar i cellulra kommunikationssystem ssom fr yttningen avmobiler mellan celler, kanaltilldelningsschema, adaptiv sndning, eektstyrning,etc. En stor mngd algoritmer fr estimering av Dopplerspriding har frslagitsi litteraturen, men det r ovanligt med heltckande jmfrelser mellan med dessaalgoritmer. Drfr r det av stor betydelse att jmfra och utvrdera resultaten avbentliga algoritmer inom ramen fr samma simuleringsvertyg.I denna rapport anvnds upplnken fr WCDMA fr utvrdering av fyra olikatyper av algoritmer fr estimering av Dopplerspridning. Metriker fr utvrderingenr prestanda och implementeringsvnlighet. Bde Rayleigh och Rician fdningskanalmodeller har utvrderas, samt eekten av mobilens hastighet, signaltill brus frhllande, Rician faktor och infallsvinkel i ppet flt scenario. Dessutomhar den berkningsmssiga komplexiteten analyseras fr att utvrdera den praktiskaanvndbarheten i riktiga system.

Indiana University-Purdue University Indianapolis (IUPUI) / Multi-agent systems consist of multiple agents that interact and coordinate with each other to work towards to certain goal. Multi-agent systems naturally arise in a variety of domains such as robotics, telecommunications, and economics. The dynamic and complex nature of these systems entails the agents to learn the optimal solutions on their own instead of following a pre-programmed strategy. Reinforcement learning provides a framework in which agents learn optimal behavior based on the response obtained from the environment. In this thesis, we propose various novel de- centralized, learning automaton based algorithms which can be employed by a group of interacting learning automata. We propose a completely decentralized version of the estimator algorithm. As compared to the completely centralized versions proposed before, this completely decentralized version proves to be a great improvement in terms of space complexity and convergence speed. The decentralized learning algorithm was applied; for the first time; to the domains of distributed object tracking and distributed watershed management. The results obtained by these experiments show the usefulness of the decentralized estimator algorithms to solve complex optimization problems. Taking inspiration from the completely decentralized learning algorithm, we propose the novel concept of partial decentralization. The partial decentralization bridges the gap between the completely decentralized and completely centralized algorithms and thus forms a comprehensive and continuous spectrum of multi-agent algorithms for the learning automata. To demonstrate the applicability of the partial decentralization, we employ a partially decentralized team of learning automata to control multi-agent Markov chains. More flexibility, expressiveness and flavor can be added to the partially decentralized framework by allowing different decentralized modules to engage in different types of games. We propose the novel framework of heterogeneous games of learning automata which allows the learning automata to engage in disparate games under the same formalism. We propose an algorithm to control the dynamic zero-sum games using heterogeneous games of learning automata.

No description available.

No description available.

<p>A decentralized discrete-event system (DES) consists of supervisors that are physically distributed. Co-observability is one of the necessary and sufficient conditions for the existence of a decentralized supervisors that correctly solve the control problem. In this thesis we present a state-based definition of co-observability and introduce algorithms for its verification. Existing algorithms for the verification of co-observability do not scale well, especially when the system is composed of many components. We show that the implementation of our state-based definition leads to more efficient algorithms.</p> <p>We present a set of algorithms that use an existing structure for the verification of state-based co-observability (SB Co-observability). A computational complexity analysis of the algorithms show that the state-based implementation of algorithms result in quadratic complexity. Further improvements come from using a more compact way of representing finite-state machines namely Binary Decision Diagrams (BDD).</p> / Master of Science (MSc)

No / This paper presents a new partitioning strategy with the objective of increasing scalability by reducing computational effort of routing in networks. The original network is partitioned into blocks (subnetworks) so that there is a bi-directional link between any two blocks. When there is a connection request between a pair of nodes, if the nodes are in the same block, we only use the small single block to derive routings. Otherwise we combine the two blocks where the two nodes locate and in this way the whole network will never be used. The strategy is generic in that it can be used in any underlying routing algorithms in the network layer and can be applied to any networks with fixed topology such as fixed wired subnetworks of the Internet. The performance of this strategy has been investigated by building a simulator in Java and a comparison with existing stochastic partitioning techniques is shown to give superior performance in terms of trade-off in blocking probability (the probability of failure to find a path between source and destination satisfying QoS constraints) and reduction of computational effort.