Trabalho Algoritmo 3

294 palavras 2 páginas
Á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

Relacionados

  • Trabalho APS ORDENA O
    2723 palavras | 11 páginas
  • Algoritmos 4
    2142 palavras | 9 páginas
  • Algoritimo Termindado
    1076 palavras | 5 páginas
  • Trabalho de augoritimo
    1936 palavras | 8 páginas
  • Relatório técnico de analise experimental da complexidade de algoritmos em classificação de dados em tempo linear
    4795 palavras | 20 páginas
  • algoritmos e estrutura de dados
    958 palavras | 4 páginas
  • Substituição de Páginas
    1965 palavras | 8 páginas
  • ATPS Algoritmo e Programação
    1902 palavras | 8 páginas
  • Algg
    1579 palavras | 7 páginas
  • fisica 2
    1877 palavras | 8 páginas