Algoritimo

Páginas: 3 (603 palavras) Publicado: 19 de agosto de 2013
Trabalho 1 – ordenação (para 13/9)
O objetivo do trabalho é comparar alguns algoritmos de ordenação.

Implemente os algoritmos estudados em aula (seleção, inserção, mergesort, quicksort,heapsort). Escreva o programa mais simples possível para testar cada algoritmo. Compare o esforço necessário para a implementação correta de cada algortimo.

Compare o desempenho dos algoritmos emsequências de números inteiros gerados aleatoriamente. Use sequências de 100 até 100000 números. (E mais se for possível.) Meça e compare os tempos de cada algoritmo.

Repita os testes comsequências especiais: ordenadas em ordem crescente, ordenadas em ordem descrescente, com muitas repetições, com poucas repetições.

No caso de mergesort e quicksort, interrompa a recursão quando osubproblema for pequeno e execute ordenação por inserção em cada subproblema. No caso de quicksort, faça o mesmo executando ordenação por inserção uma única vez, ao final do processo. Vale a pena fazeressas modificações? A partir de quando? Para qual definição de pequeno?

Trabalho 2 – grafos (para 23/10)
map O grafo ao lado mostra 128 cidades da América do Norte. Ele foi extraído do arquivomiles.dat do livro The Stanford GraphBase. O arquivo map.txt representa esse grafo: os vértices estão numerados de 1 a 128 e cada linha lista uma aresta do grafo e o seu comprimento, isto é, a distânciaentre as cidades dadas.

Encontre uma árvore geradora mínima para esse grafo.
Encontre o menor caminho entre a cidade 93 e a cidade 112.
Encontre a árvore de menores caminhos a partir dacidade 104.

Para cada um desses subgrafos, calcule o comprimento total.

Se quiser gerar uma figura, edite o arquivo map.eps para incluir o subgrafo após a linha marcada subgraph no formatoindicado.

Faça o mesmo para o grafo das 5565 sedes dos municípios do Brasil, encontrando o menor caminho entre a cidade 1 e cidade 2646, e a árvore de menores caminhos a partir da cidade 2646. Veja...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • algoritimo
  • Algoritimo
  • Algoritimos
  • Algoritimo
  • algoritimos
  • algoritimos
  • Algoritimo
  • Algoritimo

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!