Trabalho Algoritmo 3

Área:

Tecnologia e Computação - Campus Canoas

Verificação:

Curso:

Cursos de Informática

Aula:

Disciplina:

APIII

Turma:

Professor :

G1

G2
Rec

Edemar Costa Oliveira

Trabalho a ser entregue em link no moodle até o dia 13/11/2013.
Individual - Peso 1,0 na nota de G2.
1. Suponha um algoritmo A e um algoritmo B com funções de complexidade de tempo a(n) = n2 – n + 549 e b(n) = 49n + 49, respectivamente.
Determine quais são os valores de n pertencentes ao conjunto dos números naturais para os quais A leva menos tempo para executar do que B.
2.
Considere que você tenha um problema para resolver e duas opções de algoritmos. O primeiro algoritmo é quadrático tanto no pior caso quanto no melhor caso. Já o segundo algoritmo, é linear no melhor caso e cúbico no pior caso.
Considerando que o melhor caso ocorre 90% das vezes que você executa o programa enquanto o pior caso ocorre apenas 10% das vezes, qual algoritmo você escolheria? Justifique a sua resposta em função do tamanho da entrada.
3.
Dois algoritmos A e B possuem complexidade n5 e 2n, respectivamente. Você utilizaria o algoritmo B ao invés do A. Em qual caso? Exemplifique.
4.
Tabuleiro com n x n posições:
• cavalo se movimenta segundo regras do xadrez. Problema: a partir de (x0; y0), encontrar, se existir, um passeio do cavalo que visita todos os pontos do tabuleiro uma única vez.
Elaborar o algoritmo com a melhor solução possível e avalie a complexidade desse algoritmo Implementar e calcular a complexidade do algoritmo que determina o valor de um polinômio. Algoritmo:
Início
Leia(n,an, an-1,..., a0 x0) p = a0 para j=1 até n faça p = p + aj x0j fim; imprima(p);
fim