Powered By Blogger

Seja bem vindo

Espero que este blog possa proporcionar a você leitor uma nova abordagem do ensino da matemática.

Pesquisar este blog

domingo, 21 de novembro de 2010

Mais fotos do Passa ou Repassa











Jogo Passa ou Repassa na EMEB Professora Gércia Ferreira Guimarães











Resolução de problemas

RESOLUÇÃO DE PROBLEMAS MATEMÁTICOS


Seu problema pode ser modesto; mas se ele desafia sua curiosidade e desperta suas faculdades inventivas, e se você resolvê-lo por seus próprios meios, então você pode experimentar a tensão e o prazer do triunfo do descobrimento. Tais experiências criam o gosto pelo trabalho mental e ficam impressas em sua mente por toda a vida. (Polya)

Quando um matemático fala de seu trabalho, duas são as palavras que não pode deixar de mencionar:
· a primeira é problema e corresponde ao "alimento" de que se nutre a Matemática; com efeito, para o verdadeiro matemático, um grande problema é aquele que torna-se fonte de novas idéias e é capaz de fertilizar outros campos da Matemática.
a segunda palavra é prova; uma companheira inseparável da primeira e é quem produz o rigor que dá solidez e consistência ao edifício matemático; uma prova matemática é uma sequência de raciocínios dedutivos que parte de fatos de veracidade já reconhecida, como teoremas e axiomas, e chega até o resultado em demonstração; somente provas são capazes de dar atestado de veracidade matemática à solução de um problema, semelhantemente ao que fazem observações e experimentos controlados para o cientista natural.
O QUE É UM PROBLEMA MATEMÁTICO?

A Matemática é a única ciência onde pouco valor se dá à erudição. O valor de um matemático é avaliado não pelo que ele sabe mas por sua capacidade de resolver problemas. Um problema matemático é toda situação requerendo a descoberta de informações matemáticas desconhecidas para a pessoa que tenta resolvê-lo, e/ou a invenção de uma demonstração de um resultado matemático dado. O fundamental é que o resolvedor tenha de inventar estratégias e criar idéias; ou seja: pode até ocorrer que o resolvedor conheça o objetivo a chegar, mas só estará enfrentando um problema se ele ainda não tem os meios para atingir tal objetivo.

Resnick apontou várias características dos problemas que, bastante modificadas, resumimos assim:
· sem-algoritmização:o caminho da resolução é desconhecido, ao menos em boa parte.
· complexosprecisam de vários pontos de vista.
· exigentesa solução só é atingida após intenso trabalho mental; embora o caminho possa ser curto, ele tende a ser difícil.
· exigem-lucidêz-e-paciênciapara na aparente desordem vermos as regularidades, os padrões que permitirão a construção do caminho até a solução.
· nebulosospode ocorrer que nem todas as informações necessárias estejam aparentes; por outro lado, pode ocorrer que existam conflitos entre as condições estabelecidas pelo problema.
· não-há-resposta-únicaalém de normalmente ocorrer de existirem várias maneiras de se resolver um dado problema, pode ocorrer de não existir uma melhor solução e até de não existir solução; ao contrário do que a Escola ensina:
resolver um problema não é o mesmo que achar "a" resposta

A DIFERENÇA ENTRE PROBLEMA E EXERCÍCIO
O exercício é uma atividade de adestramento no uso de alguma habilidade / conhecimento matemático já conhecido pelo resolvedor, como a aplicação de um algoritmo CONHECIDO, de uma fórmula CONHECIDA, etc. O exercício envolve mera aplicação e o problema necessariamente envolve invenção ou/e criação significativa. Exemplificando: Tomemos como "resolvedor" um aluno de final do primeiro grau ( é importante apontar a pessoa, pois o que pode ser um problema para uma pessoa, pode não o ser para outra ):
o exercício:resolver a equação x 2 - 3x + 1 = 0 ( supõe-se que tal aluno conheça a fórmula de Bhaskara ).
o problema:provar a fórmula de Bhaskara ( supõe-se que tal aluno nunca tenha visto tal demonstração, mas conheça a fórmula ).
o problema:(mais-difícil)descobrir, provando, uma fórmula para resolver toda e qualquer equação algébrica do segundo grau ( supõe-se que tal aluno não conheça a fórmula de Bhaskara ).
problema:(ainda-mais-difícil)descobrir uma fórmula diferente da de Bhaskara e capaz de resolver toda e qualquer equação algébrica do segundo grau
O QUE É UM BOM PROBLEMA?

