Considere um meio desordenado formado por $N$ pontos cujas coordenadas são geradas aleatoriamente com probabilidade uniforme ao longo das arestas unitárias de um hipercubo de $d$ dimensões. Um caminhante, partindo de um ponto qualquer desse meio, se desloca seguindo a regra determinista de dirigir-se sempre ao ponto mais próximo que não tenha sido visitado nos últimos $\\mu$ passos. Esta dinâmica de movimentação, denominada caminhada determinista do turista, leva a trajetórias formadas por uma parte inicial transiente de $t$ pontos, e uma parte final cíclica de $p$ pontos. A exploração do meio se limita aos $t+p$ pontos percorridos na trajetória. O sucesso da exploração depende do valor da memória $\\mu$ do viajante. Para valores pequenos de $\\mu$ a exploração é altamente localizada e o sistema não é satisfatoriamente explorado. Já para $\\mu$ da ordem de $N$, aparecem ciclos longos, permitindo a exploração global do meio. O objetivo deste estudo é determinar o valor de memória $\\mu_1$ para o qual ocorre uma transição abrupta no comportamento exploratório do turista em meios unidimensionais. Procuramos também entender a distribuição da posição final do turista após atingir um estado estacionário que é atingido quando o turista fica aprisionado nos ciclos. Os resultados obtidos por simulações numéricas e por um tratamento analítico mostram que $\\mu_1 = \\log_2 N$. O estudo também mostrou a existência de uma região de transição com largura $\\varepsilon = e/ \\ln 2$ constante, caracterizando uma transição aguda de fase no comportamento exploratório do turista em uma dimensão. A análise do estado estacionário da caminhada em função da memória mostrou que, para $\\mu$ distante de $\\mu_1$, a dinâmica de exploração ocorre como um processo difusivo tradicional (distribuição gaussiana). Já para $\\mu$ próximo de $\\mu_1$ (região de transição), essa dinâmica segue um processo superdifusivo não-linear, caracterizado por distribuições $q$-gaussianas e distribuições $\\alpha$-estáveis de Lévy. Neste processo, o parâmetro $q$ funciona como parâmetro de ordem da transição. / Consider a disordered medium formed by $N$ point whose coordinates are randomly generated with uniform probability along the unitary edges of a $d$-dimensional hypercube. A walker, starting to walk from any point of that medium, moves following the deterministic rule of always going to the nearest point that has not been visited in the last $\\mu$ steps. This dynamic of moving, called deterministic tourist walk, leads to trajectories formed by a initial transient part of $t$ points and a final cycle of $p$ points. The exploration of the medium is limited to the $t+p$ points covered. The success of the exploration depends on the traveler\'s memory value $\\mu$. For small values of $\\mu$, the exploration is highly localized and the whole system remains unexplored. For values of $\\mu$ of the order of $N$, however, long cycles appear, allowing global exploration of the medium. The objective of this study is to determine the memory value $\\mu_1$ for which a sharp transition in the exploratory behavior of the tourist in one-dimensional media occurs. We also want to understand the distribution of the final position of the tourist after reaches a steady state in exploring the medium. That steady state is reached when the tourist is trapped in cycles. The results achieved by numerical simulations and analytical treatment has shown that $\\mu_1 = \\log_2 N$. The study has also shown the existence of a transition region, with a constant width of $\\varepsilon = e/ \\ln 2$, characterizing a phase transition in the exploratory behavior of the tourist in one dimension. The analysis of the walk steady state as a function of the memory has shown that for $\\mu$ far from $\\mu_1$, the exploratory dynamic follows a traditional diffusion process (with gaussian distribution). In the other hand, for $\\mu$ near $\\mu_1$ (transition region), the dynamic follows a non-linear superdiffusion process, characterized by $q$-gaussian distributions and Lèvy $\\alpha$-stable distributions. In this process, the parameter $q$ plays the role of a transition order parameter.

