ENEM
Um gostinho do impossível
Ao explorar uma questão do Enem, o estudante chega a um dos grandes problemas atuais: o de minimizar o somatório dos pesos de um grafo
Diante de um grafo (vértices interligados por arestas), o estudante pode fazer uma pergunta inicial importante: “Todos os pontos estão interconectados a todos os outros? De que modo?” Basta inspecionar o grafo para ver que nenhum ponto está conectado a nenhum outro por mais de uma aresta. Em outras palavras, há apenas uma rota entre duas cidades; trata-se de um grafo simples. Para dar resposta à pergunta, portanto, basta contar o número de arestas que chegam (saem) a cada vértice: quatro. Isso significa que cada vértice está interligado a todos os outros; trata-se de um grafo completo.
Bem, de quantos modos alguém pode organizar uma sequência de sete letras, sabendo que a primeira e a última são sempre iguais a A e que não deve repetir as letras do meio? Para pensar melhor sobre esse assunto, basta um desenho:
A.___.___.___.___.___.A
Na segunda casa, o estudante pode escolher uma entre cinco letras; na terceira, uma entre quatro letras; na quarta, uma entre três letras; etc. É um problema de contagem: “Quantas permutações posso montar com as letras BCDEF?”
5 · 4 · 3 · 2 · 1 = 5! = 120
Se nem todos os pontos estivessem ligados a todos os outros, o problema ficaria mais complicado. Por exemplo, se não houvesse uma aresta entre os vértices B e F, o estudante teria de tirar todas as permutações nas quais aparecem BF ou FB em qualquer posição válida. Ao redigir essa questão 173, o povo do Enem facilitou as coisas deixando todos os vértices interligados a todos os outros.
Esse é um grafo valorado, no qual ou os vértices, ou as arestas, ou ambos estão associados a números, oupesos, que podem significar custo, tempo, taxa de congestionamento, etc. Num grafo como o da questão 173, a permutação ABCDEFA vale tanto quanto a permutação AFEDCBA (que é ABCDEFA de trás para frente). Então, o personagem João não tem de calcular o custo de todas as 120 permutações, mas de metade delas. Como precisa de um minuto e meio para executar a adição e riscar a permutação simétrica, levará quanto tempo para correlacionar cada permutação a uma soma?
60 · 1,5 = 90
A resposta certa é, portanto, a (b): 90 minutos.
Na matemática, problemas como esse são conhecidos pela sigla TSP, que vem da locução inglesa traveling-salesman problem, isto é, problema do vendedor ambulante ou problema do caixeiro-viajante. Ainda não existe fórmula com a qual o estudante possa, de um jeito simples, calcular a rota de menor custo. (Ou, em termos mais técnicos, minimizar a soma dos pesos.) Ele pode delegar a tarefa a um computador bem programado, mas, conforme o número de vértices aumenta, até computadores rápidos precisam de muito tempo para achar a solução de menor custo. Em alguns casos, várias vezes a idade do universo…
O estudante pode imaginar, por exemplo, o caso do engenheiro que precisa programar um braço robótico para soldar componentes numa placa de circuito impresso. Pode imaginar o local de cada componente como um vértice. E pode ver que a ordem de soldagem altera o custo da operação: soldar o componente A e depois o B não custa a mesma coisa que soldar o A e depois o C. Para fabricar placas com 120 componentes, o engenheiro teria de achar a permutação de menor custo entre ≈6,7 · 10(elevado a)198 permutações, o que é um inteiro positivo com 199 algarismos. Um computador de mesa moderno levaria vários trilhões de anos para completar os cálculos. É por isso que tantos matemáticos se especializam em otimização combinatória: eles vivem de imaginar métodos pelos quais calcular não a rota de menor custo (o que com frequência é impossível), mas uma rota de custo relativamente baixo, dentro de determinada margem de erro, e num tempo razoável.
REVISTA CÁLCULOS - matemática para tdos
Nenhum comentário:
Postar um comentário