O princípio da inclusão-exclusão e o cálculo de permanentes
DOI:
https://doi.org/10.35819/remat2024v10i2id6987Palavras-chave:
matemática discreta, análise combinatória, partição de conjuntos, algoritmo de Ryser, problemas #P-completosResumo
Neste artigo revisamos o princípio da inclusão-exclusão (PIE) sob os pontos de vista conjuntista e algébrico e discutimos sua aplicação ao cálculo de permanentes, um assunto que normalmente não é abordado em cursos de graduação. A apresentação procura ser rigorosa porém elementar e acessível a alunos dos anos iniciais de cursos de licenciatura ou bacharelado em matemática, ciências e engenharias, exigindo somente familiaridade com notação de conjuntos, aritmética e álgebra de matrizes. No tratamento do cálculo de permanentes, apresentamos o algoritmo de Ryser, um dos desenvolvimentos mais espetaculares na abordagem de problemas combinatoriais difíceis, cuja complexidade algorítmica discutimos brevemente. O artigo inclui exemplos, notas complementares e um programa em Python que implementa o algoritmo de Ryser usando códigos de Gray para o cálculo de permanentes, juntamente com sua discussão.
Downloads
Referências
ARORA, Sanjeev; BARAK, Boaz. Computational Complexity: A Modern Approach. Cambridge, UK: Cambridge University Press, 2009. ISBN: 978-0-521-42426-4.
BARVINOK, Alexander. Combinatorics and Complexity of Partition Functions. [S. l.]: Springer, 2016. v. 30. ISBN: 978-3-319-51828-2. DOI: https://doi.org/10.1007/978-3-319-51829-9.
BRUALDI, Richard A.; RYSER, Herbert John. Combinatorial Matrix Theory. Cambridge, UK: Cambridge University Press, 1991. v. 39. Encyclopedia of Mathematics and its Applications. ISBN: 0-521-32265-0.
GOLDREICH, Oded. Computational Complexity: A Conceptual Perspective. Cambridge, UK: Cambridge University Press, 2008. ISBN: 978-0-521-88473-0.
HAZZAN, Samuel. Fundamentos de Matemática Elementar: Combinatória e Probabilidade. 8. ed. São Paulo, SP: Atual, 2013. v. 5. ISBN: 978-8-535-71750-1.
HEFEZ, Abramo. Aritmética. 2. ed. Rio de Janeiro, RJ: SBM, 2016. v. 8. Coleção PROFMAT. ISBN 978-85-8337-105-2.
KALMANN, Ralph. A method for finding permanents of 0, 1 matrices. Mathematics of Computation, Providence, RI, v. 38, n. 157, p. 167-170, 1982. DOI: https://doi.org/10.1090/S0025-5718-1982-0637294-0.
MINC, Marvin. Permanents. London: Addison-Wesley, 1978. v. 6. Encyclopedia of Mathematics and its Applications. ISBN: 0-201-13505-1.
MORGADO, Augusto César; CARVALHO, João Bosco Pitombeira de; CARVALHO, Paulo Cezar Pinto; FERNANDEZ, Pedro. Análise Combinatória e Probabilidade. 11. ed. Rio de Janeiro, RJ: SBM, 2020. Coleção do Professor de Matemática. ISBN 978-65-990-3953-9.
NIJENHUIS, Albert; WILF, Herbert Saul. Combinatorial Algorithms for Computers and Calculators. 2. ed. New York: Academic Press, 1978.
REALE, Fábio Tosetto. Métodos de Monte Carlo para amostragem de permutações com restrições e aplicações. Orientador: José Ricardo Gonçalves de Mendonça. 2018. 57 f. Dissertação (Mestrado em Modelagem de Sistemas Complexos) - Escola de Artes, Ciências e Humanidades, Universidade de São Paulo, São Paulo, 2018. DOI: https://doi.org/10.11606/D.100.2018.tde-06092018-144335.
RIORDAN, John. Introduction to Combinatorial Analysis. Mineola, NY: Dover, 2002. ISBN 0-486-42536-3.
RYSER, Herbert John. Combinatorial Mathematics. Rahway, NJ: The Mathematical Association of America, 1963. v. 14. Carus Mathematical Monographs.
SCHROEDER, Manfred Robert. Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity. 5. ed.
Berlin: Springer, 2009. ISBN: 978-3-540-85297-1. DOI: http://doi.org/10.1007/978-3-540-85298-8.
TENENBAUM, Gérald; FRANCE, Michel Mendès. The Prime Numbers and Their Distribution. Providence, RI: AMS, 2000. v. 6. Student Mathematical Library. ISBN: 978-0-821-81647-9.
VALIANT, Leslie Gabriel. The complexity of computing the permanent. Theoretical Computer Science, Amsterdam, NL, v. 8, n. 2, p. 189-201, Mar. 1979. DOI: https://doi.org/10.1016/0304-3975(79)90044-6.
VALIANT, Leslie Gabriel. The complexity of enumeration and reliability problems. SIAM Journal on Computing, v. 8, n. 3, p. 410-421, Aug. 1979. DOI: https://doi.org/10.1137/0208032.
VAN LINT, Jacobus Hendricus; WILSON, Richard Michael.A Course in Combinatorics. 2. ed. Cambridge, UK: Cambridge University Press, 2001. ISBN: 978-0-521-80340-3. Disponível em: http://www.cambridge.org/9780521803403. Acesso em: 23 set. 2024.
WHITNEY, Hassler. A logical expansion in mathematics. Bulletin of the American Mathematical Society, New York, v. 38, n. 8, p. 572-579, Aug. 1932. DOI: https://doi.org/10.1090/S0002-9904-1932-05460-X.
Downloads
Publicado
Edição
Seção
Licença
Copyright (c) 2024 José Ricardo Gonçalves de Mendonça
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
Os autores detêm os direitos autorais dos artigos publicados e concedem à REMAT o direito de primeira publicação e distribuição de partes ou do trabalho como um todo com o objetivo de promover a revista. Os autores são autorizados a distribuir a versão publicada do artigo, como por exemplo em repositórios institucionais, desde que façam menção de publicação inicial nesta revista a partir da disponibilização do DOI do artigo.
Os artigos são publicados sob a licença Creative Commons Attribution 4.0 International License (CC BY 4.0). Isso permite que o conteúdo seja utilizado para criação de novos trabalhos, tanto para fins comerciais quanto não comerciais, desde que seja feita a devida atribuição ao autor original, conforme especificado na licença.
Como Citar
https://orcid.org/0000-0002-0893-7426
