Detalhes - Dissertação do PROFMAT

Aluno: ANDERSON OLIVEIRA VIANA

UFSJ - Universidade Federal de São João del-Rei - Ouro Branco - MG

Dissertação

Título
Algoritmos em Grafos e o Problema do Caixeiro Viajante: uma abordagem no Ensino Médio utilizando planilhas eletrônicas.
Resumo
Este trabalho apresenta uma visão geral e básica sobre Grafos e uma abordagem especial de dois problemas relacionados a esse tema da Matemática: o Problema do Caminho Mais Curto e o Problema do Caixeiro Viajante. O Problema do Caminho Mais Curto, pelo grande número de aplicações práticas, mereceu um destaque especial neste texto. Dois algoritmos resolutivos do problema, o Algoritmo de Dijkstra e o Algoritmo de Floyd-Warshall, são apresentados e modelos são implementados em planilhas eletrônicas. O Problema do Caixeiro Viajante (PCV), um dos problemas mais conhecidos e estudados na Otimização Combinatória, é caracterizado e variantes são apresentadas. Modelos do problema na versão clássica e da variante PCV com Coleta de Prêmios são implementados em planilhas eletrônicas. Na seção final do trabalho, apresentamos atividades que podem ser ministradas por professores de Matemática em aulas sobre o tema Grafos em turmas do ensino médio.
[Download TCC]

---