• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
DOI
10.11606/T.59.2002.tde-24052006-144856
Documento
Autor
Nome completo
Gilson Francisco de Lima
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
Ribeirão Preto, 2002
Orientador
Banca examinadora
Martinez, Alexandre Souto (Presidente)
Alfonso, Nestor Felipe Caticha
Felicio, Jose Roberto Drugowich de
Idiart, Marco Aurelio Pires
Silva Filho, Antonio Carlos Roque da
Título em português
"Caminhadas determinísticas em meios desordenados: problema da caminhada do turista".
Palavras-chave em português
caminhadas aleatórias
caminhadas deterministas
meios desordenados
sistemas complexos
Resumo em português
O estudo de caminhadas aleatórias em meios desordenados e um assunto bastante explorado e pode modelar uma grande variedade de problemas, como por exemplo, problemas de transporte (difusão). O estudo de caminhadas determinísticas em meios desordenados é um assunto pouco explorado. Em uma paisagem composta de N sítios distribuídos aleatoriamente no espaço, um caminhante ("turista") visita estes sítios seguindo a seguinte regra determinística: ir para o sítio vizinho mais próximo que não tenha sido visitado nos últimos passos. De cada sítio inicial, a trajetória obtida com esta dinâmica determinística apresenta inicialmente um tempo de transiente t, onde novos sítios são visitados, e no final um atrator de período p, onde os mesmos sítios são sempre revisitados. Apesar da simplicidade do modelo, a dinâmica e complexa e os resultados não são triviais. Para dimensionalidades d = 2, a distribuição de atratores de período p, obtida numericamente, pode ser descrita por uma lei de potência com um corte exponencial. Os modelos de ligações aleatórias simétricas (que representa o limite de alta dimensionalidade d = 1 do modelo proposto) e assimétricas indicam que o corte exponencial se torna menos importante à medida que N aumenta. O expoente da lei de potência independe da memória tau, sendo portanto uma distribuição robusta. A dinâmica do turista pode ser aplicada a problemas mais abstratos, onde apenas relações de ordem entre vizinhos são dados. O estudo (por amostragem) da estrutura de um dicionário de sinônimos e um exemplo que foi considerado. Mostrou-se que as palavras podem ser embebidas em um espaço Euclidiano de baixa dimensionalidade.Este resultado concorda com um recente estudo exaustivo realizado e questiona o modelo de análise semântica latente. Com a finalidade de entender a transição entre uma caminhada determinística e uma caminhada aleatória, generalizou-se o problema com memória nula designando uma distribuição de probabilidades para o turista visitar os diversos sítios. Esta distribuição e parametrizada por uma variável externa T (temperatura) de modo que para T = 0 têm-se a caminhada do turista como caso limite e para T tendendo para infinito todos os sítios são visitados com igual probabilidade. Resultados analíticos (d = 1) e numéricos mostram a existência de uma região bem delimitada de transição entre os regimes não-ergódico (baixa temperatura) e ergódico (alta temperatura). Uma analogia é estabelecida com o modelo de vidros de Bouchaud. A eficiência da caminhada com relação aos novos sítios visitados, foi estudada e ela e máxima na borda da aleatoriedade, ou seja, ao redor da temperatura de transição.
Título em inglês
"Deterministic walks in random media: tourist walk problem"
Palavras-chave em inglês
complex systems
deterministic walks
disordered media
random walks
Resumo em inglês
The study of random walks in disordered media is one well-developed subject and it can model a great variety of problems, for instance, problems of transport (diffusion). The study of deterministic walks in disordered media is a subject not too explored. In a landscape composed of N sites randomly distributed in of, a walker ("tourist") visits these sites following the deterministic rule: going to the nearest site that has not been visited in the last tau steps. From each initial site, the trajectory, obtained with this deterministic dynamics, presents initially a time transient t, where new sites are visited, and, in the end, a p-period attractor, where the same sites are always revisited. In spite of the simplicity of the model, the dynamics is complex and the results are not trivial. For dimensionalities d = 2, the distribution of p-period obtained numerically can be described by a power law with an exponential cut. The models of symmetrical random connections (that represents the limit of high dimensionality d = 1 of the proposed model) and asymmetrical random connections indicate that the exponential cut turns out to be less important as N increases. The exponent law of the power law does not depend on the memory tau, being therefore a robust distribution. The tourist dynamics can be applied to more abstract problems, where just relationships of neighbor order are given. The study (by sampling) of the structure of a dictionary of synonyms has been considered. It has been shown that the words can be embedded in an Euclidean space of low dimensionality. This result agrees with a recent exhaustive study accomplished and it challenges the model of latent semantic analysis. With the purpose of understanding the transition between a deterministic and a random walk a generalization of the problem, with null memory has been performed by designating a distribution of probabilities for the tourist to visit the several sites. This distribution has the external variable T (temperature) as a parameter so that, when T = 0 it has the tourist walk as a limiting case and for T tending to infinity all of the sites are visited ith equal probability. Analytical numerical results (d = 1) show the existence of well delimited transition between non-ergodic (low temperature) and ergodic (high temperature) regime. An analogy is established Bouchaud glass model. The walk efficiency, regarding the new visited sites to trajectory length, has been studied and it is maximum at the edge of stochasticity, in other words, around the temperature of transition.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
LIMA_GF.pdf (1.64 Mbytes)
Data de Publicação
2006-05-31
 
