Algoritimo

603 palavras 3 páginas
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 em sequê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 com sequê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 o subproblema 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 fazer essas 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 arquivo miles.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ância entre 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 da cidade 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 formato indicado.

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

Relacionados

  • Algoritimo
    616 palavras | 3 páginas
  • algoritimos
    331 palavras | 2 páginas
  • Algorítimos
    938 palavras | 4 páginas
  • Algoritimo
    3804 palavras | 16 páginas
  • algoritimo
    413 palavras | 2 páginas
  • Algoritimo
    3446 palavras | 14 páginas
  • Algoritimo
    253 palavras | 2 páginas
  • Algoritimo
    294 palavras | 2 páginas
  • Algoritimo
    362 palavras | 2 páginas
  • Algoritimo
    281 palavras | 2 páginas