Um bom problema matemático além de representar um desafio, tanto ao poder dos matemáticos como ao poder da disciplina por eles criada, também "mexe" com a Matemática: faz com que a melhor entendamos, fertiliza-a e permite que possamos resolver outros problemas. Um ótimo exemplo é o chamado Problema de Fermat:

Sendo n = 3, 4, 5, ...,mostrar que NAO HA' nenhuma trinca de inteiros positivos x, y e z verificando a equação:
x n + y n = z n

enunciado mais simples é difícil achar, contudo esse problema precisou de quase 400 anos de esforços até ser resolvido por Andrew Wiles em 1995. Sua grandeza não está na dificuldade e também não está na utilidade desse resultado ( que é praticamente inexistente ); ela está no fato que as tentativas de resolvê-lo produziram idéias e problemas que fertilizam inúmeros campos: Teoria dos Números, Geometria Algébrica, etc.

COMO RESOLVER PROBLEMAS SEGUNDO GEORGE POLYA

A base para muita pesquisa em resolução de problemas matemáticos pode ser encontrada nos escritos de Polya, o campo da ciência cognitiva. Cientistas cognitivos buscam desenvolver ou validar teorias de aprendizagem humana enquanto educadores matemáticos buscam entender como seus alunos interagem com a matemática. A área da ciência cognitiva tem particular confiança nas simulações computacionais de resolução de problemas. Se um programa de computador gera uma sequência de comportamentos semelhantes aos dos humanos, então o programa é um modelo ou teoria do comportamento. Teorias construtivistas têm recebido considerável aceitação na educação matemática em anos recentes. Na pespectiva construtivista, o aprendiz deve ser envolvido ativamente na construção de seu próprio conhecimento ao invés de recebê-lo passivamente. A responsabilidade do professor é arranjar situações e contextos dentro das quais o aprendiz construa o conhecimento apropriado.

Procurando organizar um pouco o processo de resolução de problemas, o grande matemático George Polya o dividiu em quatro etapas, que resumimos abaixo. Antes de passarmos a elas, é muito importante enfatizar que Polya nunca pretendeu que sua divisão implicasse que resolver problemas fosse um procedimento a ser decorado nem que funcionasse como uma poção mágica.

