Força bruta e ignorância

Força bruta e ignorância, em matemática, é o método que consiste em provar algum teorema (ou apresentar algum contra-exemplo) pelo método exaustivo de calcular cada caso possível. Algumas vezes abreviado, em inglês, como BFI (de brute force and ignorance).[1]

Exemplos

editar

O problema do caixeiro viajante, que consiste em, dado um conjunto de n pontos, determinar o menor caminho que passa por todos os pontos, admite uma solução trivial pelo método da força bruta e ignorância, que consiste em calcular todos os n! caminhos (ou (n-1)!, se a cidade inicial for fixada) e escolher o menor; mas este método é inviável conforme n cresce.[2]

O procedimento de Chien (Chien search), que determina as raízes de polinômios em corpos finitos, é um método de exaustão, ou seja, força bruta e ignorância.[3]

Um exemplo de aplicação no passado de métodos BFI foram tentativas de demonstração do último teorema de Fermat, quando, já pelo ano de 1979, já se tinham exaustões para expoente n menores que 30.000, como sustentando a ainda conjectura.[4]

Referências

  1. Jeffrey Stopple, A Primer of Analytic Number Theory: from Pythagoras to Riemann, Exercises on binary quadratic forms [em linha]
  2. Rob Womersley, Parabola Volume 37, Issue 2 (2001)m The Travelling Salesman Problem and Computational Complexity [https://web.archive.org/web/20110410005720/http://www.parabola.unsw.edu.au/vol37_no2/node1.html Arquivado em 10 de abril de 2011, no Wayback Machine. [em linha]]
  3. Joel Sylvester, Reed Salomon Codes, Finding the error polynomial roots - Chien search [https://web.archive.org/web/20130512161447/http://www.csupomona.edu/~jskang/files/rs1.pdf Arquivado em 12 de maio de 2013, no Wayback Machine. [em linha]]
  4. Leon M. Hall; Notes on the Great Theorems; Department of Mathematics and Statistics, University of Missouri - Rolla, 1987. - web.mst.edu