A caminhada do turista pode ser enunciada num meio desordenado formado por N pontos espalhados aleatoriamente num hipercubo de d dimensoes. Um caminhante, partindo de um ponto qualquer desse meio, se desloca seguindo a regra determinista de dirigir-se sempre ao ponto mais proximo que nao tenha sido visitado nos ultimos µ pas- sos. Esta dinamica de movimentacao leva a trajetorias formadas por uma parte inicial transiente de t pontos, e uma parte final c?clica de p pontos. As trajetorias obtidas sao altamente dependentes da configuracao do meio. Este cenario sugere que este modelo possa ser usado como uma ferramenta de reconhecimento de padroes em conjuntos de dados. O objetivo desta tese e mostrar que as propriedades da caminhada do turista permitem a sua utilizacao na caracterizacao e exploracao de diversos tipos de sistemas. Aplicamos o modelo descrito em dois tipos distintos de sistemas, sistemas cont´?nuos e redes regulares, estudando suas ropriedades em funcao de parametros como tamanho do sistema, valor de memoria (µ), condicoes de contorno e regras de movimentacao. Finalmente, propomos e exploramos duas novas metodologias de reconhecimento de padroes baseadas nesta caminhada. A primeira consiste de um algoritmo de an´alise de imagens para caracterizar texturas que utiliza os resultados da matriz conjunta S(t, p) que carrega as informacoes sobre todas as trajetorias obtidas, reduzindo sua dimensionalidade e permitindo a classificacao eficiente de diferentes classes de imagens por um algoritmo de analise discriminante. O diferencial desta metodologia esta em sua capacidade de extrair da imagem as informacoes presentes em diversas escalas simultaneamente. A segunda metodologia e um algoritmo de agrupamento de dados n~ao supervisionado que considera cada atrator formado num dado valor de µ como um agrupamento natural e tem como resultado final uma arvore hierarquica geral, onde os grupos se conectam conforme se aumenta o valor de µ. Os resultados desta metodologia comparam-se em eficiencia aos resultados obtidos pela metodologia adicional para os dados testados e, entre as vanta- gens obtidas, podemos citar (i) independencia de uma metrica relacionando os elementos do conjunto, ja que trabalha apenas com uma matriz de vizinhancas, (ii) respeito a estrutura natural embutida no conjunto de dados, gerando uma arvore geral ao inves de uma arvore binaria e (iii) a representacao de maneira identica de conjuntos que sofreram transformacao de escala devido a independencia de uma metrica. / The tourist walk is defined in a disordered environment characterized by N points randomly distributed in a d-dimensional hypercube. Leaving from a given point, a wal- ker moves according to the deterministic rule of going to next point not visited in the last µ time steps. This dynamics leads to trajectories consisting in a transient part of t points e a final cyclic part of p points. The obtained trajectories are strongly dependent on the configuration of points. This described scenario suggests that the model can be treated as a tool for pattern recognition. The aim of this thesis is to demonstrate that the tourist walk\'s properties allow for its use in the characterization and exploration of various kinds of systems. We have applied the model in two distinct kinds of systems - continuous systems and regular networks and studied its properties as a function of the following parameters: system size, memory (µ), boundary conditions and movimentation rule. Eventually we have proposed and explored two new pattern recognition methodolo- gies based on this deterministic walk. The first one consists of an image analysis algorithm to characterize textures that makes use of the joint matrix S(t, p) which carries the data about all trajectories obtained, reducing its dimensionality and allowing an efficient clas- sification of different classes of images by a discriminant analysis algorithm. Its distinctive feature is its ability to extract informations in all scales from an image simultaneously. The second methodology proposed is a non-supervised clustering algorithm that considers each attractor in a given µ as a natural cluster. Its final result is a general hierarchical tree where groups coalesce as µ is increased. The results obtained with this methodology are comparable in efficiency with the results obtained with the tradicional method for the datasets tested. Among the advantages presented we can cite (i) independence from a metrics relating the elements since it works only with a neighborhood ranking table, (ii) respect for the natural structure hidden in the dataset, generating a general tree instead of a binary one and (iii) the representation of two sets transformed by scale in an identic manner due to the independence from a metrics.

