Orientador: Prof. Dr. Rafael de Mattos Grisi / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2014. / Neste trabalho apresentamos o algoritmo PageRank, usado pela Google para ordenar páginas no resultado de buscas. No primeiro capítulo descrevemos de maneira detalhada as estruturas matemáticas por trás do algoritmo, apresentando uma interpretação probabilística para suas estruturas e resultados. Para melhor entender a matemática do Google, nos capítulos 2 e 3 trabalhamos conceitos básicos de Cadeias de Markov, em especial a noção de medidas invariantes. / In the present work we present the PageRank algorithm, used by Google to sort the search results on the web. At the first chapter we describe in details the mathematical structures behind the algorithm, providing a probabilistic interpretation for it¿s structures and results. For a better understanding of Google¿s math, in chapters 2 and 3 we work on some basic concepts of Markov Chains, specially the notion of invariant measures.

The development of economically viable production systems, which can make compatible good beef cattle profit and the preservation of natural grassland ecosystems, should be supported by knowledge of dynamic of vegetation that occur after some management practices. Vegetation dynamic studies show the existence of populations replacement processes which can be observed in space and time, in different scales. Modeling these systems would be one alternative to achieve this premise. To achieve this purpose, this thesis, is divided in two chapters. In the are presented, respectively, temporal dynamics of grasslands vegetation, based on species composition (taxons) or Plants´ Functional Types (PFT) groups. These were based on the traits: Specific Leaf Area (SLA) e Leaf Dry Matter Content (LDM), which grouped Poaceae family species in four groups (A, B, C and D). Data used in this thesis came from vegetation relévés from 1995 to 2001, and data predict by Markov chains. Typical disturbance factors of grassland vegetation, grazing and burning, and their interactions, combined with relief position, express the scenarios which should be modeled along the time. Results obtained by using ordination and randomization analysis show that is possible using this tool to build up predictive models of vegetation composition in grassland areas, independently from the evaluation being based on taxons or PFT. When it was based in taxons, a certain degree of imprecision in the estimation of forage mass of species with a low initial contribution. Grazing and relief position were determinant of ordination trajectory, and that was not possible to identify in burning. When based in PFTs, results obtained from model validation, from ordination analysis and from randomization tests, showed a tendency of trajectories and of predicted values of functional groups, which is more suitable for plots under grazing. Using this model, as a management tool for areas under grazing, is in dependence of new validation researches, using new data, but for this is necessary to make strong the exchange of informations among research groups in this area. / O desenvolvimento de sistemas de produção viáveis economicamente, que tornem compatíveis bons ganhos animais com a preservação dos ecossistemas de pastagens naturais, deve ser apoiado pelo conhecimento da dinâmica da vegetação que ocorre após determinadas práticas de manejo. Estudos de dinâmica da vegetação revelam processos de substituição de populações, que podem ser observados no espaço e no tempo, em diferentes escalas. A modelagem destes sistemas pode representar uma alternativa para revelar esses processos. Deste modo, a presente tese, está dividida em dois capítulos, sendo abordadas, respectivamente, as dinâmicas temporais da vegetação, baseadas na composição de espécies da área (Táxons) ou dos grupos de Tipos Funcionais de Plantas (TFP). Estes foram baseados nos atributos Área Foliar Específica (AFE) e Teor de Matéria Seca Foliar (TMS), os quais agruparam as espécies pertencentes à família Poaceae, em quatro grupos (A, B, C e D). Os dados utilizados nesta tese foram procedentes de inventários da vegetação, dos anos de 1995 a 2001, e de matrizes de transição das Cadeias de Markov. Os fatores pastejo e queima, e suas interações, combinados com as posições de relevo, foram os fatores de distúrbio que expressam os cenários a serem modelados no tempo. Os resultados obtidos através das análises de ordenação e aleatorização demonstram a aplicabilidade das Cadeias de Markov na construção de modelos preditivos da composição da vegetação em áreas campestres, independentemente da avaliação ser baseada em Taxóns ou TFP. Quando a avaliação foi realizada com base em Táxons, houve certa imprecisão na estimativa de valores de massa de forragem das espécies com baixa contribuição inicial. Os fatores pastejo e posição topográfica apresentaram-se como determinantes das trajetórias de ordenação, o que não foi identificado para o fator queima. Com relação aos TFP, os resultados obtidos na validação do modelo, através das análises de ordenação e aleatorização, indicam uma tendência das trajetórias e dos valores preditos para grupos de TFP, serem mais adequados para as parcelas sobre influencia de pastejo. A difusão deste modelo, como ferramenta de manejo das áreas sobre pastejo, depende ainda de novas validações, utilizandose novos grupos de dados, para isso se torna necessário o fortalecimento do intercâmbio de informações entre os grupos de pesquisa nesta área.

