Exercicios Analise e Sintese de Algoritmos

IC/UFF - An´ alise e S´ıntese de Algoritmos - 2013/1 - Segunda Prova
Quest˜
ao 1: Considere um tabuleiro n × n onde cada casa possui um custo associado c(i, j)
(inteiro positivo), onde o ´ındice i indica a linha e o ´ındice j a coluna. (A linha 1 ´e a primeira de baixo para cima, e a coluna 1 ´e a mais `a esquerda.) Um caminho neste tabuleiro consiste de uma sequˆencia de casas (1, j1 ), (2, j2 ), . . . , (r, jr ) tais que, para cada valor de k ∈ {1, . . . , r − 1}, vale que jk+1 ∈ {jk − 1, jk , jk + 1}. Em outras palavras, os caminhos sempre partem da primeira linha e v˜ao subindo linha a linha, sendo que a pr´oxima casa est´a na mesma coluna ou em uma mesma diagonal que a casa anterior. Exemplo: iniciando na casa (1, 3), a pr´oxima casa do caminho pode ser (2, 2), (2, 3) ou (2, 4).
(a) (1,0) Seja q(i, j) o custo m´ınimo de um caminho que parte da primeira linha e chega `a casa
(i, j). Escreva equa¸c˜oes de recorrˆencia para determinar q(i, j). (Obs: o custo de um caminho ´e a soma dos custos das casas que comp˜oem o caminho.)
(b) (2,0) Escreva um algoritmo de programa¸c˜ao dinˆamica que determine o custo m´ınimo de um caminho que parte da primeira linha e chega `a linha n. Determine sua complexidade.
(c) (2,0) Escreva um algoritmo de backtracking que enumera todos os poss´ıveis caminhos que partem da primeira linha e chegam `a linha n. Determine sua complexidade.
Quest˜
ao 2: Considere o problema caminho longo em grafos, assim definido:
Entrada: Um grafo G e um inteiro positivo k.
Quest˜
ao: Existe em G um caminho com pelo menos k arestas?
(a) (1,0) Escreva a vers˜ao de otimiza¸c˜ ao do problema acima.
(b) (1,0) Mostre que o problema caminho longo em grafos pertence `a classe NP.
(c) (1,0) Mostre uma redu¸c˜ao polinomial do problema caminho Hamiltoniano para o problema caminho longo em grafos. caminho Hamiltoniano
Entrada: Um grafo G.
Quest˜
ao: Existe em G um caminho que passa por todos os v´ertices?
(d) (1,0) Dˆe a defini¸c˜ao de