Considere um meio desordenado formado por $N$ pontos cujas coordenadas são geradas aleatoriamente com probabilidade uniforme ao longo das arestas unitárias de um hipercubo de $d$ dimensões. Um caminhante, partindo de um ponto qualquer desse meio, se desloca seguindo a regra determinista de dirigir-se sempre ao ponto mais próximo que não tenha sido visitado nos últimos $\\mu$ passos. Esta dinâmica de movimentação, denominada caminhada determinista do turista, leva a trajetórias formadas por uma parte inicial transiente de $t$ pontos, e uma parte final cíclica de $p$ pontos. A exploração do meio se limita aos $t+p$ pontos percorridos na trajetória. O sucesso da exploração depende do valor da memória $\\mu$ do viajante. Para valores pequenos de $\\mu$ a exploração é altamente localizada e o sistema não é satisfatoriamente explorado. Já para $\\mu$ da ordem de $N$, aparecem ciclos longos, permitindo a exploração global do meio. O objetivo deste estudo é determinar o valor de memória $\\mu_1$ para o qual ocorre uma transição abrupta no comportamento exploratório do turista em meios unidimensionais. Procuramos também entender a distribuição da posição final do turista após atingir um estado estacionário que é atingido quando o turista fica aprisionado nos ciclos. Os resultados obtidos por simulações numéricas e por um tratamento analítico mostram que $\\mu_1 = \\log_2 N$. O estudo também mostrou a existência de uma região de transição com largura $\\varepsilon = e/ \\ln 2$ constante, caracterizando uma transição aguda de fase no comportamento exploratório do turista em uma dimensão. A análise do estado estacionário da caminhada em função da memória mostrou que, para $\\mu$ distante de $\\mu_1$, a dinâmica de exploração ocorre como um processo difusivo tradicional (distribuição gaussiana). Já para $\\mu$ próximo de $\\mu_1$ (região de transição), essa dinâmica segue um processo superdifusivo não-linear, caracterizado por distribuições $q$-gaussianas e distribuições $\\alpha$-estáveis de Lévy. Neste processo, o parâmetro $q$ funciona como parâmetro de ordem da transição. / Consider a disordered medium formed by $N$ point whose coordinates are randomly generated with uniform probability along the unitary edges of a $d$-dimensional hypercube. A walker, starting to walk from any point of that medium, moves following the deterministic rule of always going to the nearest point that has not been visited in the last $\\mu$ steps. This dynamic of moving, called deterministic tourist walk, leads to trajectories formed by a initial transient part of $t$ points and a final cycle of $p$ points. The exploration of the medium is limited to the $t+p$ points covered. The success of the exploration depends on the traveler\'s memory value $\\mu$. For small values of $\\mu$, the exploration is highly localized and the whole system remains unexplored. For values of $\\mu$ of the order of $N$, however, long cycles appear, allowing global exploration of the medium. The objective of this study is to determine the memory value $\\mu_1$ for which a sharp transition in the exploratory behavior of the tourist in one-dimensional media occurs. We also want to understand the distribution of the final position of the tourist after reaches a steady state in exploring the medium. That steady state is reached when the tourist is trapped in cycles. The results achieved by numerical simulations and analytical treatment has shown that $\\mu_1 = \\log_2 N$. The study has also shown the existence of a transition region, with a constant width of $\\varepsilon = e/ \\ln 2$, characterizing a phase transition in the exploratory behavior of the tourist in one dimension. The analysis of the walk steady state as a function of the memory has shown that for $\\mu$ far from $\\mu_1$, the exploratory dynamic follows a traditional diffusion process (with gaussian distribution). In the other hand, for $\\mu$ near $\\mu_1$ (transition region), the dynamic follows a non-linear superdiffusion process, characterized by $q$-gaussian distributions and Lèvy $\\alpha$-stable distributions. In this process, the parameter $q$ plays the role of a transition order parameter.