Este trabalho apresenta um modelo analítico para a análise de vazão (throughput) da camada MAC do IEEE 802.11. A proposta se diferencia da maioria dos desenvolvimentos realizados na área por apresentar uma modelagem de ambientes com estações não-saturadas, levando em consideração o perfil do tráfego gerado pelas camadas superiores ao nível de enlace. Dessa maneira, o modelo permite uma análise do desempenho de aplicações reais sobre redes sem fio, a partir de resultados provenientes de um modelo matemático, enquanto diversos outros trabalhos avaliam somente situações de saturação das estações. Simulações utilizando Network Simulator 2 e comparações com resultados obtidos em trabalhos análogos desenvolvidos por outros pesquisadores validam o modelo proposto. Cenários com variações na quantidade de estações e carga oferecida à rede são avaliados utilizando o modelo teórico e comparados aos resultados simulados, provendo uma análise do comportamento dos limites de vazão do sistema. As estruturas do IEEE 802.11 MAC foram estudadas a fim de embasar o desenvolvimento do modelo proposto. Também foi realizada uma pesquisa a respeito de Cadeias de Markov, que serve como estrutura básica para a descrição do IEEE 802.11 DCF. / This work provides an analytical model to compute the IEEE 802.11 DCF throughput. The proposed analysis differs from most of the related work by presenting scenario modeling with unsaturated stations, accounting for the traffic characteristics generated by the upper layers to the data link layer. As a consequence, the proposed model allows for an accurate analysis of real applications over wireless networks, based on mathematical model results, while several other researches evaluate only saturate stations situations. Simulations ran using Network Simulator 2 and comparisons with results obtained on similar works developed by other researchers are used to validate the proposed model. Scenarios with different number of stations and offered loads are evaluated using the theoretical model and compared to the simulated results, providing an analysis on the behavior of the maximum throughput provided by the network. A study was made on the structures and mechanisms of IEEE 802.11 MAC in order to support the development of the proposed model. A research on Markov Chains was also done, since it is the basic structure used to describe the IEEE 802.11 DCF.

abstract: In the study of regional economic growth and convergence, the distribution dynamics approach which interrogates the evolution of the cross-sectional distribution as a whole and is concerned with both the external and internal dynamics of the distribution has received wide usage. However, many methodological issues remain to be resolved before valid inferences and conclusions can be drawn from empirical research. Among them, spatial effects including spatial heterogeneity and spatial dependence invalidate the assumption of independent and identical distributions underlying the conventional maximum likelihood techniques while the availability of small samples in regional settings questions the usage of the asymptotic properties. This dissertation is comprised of three papers targeted at addressing these two issues. The first paper investigates whether the conventional regional income mobility estimators are still suitable in the presence of spatial dependence and/or a small sample. It is approached through a series of Monte Carlo experiments which require the proposal of a novel data generating process (DGP) capable of generating spatially dependent time series. The second paper moves to the statistical tests for detecting specific forms of spatial (spatiotemporal) effects in the discrete Markov chain model, investigating their robustness to the alternative spatial effect, sensitivity to discretization granularity, and properties in small sample settings. The third paper proposes discrete kernel estimators with cross-validated bandwidths as an alternative to maximum likelihood estimators in small sample settings. It is demonstrated that the performance of discrete kernel estimators offers improvement when the sample size is small. Taken together, the three papers constitute an endeavor to relax the restrictive assumptions of spatial independence and spatial homogeneity, as well as demonstrating the difference between the small sample and asymptotic properties for conventionally adopted maximum likelihood estimators towards a more valid inferential framework for the distribution dynamics approach to the study of regional economic growth and convergence. / Dissertation/Thesis / Doctoral Dissertation Geography 2018

