Revisão MC458

Questões-guia:

1. O que é um algoritmo?
2. O que é um problema computacional?
3. O que é um invariante de malha (ou de laço)? [em inglês: loop invariant]
4. Qual o modelo de computação usado no Cormen?
5. O que é o tamanho da entrada de um algoritmo?
6. Qual a diferença entre análise de caso médio e análise de pior caso?
7. O que é e para que serve uma árvore de recursão?
8. O que significa f(n) = O(g(n))?
9. O que diz e para que serve o Teorema Mestre?

Exercícios:

1. Faça o diagrama JSP para um dos seguintes algoritmos: insertion sort, merge sort, selection sort.
2. No exercício C3-3a, escolha uma linha ou uma coluna e faça o exercício só para estas funções.
3. No exercício C4-1, escolha uma das recorrências (a-g) e resolva.