A caminhada do turista pode ser enunciada num meio desordenado formado por N pontos espalhados aleatoriamente num hipercubo de d dimensoes. Um caminhante, partindo de um ponto qualquer desse meio, se desloca seguindo a regra determinista de dirigir-se sempre ao ponto mais proximo que nao tenha sido visitado nos ultimos µ pas- sos. Esta dinamica de movimentacao leva a trajetorias formadas por uma parte inicial transiente de t pontos, e uma parte final c?clica de p pontos. As trajetorias obtidas sao altamente dependentes da configuracao do meio. Este cenario sugere que este modelo possa ser usado como uma ferramenta de reconhecimento de padroes em conjuntos de dados. O objetivo desta tese e mostrar que as propriedades da caminhada do turista permitem a sua utilizacao na caracterizacao e exploracao de diversos tipos de sistemas. Aplicamos o modelo descrito em dois tipos distintos de sistemas, sistemas cont´?nuos e redes regulares, estudando suas ropriedades em funcao de parametros como tamanho do sistema, valor de memoria (µ), condicoes de contorno e regras de movimentacao. Finalmente, propomos e exploramos duas novas metodologias de reconhecimento de padroes baseadas nesta caminhada. A primeira consiste de um algoritmo de an´alise de imagens para caracterizar texturas que utiliza os resultados da matriz conjunta S(t, p) que carrega as informacoes sobre todas as trajetorias obtidas, reduzindo sua dimensionalidade e permitindo a classificacao eficiente de diferentes classes de imagens por um algoritmo de analise discriminante. O diferencial desta metodologia esta em sua capacidade de extrair da imagem as informacoes presentes em diversas escalas simultaneamente. A segunda metodologia e um algoritmo de agrupamento de dados n~ao supervisionado que considera cada atrator formado num dado valor de µ como um agrupamento natural e tem como resultado final uma arvore hierarquica geral, onde os grupos se conectam conforme se aumenta o valor de µ. Os resultados desta metodologia comparam-se em eficiencia aos resultados obtidos pela metodologia adicional para os dados testados e, entre as vanta- gens obtidas, podemos citar (i) independencia de uma metrica relacionando os elementos do conjunto, ja que trabalha apenas com uma matriz de vizinhancas, (ii) respeito a estrutura natural embutida no conjunto de dados, gerando uma arvore geral ao inves de uma arvore binaria e (iii) a representacao de maneira identica de conjuntos que sofreram transformacao de escala devido a independencia de uma metrica. / The tourist walk is defined in a disordered environment characterized by N points randomly distributed in a d-dimensional hypercube. Leaving from a given point, a wal- ker moves according to the deterministic rule of going to next point not visited in the last µ time steps. This dynamics leads to trajectories consisting in a transient part of t points e a final cyclic part of p points. The obtained trajectories are strongly dependent on the configuration of points. This described scenario suggests that the model can be treated as a tool for pattern recognition. The aim of this thesis is to demonstrate that the tourist walk\'s properties allow for its use in the characterization and exploration of various kinds of systems. We have applied the model in two distinct kinds of systems - continuous systems and regular networks and studied its properties as a function of the following parameters: system size, memory (µ), boundary conditions and movimentation rule. Eventually we have proposed and explored two new pattern recognition methodolo- gies based on this deterministic walk. The first one consists of an image analysis algorithm to characterize textures that makes use of the joint matrix S(t, p) which carries the data about all trajectories obtained, reducing its dimensionality and allowing an efficient clas- sification of different classes of images by a discriminant analysis algorithm. Its distinctive feature is its ability to extract informations in all scales from an image simultaneously. The second methodology proposed is a non-supervised clustering algorithm that considers each attractor in a given µ as a natural cluster. Its final result is a general hierarchical tree where groups coalesce as µ is increased. The results obtained with this methodology are comparable in efficiency with the results obtained with the tradicional method for the datasets tested. Among the advantages presented we can cite (i) independence from a metrics relating the elements since it works only with a neighborhood ranking table, (ii) respect for the natural structure hidden in the dataset, generating a general tree instead of a binary one and (iii) the representation of two sets transformed by scale in an identic manner due to the independence from a metrics.