This thesis deals with discrete-time Markov jump linear systems (MJLS) with Markov chain in a general Borel space S. Several control issues have been addressed for this class of dynamic systems, including stochastic stability (SS), linear quadratic (LQ) optimal control synthesis, fllter design and a separation principle. Necessary and sffcient conditions for SS have been derived. It was shown that SS is equivalent to the spectral radius of an operator being less than 1 or to the existence of a solution to a \\Lyapunov-like\" equation. Based on the SS concept, the finite- and infinite-horizon LQ optimal control problems were tackled. The solution to the finite- (infinite-)horizon LQ optimal control problem was derived from the associated control S-coupled Riccati difference (algebraic) equations. By S-coupled it is meant that the equations are coupled via an integral over a transition probability kernel having a density with respect to a in-finite measure on the Borel space S. The design of linear Markov jump filters was analyzed and a solution to the finite- (infinite-)horizon filtering problem was obtained based on the associated filtering S-coupled Riccati difference (algebraic) equations. Conditions for the existence and uniqueness of a stabilizing positive semi-definite solution to the control and filtering S-coupled algebraic Riccati equations have also been derived. Finally a separation principle for discrete-time MJLS with Markov chain in a general state space was obtained. It was shown that the optimal controller for a partial information optimal control problem separates the partial information control problem into two problems, one associated with a filtering problem and the other associated with an optimal control problem with complete information. It is expected that the results obtained in this thesis may motivate further research on discrete-time MJLS with Markov chain in a general state space. / Esta tese trata de sistemas lineares com saltos markovianos (MJLS) a tempo discreto com cadeia de Markov em um espaço geral de Borel S. Vários problemas de controle foram abordados para esta classe de sistemas dinâmicos, incluindo estabilidade estocástica (SS), síntese de controle ótimo linear quadrático (LQ), projeto de filtros e um princípio da separação. Condições necessárias e suficientes para a SS foram obtidas. Foi demonstrado que SS é equivalente ao raio espectral de um operador ser menor que 1 ou à existência de uma solução para uma equação de Lyapunov. Os problemas de controle ótimo a horizonte finito e infinito foram abordados com base no conceito de SS. A solução para o problema de controle ótimo LQ a horizonte finito (infinito) foi obtida a partir das associadas equações a diferenças (algébricas) de Riccati S-acopladas de controle. Por S-acopladas entende-se que as equações são acopladas por uma integral sobre o kernel estocástico com densidade de transição em relação a uma medida in-finita no espaço de Borel S. O projeto de filtros lineares markovianos foi analisado e uma solução para o problema da filtragem a horizonte finito (infinito) foi obtida com base nas associadas equações a diferenças (algébricas) de Riccati S-acopladas de filtragem. Condições para a existência e unicidade de uma solução positiva semi-definida e estabilizável para as equações algébricas de Riccati S-acopladas associadas aos problemas de controle e filtragem também foram obtidas. Por último, foi estabelecido um princípio da separação para MJLS a tempo discreto com cadeia de Markov em um espaço de estados geral. Foi demonstrado que o controlador ótimo para um problema de controle ótimo com informação parcial separa o problema de controle com informação parcial em dois problemas, um deles associado a um problema de filtragem e o outro associado a um problema de controle ótimo com informação completa. Espera-se que os resultados obtidos nesta tese possam motivar futuras pesquisas sobre MJLS a tempo discreto com cadeia de Markov em um espaço de estados geral.

