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.
Declaração de acesso aberto: A REMAT é uma revista de acesso aberto, o que implica que todo o seu conteúdo está acessível sem custo para o usuário ou sua instituição. Os leitores têm permissão para visualizar, fazer download, copiar, distribuir, imprimir, pesquisar ou vincular aos textos completos dos artigos, bem como usá-los para qualquer outra finalidade legal, sem a necessidade de solicitar autorização prévia da revista ou dos autores. Essa declaração alinha-se com a definição de acesso aberto estabelecida pela Budapest Open Access Initiative (BOAI).