O princípio da inclusão-exclusão e o cálculo de permanentes

José Ricardo Gonçalves de  Mendonça

doi:10.35819/remat2024v10i2id6987

Autores

José Ricardo Gonçalves de Mendonça Universidade de São Paulo (USP), São Paulo, SP, Brasil https://orcid.org/0000-0002-5516-0568

DOI:

https://doi.org/10.35819/remat2024v10i2id6987

Palavras-chave:

matemática discreta, análise combinatória, partição de conjuntos, algoritmo de Ryser, problemas #P-completos

Resumo

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

Os dados de download ainda não estão disponíveis.

Biografia do Autor

José Ricardo Gonçalves de Mendonça, Universidade de São Paulo (USP), São Paulo, SP, Brasil

http://lattes.cnpq.br/8792749813872106

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.