64ª Reunião Anual da SBPC

A. Ciências Exatas e da Terra - 2. Ciência da Computação - 16. Teoria da Computação

QUADRADOS SEMI-MÁGICOS A PARTIR DE “SUBSET SUM”

L'hauã Barbosa Pereira de Miranda 1 Lossian Barbosa Bacelar Miranda 1 Lohans de Oliveira Miranda 2 Liuhan OLiveira de Miranda 2

1. Coordenação de Análise e Desenvolvimento de Sistemas, Instituto Federal de Educação Ciência e Tecnologia do Piauí – IFPI. 2. Coordenação Pedagógica, Instituto Antoine Lavoisier de Ensino, Teresina, Piauí.

INTRODUÇÃO:

Por mais de 4.100 anos os quadrados semi-mágicos têm intrigado a Humanidade e a classificação dos mesmos continua a ser um dos mais fascinantes problemas abertos da matemática e da moderna teoria da computação. Têm sido desenvolvidos métodos de construção de quadrados semi-mágicos a partir de matrizes em forma de cobra (referência [RDMV]), os quais consistem de duas etapas. Em [MM] é apresentado um método que também faz uso das matrizes em forma de cobra, composto de três etapas, sendo a primeira a mesma estabelecida em [RDMV], a segunda um pouco diferente e, a terceira, um problema de tipo “subset sum” cuja solução fornece uma grande variedade de quadrados semi-mágicos. Nossa abordagem está restrita aos quadrados de ordens pares, mas se aplica a retângulos quaisquer com números pares de linhas e colunas. Também é possível fazermos os procedimentos (etapas) sobre as linhas em lugar das colunas e, constrói-se os quadrados semi-mágicos efetuando-se o segundo procedimento (reflexão) sobre as colunas de ordem ímpar. O programa que apresentamos resolve o problema proposto em [MM] em tempo não polinomial.

METODOLOGIA:

Matemáticos: intuição sobre as propriedades dos inteiros; discussões; técnicas de “subset sum”. Computacionais: técnicas de “subset sum” em linguagem Java. Fizemos um artigo (ref. [MM]). Usamos PCs e o programa faz o seguinte: 1) Fixado um número par, distribui os números naturais positivos menores ou iguais ao quadrado do número par previamente fixado em ordem crescente (em PA de razão 1) ao longo das linhas de ordens ímpares e em ordem decrescente ao longo das linhas de ordens pares de uma matriz quadrada de ordem igual ao número par previamente fixado (construção da “matriz serpentiforme”); 2) Inverte os sentidos das colunas de ordens pares da matriz serpentiforme (construção da “matriz serpentiforme refletida em colunas pares”); 3) A partir dos conjuntos de soluções de problemas do tipo “subset sum”, transforma uma matriz serpentiforme refletida em colunas pares em vários quadrados semi-mágicos. Referências: [RDMV] J. P. De Los Reyes, Ashish Das, Chand K. Midha and P. Vellaisamy. On a method to construct magic rectangles of even order. New Delhi: Indian Statistical Institute, Delhi Centre, 2007. [MM] MIRANDA, L. O. and MIRANDA, L. Semi-Magic Squares From Snake-Shaped Matrices. Integers: Electronic Journal of Combinatorial Number Theory, Preprint, 2012. [SW] SEDGEWICK, R.; WAYNE, K. Introduction to Programming in Java: An Interdisciplinary Approach. Addison-Wesley, 2008.

RESULTADOS:

A partir da teoria matemática estabelecida na acima citada pré-publicação, foi possível construir um programa em linguagem Java que constrói rapidamente milhões de quadrados semi-mágicos de ordens pares até a trigésima ordem. A partir desta ordem o sistema fica muito lento, indicando claramente um crescimento temporal superior ao polinomial. Pelo fato de o programa resolver um problema do tipo “subset sum” vindo da raiz da teoria dos números (quadrados semi-mágicos), julgamos que o mesmo pode ser muito útil no estudo da acirrada questão “P=NP?”.

CONCLUSÃO:

A partir de matrizes serpentiformes e resolução de problemas do tipo “subset sum” é possível a elaboração de programas computacionais que constroem uma grande variedade de quadrados semi-mágicos de ordens pares. O tempo de execução, como função da ordem do quadrado não é polinomial e o número de combinações feitas é função exponencial desta ordem. Os dados encontrados indicam que o número de quadrados semi-mágicos fornecidos pelo método, expressos como função da ordem do quadrado mágico possui, para múltiplos de quatro, crescimento superior ao da função correspondente ao quociente entre o fatorial da metade da ordem e o quadrado do fatorial da quarta parte da mesma ordem.

Palavras-chave: Quadrados semi-mágicos, Matrizes serpentiformes, Problemas do tipo “subset sum”.