Lista de exercicio 1 - Cormen 2º Edição

Prévia do material em texto

Aluno: Vinícius Barcelos Silva
Matricula: 108251
1.1­2:
Espaço
1.1­3:
A lista encadeada.
Ponto forte: podemos inserir em qualquer posição e poder determinar níveis de prioridades 
dentro para determinar onde ele será inserido na lista caso seja necessário.
Fraco: para se remover um elemento é necessário percorrer a lista praticamente inteira até que 
se encontre o elemento desejado.
1.1­4:
Semelhanças: buscar o “melhor” caminho. Diferenças: ciclo, necessita que todos pontos sejam 
visitados e ponto inicial é o mesmo do ponto final, fechando assim o ciclo.
1.1­5:
Melhor solução: quando é necessário o uso de um algoritmo de ordenação.
“Aproximadamente” a melhor: em um problema NP­completo no qual não tivermos a melhor 
solução, por exemplo o problema do caixeiro­viajante.
1.2­2:
No intervalo entre 2 <= n <= 43
1­1:
2) Apresente duas nova melhorias para o código do programa primo.c, descrito em aula, de 
forma a reduzir ainda mais o seu tempo de execução.
Algoritmo melhor que primo1, primo2 e primo3:
Crivo de Erastotenes:
Para encontrar os números primo de 2 a N, usamos o piso da raiz de N como o limite de 
números a serem verificados.
Em seguida encontre o primeiro número primo da lista, no caso 2, deleta todos os múltiplos 
desse primo e avança ao próximo número até encontrar o piso da raiz de N.
Logo os números que não foram excluídos da lista são todos primos.