Pseudo-código de algoritmo de tentativa e erro (backtracking) - slide do livro do Ziviani baixado da Web - Aula de 08.08.2017

Em linhas gerais um método guloso tem os passos descritos no slide abaixo:

Desafio 1: Compare os pseudo-códigos do algoritmo guloso e do tentativa e erro. Aponte semelhanças e diferenças.


Desafio 2: Use o algoritmo de tentativa e erro para tentar resolver um problema que conhece, por exemplo o problema da mochila. Procure saber o que é árvore de execução. Simule a execução (ou: faça o teste de mesa) do algoritmo de tentativa e erro representando a simulação em uma árvore de execução.

Desafio 3: Analise o código que escreveu a fim de saber que variável ṕode ser usada como "tamanho do problema" e como o tempo de execução (ou quantidade de operações executadas, ou quantidade de comparações executadas) evolui em função do tamanho do problema.

Desafio 4: Escreva o programa, meça os tempos de execução de diferentes conjuntos de dados para o problema da mochila e construa o gráfico do tempo de execução em função do tamanho do problema. O resultado coincide com o que intuiu no desafio 1?

Problemas muito usados para exemplificar tentativa e erro:

• Passeio do cavalo;
• 8 rainhas;
• n rainhas;
• Problema da mochila;
• Problema do circuito Hamiltoniano.

Próximos assuntos em ordem cronológica (previsto em 06.08.2017):

• combinatória;
• crescimento de funções;
• divisão e conquista (exemplos: busca binária e MergeSort);
• sequências e séries, fórmulas de recorrência e fórmulas fechadas;
• demonstração por indução;
• indução fraca/forte;
• Notação Assintótica;
• Teorema Mestre;
• HeapSort;
• QuickSort;
• Cota Inferior para algoritmos de ordenação, aproximação de Stirling;
• Ordenação em tempo linear;
• Espalhamento (hashing);