A fibrilação atrial (FA) é um dos tipos mais freqüentes de arritmia cardíaca e é caracterizada principalmente pela aleatoriedade na ocorrência dos batimentos do coração. Sob este aspecto, a fibrilação atrial pode ser considerada um processo estocástico e por isso tem sido freqüentemente modelada através de cadeias de Markov. Seguindo trabalhos anteriores sobre este tópico, este trabalho modela seqüências temporais de batimentos cardíacos como um processo markoviano de três estados para detecção automática de FA. O modelo foi treinado e desenvolvido através dos sinais da base de dados MIT-BIH. Outro método mais consolidado na detecção de FA, denominado \"Razão RR\", também foi implementado, com o objetivo de comparar os resultados do Modelo Markoviano. A avaliação de desempenho para ambos os métodos implementados fo i realizada medindo-se a sensibilidade (Se) e o valor preditivo positivo (+P) para a detecção de FA. Estes dois métodos - Modelos Markovianos e \"Razão RR\" - tiveram seus coeficientes e limiares otimizados com o objetivo de maximizar, ao mesmo tempo, os valores de Se e +P. Após a otimização, ambos os métodos foram testados com uma nova base de dados, independente da base de dados de desenvolvimento. Os resultados obtidos com a base de dados de teste foram Se=84,940% e +P=81,579%, consolidando os Modelos Markoviano s para detecção de batimentos aleatórios. / Atrial fibrillation (AF) is one of the most common cardiac arrhythmia and it is mainly characterized by the presence of random RR intervals. In this way, atrial fibrillation has been studied as a stochastic process and it has been often modeled through Markov chains. Following previous studies on this subject, this work models time sequences of heartbeats as a three states Markov process for AF automatic detection. The model was trained and developed using signals from MIT-BIH database. Another consolidated method for AF detection, called \"RR Ratios\", was also applied to compare Markov Model\'s results. The performance evaluation of both methods was measured through sensitivity (Se) and positive predictive (+P) for AF detection. These two methods - Markov Model and \"RR Ratio\" - had their coefficients and thresholds optimized in order to maximize the values of Se and +P at the same time. After optimization, both methods were tested with another database, independent of development database. The obtained results were Se = 84,940% and +P = 81,579%, consolidating Markov Models for detecting random heartbeats.

Neste trabalho, aplicamos o algoritmo Breadth-First Search para encontrar o tamanho de uma componente conectada no grafo aleatório de Erdos-Rényi. Uma cadeia de Markov é obtida deste procedimento. Apresentamos alguns resultados bem conhecidos sobre o comportamento dessa cadeia de Markov. Combinamos alguns destes resultados para obter uma proposição sobre a probabilidade da componente atingir um determinado tamanho e um resultado de convergência do estado da cadeia neste instante. Posteriormente, aplicamos o teorema de convergência de Darling (2002) a sequência de cadeias de Markov reescaladas e indexadas por N, o número de vértices do grafo, para mostrar que as trajetórias dessas cadeias convergem uniformemente em probabilidade para a solução de uma equação diferencial ordinária. Deste resultado segue a bem conhecida lei fraca dos grandes números para a componente gigante do grafo aleatório de Erdos-Rényi, no caso supercrítico. Além disso, obtemos o limite do fluído para um modelo epidêmico que é uma extensão daquele proposto em Kurtz et al. (2008). / In this work, we apply the Breadth-First Search algorithm to find the size of a connected component of the Erdos-Rényi random graph. A Markov chain is obtained of this procedure. We present some well-known results about the behavior of this Markov chain, and combine some of these results to obtain a proposition about the probability that the component reaches a certain size and a convergence result about the state of the chain at that time. Next, we apply the convergence theorem of Darling (2002) to the sequence of rescaled Markov chains indexed by N, the number of vertices of the graph, to show that the trajectories of these chains converge uniformly in probability to the solution of an ordinary dierential equation. From the latter result follows the well-known weak law of large numbers of the giant component of the Erdos-Renyi random graph, in the supercritical case. Moreover, we obtain the uid limit for an epidemic model which is an extension of that proposed in Kurtz et al. (2008).

Orientador: Prof. Dr. Daniel Miranda Machado / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2017. / O foco principal deste trabalho é o estudo das Cadeias de Markov e das Cadeias de Markov Ocultas. As cadeias de Markov fornecem uma forma prática para o estudo de conceitos probabilísticos e matriciais. Procuramos utilizar de forma contextualizada a aplicação do produto e potência de matrizes associados ao software Geogebra. Além dos exemplos, estão contidas questões de aprendizagem, sempre com objetivo de torná-los aliados e valiosos ao aprendizado referente a este tema. / The main focus of this work is the study of Markov Chains and the Markov Hidden Chains, which in turn brings the study of probabilistic and matrix concepts into practice. We seek to use in a contextualized way the application of the multiplication and potency of matrices associated to the software Geogebra. In addition to the examples, are contained learning issues, always with the goal of making them allies and valuable to the learning related to this theme.

