201501 APA Aula ProjetoAlgoritmos 1

Análise e Projeto de Algoritmos
Paradigmas de Projetos de Algoritmos
Jaqueline Faria de Oliveira
Mestre em Informática
E-mail: [e-mail]

1

Recursividade
Paradigmas de Projetos de Algoritmos

2

Recursividade

3

Recursividade

4

Implementação de recursividade

5

Problema de Terminação em
Procedimentos Recursivos

6

Problema de Terminação em
Procedimentos Recursivos

7

Quando não usar recursividade

8

Quando não usar recursividade Exemplo

9

Quando não usar recursividade Exemplo

10

Versão iterativa do Cálculo de
Fibonacci

11

Recursividade
• Comentários finais:
– Técnica bastante adequada para expressar algoritmos que são definidos recursivamente.
– No entanto, deve ser usada com muito cuidado.
– Na maior parte dos casos funciona como uma técnica conceitual ao invés de uma técnica computacional.
– Algoritmos recursivos são normalmente modelados por uma equação de recorrência.
– Ao se fazer a análise de um algoritmo recursivo, devese também analisar o crescimento da pilha.
12

Algoritmos tentativa e erro
(Backtracking)
Paradigmas de Projetos de Algoritmos

13

Algoritmos tentativa e erro
(Backtracking)
• Tentativa e erro: decompor o processo em um número finito de sub-tarefas parciais que devem ser exploradas exaustivamente. • O processo de tentativa gradualmente constrói e percorre uma árvore de subtarefas.
• Algoritmos tentativa e erro não seguem uma regra fixa de computação:
– Passos em direção à solução final são tentados e registrados.
– Caso esses passos tomados não levem à solução final, eles podem ser retirados e apagados do registro.
14

Algoritmos tentativa e erro
(Backtracking)
• Tentativa e erro: decompor o processo em um número finito de sub-tarefas parciais que devem ser exploradas exaustivamente. • O processo de tentativa gradualmente constrói e percorre uma árvore de subtarefas.
• Algoritmos tentativa e erro não seguem uma regra fixa de computação:
– Passos em direção à solução final são tentados e