AVISO: O material descrito abaixo refere-se a trabalhos decorrentes desta tese ou dissertação. O conteúdo desses trabalhos é de inteira responsabilidade do autor da tese ou dissertação.
  • KINOUCHI, O, et al. Deterministic walks in random networks : an application to thesaurus graphs [doi:10.1016/S0378-4371(02)00972-X]. Physica A: Statistical Mechanics and its Applications [online], 2002, vol. 315, n. 3-4, p. 665-676.
  • KINOUCHI, O., et al. Deterministic walks in random networks: an application to thesaurus graphs [doi:10.1016/S0378-4371(02)00972-X]. Physica. A [online], 2002, vol. 315, nº 3/4, p. 665-676.
  • LIMA, G. F., MARTINEZ, A. S., and KINOUCHI, O. Deterministic Walks in Random Media [doi:10.1103/PhysRevLett.87.010603]. Physical Review Letters [online], 2001, vol. 87, nº 1, p. 010603.
  • LIMA, Gilson, MARTINEZ, Alexandre, and KINOUCHI, Osame. Deterministic Walks in Random Media [doi:10.1103/PhysRevLett.87.010603]. Physical Review Letters [online], 2001, vol. 87, n. 1.
  • KINOUCHI, O., et al. Comportamento exploratório do turista. In Simpósio em Homenagem ao Professor S. R. Salinas nos seus 60 Anos, Campos do Jordão, SP, 2002. Anais da Tendências da Física Estatística no Brasil: Escala e Complexidade., 2003.
  • LIMA, G. F., MARTINEZ, A. S., and KINOUCHI, O. Evidence of generic scale invariance in deterministic walks in random media. In IUPAP International Conference New Trends in Fractals Aspects of Complex Systems (FACS2000), Maceió AL, 2000. Abstract. Available from: http://facs2000.fis.ufal.br/.
  • MARTINEZ, A. S., et al. Escaping from random vicious cycles through a glass transition: exploration of disordered media with tourist-like walk. In Colloque en l'honneur du 65e anniversaire de Roger Maynard, Grenoble, 2003. Livro de Programa do Colloque en l'honneur du 65e anniversaire de Roger Maynard., 2003. Resumo. Disponible sur internet: http://lpm2c.polycnrs-gre.fr/Themes/tiggelen/RM.html.
  • KINOUCHI, O., et al. Comportamento exploratório do turista. In Tânia Tomé. Tendências da Física Estatística no Brasil: Em homenagem ao Professor Silvio Salinas no seu 60 aniversário. Organizador. São Paulo : Editora Livraria da Física, 2003{Volume}, p. 171-174.http://www.teses.usp.br/teses/disponiveis/59/59135/tde-24052006-144856/
  • Artigo de H. E. Stanley e S. Buldyrev publicado na seção News e Views da revista Nature sobre a caminhada do turista - Revista Nature 413 páginas 373-374
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2018. Todos os direitos reservados.