Estudos comportamentais têm sido conduzidos, há séculos, por cientistas e filósofos, abordando assuntos tais como trajetórias de estrelas e planetas, organizações da sociedade, evolução dos seres vivos, comportamento e linguagem humana. Com o advento da computação, grandes quantidades de informação tornaram-se disponíveis, as quais geram novos desafios a fim de explorar e compreender variações comportamentais de interação com esses sistemas. Motivado por esses desafios e pela disponibilidade de informações, esta dissertação de mestrado propõe uma metodologia com objetivo de classificar, detectar e identificar padrões de comportamento. A fim de validar essa metodologia, modelou-se conhecimentos embutidos em informações relativas a interações de usuários durante a grafia digital de assinaturas (tais informações foram obtidas de uma base de dados do campeonato SVC2004 -- First International Signature Verification Competition). Os modelos de conhecimento gerados foram, posteriormente, empregados em experimentos visando o reconhecimento de assinaturas. Resultados obtidos foram comparados a outras abordagens propostas na literatura / Throughout the centuries, behavioral studies have been conducted by scientists and philosophers, approaching subjects such as stars and planet trajectories, social organizations, living beings, human behavior and language. With the advent of computer science, large amounts of information have been made available, which brings out new challenges in the interactive behavior context. Such challenges have motivated this master thesis which proposes a methodology to classify, detect and identify behavioral patterns. A digital signature verification database, obtained from the First International Signature Verification Competition (SVC2004), was used to validate the proposed methodology. Knowledge models were obtained and, afterwards, employed in signature verification experiments. Results were compared to other approaches from the literature

Estudos têm mostrado que nem sempre indivíduos maximizam seus ganhos. Quando confrontados a uma sequência binária, cuja recompensa aparece mais em uma das alternativas, ao invés de perseverarem no lado de maior aparecimento, os voluntários adultos escolhem um lado tantas vezes quanto esse lado apresente a recompensa. Foi relatado, entretanto, que crianças perseverariam no lado mais freqüente, maximizando. Estudos relatam a possibilidade de adultos não perseverarem, porque procurariam padrões na sequência; procurou-se realizar quatro experimentos com sequências sem e com padrões (cadeias de Markov), de modo que se pudesse observar e comparar as estratégias de decisão das faixas etárias para padrão ou sem ele. Os resultados mostraram que existe uma tendência à perseveração, com o envelhecimento, e não o contrário, em detrimento da possibilidade de assimilar padrões. Eles também mostram que a assimilação de padrões se desenvolve gradualmente e decai com o envelhecimento, invalidando a ideia de que a não-maximização seja apenas fruto da busca por padrões. / Studies have shown subjects dont maximize their profits all the time. When confronted with binary sequences, with rewards that show up more in one alternative than another, adult volunteers choose one side as the number of rewards the side shows; instead of maximizing in the side that shows more rewards. However, it was related children maximize. Studies assert to the possibility that adults dont maximize because they are searching for a pattern in the sequence. Four experiments were made with sequences with and without a pattern, so that we could observe and compare the decision making strategies between ages for patterns and non-patterns. Results show a tendency to maximization with aging and not the contrary, how was related, and to the detriment of pattern assimilation possibilities; also results show the pattern finding develops gradually with growth and worse with aging. In this way, searching for patterns cant be the only explanation for the non-maximization behavior.

O labirinto em cruz elevado é muito usado em estudos relacionados à ansiedade em ratos. As medidas tradicionalmente usadas são o número de entradas e o tempo passado nos braços abertos. Trabalhos recentes analisam a movimentação no interior dos braços, mas não propõem um índice que resuma as análises feitas. Esta tese sintetiza as informações de um destes trabalhos em índices. Um dos índices propostos usa os tempos médios de primeira visita a cada posição do labirinto e o outro se baseia na distribuição estacionária de probabilidade, o primeiro é capaz de diferenciar grupos de ratos submetidos a diferentes drogas ansiolíticas. Além disso, a tese propõe um modelo de processo Markoviano que incorpora informações desconsideradas no modelo anterior. A comparação entre os modelos revelou valores super ou subestimados no primeiro. Por fim, esta tese propõe um modelo de cadeias de Markov considerando como estados o seguinte conjunto de comportamentos: \"rearing\", \"stretching\", \"dipping\", \"freezing\" e \"grooming\". Tal abordagem inédita, apesar de simplificar exageradamente o modelo, foi capaz de reproduzir várias características conhecidas da exploração. / The elevated plus maze is widely used in studies related to anxiety in rats. The most widely used measures are the amount of entries and time spent on open arms. Recent studies analyze the movement inside the arms, but do not propose an index that summarizes the analyzes. This thesis summarizes by indices the information in one of these studies. An index uses the first visit average time to each position of the maze and another is based on the stationary probability distribution, the first one are able to differentiate groups of rats submitted to different anxiolytic drugs. These thesis also proposes a Markov process model that incorporates more information than the other model. The comparison between the models showed over- or underestimated values in the first. Finally, this thesis proposes a Markov chains model considering the following behaviors as states: rearing, stretching, dipping, freezing and grooming. This new approach, though oversimplify the model was able to reproduce several known features of exploitation.

