ProjetoAnaliseAlgoritmo_6_AtividadeAvaliacao - Gabarito (1)

Prévia do material em texto

06
PROJETO E ANÁLISE DE ALGORITMOS
ATIVIDADE PARA AVALIAÇÃO
EXERCÍCIO 1
Considere o grafo da figura 2. Para cada uma das sequências de vér-
Figure 1: Exercício1.
tices a seguir, indique se ela pode corresponder a uma sequência de des-
coberta de vértices produzida pelos algoritmos apresentados na videoaula
de busca em largura, em profundidade, por ambos algoritmos ou por
Projeto e Análise de Algoritmos / Aula 11-12 Atividade para Avaliação 2
nenhum dos dois algoritmos.
(a) F,C,H,A,B,G,E,D (0,75 ponto)
(b) F,H,A,C,E,G,B,D (0,75 ponto)
(c) F,C,H,A,B,D,E,G (0,75 ponto)
(d) C,A,H,D,B,G,E,F (0,75 ponto)
EXERCÍCIO 2
Suponha o algoritmo de busca em largura como vérticem sendo a origem
para a busca no grafo G = (V, A). Suponha outros dois vértices: a e b. Se
existe apenas um caminho de m até a de tamanho 2, e apenas um cam-
inho de m até b de tamanho 4, então, b será localizado antes que a na
busca em largura. A afirmação é verdadeira ou falsa. (0,5 ponto). Justi-
fique (2,5 pontos).
EXERCÍCIO 3
(4 pontos)Modifique o algoritmoDFS para verificar se um grafo é acíclico.
O algoritmo deve retornar verdadeiro se o grafo não possui ciclos, e falso
caso contrário.
DFS (V, A)
1. for each vertex u in V
2. color[u]←WHITE
3. π[u]← NIL
4. time← 0
5. for each vertex u in V
6. if color[u] = WHITE
7. then DFS-Visit(u)
DFS-Visit(u)
1. color[u]← GRAY
2. time← time + 1
3. d[u]← time
4. for each vertex v adjacent to u
5. if color[v] = WHITE
Projeto e Análise de Algoritmos / Aula 11-12 Atividade para Avaliação 3
6. then π[v]← u
7. DFS-Visit(v)
8. color[u]← BLACK
9. time← time + 1
10. f[u]← time
Projeto e Análise de Algoritmos / Aula 11-12 Atividade para Avaliação 4
GABARITO
EXERCÍCIO 1
Considere o grafo da figura 2. Para cada uma das sequências de vér-
Figure 2: Exercício1.
tices a seguir, indique se ela pode corresponder a uma sequência de des-
coberta de vértices produzida pelos algoritmos apresentados na videoaula
de busca em largura, em profundidade, por ambos algoritmos ou por
nenhum dos dois algoritmos.
(a) F,C,H,A,B,G,E,D (0,75 ponto)
Busca em largura.
(b) F,H,A,C,E,G,B,D (0,75 ponto)
Busca em profundide.
(c) F,C,H,A,B,D,E,G (0,75 ponto)
Nenhum dos dois.
(d) C,A,H,D,B,G,E,F (0,75 ponto)
Busca em profundide.
EXERCÍCIO 2
Suponha o algoritmo de busca em largura como vérticem sendo a origem
para a busca no grafo G = (V, A). Suponha outros dois vértices: a e b. Se
Projeto e Análise de Algoritmos / Aula 11-12 Atividade para Avaliação 5
existe apenas um caminho de m até a de tamanho 2, e apenas um cam-
inho de m até b de tamanho 4, então, b será localizado antes que a na
busca em largura. A afirmação é verdadeira ou falsa. (0,5 ponto). Justi-
fique (2,5 pontos).
É falsa. O algoritmo de busca em largura antes de encontrar um vértice
à distância k+1 de m, encontrará todos os vértices à distância k. Assim, a
será localizado antes que b.
EXERCÍCIO 3
(4 pontos)Modifique o algoritmo DFS para verificar se um grafo não di-
rigido é acíclico. O algoritmo deve retornar verdadeiro se o grafo não
possui ciclos, e falso caso contrário.
DFS (V, A)
1. for each vertex u in V
2. color[u]←WHITE
3. π[u]← NIL
4. time← 0
5. for each vertex u in V
6. if color[u] = WHITE
7. then DFS-Visit(u)
8. return true
DFS-Visit(u)
1. color[u]← GRAY
2. time← time + 1
3. d[u]← time
4. for each vertex v adjacent to u
5. if color[v] = GRAY and π[u] 6= v
6. then return false
7. if color[v] = WHITE
8. then π[v]← u
9. DFS-Visit(v)
10. color[u]← BLACK
Projeto e Análise de Algoritmos / Aula 11-12 Atividade para Avaliação 6
11. time← time + 1
12. f[u]← time