Nesta tese, introduzimos o conceito de sequência convergente de permutações e provamos a existência de um objeto limite para tais sequências. Introduzimos ainda um novo modelo de permutação aleatória baseado em tais objetos e introduzimos um conceito novo de distância entre permutações. Provamos então que sequências de permutações aleatórias são convergentes e provamos a equivalência entre esta noção de convergência e convergência nesta nova distância. Obtemos ainda resultados de amostragem e quase-aleatoriedade para permutações. Provamos também uma caracterização para parâmetros testáveis de permutações. / We introduce the concept of convergent sequence of permutations and we prove the existence of a limit object for these sequences. We also introduce a new and more general model of random permutation based on these limit objects and we introduce a new metric for permutations. We also prove that sequences of random permutations are convergent and we prove the equivalence between this notion of convergence and convergence in this new metric. We also show some applications for samplig and quasirandomness. We also prove a characterization for testable parameters of permutations.
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-08122008-163417 |
| Date | 18 November 2008 |
| Creators | Rudini Menezes Sampaio |
| Contributors | Yoshiharu Kohayakawa, Carlos Hoppen, Elisabeti Kira, Carlos Gustavo Tamm de Araujo Moreira, Roberto Imbuzeiro Moraes Felinto de Oliveira |
| Publisher | Universidade de São Paulo, Ciência da Computação, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0018 seconds