ROTEIRO PARA RESOLVER PROBLEMAS
1).- ENTENDA O PROBLEMA:
Este princípio é evidente, mas às vezes, por sermos apressados ou por pressas que nos impõem de fora, colocamo-nos imediatamente a caminho. Quando lhe propuserem um problema, assegure-se de que entende os dados, as incógnitas e as condições que devem ser satisfeitas. Mesmo que ao princípio pareça melhor outro caminho, você ganhará tempo. O objetivo aqui é manter em mente o ponto onde se quer chegar.
Primeiro, você.tem de entender o problema.
Qual é a incógnita? Quais são os dados? Quais são as condições?
É possível satisfazer as condições? Elas são suficientes para determinar a incógnita? Ou são insuficientes? Ou redundantes? Ou contraditórias?
Faça uma figura. Outra se necessário. Introduza notação adequada.
o Separe as condições em partes.
2). CONSTRUA UMA ESTRATEGIA DE RESOLUCAO
Ache conexões entre os dados e a incógnita. Talvez seja conveniente considerar problemas auxiliares ou particulares, se uma conexão não for achada em tempo razoável. Use isso para "bolar" um plano ou estratégia de resolução do problema. Nesta fase do processo, você deve tentar reunir uma quantidade de possíveis modos de atacar o problema. É preciso que surjam muitas idéias, mesmo que de início possam parecer totalmente despropositadas. As idéias mais extravagantes podem depois vir a ser as melhores. Vale a pena expandirmos um pouco esses conselhos:
Você já encontrou este problema ou algum parecido?
Você conhece um problema semelhante? Você conhece teoremas ou fórmulas que possam ajudar?
Olhe para a incógnita! E tente achar um problema familiar e que tenha uma incógnita semelhante
Aqui está um problema relacionado com o seu e que você já sabe resolver. Você consegue aproveitá-lo? Você pode usar seu resultado? Ou seu método? Deve-se introduzir algum elemento auxiliar de modo a viabilizar esses objetivos?
Você consegue enunciar o problema de uma outra maneira?
Se você não consegue resolver o problema dado, tente resolver um problema parecido. Você consegue imaginar um caso particular mais acessível? Um caso mais geral e mais acessível? Você consegue resolver alguma parte do problema? Mantenha apenas parte das condições do problema e observe o que ocorre com a incógnita, como ela varia agora? Você consegue obter alguma coisa desde os dados? Você consegue imaginar outros dados capazes de produzir a incógnita? Você consegue alterar a incógnita ou os dados, ou ambos, de modo que a nova incógnita e os novos dados fiquem mais próximos? Talvez o problema seja complicado porque há muitos elementos. Por que você mesmo não o torna mais fácil. Tente resolver um problema parecido com menos elementos. Talvez com isso você tenha uma idéia para resolver o mais complicado. Começar pelo fácil torna fácil o difícil.
Você está levando em conta todos os dados? E todas as condições?
Faça um esquema. Muitas pessoas pensam melhor com imagens do que com palavras, ou seja, o pensamento durante uma investigação pode ser não-verbal, mas acompanhado de imagens sensoriais e até mesmo motoras.
Suponha que não ... Onde isto o leva? Este é o raciocínio a que se costuma chamar de indireto ou por redução ao absurdo. São muitos os problemas que se podem tratar assim. Você pretende demonstrar que uma situação se comporta de determinada forma. Começa supondo que não se comporta assim e vai fazendo deduções e raciocinando corretamente e a cadeia de raciocínios o leva a uma conclusão contrária ao senso comum. Fica claro então que o seu ponto de partida estava incorreto e fica assim demonstrado o resultado.
o Suponha o problema resolvido. Esta tática será especialmente útil nos problemas em que tenha que construir alguma figura, algum elemento que tenha de estar relacionado, de forma determinada pelas condições, com outros que são dados. Imagine o problema resolvido. E construindo de forma aproximada, a olho, como a coisa deve funcionar, terá oportunidade de explorar as relações entre os elementos dados e os que procura. Finalmente, ao aproximá-los, pode saltar a faísca que o faça ver claro como deve proceder a partir dos dados.
· 3).- EXECUTE A ESTRATÉGIA
Frequentemente, esta é a etapa mais fácil do processo de resolução de um problema. Contudo, a maioria dos principiantes tendem a pular para essa etapa prematuramente, e acabam dando-se mal. Outros elaboram estratégias inadequadas e acabam se enredando terrivelmente na execução.
Execute a estratégia.
Ao executar a estratégia, verifique cada passo. Você consegue mostrar claramente que cada um deles está correto?
Escolha uma boa notação. Muitos problemas ficam imensamente complicados com uma notação inadequada e tornam-se transparentes quando tomamos eixos adequados, os nomes apropriados para os elementos.
Se ao por em prática uma idéia lhe ocorrer outra totalmente desligada da primeira e que pensa poder lhe ajudar, não a despreze! Mas também não deixe desviar a atenção do que agora está a explorar.
Não abandone facilmente uma idéia que lhe pareceu boa. Mas também não insista demais com uma só idéia. Se as coisas se complicarem, haverá provavelmente um outro caminho. Você tem que estar preparado para reconhecer que as suas virtualidades talvez fossem uma miragem que se torna mais clara à medida que a explora. Se vir que a idéia não o faz aproximar-se da solução, tente outra.
4).- REVISE
Resolveu o problema? Parabéns! Ou trabalhou horas a fio, acabou por não o resolver? Parabéns também! Se passou algum tempo interessado e tentando resolver o problema e decidiu pedir auxílio para ver como se resolve o problema, a experiência até pode ser mais satisfatória do que no primeiro caso. Muitas vezes aprende-se muito mais, e mais profundamente, com os problemas que se tentaram com interesse e persistência e não se resolveram, do que com os que se resolvem quase à primeira vista. Lembre-se: O erro pode ser instrutivo, e as pessoas que realmente pensam, aprendem tanto com os sucessos quanto com os insucessos. Seja como for, o que é preciso agora é que reflita um pouco sobre todo o processo, para que fique com uma idéia de quais foram as suas dificuldades, os becos sem saída em que se encontrou e porquê e como poderia proceder no futuro para resolver melhor outros problemas, parecidos ou não. Esta fase do processo pode ser a mais proveitosa de todas e a que mais vezes nos esquecemos de realizar.
Examine a solução obtida. Examine o caminho que seguiu para obter a solução. Utilizou todos os dados? Satisfez todas as condições?
Verifique o resultado e o argumento. Não se contente em obter a resposta por acaso, pois a maior parte das vezes não terá tanta sorte.
Você pode obter a solução de um outro modo?
Qual a essência do problema e do método de resolução empregado? Em particular, você consegue usar o resultado, ou o método, em algum outro problema? Talvez você mesmo possa inventar outros problemas mais interessantes que se resolvam com os mesmos processos.
Neste roteiro é necessário enfatizar a dinâmica e a natureza cíclica deste. Um estudante pode iniciar com um problema e empregar seu pensamento para entendê-lo. O estudante tentará fazer um plano e no processo pode descobrir uma necessidade para entender o problema melhor. Ou quando um plano tem sido formado, o estudante pode tentar executá-lo e ser incapaz de fazê-lo. A próxima atividade pode ser tentar fazer um novo plano, ou voltar para desenvolver um novo entendimento do problema, ou apresentar um novo (possivelmente relacionado) problema para trabalhar.
Entendimento do Problema




