El principio de inclusión-exclusión y el cálculo de permanentes
DOI:
https://doi.org/10.35819/remat2024v10i2id6987Palabras clave:
matemáticas discretas, análisis combinatorio, partición de conjuntos, algoritmo de Ryser, problemas #P-completosResumen
En este artículo revisamos el principio de inclusión-exclusión (PIE) desde puntos de vista conjuntista y algebraico y discutimos su aplicación al cálculo de permanentes, un tema que normalmente no se trata en los cursos de pregrado. La presentación busca ser rigurosa pero elemental y accesible para los estudiantes en los primeros años en programas de matemáticas, ciencias e ingeniería, y que sólo requiera familiaridad con la notación de conjuntos, aritmética y el álgebra matricial. Al abordar el cálculo de permanentes, presentamos el algoritmo de Ryser, uno de los desarrollos más espectaculares en el abordaje de problemas combinatorios difíciles, cuya complejidad computacional discutimos brevemente. El artículo contiene ejemplos, notas complementarias y un programa Python que implementa el algoritmo de Ryser utilizando códigos de Gray para calcular permanentes, acompañado de su discusión.
Descargas
Referencias
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.
Descargas
Publicado
Número
Sección
Licencia
Derechos de autor 2024 José Ricardo Gonçalves de Mendonça
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
REMAT conserva los derechos de autor de los artículos publicados, teniendo derecho a la primera publicación del trabajo, mención de la primera publicación en la revista en otros medios publicados y distribución de partes o del trabajo en su conjunto con el fin de promover la revista.
Esta es una revista de acceso abierto, lo que significa que todo el contenido está disponible de forma gratuita, sin costo para el usuario o su institución. Los usuarios pueden leer, descargar, copiar, distribuir, imprimir, buscar o vincular los textos completos de los artículos, o utilizarlos para cualquier otro propósito legal, sin solicitar permiso previo a la revista o al autor. Esta declaración está de acuerdo con la definición de BOAI de acceso abierto.
Cómo citar