Este trabalho apresenta um modelo analítico para a análise de vazão (throughput) da camada MAC do IEEE 802.11. A proposta se diferencia da maioria dos desenvolvimentos realizados na área por apresentar uma modelagem de ambientes com estações não-saturadas, levando em consideração o perfil do tráfego gerado pelas camadas superiores ao nível de enlace. Dessa maneira, o modelo permite uma análise do desempenho de aplicações reais sobre redes sem fio, a partir de resultados provenientes de um modelo matemático, enquanto diversos outros trabalhos avaliam somente situações de saturação das estações. Simulações utilizando Network Simulator 2 e comparações com resultados obtidos em trabalhos análogos desenvolvidos por outros pesquisadores validam o modelo proposto. Cenários com variações na quantidade de estações e carga oferecida à rede são avaliados utilizando o modelo teórico e comparados aos resultados simulados, provendo uma análise do comportamento dos limites de vazão do sistema. As estruturas do IEEE 802.11 MAC foram estudadas a fim de embasar o desenvolvimento do modelo proposto. Também foi realizada uma pesquisa a respeito de Cadeias de Markov, que serve como estrutura básica para a descrição do IEEE 802.11 DCF. / This work provides an analytical model to compute the IEEE 802.11 DCF throughput. The proposed analysis differs from most of the related work by presenting scenario modeling with unsaturated stations, accounting for the traffic characteristics generated by the upper layers to the data link layer. As a consequence, the proposed model allows for an accurate analysis of real applications over wireless networks, based on mathematical model results, while several other researches evaluate only saturate stations situations. Simulations ran using Network Simulator 2 and comparisons with results obtained on similar works developed by other researchers are used to validate the proposed model. Scenarios with different number of stations and offered loads are evaluated using the theoretical model and compared to the simulated results, providing an analysis on the behavior of the maximum throughput provided by the network. A study was made on the structures and mechanisms of IEEE 802.11 MAC in order to support the development of the proposed model. A research on Markov Chains was also done, since it is the basic structure used to describe the IEEE 802.11 DCF.

Orientador: Furio Damiani / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-21T21:06:15Z (GMT). No. of bitstreams: 1 Feijao_PedroCipriano_M.pdf: 2409509 bytes, checksum: ef809fef536991065abf131c6a599340 (MD5) Previous issue date: 2004 / Resumo: Um levantamento detalhado dos trabalhos em composição computacional será apresentado. Um algoritmo de composição e performance em tempo real de solos de jazz foi criado, inspirado no estilo bebop. Técnicas utilizadas por músicos de bebop durante os seus improvisos foram implementadas usando-se várias regras. Um novo modelo estocástico, baseado no raciocínio de um músico durante o seu solo, escolhe a saída do algoritmo. O usuário pode avaliar a saída do algoritmo em tempo-real, e isto será utilizado em um processo de aprendizado supervisionado para modificar os parâmetros do modelo estocástico. Algumas amostras de saídas do algoritmo serão mostradas, junto com as conclusões / Abstract: An extensive review of the most prominent works in the field of computer music is presented. A real-time algorithm for composition and performance of jazz solos in the style of bebop was created. Techniques that bebop musicians use on their solos were implemented using several rules. A new stochastic model, inspired by the thinking of a musician during his solo chooses the algorithm output. The user evaluates the algorithm output in real-time, and this input is used in a supervised learning process to change the stochastic model parameters. Samplings of the algorithm output are shown, along with concluding remarks / Mestrado / Eletrônica, Microeletrônica e Optoeletrônica / Mestre em Engenharia Elétrica