Fazer um plano
Revisar a Resolução



Executar o Plano




Reflita sobre o seu próprio processo de pensamento. Repetindo experiências como esta, talvez consiga fazer um diagnóstico do seu próprio estilo de conhecimento. Como é o seu pensamento? É analítico ou visual? Depende da expressão verbal ou da fórmula escrita? Você tem tendência para o compromisso com uma única idéia, sem flexibilidade, ou para o raciocínio interativo? Como poderia aumentar o fluxo espontâneo de idéias variadas, novas, originais? Descobrindo as respostas a essas perguntas, você saberá como tratar problemas, não só matemáticos, mas de todos os gêneros, tentando, ao abordá-los, tirar o melhor partido possível das vantagens do seu próprio estilo.
NÍVEIS DE CAPACIDADE DE RESOLUÇÃO DE PROBLEMAS

Mesmo que uma pessoa tenha extenso conhecimento de um certo assunto matemático, estando aí incluídos um extenso conhecimento de algoritmos e até mesmo de heurísticas, isso não é bastante para garantir que ela tenha uma capacidade minimal de resolver problemas sobre esse assunto. Em Matemática, diferentemente do que ocorre em muitas disciplinas, muito mais importante que erudição e treinamento são:
· uma intuição cultivada, capaz de fazer ressonar as informações dadas no problema com conhecimentos e experiências do resolvedor
uma profundidade intelectual do resolvedor que seja capaz de relacionar itens conceitualmente e/ou proceduralmente muito distantes entre si
Em outras palavras: para uma dada pessoa, além de muito da sua capacidade de resolver problemas ser determinada geneticamente, a realização plena de seu potencial passa por uma orientação adequada e experiente.

M. G. Kantowski, em 1980, a partir de longas observações, dividiu o continuum das capacidades pessoais de resolução de problemas matemáticos em quatro estágios. Novamente, a dotação genética e a qualidade da orientação didática determinarão quão longe uma dada pessoa conseguirá ir nesse continuum. Ampliando os estágios de Kantowski para cinco, e usando nossa terminologia, teremos como estágios ou níveis de capacitação de resolvedor:
inerte:a pessoa tem nenhum ou quase nenhum entendimento do que seja resolver um problema matemático; em particular, não é capaz de atinar por onde começar. O máximo que se consegue fazer nesse estágio é reproduzir procedimentos de resolução muito simples e que foram exaustivamente explicados e exemplificados. Ou seja: uma pessoa nesse estágio está restrita ao mundo dos exercícios, e é necessário que esses sejam bastante exemplificados.
· imitador:com pouca explicação e exemplificação, torna-se capaz de fazer exercícios mas ainda não é capaz de resolver verdadeiros problemas; é capaz de participar produtivamente em grupos que estejam discutindo a resolução de problemas de tipo novo, contudo é incapaz de trabalhar sozinho.
· capaz:atingiu a capacidade de resolver problemas, mas esses devem ser variantes relativamente simples de problemas que aprendeu ou já resolveu.
· avançado:além de demonstrar uma capacidade superior de resolução, através da velocidade de resolução, da variedade e da maior complexidade dos problemas que é capaz de enfrentar, a pessoa começa a ser capaz de conceber processos de resolução diferentes dos que tinha aprendido.
· artista:a pessoa não só atingiu uma proficiência superior de inventar novos processos de resolução como preocupa-se em explorar caminhos alternativos, buscando resoluções mais elegantes ou poderosas