Neste trabalho foi elaborada uma estrutura de modelos probabilísticos simples que pudessem descrever o processo de tomada de decisão de agentes humanos que são confrontados com a tarefa de prever elementos de uma sequência aleatória gerada por uma cadeia de Markov de memória L. Essa estrutura partiu de uma abordagem bayesiana em que o agente infere uma distribuição de probabilidades a partir de uma série de observações da sequência e de suas próprias respostas, considerando que o agente tenha uma memória de tamanho K. Como resultado da abordagem bayesiana, o agente adota uma estratégia ótima que consiste na perseveração na alternativa mais provável dado o histórico das últimas tentativas; por conta disso e de observações experimentais de que humanos tendem a adotar nesse tipo de problema estratégias sub-ótimas, por exemplo a de pareamento de probabilidades (probability matching), foram desenvolvidas variações sobre esse modelo que tentassem descrever mais de perto o comportamento adotado por humanos. Nesse sentido, foram adotadas as variáveis de troca de resposta (possível ação tomada pelo agente) e de recompensa (possível resultado da ação) na formulação do modelo e foram adicionados parâmetros, inspirados em modelos de ação dopaminérgica, que permitissem um desvio da estratégia ótima resultante da abordagem bayesiana. Os modelos construídos nessa estrutura foram simulados computacionalmente para diversos valores dos parâmetros, incluindo as memórias K e L do agente e da cadeia de Markov, respectivamente. Através de análises de correlação, esses resultados foram comparados aos dados experimentais, de um grupo de pesquisa do Instituto de Ciências Biomédicas da USP, referentes a tarefas de tomada de decisão envolvendo pessoas de diversas faixas etárias (de 3 a 73 anos) e cadeias de Markov de memórias 0, 1 e 2. Nessa comparação, concluiu-se que as diferenças entre grupos etários no experimento podem ser explicadas em nossa modelagem através da variação da memória K do agente crianças de até 5 anos mostram um limite K = 1, e as de até 12 anos mostram um limite K = 2 e da variação de um parâmetro de reforço de aprendizado dependendo do grupo e da situação de decisão à qual os indivíduos eram expostos, o valor ajustado desse parâmetro variou de 10% para baixo até 30% para cima do seu valor original de acordo com a abordagem bayesiana. / In this work we developed a simple probabilistic modeling framework that could describe the process of decision making in human agents that are presented with the task of predicting elements of a random sequence generated by a Markov chain with memory L. Such framework arised from a Bayesian approach in which the agent infers a probability distribution from a series of observations on the sequence and on its own answers, and considers that the agent\'s memory has length K. As a result of the Bayesian approach, the agent adopts an optimal strategy that consists in perseveration of the most likely alternative given the history of the last few trials; because of that and of experimental evidence that humans tend, in such kinds of problems, to adopt suboptimal strategies such as probability matching, variations on that model were developed in an attempt to have a closer description of the behavior adopted by humans. In that sense, the `shift\' (possible action taken by the agent on its response) and `reward\' (possible result of the action) variables were adopted in the formulation of the model, and parameters inspired by models of dopaminergic action were added to allow deviation from the optimal strategy that resulted from the Bayesian approach. The models developed in that framework were computationally simulated for many values of the parameters, including the agent\'s and the Markov chain\'s memory lengths K and L respectively. Through correlation analysis these results were compared to experimental data, from a research group from the Biomedical Science Institute at USP, regarding decision making tasks that involved people of various ages (3 to 73 years old) and Markov chains of orders 0, 1 and 2. In this comparison it was concluded that the differences between age groups in the experiment can be explained in our modeling through variation of the agent\'s memory length K children up to 5 years old exhibited a limitation of K = 1, and those up to 12 years old were limited to K = 2 and through variation of a learning reinforcement parameter depending on the group and the decision situation to which the candidates were exposed, the fitted value for that parameter ranged from 10% below to 30% above its original value according to the Bayesian approach.