A análise de texturas dinâmicas tem se apresentado como uma área de pesquisa crescente e em potencial nos últimos anos em visão computacional. As texturas dinâmicas são sequências de imagens de textura (i.e. vídeo) que representam objetos dinâmicos. Exemplos de texturas dinâmicas são: evolução de colônia de bactérias, crescimento de tecidos do corpo humano, escada rolante em movimento, cachoeiras, fumaça, processo de corrosão de metal, entre outros. Apesar de existirem pesquisas relacionadas com o tema e de resultados promissores, a maioria dos métodos da literatura possui limitações. Além disso, em muitos casos as texturas dinâmicas são resultado de fenômenos complexos, tornando a tarefa de caracterização um desafio ainda maior. Esse cenário requer o desenvolvimento de um paradigma de métodos baseados em complexidade. A complexidade pode ser compreendida como uma medida de irregularidade das texturas dinâmicas, permitindo medir a estrutura dos pixels e quantificar os aspectos espaciais e temporais. Neste contexto, o objetivo deste mestrado é estudar e desenvolver métodos para caracterização de texturas dinâmicas baseado em metodologias de complexidade advindas da área de sistemas complexos. Em particular, duas metodologias já utilizadas em problemas de visão computacional são consideradas: redes complexas e caminhada determinística parcialmente auto-repulsiva. A partir dessas metodologias, três métodos de caracterização de texturas dinâmicas foram desenvolvidos: (i) baseado em difusão em redes - (ii) baseado em caminhada determinística parcialmente auto-repulsiva - (iii) baseado em redes geradas por caminhada determinística parcialmente auto-repulsiva. Os métodos desenvolvidos foram aplicados em problemas de nanotecnologia e tráfego de veículos, apresentando resultados potenciais e contribuindo para o desenvolvimento de ambas áreas. / Dynamic texture analysis has been an area of research increasing and in potential in recent years in computer vision. Dynamic textures are sequences of texture images (i.e. video) that represent dynamic objects. Examples of dynamic textures are: evolution of the colony of bacteria, growth of body tissues, moving escalator, waterfalls, smoke, process of metal corrosion, among others. Although there are researches related to the topic and promising results, most literature methods have limitations. Moreover, in many cases the dynamic textures are the result of complex phenomena, making a characterization task even more challenging. This scenario requires the development of a paradigm of methods based on complexity. The complexity can be understood as a measure of irregularity of the dynamic textures, allowing to measure the structure of the pixels and to quantify the spatial and temporal aspects. In this context, this masters aims to study and develop methods for the characterization of dynamic textures based on methodologies of complexity from the area of complex systems. In particular, two methodologies already used in computer vision problems are considered: complex networks and deterministic walk partially self-repulsive. Based on these methodologies, three methods of characterization of dynamic textures were developed: (i) based on diffusion in networks - (ii) based on deterministic walk partially self-repulsive - (iii) based on networks generated by deterministic walk partially self-repulsive. The developed methods were applied in problems of nanotechnology and vehicle traffic, presenting potencial results and contribuing to the development of both areas.

A análise de texturas dinâmicas tem se apresentado como uma área de pesquisa crescente e em potencial nos últimos anos em visão computacional. As texturas dinâmicas são sequências de imagens de textura (i.e. vídeo) que representam objetos dinâmicos. Exemplos de texturas dinâmicas são: evolução de colônia de bactérias, crescimento de tecidos do corpo humano, escada rolante em movimento, cachoeiras, fumaça, processo de corrosão de metal, entre outros. Apesar de existirem pesquisas relacionadas com o tema e de resultados promissores, a maioria dos métodos da literatura possui limitações. Além disso, em muitos casos as texturas dinâmicas são resultado de fenômenos complexos, tornando a tarefa de caracterização um desafio ainda maior. Esse cenário requer o desenvolvimento de um paradigma de métodos baseados em complexidade. A complexidade pode ser compreendida como uma medida de irregularidade das texturas dinâmicas, permitindo medir a estrutura dos pixels e quantificar os aspectos espaciais e temporais. Neste contexto, o objetivo deste mestrado é estudar e desenvolver métodos para caracterização de texturas dinâmicas baseado em metodologias de complexidade advindas da área de sistemas complexos. Em particular, duas metodologias já utilizadas em problemas de visão computacional são consideradas: redes complexas e caminhada determinística parcialmente auto-repulsiva. A partir dessas metodologias, três métodos de caracterização de texturas dinâmicas foram desenvolvidos: (i) baseado em difusão em redes - (ii) baseado em caminhada determinística parcialmente auto-repulsiva - (iii) baseado em redes geradas por caminhada determinística parcialmente auto-repulsiva. Os métodos desenvolvidos foram aplicados em problemas de nanotecnologia e tráfego de veículos, apresentando resultados potenciais e contribuindo para o desenvolvimento de ambas áreas. / Dynamic texture analysis has been an area of research increasing and in potential in recent years in computer vision. Dynamic textures are sequences of texture images (i.e. video) that represent dynamic objects. Examples of dynamic textures are: evolution of the colony of bacteria, growth of body tissues, moving escalator, waterfalls, smoke, process of metal corrosion, among others. Although there are researches related to the topic and promising results, most literature methods have limitations. Moreover, in many cases the dynamic textures are the result of complex phenomena, making a characterization task even more challenging. This scenario requires the development of a paradigm of methods based on complexity. The complexity can be understood as a measure of irregularity of the dynamic textures, allowing to measure the structure of the pixels and to quantify the spatial and temporal aspects. In this context, this masters aims to study and develop methods for the characterization of dynamic textures based on methodologies of complexity from the area of complex systems. In particular, two methodologies already used in computer vision problems are considered: complex networks and deterministic walk partially self-repulsive. Based on these methodologies, three methods of characterization of dynamic textures were developed: (i) based on diffusion in networks - (ii) based on deterministic walk partially self-repulsive - (iii) based on networks generated by deterministic walk partially self-repulsive. The developed methods were applied in problems of nanotechnology and vehicle traffic, presenting potencial results and contribuing to the development of both areas.