PROBLEMAS DESAFIOS

Quatro bolas do mesmo tamanho podem ser posicionadas de forma que qualquer duas delas se toquem. Cinco moedas iguais também. E seis cigarros? (Não vale dobrar nem quebrar os mesmos).

Dois barcos saem ao mesmo tempo de margens opostas de um rio bem largo, viajando em direção perpendicular às margens. Cada um trafega a velocidade constante, mas um é mais veloz do que o outro. Eles se cruzam a 720 metros de uma das margens. Chegando à margem oposta cada um deles pára por 10 minutos antes de começar a voltar, sempre com a mesma velocidade. Na viagem de volta eles se cruzam a 400 metros da outra margem. Qual é a largura do rio?

Um eletricista, trabalhando sozinho, encontra um problema intrigante. Na garagem de um edifício de 3 andares sem elevador ele encontra 11 extremidades de fios. Num buraco no topo do edifício descobre as outras extremidades dos mesmos fios. Seu objetivo é rotular as 22 extremidades com 11 rótulos de forma que as extremidades de um mesmo fio tenha rótulos iguais. Para cumprir sua tarefa ele pode fazer duas coisas: (1) por em curto circuito os fios na garagem ou no teto juntando extremidades; (2) testar por um circuito fechado por meio de testador de continuidade formado por uma bateria e uma campainha. A campainha toca quando o instrumento é acoplado às duas extremidades de um circuito contínuo formado por fios em série. Não querendo se exaurir subindo e descendo escadas desnecessariamente e sendo um apaixonado por Pesquisa Operacional, o eletricista sentou com lápis e papel, logo descobrindo a maneira mais eficiente de rotular os fios. Qual foi esse método? Será possível subir as escadas uma única vez?

Assumindo que um fósforo tem uma unidade de comprimento, é possível posicionar 12 fósforos formando um polígono com área inteira. Área 9 é muito fácil. Também é fácil área 5. Descubra se é possível usar todos os 12 fósforos para obter um polígono de área 4.

Um dos quebra-cabeças topológicos mais comuns consiste em desenhar uma linha contínua cruzando uma única vez cada uma das 16 arestas do retângulo subdividido em 5 retângulos abaixo:
É ou não possível resolver este problema? E se os retângulos forem desenhados na superfície de uma esfera? E na superfície de uma bóia salva-vidas, ou de uma câmara de ar (um toro, para os matemáticos)?

Quatro besouros, A, B, C e D ocupam os cantos de um quadrado de 10cm. A e C são machos, B e D fêmeas. Simultaneamente A rasteja em direção a B, B em direção a C, C em direção a D e D em direção a A. Se todos os besouros rastejam com a mesma velocidade eles vão formar 4 espirais logarítmicas que se encontram no centro do quadrado. Que distância cada besouro rasteja antes de se encontrarem? O problema pode ser resolvido sem cálculo integral.
Um número de nove dígitos é formado usando cada um dos dígitos 1,2,3, ... ,9 exatamente uma vez. Para n = 1,2,3, ... ,9, n divide o primeiro n dígito do número. Encontre o número.
Encontre um número irracional tal que é racional.

Uma câmara de bolhas contém três tipos de partículas sub-atômicas: 1998 partículas X, 2002 partículas Y e 2003 de tipo Z. Sempre que uma partícula X e uma Y colidem ambas se transformam em partículas de tipo Z. Igualmente, a colisão de uma Y com uma Z torna ambas do tipo X, e a colisão de uma X e uma Z torna ambas do tipo Y. Poderá ocorrer de com o tempo restar apenas um tipo de partículas em tal câmara?

