Em matemática, uma explosão combinatória é o rápido crescimento da complexidade de um problema devido a como a combinatória do problema é afetada pelos seus inputs, restrições e limites. A explosão combinatória às vezes é usada para justificar a intratabilidade de certos problemas. http://intelligence.worldofcomputing/combinatorial-explosion Combinatorial Explosion. Exemplos incluem certas funções matemáticas, a análise de alguns quebra-cabeças e jogos e alguns exemplos que podem ser modelados como a função de Ackermann.
Exemplos
Quadrados latinos Um quadrado latino de ordem é um quadrado com entradas de um conjunto de elementos com a propriedade de que cada elemento do conjunto ocorra exatamente uma vez em cada linha e cada coluna do quadrado.
Um exemplo comum de um quadrado latino é um quebra-cabeça Sudoku completo. All completed puzzles are Latin squares, but not all Latin squares can be completed puzzles since there is additional structure in a Sudoku puzzle. Um quadrado latino é um objeto combinatório (em oposição a um objeto algébrico), pois apenas o arranjo das entradas importa e não o que as entradas realmente são. O número de quadrados latinos em função da ordem fornece um exemplo de explosão combinatória conforme ilustrado na tabela abaixo. O número de quadrados latinos de ordem 112231245765161,2806812,851,200761,479,419,904,0008108,776,032,459,082,956,80095,524,751,496,156,892,842,531,225,600109,982,437,658,213,039,871,725,064,756,920,320,00011776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000
Informática A explosão combinatória pode ocorrer em ambientes computacionais de maneira análoga ao espaço multidimensional. Imagine um sistema simples com apenas uma variável, uma booleana chamada A. O sistema possui dois estados possíveis, A = verdadeiro ou A = falso. Adicionar outra variável booleana B dará ao sistema quatro estados possíveis, A = verdadeiro e B = verdadeiro, A = verdadeiro e B = falso, A = falso e B = verdadeiro, A = falso e B = falso. Um sistema com n booleanos tem 2n estados possíveis, enquanto um sistema de n variáveis, cada uma com Z valores permitidos, terá Z n estados possíveis.
Ver também
Paradoxo do aniversário
Referências
Categoria:Teoria dos jogos Categoria:Combinatória