7.9.	Exercício de Implementação
O primeiro passo para irmos de encontro a uma “solução” para problemas complexos, é você ganhar um “feeling” para estes problemas. 
Para poder ter uma noção de o que significa resolver um problema complexo, nós vamos implementar o problema do caixeiro viajante, que todos vimos em Teoria dos Grafos, e observar o seu comportamento no tempo:
Para a solução do Problema do Caixeiro Viajante existem muitos algoritmos, dentre eles o “Método Algébrico de Christofides”, o Algoritmo de Rubin e o Algoritmo de Roberts e Flores. O mais interessante é o de Roberts e Flores pois pode ser implementado de forma recursiva bastante simples em uma linguagem como Prolog. Podemos também implementá-lo em “C” ou Pascal sem muitos problemas.

Exercício 2.1 (prazo: 2 semanas):
•	Implemente o Problema do Caixeiro Viajante usando um algoritmo de sua escolha e uma linguagem de sua escolha. 
•	Calcule o Ciclo de Menor Custo para os grafos abaixo, observando o tempo de execução para cada um deles.
•	Plote o tempo de execução em uma curva, mostrando o comportamento assintótico deste algoritmo com relação a: a) o número de vértices do grafo, b) o número de arestas do grafo. Para isso você pode utilizar uma função de plotagem de alguma planilha que você use ou o programa Gnuplot.
•	Qual a complexidade de tempo aproximada do algoritmo para n=número de vértices ? E para n=número de arestas ?

•	Além dos grafos acima, rode o programa também para:
- Um grafo de 7 vértices, 
- um grafo de 10 vértices, 
- um grafo de 15 vértices e 
- um grafo 20 vértices
onde os custos das arestas são valores aleatórios entre 5 e 30.
Exercício 2.2 (prazo: 2 semanas):
Torres de Hanoi
Este é um jogo milenar consistindo de três pinos e de um conjunto variável de discos, todos de tamanhos diferentes. Inicialmente os discos estão empilhados em um extremo, o maior embaixo, o menor em cima. O objetivo é colocar todos os discos no outro lado do tabuleiro, na mesma ordem, seguindo as seguintes regras:
•	Um único disco pode ser movido diretamente, saltando por cima do pino do meio;
•	N discos podem ser movidos em três passos:
•	Mova N - 1 discos para o pino do meio,
•	Mova o último disco diretamente para o pino da direita,
•	Mova os N - 1 discos do pino do meio para o da direita.
O único prerequisito é que nunca um disco maior poderá estar sobre um menor. 
Resolva este exercício da mesma forma que o anterios, implementando-o (pesquise na literatura - o mais simples é usar Prolog), rodando-o para 2,3,4,5,10,15,20,30 e 50 discos e plotando o sresultados em uma curva. Identifique a complexidade do problema justificando.