PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2008.1
2 de maio de 2008
Horário: 2as-feiras e 4as-feiras de 9 às 11 horas
ANÁLISE DE ALGORITMOS (INF 1721)
2a Lista de Exercícios
  1. Exercícios Livro Algorithms, Dasgupta, Papadimitriou e Vazirani.
  2. Seja o algoritmo de Dijkstra abaixo.
    Algoritmo Dijkstra (s - fonte)
  3. Seja G=(V,E) um grafo orientado e acíclico, com distâncias le para e Î E , e s um vértice a partir do qual existe caminho para todos os demais vértices do grafo. Proponha um algoritmo com complexidade O(m), m=|E|, para encontrar os c.m.c.'s de s aos outros vértices do grafo. (Dica: use ordenação topológica.)

  4. Considere o Algoritmo de Dijkstra para encontrar o Caminho-mais-curto (c.m.c.) entre o vértice s e os outros vértices de um grafo G=(V,E), orientado onde as distâncias dos arcos e Î E é dada por we.
  5. Prove que é verdade ou que é falso (nesse caso apresentando um contra-exemplo).
  6. Seja G=(V,E) um grafo orientado e acíclico, e s um vértice a partir do qual existe caminho para todos os demais vértices do grafo. Proponha um algoritmo com complexidade O(m), m=|E|, para encontrar os c.m.c.'s de s aos outros vértices do grafo. Para isso, percorra os vértices seguindo uma ordenação topológica. O seu algoritmo deve encontrar uma ordenação topológica e o c.m.c de s aos demais vértices do grafo em O(m). Explique com detalhes este algoritmo.

  7. Suponha que foram obtidos os c.m.c.'s de s aos outros vértices de G e a árvore de c.m.c. é conhecida. Suponha agora que as distâncias de todos os arcos deve ser aumentada de k unidades. Proponha um algoritmo O(m) para obter os novos c.m.c.'s.

  8. Uma floresta é um grafo sem ciclos. Seja um grafo G=(V,E), não-orientado onde os pesos das arestas e Î E são dados por de. Proponha um algoritmo para encontrar uma floresta com k arestas, k £ n - 1, de peso total mínimo. Sua complexidade tem que ser O(n2) ou inferior.

  9. Seja o grafo G=(V,E), não-orientado onde os pesos das arestas e Î E são dados por de. Seja também T(e) a árvore geradora mínima que inclui a aresta e. Proponha um algoritmo que encontra as árvores geradoras T(e) para e Î E (i.e. são m=|E| árvores geradoras mínimas) (todas) em O(n2) (n=|V|).

  10. Considere que a árvore geradora de peso mínimo (AGM) de G=(V,E), não-orientado onde os pesos das arestas e Î E são dados por de, é conhecida. Considere agora que um novo vértice foi acrescentado à G com arestas para todos os vértices em V. Proponha um algoritmo para encontrar a nova AGM. Seu algoritmo deve excutar em O(n    log    n) ou menos. Tente encontrar um algoritmo O(n), existe.

  11. Considere um mapa rodoviário e um motorista que tem que ir do vértice s ao t. O mapa é representado pelo grafo G=(V,E), não-orientado onde os valores associados às arestas e Î E, he, correspondem às altitudes das estradas correspondentes aos trechos. O motorista não gosta de altitude e quer fazer o caminho que minimiza a maior altitude que ele vai passar. Utilize um algoritmo de árvore geradora mínima para encontrar esse caminho. Qual a complexidade?

This document was translated from LATEX by HEVEA.