Cette thèse contient des preuves de convergence ou de divergence d'algorithmes d'optimisation appelés stratégies d'évolution (ESs), ainsi que le développement d'outils mathématiques permettant ces preuves.Les ESs sont des algorithmes d'optimisation stochastiques dits ``boîte noire'', i.e. où les informations sur la fonction optimisée se réduisent aux valeurs qu'elle associe à des points. En particulier, le gradient de la fonction est inconnu. Des preuves de convergence ou de divergence de ces algorithmes peuvent être obtenues via l'analyse de chaînes de Markov sous-jacentes à ces algorithmes. Les preuves de convergence et de divergence obtenues dans cette thèse permettent d'établir le comportement asymptotique des ESs dans le cadre de l'optimisation d'une fonction linéaire avec ou sans contrainte, qui est un cas clé pour des preuves de convergence d'ESs sur de larges classes de fonctions.Cette thèse présente tout d'abord une introduction aux chaînes de Markov puis un état de l'art sur les ESs et leur contexte parmi les algorithmes d'optimisation continue boîte noire, ainsi que les liens établis entre ESs et chaînes de Markov. Les contributions de cette thèse sont ensuite présentées:o Premièrement des outils mathématiques généraux applicables dans d'autres problèmes sont développés. L'utilisation de ces outils permet d'établir aisément certaines propriétés (à savoir l'irreducibilité, l'apériodicité et le fait que les compacts sont des small sets pour la chaîne de Markov) sur les chaînes de Markov étudiées. Sans ces outils, établir ces propriétés était un processus ad hoc et technique, pouvant se montrer très difficile.o Ensuite différents ESs sont analysés dans différents problèmes. Un (1,\lambda)-ES utilisant cumulative step-size adaptation est étudié dans le cadre de l'optimisation d'une fonction linéaire. Il est démontré que pour \lambda > 2 l'algorithme diverge log-linéairement, optimisant la fonction avec succès. La vitesse de divergence de l'algorithme est donnée explicitement, ce qui peut être utilisé pour calculer une valeur optimale pour \lambda dans le cadre de la fonction linéaire. De plus, la variance du step-size de l'algorithme est calculée, ce qui permet de déduire une condition sur l'adaptation du paramètre de cumulation avec la dimension du problème afin d'obtenir une stabilité de l'algorithme. Ensuite, un (1,\lambda)-ES avec un step-size constant et un (1,\lambda)-ES avec cumulative step-size adaptation sont étudiés dans le cadre de l'optimisation d'une fonction linéaire avec une contrainte linéaire. Avec un step-size constant, l'algorithme résout le problème en divergeant lentement. Sous quelques conditions simples, ce résultat tient aussi lorsque l'algorithme utilise des distributions non Gaussiennes pour générer de nouvelles solutions. En adaptant le step-size avec cumulative step-size adaptation, le succès de l'algorithme dépend de l'angle entre les gradients de la contrainte et de la fonction optimisée. Si celui ci est trop faible, l'algorithme convergence prématurément. Autrement, celui ci diverge log-linéairement.Enfin, les résultats sont résumés, discutés, et des perspectives sur des travaux futurs sont présentées. / In this dissertation an analysis of Evolution Strategies (ESs) using the theory of Markov chains is conducted. Proofs of divergence or convergence of these algorithms are obtained, and tools to achieve such proofs are developed.ESs are so called "black-box" stochastic optimization algorithms, i.e. information on the function to be optimized are limited to the values it associates to points. In particular, gradients are unavailable. Proofs of convergence or divergence of these algorithms can be obtained through the analysis of Markov chains underlying these algorithms. The proofs of log-linear convergence and of divergence obtained in this thesis in the context of a linear function with or without constraint are essential components for the proofs of convergence of ESs on wide classes of functions.This dissertation first gives an introduction to Markov chain theory, then a state of the art on ESs and on black-box continuous optimization, and present already established links between ESs and Markov chains.The contributions of this thesis are then presented:o General mathematical tools that can be applied to a wider range of problems are developed. These tools allow to easily prove specific Markov chain properties (irreducibility, aperiodicity and the fact that compact sets are small sets for the Markov chain) on the Markov chains studied. Obtaining these properties without these tools is a ad hoc, tedious and technical process, that can be of very high difficulty.o Then different ESs are analyzed on different problems. We study a (1,\lambda)-ES using cumulative step-size adaptation on a linear function and prove the log-linear divergence of the step-size; we also study the variation of the logarithm of the step-size, from which we establish a necessary condition for the stability of the algorithm with respect to the dimension of the search space. Then we study an ES with constant step-size and with cumulative step-size adaptation on a linear function with a linear constraint, using resampling to handle unfeasible solutions. We prove that with constant step-size the algorithm diverges, while with cumulative step-size adaptation, depending on parameters of the problem and of the ES, the algorithm converges or diverges log-linearly. We then investigate the dependence of the convergence or divergence rate of the algorithm with parameters of the problem and of the ES. Finally we study an ES with a sampling distribution that can be non-Gaussian and with constant step-size on a linear function with a linear constraint. We give sufficient conditions on the sampling distribution for the algorithm to diverge. We also show that different covariance matrices for the sampling distribution correspond to a change of norm of the search space, and that this implies that adapting the covariance matrix of the sampling distribution may allow an ES with cumulative step-size adaptation to successfully diverge on a linear function with any linear constraint.Finally, these results are summed-up, discussed, and perspectives for future work are explored.