Considere $N$ pontos distribuídos de forma aleatória e uniforme num hipercubo $d$-dimensional. Cada ponto representa um sítio num meio desordenado. Um caminhante explora este meio saltando para os sítios mais próximos, que não tenham sido visitados nos últimos $\\mu$ (memoria) passos, inclusive o próprio sítio. A trajetória do caminhante é composta de uma parte transiente e de uma parte periódica (ciclos). Neste caso, o viajante pode ou não explorar todos espaço disponível. A partir de uma memória crítica, ocorre uma transição entre os regimes de exploração localizado e estendido. Para sistemas unidimensionais, essa transição ocorre na memória crítica $\\mu_1=\\log_2{N}$. A regra determinista pode ser suavizada, a fim de considerar situações mais realistas, com a inclusão do parâmetro estocástico $T$ (temperatura). Agora, os movimentos do caminhante são definidos por uma função densidade de probabilidade (PDF) que é parametrizada por $T$ e por uma função custo, que cresce à medida que a distância entre os sítios cresce. A PDF é escolhida de forma a favorecer saltos para sítios mais próximos. Com o aumento da temperatura, o caminhante pode sair de ciclos e estender sua exploração. Aqui, nós apresentamos os estudos analíticos e numéricos sobre a influência da temperatura e da memória crítica na exploração de um meio desordenado unidimensional. / Consider $N$ sites randomly and uniformly distributed in a $d$-dimensional hypercube. A walker explores this disordered medium going to the nearest site, which has not been visited in the last $\\mu$ (memory) steps. The walker trajectory is composed of a transient part and a periodic part (cycles). In this case, travelers can or cannot explore all available space, given rise to a crossover at critical memory, for one-dimensional systems $\\mu_1=\\log_2{N}$, between localized and extended regimes. % as function of $\\mu$. The deterministic rule can be softened to consider more realistic situations with the inclusion of a stochastic parameter $T$ (temperature). In this case, the walker movement is defined by a probability density function (PDF) that is parameterized by $T$ and a cost function, which increases as the distance among sites increases. The PDF is chosen to favor hops to nearest sites. As the temperature increases, the walker can escape from cycles and extend the exploration. Here we report the analytical and numerical studies of the influence of the temperature and the critical memory in the exploration of a one-dimensional disordered system.

