• 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
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.100.2020.tde-07022020-121851
Documento
Autor
Nombre completo
Luis Amato Neto
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2020
Director
Tribunal
Mendonça, José Ricardo Gonçalves de (Presidente)
Camargo, Raphael Yokoingawa de
Freire, Alexandre da Silva
Rodrigues Neto, Camilo
Título en portugués
Coincidências: Problema dos aniversários e polinômios cromáticos
Palabras clave en portugués
Coincidências
Polinômios cromáticos
Problema dos aniversários
Resumen en portugués
Como discutido em Diaconis e Mosteller (1989), o problema dos aniversários é um ponto importante de partida no estudo de coincidências. Uma definição de coincidência é adotada, seguida de uma breve apresentação dos seus principais aspectos: entre eles a subjetividade e a surpresa. Na literatura são encontradas as principais variações do problema dos aniversários, que analisadas, fornecem as bases para um estudo do aspecto probabilístico das coincidências. Neste trabalho os eventos são associados a variáveis aleatórias independentes e igualmente distribuídas, ou seja, os problema são estudados por técnicas de contagem. Desta forma o problema clássico dos aniversários pode ser associado à coloração dos vértices de um grafo completo, assim como o problema do aniversariante pode ser associado à coloração dos vértices de um grafo estrela. A partir destas observações, é proposta a formulação de problema dos aniversários sujeito a restrições de uma rede de relacionamentos, que equivale a um problema da coloração própria dos vértices de um grafo simples, cuja topologia modela as restrições do problema original. O objetivo do trabalho é aplicar o conhecimento desenvolvido sobre polinômios cromáticos no estudo das coincidências associadas a problemas dos aniversários sujeito a restrições, Um resumo sobre teoria dos grafos e os principais resultados referentes a polinômios cromáticos são apresentados com o objetivo de dar clareza e consistência entre definições adotadas, teoremas utilizados e sua aplicação nos casos de árvores de Cayley, grafos Bollobas-Chung e redes sociais simples. A análise das coincidências se concentra na determinação do polinômio cromático e suas representações em diferentes bases, entre elas as formas: de potência, fatorial e de árvore. A decisão se um grafo pode ou não ser colorido de maneira própria com k > 2 cores é um problema de decisão NP-completo, portanto um objetivo secundário é analisar as limitações dos algoritmos existentes e dos sistemas disponíveis para de calculo de polinômios cromáticos, que possuem coeficientes inteiros e podem alcançar centenas de dígitos. Os cálculos e as simulações foram realizadas no Sage Mathematics Software (Linux Version 8.8). A conclusão demonstra que o conhecimento e as técnicas de polinômios cromáticos contribuem com a solução da generalização proposta do problema dos aniversários, sendo analisadas as limitações atuais quanto à eficácia dos algoritmos disponíveis e a capacidade computacional demandada pela topologia do grafo associado ao problema original
Título en inglés
Coincidences: birthday problem and chromatic polynomials
Palabras clave en inglés
Birthday problem
Chromatic polynomials
Coincidences
Resumen en inglés
As discussed in Diaconis e Mosteller (1989), the birthday problem is an important starting point in the study of coincidences. A definition of coincidence is adopted, followed by a brief presentation of its main aspects: subjectivity and surprise among them. In the literature, the main variations of the birthday problem are found, which analyzed, provide the basis for a study of the probabilistic aspect of coincidences. In this work the events are associated with independent and equally distributed random variables, that is, the problems are studied by counting techniques. Thus the classical birthday problem can be associated with the coloring of vertices of a complete graph, just as the birthmate problem can be associated with the coloring of the vertices of a star graph. From these observations, it is proposed a formulation of the birthday problem, subject to constraints of a relationships network, which is equivalent to a problem of proper coloring of the vertices of a simple graph, whose topology shapes the constraints of the original problem. The objective of this work is to apply the knowledge developed about chromatic polynomials in the study of coincidences associated with restricted birthday problems. A summary of graph theory and the main results concerning chromatic polynomials are presented with the purpose of providing clarity and consistency between adopted definitions, used theorems and their application in the case of Cayley trees, Bollobas-Chung graphs and simple social networks. The analysis of coincidences focuses on the determination of the chromatic polynomial and its representations in different bases, among them the power, factorial and tree bases. Whether or not a graph can be properly colored with k > 2 colors is an NP-complete decision problem, so a secondary objective is to analyze the limitations of existing algorithms and available systems for calculating chromatic polynomials, which have integer coefficients and can reach hundreds of digits. Calculations and simulations were performed in Sage Mathematics Software (Linux Version 8.8). The conclusion demonstrates that the knowledge and techniques of chromatic polynomials contribute to the solution of the proposed generalization of the birthdays problem, it is also analyzed the current limitations regarding the effectiveness of available algorithms and the computational capacity demanded by the graph topology associated with the original problem
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2020-02-14
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2024. Todos los derechos reservados.