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

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 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 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.