Nous étudions dans cette thèse le problème de l’exploration parallèle d’un graphe à l’aide des multiples, synchronisés et mobiles agents. Chaque agent est une entité individuelle qui peut, indépendamment des autres agents, visiter les sommets du graphe ou parcourir ses arêtes. Le but de ensemble des agents est de visiter tous les sommets de graphe.Nous étudions d’abord l’exploration du graphe dans un modèle où chaque agent est équipé de mémoire interne, mais les noeuds n’ont pas de mémoire. Dans ce modèle les agents sont autorisés à communiquer entre eux en échangeant des messages. Nous présentons des algorithmes qui s’exécutent dans un minimum de temps possible pour polynomiale nombre d’agents (polynomiale en nombre de sommets du graphe). Nous étudions aussi quelle est l’impact de différentes méthodes des communications. Nous étudions des algorithmes où les agents peuvent se communiquer à distance arbitraire,mais aussi où communication est possible seulement entre les agents situés dans le même sommet. Dans les deux cas nous présentons des algorithmes efficaces. Nous avons aussi obtenu des limites inférieures qui correspondent bien à la performance des algorithmes.Nous considérons également l’exploration de graphe en supposant que les mouvements des agents sont déterminés par le soi-disant rotor-router mécanisme. Du point de vue d’un sommet fixé, le rotor- router envoie des agents qui visitent les sommet voisins dans un mode round-robin. Nous étudions l’accélération défini comme la proportion entre le pire des cas de l’exploration d’un agent unique et des plusieurs agents. Pour générales graphes, nous montrerons que le gain de vitesse en cas de multi-agent rotor-router est toujours entre fonction logarithmique et linéaire du nombre d’agents. Nous présentons également des résultats optimaux sur l’accélération de multi-agent rotor-router pour cycles, expanseurs, graphes aléatoires, cliques, tores de dimension fixé et une analyse presque optimale pour hypercubes.Finalement nous considérons l’exploration sans collision, où chaque agent doit explorer le graphe de manière indépendante avec la contrainte supplémentaire que deux agents ne peuvent pas occuper le même sommet. Dans le cas où les agents sont donnés le plan de graphe, on présente un algorithme optimal pour les arbres et un algorithme asymptotiquement optimal pour générales graphes. Nous présentons aussi des algorithmes dans le cas de l’exploration sans collision des arbres et des générales graphes dans la situation où les agents ne connaissent pas le graphe. Nous fermons la thèse par des observations finales et une discussion de problèmes ouverts liés dans le domaine de l’exploration des graphes. / In this thesis we study the problem of parallel graph exploration using multiple synchronized mobile agents. Each mobile agent is an entity that can, independently of other agents, visit vertices of the graph and traverse its edges. The goal of the agents is to visit all vertices of the graph. We first study graph exploration in the model where agents are equipped with internal memory but no memory is available at the nodes. Agents in this model are also allowed to communicate between each other by exchanging messages. We present algorithms working in a minimal possible time for a team of polynomial size (in the number of vertices of the graph). We also study the impact of the available range of communication by analysing algorithms for agents which can communicate at arbitrary distance, or only with other agents located at the same node. We present efficient algorithms and lower bounds that almost match our positive results in both communication models. We also consider graph exploration when movements of agents are determined according to the so-called rotor-router mechanism. From the perspective of a fixed node, the rotor-router sends out agents which visit the node along its outgoing edges, ina round-robin fashion. We study the speedup which is the ratio between the worst-case exploration of a single agent and of multiple agents. We first show that the speed up for general graphs for the multi-agent rotor-router is always between logarithmic and linear in the number of agents. We also present a tight analysis of the speedup for the multi-agent rotor-router for cycles, expanders, random graphs, cliques, constant dimensional tori and an almost-tight analysis for hypercubes. Finally we consider collision-free exploration, where each agent has to explore the graph independently with the additional constraint that no two agents can occupy the same node at the same time. In the case when agents are given the map of the graph, we show an optimal algorithm for trees and an asymptotically optimal algorithm for general graphs. We also present algorithms for collision-free exploration of trees and general graphs in the case when agents have no initial knowledge about the graph. We close the thesis with concluding remarks and a discussion of related open problems in the area of graph exploration.

Considere $N$ pontos distribuídos de forma aleatória e uniforme num hipercubo $d$-dimensional. Cada ponto representa um sítio num meio desordenado. Um caminhante explora este meio saltando para os sítios mais próximos, que não tenham sido visitados nos últimos $\\mu$ (memoria) passos, inclusive o próprio sítio. A trajetória do caminhante é composta de uma parte transiente e de uma parte periódica (ciclos). Neste caso, o viajante pode ou não explorar todos espaço disponível. A partir de uma memória crítica, ocorre uma transição entre os regimes de exploração localizado e estendido. Para sistemas unidimensionais, essa transição ocorre na memória crítica $\\mu_1=\\log_2{N}$. A regra determinista pode ser suavizada, a fim de considerar situações mais realistas, com a inclusão do parâmetro estocástico $T$ (temperatura). Agora, os movimentos do caminhante são definidos por uma função densidade de probabilidade (PDF) que é parametrizada por $T$ e por uma função custo, que cresce à medida que a distância entre os sítios cresce. A PDF é escolhida de forma a favorecer saltos para sítios mais próximos. Com o aumento da temperatura, o caminhante pode sair de ciclos e estender sua exploração. Aqui, nós apresentamos os estudos analíticos e numéricos sobre a influência da temperatura e da memória crítica na exploração de um meio desordenado unidimensional. / Consider $N$ sites randomly and uniformly distributed in a $d$-dimensional hypercube. A walker explores this disordered medium going to the nearest site, which has not been visited in the last $\\mu$ (memory) steps. The walker trajectory is composed of a transient part and a periodic part (cycles). In this case, travelers can or cannot explore all available space, given rise to a crossover at critical memory, for one-dimensional systems $\\mu_1=\\log_2{N}$, between localized and extended regimes. % as function of $\\mu$. The deterministic rule can be softened to consider more realistic situations with the inclusion of a stochastic parameter $T$ (temperature). In this case, the walker movement is defined by a probability density function (PDF) that is parameterized by $T$ and a cost function, which increases as the distance among sites increases. The PDF is chosen to favor hops to nearest sites. As the temperature increases, the walker can escape from cycles and extend the exploration. Here we report the analytical and numerical studies of the influence of the temperature and the critical memory in the exploration of a one-dimensional disordered system.