Estudos comportamentais têm sido conduzidos, há séculos, por cientistas e filósofos, abordando assuntos tais como trajetórias de estrelas e planetas, organizações da sociedade, evolução dos seres vivos, comportamento e linguagem humana. Com o advento da computação, grandes quantidades de informação tornaram-se disponíveis, as quais geram novos desafios a fim de explorar e compreender variações comportamentais de interação com esses sistemas. Motivado por esses desafios e pela disponibilidade de informações, esta dissertação de mestrado propõe uma metodologia com objetivo de classificar, detectar e identificar padrões de comportamento. A fim de validar essa metodologia, modelou-se conhecimentos embutidos em informações relativas a interações de usuários durante a grafia digital de assinaturas (tais informações foram obtidas de uma base de dados do campeonato SVC2004 -- First International Signature Verification Competition). Os modelos de conhecimento gerados foram, posteriormente, empregados em experimentos visando o reconhecimento de assinaturas. Resultados obtidos foram comparados a outras abordagens propostas na literatura / Throughout the centuries, behavioral studies have been conducted by scientists and philosophers, approaching subjects such as stars and planet trajectories, social organizations, living beings, human behavior and language. With the advent of computer science, large amounts of information have been made available, which brings out new challenges in the interactive behavior context. Such challenges have motivated this master thesis which proposes a methodology to classify, detect and identify behavioral patterns. A digital signature verification database, obtained from the First International Signature Verification Competition (SVC2004), was used to validate the proposed methodology. Knowledge models were obtained and, afterwards, employed in signature verification experiments. Results were compared to other approaches from the literature

Uma forma de se reduzir o custo (em termos tanto de área de chip quanto de consumo de energia) de algoritmos de processamento de sinais é empregar aritmética de ponto fixo, usando o menor número de bits possível para se representar as variáveis e coeficientes necessários. Com isso, consegue-se reduzir a complexidade do hardware, levando a economias de energia e de área de chip em circuitos dedicados. A escolha do nível de quantização a que cada variável deve ser submetida depende de se conhecer o efeito da quantização de cada variável nas saídas do sistema, o que pode ser conseguido através de simulações (em geral lentas) ou por métodos analíticos. Este documento propõe avanços a uma nova metodologia de análise de algoritmos para processamento digital de sinais implementados em aritmética de ponto fixo, usando modelos baseados em cadeias de Markov. As contribuições desta dissertação são as seguintes: Filtros IIR de primeira e de segunda ordem são analisados via cadeia de Markov, pressupondo que a entrada possui uma função densidade de probabilidade conhecida. O modelo é desenvolvido de forma geral, de forma que pode ser considerada uma função de densidade de probabilidade qualquer. A saída dos filtros é usada para definir os estados da cadeia. O modelo via cadeia de Markov para o coeficiente do algoritmo LMS unidimensional é estendido para entrada correlacionada. Nesse caso, os estados passam a ser descritos em termos do coeficiente e do da entrada anterior. Um exemplo assumido função de densidade de probabilidade de entrada gaussiana para o filtro adaptativo é apresentado. / The implementation cost of signal processing algorithms may be reduced by using fixed-point arithmetic with the smallest possible word-length for each variable or parameter. This allows the designer to reduce hardware complexity, leading to economy of energy and chip area in dedicated circuits. The choice of word-length depends on the determination of the effect at the output of the quantization of each variable, which may be obtained through simulations (generally slow) or through analytical methods. This document proposes new advances to a new analysis method for digital signal processing algorithms implemented in fixed-point arithmetic, based on Markov chain models. Our contributions are the following: A Markov chain model is used to study first and second order IIR filters for an known input density probability function. The model is general and can be applied for any probability function. We use the output of the filters to define the states of the Markov chain. The unidimensional LMS Markov chain model is extended to correlated input. The states are defined by a pair considering the coefficient and the previous input and an example assuming Gaussian-distributed input is presented.

Grande parte do sucesso do Google provêm do algoritmo Page Rank, que avalia quantitativamente a importância de cada página na web. Esta ordenação é obtida através do vetor estacionário de uma matriz estocástica específica, utilizando o Método das Potências. A velocidade de convergência deste método será avaliada em detalhe, já que se trata de uma resposta imediata da pesquisa do usuário. Afim de entender as diferentes situações que o modelo pode enfrentar, diversas simulações são apresentadas neste trabalho. Em particular, estamos interessados nos fatores que influenciam a velocidade de convergência. Para tanto, o número de páginas total e de cada conjunto fechado, bem como o número de conjuntos fechados e de nós pendentes foram estudados. / Great part of Google\'s success comes from the Page Rank algorithm, wich quantitatively evaluates the importance of each page on the web. This sort is achieved through a specific stochastic matrix stationary vector, using the Power Method. The convergency speed of this method will be evaluated in details, since this is a imediate response for the user search. In order to understand the diferent situations the model can confront, several simulations are shown in this work. In particular, we are interested in the factors which influences the convergency speed. For that, the total and inside each closed set number of pages and also the closed sets and dangling nodes numbers were studied.