Na figura abaixo, ABC é um triângulo isósceles ( AB = AC ) e o ângulo BAC mede 100 graus. Prolonga-se AB até um ponto D de modo que AD = BC. Qual o valor do ângulo BCD?







Não se iluda com a aparência de brincadeira deste problema. Ele NÃO é mais uma curiosidade inconsequente para entreter alunos desmotivados. Em verdade, ele é um problema que deve fazer parte da bagagem de todo profissional competente da área matemática. Sua importância resume-se em duas capacidades:
de modo simples e concreto, exemplifica a enorme velocidade de crescimento da fatorial
· prova-se que muitos problemas combinatórios envolvem tantas alternativas de solução quanto este problema, de modo que ele é uma espécie de "metro" com o qual medimos a complexidade computacional dos problemas combinatórios ocorrendo em engenharia e no trabalho científico.
Formulando o problema do caixeiro:
Suponha que um caixeiro viajante tenha de visitar n cidades diferentes, iniciando e encerrando sua viagem na primeira cidade. Suponha, também, que não importa a ordem com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer outra. O problema do caixeiro viajante consiste em descobrir a rota que torna mínima a viagem total.
Exemplificando o caso n = 4: se tivermos quatro cidades A, B, C e D, uma rota que o caixeiro deve considerar poderia ser: saia de A e daí vá para B, dessa vá para C, e daí vá para D e então volte a A. Quais são as outras possibilidades ? É muito fácil ver que existem seis rotas possíveis: ABCDA, ABDCA, ACBDA, ACDBA, ADBCA e ADCBA.
Complexidade computacional do problema do caixeiro:
O problema do caixeiro é um clássico exemplo de problema de otimização combinatória. A primeira coisa que podemos pensar para resolver esse tipo de problema é reduzi-lo a um problema de enumeração: achamos todas as rotas possíveis e, usando um computador, calculamos o comprimento de cada uma delas e então vemos qual a menor. ( É claro que se acharmos todas as rotas estaremos contando-as, daí podermos dizer que estamos reduzindo o problema de otimização a um de enumeração ).
Para acharmos o número R( n ) de rotas para o caso de n cidades, basta fazer um raciocínio combinatório simples e clássico. Por exemplo, no caso de n = 4 cidades, a primeira e última posição são fixas, de modo que elas não afetam o cálculo; na segunda posição podemos colocar qualquer uma das 3 cidades restantes B, C e D, e uma vez escolhida uma delas, podemos colocar qualquer uma das 2 restantes na terceira posição; na quarta posição não teríamos nenhuma escolha, pois sobrou apenas uma cidade; consequentemente, o número de rotas é 3 x 2 x 1 = 6, resultado que tínhamos obtido antes contando diretamente a lista de rotas acima. De modo semelhante, para o caso de n cidades, como a primeira é fixa, o leitor não terá nenhuma dificuldade em ver que o número total de escolhas que podemos fazer é (n-1) x (n-2) x ... x 2 x 1. De modo que, usando a notação de fatorial: R( n ) = ( n - 1 )!.
Assim que nossa estratégia reducionista consiste em gerar cada uma dessas R( n ) = ( n - 1 )! rotas, calcular o comprimento total das viagens de cada rota e ver qual delas tem o menor comprimento total. Trabalho fácil para o computador, diria alguém. Bem, talvez não. Vejamos o porquê. Suponhamos que temos um computador muito veloz, capaz de fazer 1 bilhão de adições por segundo. Isso parece uma velocidade imensa, capaz de tudo. Com efeito, no caso de 20 cidades, o computador precisa apenas de 19 adições para dizer qual o comprimento de uma rota e então será capaz de calcular 109 / 19 = 53 milhões de rotas por segundo. Contudo, essa imensa velocidade é um nada frente à imensidão do número 19! de rotas que precisará examinar. Com efeito, acredite se puder, o valor de 19! é 121 645 100 408 832 000 ( ou , aproximadamente, 1.2 x 1017 em notação científica ). Consequentemente, ele precisará de
1.2 x 1017 / ( 53 milhões ) = 2.3 x 109 segundos
para completar sua tarefa, o que equivale a cerca de 73 anos . O problema é que a quantidade ( n - 1 )! cresce com uma velocidade alarmante, sendo que muito rapidamente o computador torna-se incapaz de executar o que lhe pedimos. Constate isso mais claramente na tabela a seguir:
n
rotas por segundo
( n - 1 )!
cálculo total
5
250 milhões
24
insignificante
10
110 milhões
362 880
0.003 segundos
15
71 milhões
87 bilhões
20 min
20
53 milhões
1.2 x 1017
73 anos
25
42 milhões
6.2 x 1023
470 milhões de anos
Observe que o aumento no valor do n provoca uma muito lenta diminuição na velocidade com que o computador calcula o tempo de cada rota ( ela diminui apenas de um sexto ao n aumentar de 5 para 25 ), mas provoca um imensamente grande aumento no tempo total de cálculo. Em outras palavras: a inviabilidade computacional é devida à presença da fatorial na medida do esforço computacional do método da redução. Com efeito, se essa complexidade fosse expressa em termos de um polinómio em n o nosso computador seria perfeitamente capaz de suportar o aumento do n. Confira isso na seguinte tabela que corresponde a um esforço computacional polinomial R( n ) = n5:
n
rotas por segundo
n 5
cálculo total
5
250 milhões
3 125
Insignificante
10
110 milhões
100 000
insignificante
15
71 milhões
759 375
0.01 segundos
20
53 milhões
3 200 000
0.06 segundos
25
42 milhões
9 765 625
0.23 segundos
Então o método reducionista não é prático ( a não ser para o caso de muito poucas cidades ), mas será que não pode-se inventar algum método prático ( por exemplo, envolvendo esforço polinomial na variável número de ) para resolver o problema do caixeiro? Bem, apesar de inúmeros esforços, ainda não foi achado um tal método e começa-se a achar que o mesmo não existe.
A existência ou não de um método polinomial para resolver o problema do caixeiro viajante é um dos grandes problemas em aberto da Matemática na medida em que S. A. COOK ( 1971 ) e R. M. KARP ( 1972 )) mostraram que uma grande quantidade de problemas importantes ( como é o caso de muitos tipos de problemas de otimização combinatória, o caso do problema da decifragem de senhas criptografadas com processos modernos como o DES, etc ) podem ser reduzidos, em tempo polinomial, ao problema do caixeiro.
Consequentemente: se descobrirmos como resolver o problema do caixeiro em tempo polinomial ficaremos sendo capazes de resolver, também em tempo polinomial, uma grande quantidade de outros problemas matemáticos importantes; por outro lado, se um dia alguém provar que é impossível resolver o problema do caixeiro em tempo polinomial no número de cidades, também se terá estabelecido que uma grande quantidade de problemas importantes não tem solução prática. Costuma-se resumir essas propriedades do problema do caixeiro dizendo que ele pertence à categoria dos problemas NP - completos.
EXERCÍCIOPor que o computador, no caso de 21 cidades, precisaria de 20 vezes mais anos do que precisou para resolver o caso de 20 cidades pelo método reducionista?
EXERCÍCIOVocê seria capaz de ver relação entre o problema do caixeiro viajante e os seguintes problemas tecnológicos, de enorme importância econômica?
· a minimização do tempo que um robô industrial gasta para soldar a carcaça de um automóvel ?
· custo em tempo ou combustível na rota da distribuição diária de um jornal produzido numa grande cidade?
· custo em tempo na rota de abastecimento das várias bases militares envolvidas numa guerra?
EXERCÍCIOImagine um computador com velocidade fantástica, à sua escolha. Faça tabela das fatoriais de 10 a 100, pulando de 10 em 10. Para cada uma dessas fatoriais, calcule o tempo que esse computador levaria para resolver o respectivo problema do caixeiro viajante. Conclusão?
EXERCÍCIOCompare o esforço da resolução do problema do caixeiro viajante com o do cálculo - diretamente, pela definição - de um determinante n x n.
EXERCÍCIOFaça a análise da complexidade computacional da variante do problema do caixeiro que tem cidade inicial e cidade final distintas.