Considere um meio caracterizado por $N$ pontos cujas coordenadas são geradas aleatoriamente de maneira uniforme nas arestas unitárias de um hipercubo $d$-dimensional. Um caminhante parte de cada ponto deste meio desordenado e se movimenta obedecendo à regra determinista de ir para o ponto mais próximo que não tenha sido visitado nos últimos $mu$ passos. Este processo foi denominado de caminhada determinista do turista. Cada trajetória gerada por esta dinâmica possui uma parte inicial não-periódica de $t$ passos (transiente) e uma parte final periódica de $p$ passos (atrator). As probabilidades de vizinhança são expressas através da fórmula de Cox, que é parametrizada pela função beta incompleta normalizada $I_d = I_{1/4}[1/2,(d+1)/2]$. Enfati-zamos aqui que a distribuição relevante é $S_{mu,d}^{(N)}(t,p)$, a distribuição conjunta de $t$ e $p$, que tem como casos particulares as distribuições marginais, previamente estudadas. O objetivo deste estudo é obter analiticamente estas distribuições para a caminhada determinista do turista sem memória no espaço euclideano, no modelo de distâncias aleatórias (que corresponde ao limite $d ightarrow infty$) e no modelo de mapeamento aleatório (que é um caso limite das redes de Kauffman). As distribuições analíticas obtidas foram validadas através de experimentos numéricos. A distribuição conjunta de tempos de transiente e período de atratores, no limite termodinâmico para uma dimensionalidade arbitrária vale: $S_{1,d}^{(infty)}(t,p) = [Gamma(1+I_d^{-1}) cdot (t+I_d^{-1})/Gamma(t+p+I_d^{-1})] cdot delta_{p,2}$, onde $t=0,1,2,ldots,infty$; $Gamma(z)$ é a função gama e $delta_{i,j}$ é o delta de Kronecker. A caminhada determinista do turista sem memória no modelo de mapeamento aleatório produz uma distribuição de períodos não-trivial ($S_{0,rm}^{(N)}(p) propto p^{-1}$), que é obtida de $S_{0,rm}^{(N)}(t,p) = Gamma(N)/{Gamma[N+1-(t+p)]N^{t+p}}$, onde enfatizamos que o número de pontos explorados $n_e=t+p$ é a grandeza fundamental nos problemas considerados. / Consider a medium characterized by $N$ points whose coordinates are randomly generated by a uniform distribution along the unitary edges of a $d$-dimensional hypercube. A walker leaves from each point of this disordered medium and moves according to the deterministic rule to go the nearest point which has not been visited in the preceding $mu$ steps. This process has been called the deterministic tourist walk. Each trajectory generated by this dynamics has an initial non-periodic part of $t$ steps (transient) and a final periodic part of $p$ steps (attractor). The neighborhood probabilities are given by the Cox formula, which is parameterized by the normalized incomplete beta function $I_d = I_{1/4}[1/2,(d+1)/2]$. Here we stress that the relevant distribution is the joint $t$ and $p$ distribution $S_{mu,d}^{(N)}(t,p)$, which has as particular cases, the marginal distributions previously studied. The objective of this study is to obtain analytically these distributions for the memoryless deterministic tourist walk in the euclidean space, random link model (which corresponds to $d ightarrow infty$ limit) and random map model (which is a limiting case of the Kauffman model). The obtained distributions have been validated by numerical experiments. The joint transient time and attractor period distribution in the thermodynamic limit for an arbitrary dimensionality is: $S_{1,d}^{(infty)}(t,p) = [Gamma(1+I_d^{-1}) cdot (t+I_d^{-1})/Gamma(t+p+I_d^{-1})] cdot delta_{p,2}$, where $t=0,1,2,ldots,infty$; $Gamma(z)$ is the gamma function and $delta_{i,j}$ is the Kronecker's delta. The memoryless deterministic tourist walk in the random map leads to a non-trivial cycle distribution ($S_{0,rm}^{(N)}(p) propto p^{-1}$), which is obtained from $S_{0,rm}^{(N)}(t,p) = Gamma(N)/{Gamma[N+1-(t+p)]N^{t+p}}$, where we stress that the number of explored points $n_e=t+p$ is the fundamental quantity in the considered problems.