La généralisation des mélangeurs continu dans l'industrie est freinée par le manque de connaissance générale sur ces procédés et en particulier d'une stratégie de contrôle commande de ce procédé. Se plaçant dans cette perspective, ce travail se penche, tant du point du vue expérimental et modélisation, sur la dynamique du procédé de mélange en continu, en particulier durant les phases transitoires que sont le démarrage, la vidange ou le changement de consigne. On étudie l'effet des variables opératoires, vitesse d'agitation et débit, sur la répartition massique et les débits internes des particules dans le mélangeur, ainsi que sur les variations d'homogénéité du mélange en sortie. A ce titre, un protocole expérimental spécifique basé sur l'analyse d'images est développé pour mesurer en ligne la qualité du mélange à une échelle d'observation que l'on peut ajuster. Un cadre de modélisation Markovienne est proposé pour décrire les phénomènes observés aux échelles macro et méso. Le modèle permet de décrire la composition du mélange dans les différentes zones du mélangeur ainsi qu'en sortie de l'appareil, quel que soit le régime envisagé, notamment lors de fortes perturbations de vitesse de rotation, dont l'intérêt est discuté. / The implementation of a continuous mixer in the industry requires detailed studies for a better understanding of this process, with essential aim the development of a control process strategy. The present work reports experimental and modelling results concerning the dynamics of a continuous powder mixer in steady and unsteady states. In particular, we will focus on the transitory phases that are likely to occur : starting, emptying, feeder's feeding, accidental perturbation, etc. We investigate the effect of operating variables, as rotational speed of the stirrer and the inflow rate, on the distribution of particles mass in the mixer and the intermediates flow rates, as well as that of the homogeneity of binary mixtures at the outlet of continuous mixer. A specific experimental protocol, based on image analysis, has been developed for determining mixture quality. The scale of scrutiny can be adjusted and mixture homogeneity can be calculated for this scale in real time. AMarkov chain model is proposed to describe the phenomena observed at both macro-and meso-scales. The model allows to describe the composition of the mixture in different zones of the mixer as well as in the outlet of the vessel, during steady and unsteady regimes and especially at high speed perturbations, whose interest is discussed.

Esta dissertação aborda o problema de redução do consumo de combustível para veículos. Com esse objetivo, realiza-se o levantamento de um modelo estocástico e de seus parâmetros, o desenvolvimento de um controlador para o veículo, e análise dos resultados. O problema considera a interação com o trânsito de outros veículos, que limita a aplicação de resultados antes disponíveis. Para isto, propõe-se modelar a dinâmica do problema de maneira aproximada, usando sistemas com saltos markovianos, e levantar as probabilidades de transição dos estados da cadeia através de um modelo mais completo para o trânsito no percurso. / This dissertation deals with control of vehicles aiming at the fuel consumption optimization, taking into account the interference of traffic. Stochastic interferences like this and other real world phenomena prevents us from directly applying available results. We propose to employ a relatively simple system with Markov jumping parameters as a model for the vehicle subject to traffic interference, and to obtain the transition probabilities from a separate model for the traffic. This dissertation presents the model identification, the solution of the new problem using dynamic programming, and simulation of the obtained control.