Introdução aos principais paradigmas do projeto de algoritmos – recursividade

PASSOS

Passo 1 (Equipe)

Criar um grafo com no mínimo 5 vértices, represente-o através da matriz de adjacência e através da lista de adjacência e façam um algoritmo que dê o grau de cada um de seus vértices, usando as duas maneiras representadas. Apresentar a complexidade dos algoritmos criados.

Passo 2 (Equipe)

Desenhar o grafo ponderado que representa a seguinte situação: Supor que um funcionário encarregado de verificar o estado das estradas, deseja planejar a sua rota de inspeção nas estradas que existem entre as cidades A, B, C, D e E. A rota deve se iniciar na cidade A. O custo de cada estrada é:

Estrada ligando a cidade A à cidade B = 3;

Estrada ligando a cidade A à cidade E = 12;

Estrada ligando a cidade B à cidade C = 3;

Estrada ligando a cidade B à cidade D = 2;

Estrada ligando a cidade B à cidade E = 7;

Estrada ligando a cidade C à cidade D = 2;

Estrada ligando a cidade E à cidade D = 6.

Passo 3 (Equipe)

Fazer a matriz de custos que representa o grafo do passo 2 dessa etapa.

Passo 4 (Equipe)

Calcular o caminho de custo mínimo para o inspetor percorrer. Entregar ao professor todos os passos da etapa descritos no Relatório 3.

ETAPA 4 (tempo para realização: 4 horas)

 Aula-tema: Introdução aos principais paradigmas do projeto de algoritmos – recursividade.

Essa atividade é importante para que você perceba a diferença entre as análises de um algoritmo recursivo e um algoritmo iterativo.

Para realizá-la, é importante seguir os passos descritos.

PASSOS

Passo 1 (Aluno)

Pesquisar em Ziviani (2005) ou em Cormen (2002) as diferenças entre os dois tipos de algoritmos: iterativo e recursivo, dando pelo menos um exemplo de cada um deles.

Ciência da Computação – 7ª Série – Análise e Complexidade de Algoritmos

Marcela Cristiani Ferreira

Pág. 6 de 8

Passo 2 (Aluno)

Pesquisar no livro do Cormen (2002), os métodos de resolução de uma equação de recorrência. Apresentar a equação de recorrência que representa o algoritmo recursivo extraído do livro do Ziviani (2005), capítulo 1, página 22:

Pesquisa (n);

(1) if n <= 1

(2) then ‘inspecione elemento’ e termine

else begin

(3) para cada um dos n elementos ‘inspecione elemento’;

(4) Pesquisa (n/3);

end;

Em seguida, resolva a seguinte equação