Programação Dinâmica

Universidade Federal do Cear´ a Departamento de Computa¸˜o ca Bacharelado em Ciˆncia da Computa¸˜o e ca
Constru¸˜o e An´lise de Algoritmos ca a
Lista de exerc´ ıcios 2 (Programa¸˜o Dinˆmica) ca a

1. Seja P : N → N uma fun¸˜o definida da seguinte forma: P (0) = P (1) = P (2) = P (3) = P (4) = 0 e, ca para n ≥ 5, n n n + P
+1 + P
+ 2 + n.
P (n) = P
2
2
2
Escreva um algoritmo recursivo puro que recebe um n´mero n como entrada e retorna o valor exato de u P (n). Calcule a complexidade do seu algoritmo. Escreva agora um algoritmo de programa¸˜o dinˆmica para ca a o mesmo problema e calcule a complexidade. Escreva tamb´m um algoritmo de memoiza¸˜o. Qual dos trˆs e ca e algoritmos ´ o mais r´pido? e a
2. Uma subsequˆncia ´ pal´ e e ındroma se ela ´ igual lendo da direita para esquerda ou lendo da esquerda e para direita. Por exemplo, a sequˆncia (ACGT GT CAAAAT CG) possui muitas subsequˆncias pal´ e e ındromas, como (ACGCA) e (AGT GA). Mas a subsequˆncia (ACT ) n˜o ´ pal´ e a e ındroma. Escreva um algoritmo O(n2 ) que recebe uma sequˆncia S[1 . . . n] e retorna a subsequˆncia pal´ e e ındroma de tamanho m´ximo. a 3. Vocˆ vai iniciar uma viagem bastante longa. Vocˆ inicia a viagem no Km 0 (zero). No seu percurso, e e existem n hot´is com quilometragens iguais a a1 < a2 < . . . < an , onde cada ai ´ medido a partir do ponto e e de Km 0. Os unicos lugares que vocˆ pode parar s˜o esses hot´is, mas vocˆ n˜o precisa parar em todos.
´
e a e e a
Sua viagem termina no hot´l do Km an que ´ o seu destino. Vocˆ idealmente gostaria de viajar 200 Km por e e e dia, mas nem sempre isso ´ poss´ (depende do espa¸o entre os hot´is). Se vocˆ viaja menos de 200 Km e ıvel c e e em um dia, seu pai reclama que quer chegar logo ao destino final, mas se vocˆ viaja mais de 200 Km em um e dia, sua m˜e reclama que est´ cansada. Mais especificamente, se vocˆ viaja X Km em um dia, vocˆ recebe a a e e
(200 − X)2