PAA Exercícios

Prévia do material em texto

QXD0041 Lista de Exercícios 2014.1
UNIVERSIDADE FEDERAL DO CEARÁ
E2Campus de Quixadá
Prof. Arthur Araruna
QXD0041- Projeto e Análise de Algoritmos 2014.1
Nome: Matrícula:
1. Pensando nas notações O eΩ segundo suas definições, quais funções pertencem aos conjuntos O(−1) e
Ω(−1)?
2. Qual é a ordem de grandeza das seguintes funções?
(a) f (n) = (n2 +n) · (n− 1)
(b) g(n) =
(
n− 1
n− k
)
+
(
n− 1
k + 1
)
(c) h(n) =
n∑
i=0
(
n
i
)
(d) F(n) = 9F(n/3) +n2; F(1) = 1
(e) G(n) = 3G(n− 1) +n; G(0) = 0
3. Considere dois computadores C1 e C2 que executam 107 e 109 passos por segundo (P /s) e dois algorit-
mos de ordenação A e B com funções de complexidade de pior caso respectivamente f1(n) = 2n + 2 e
f2(n) = 50n log10n para uma entrada de tamanho n.
(a) Qual seria o tempo de execução de cada algoritmo se considerássemos executá-los em cada um dos
computadores descritos?
(b) Assintoticamente, qual dos algoritmo é mais eficiente?
4. Considere a função definida pela recorrência
F(n) =2 ·F(n− 1)
F(0) =1.
Marotônio afirma que F(n) = O(n), e que isso pode ser verificado simplesmente da seguinte forma:
F(n) =2 ·F(n− 1)
=2 ·O(n− 1)
=2 ·O(n)
=O(n)
O raciocínio de Marotônio não está correto, está? Qual seria a resposta correta? Onde ocorreu erro?
5. Determine a complexidade de pior caso do Algoritmo 1 a seguir.
6. Considere o Algoritmo 2 a seguir, que dependendo dos dados de entrada determina o menor elemento
de três maneiras distintas.
Qual a complexidade de pior caso desse algoritmo?
7. Sejam AlgoritmoA e AlgoritmoB dois algoritmos para resolver um dado problema. Imagine que divi-
dimos as possíveis instâncias desse problema em dois conjuntos, I1 e I2. Após essa divisão, observamos
que o AlgoritmoA necessita de O(n2) passos para resolver o problema para as instâncias em I1 e O(n2)
passos para as em I2, e o AlgoritmoB, contrariamente, precisa de O(n2) passos para I1 e O(n) para I2.
Assim, qual seria então a complexidade do Algoritmo 3 a seguir?
QXD0041 Lista de Exercícios 2014.1
Algoritmo 1:
Algoritmo: Loteria(R,A,n)
Entrada: Vetor de resultados R e Matriz de apostas A13×n, natural n
Saída: Um vetor P com os pontos feitos por cada apostador.
para i← 1,2, . . . ,n faça
P [i]← 0;
para j← 1,2, . . . ,13 faça
se A[i][j] = R[j] então
P [i]← P [i] + 1;
para i← 1,2, . . . ,n faça
se P [i] = 13 então
escreva “Apostador i é ganhador!”
retorne P
Algoritmo 2:
Algoritmo: ElementoMinimo(V )
Entrada: Vetor V
Saída: Maior elemento em V
se V [1] mod 3 = 0 então
retornaMenor(V);
senão se V [1] mod 3 = 1 então
MergeSort(V);
senão
BubbleSort(V);
retorna V [1];
Algoritmo 3:
Algoritmo: AlgoritmoC(e)
Entrada: e ∈ I1 ∪ I2
AlgoritmoA(e);
AlgoritmoB(e);
QXD0041 Lista de Exercícios 2014.1
8. Escreva um algoritmo para resolver o problema de determinar o segundo menor elemento de um vetor
de elementos dado como entrada. Quais as complexidades de pior caso de tempo e de memória do seu
algoritmo?
9. Escreva um algoritmo que, dada uma sequência a1, a2, . . . , an, com ai ∈ N, determina um conjunto de
índices I tal que o valor ∣∣∣∣∣∣∣∣
∑
i ∈ I
ai −
∑
j < I
aj
∣∣∣∣∣∣∣∣
é mínimo. Qual a complexidade de pior caso do seu algoritmo?
10. Considere uma variação no algoritmo de busca eficiente em vetores ordenados, onde dividiremos nosso
vetor em três porções ao invés de duas, continuando a busca na porção favorável. Supondo que o
elemento procurado sempre está presente no vetor, escreva esse algoritmo e calcule sua complexidade
de pior caso. Verifique se seu algoritmo é correto.
11. Seja um algoritmo A1 com tempo de execução O(n lgn) para resolver um dado problema. Suponha que
possamos escrever um segundo algoritmo, A2, para resolver esse problema usando uma estratégia de
Divisão e Conquista onde, para n > 1, geramos duas subinstâncias de tamanho n/2 para o problema,
com combinação em a > 4 passos constantes, e apenas um passo no caso-base. Imagine que n é uma
potência de 2.
(a) Avalie a complexidade de A2.
(b) Considere um terceiro algoritmo, A3, que chama o algoritmo A2 para n > n0 e o algoritmo A1 para
n ≤ n0, com n0 dado. Determine o tempo de execução de A3 (observe que esse tempo também
dependerá de n0).
12. Imagine que exista um algoritmo TrocaMatrizes que recebe duas matrizes A e B de dimensão n × n
e realiza a troca dos elementos dessas matrizes em tempo O(n), de forma que, após a troca, todos os
elementos de A estejam nas respectivas posições na matriz B e vice-versa. Utilizando esse algoritmo,
desenvolva um algoritmo com a técnica de Divisão e Conquista para rotacionar uma matriz. Qual é a
complexidade de pior caso do seu algoritmo?
Observe abaixo, dada a matriz C, a matriz Cr obtida ao rotacionarmos a matriz C.
C =
a b cd e f
g h j
 Cr =
g d ah e b
j f c

13. Para um valor de n que seja uma potência de 2, dizemos que uma matriz An×n é repetitiva se n = 1 ou
se, para n > 1, A pode ser dividida em quatro submatrizes (n/2)× (n/2) da seguinte forma:
A =
(
B B
C B
)
,
onde B e C são também matrizes repetitivas.
Por exemplo, a matriz M abaixo é repetitiva.
3 3 3 3
4 3 4 3
5 5 3 3
6 5 4 3
 .
Escreva um algoritmo de Divisão e Conquista para multiplicar duas matrizes repetitivas de maneira
eficiente, fazendo uso dessa propriedade (eficiente, nesse caso, significa um algoritmo com um limite
melhor que O(n3)), e faça sua análise de complexidade.
14. Dê dois exemplos de problemas para os quais não encontramos instâncias com subestrutura ótima.
QXD0041 Lista de Exercícios 2014.1
15. Na nação de Monolitávia, a casa da moeda local produz cédulas de 1, 7 e 10 coroas, moeda oficial da
nação. Um dos bancos do país, visando diminuir a frequência de reposição de notas em seus caixas
automáticos espalhados pela Monolitávia, deseja entregar aos clientes a quantia a sacar fazendo uso
do menor número de cédulas possível. Escreva um algoritmo de Programação Dinâmica para resolver
esse problema e faça sua análise de complexidade.
16. Suponha que você foi contratado por uma empresa administradora de rodovias para solucionar o se-
guinte problema. A empresa deseja instalar postos de pedágio na rodovia BR-000 que sai de Quixadá
e atravessa o país na direção sul por M kilômetros. Os possíveis lugares de instalação desses postos
ficam nos marcos dados por x[1] < x[2] < · · · < x[n], onde cada x[i] representa a quantos quilômetros de
Quixadá fica o possível local de instalação i. Se for construído um posto de pedágio no marco x[i], o
valor a ser cobrado é dado por r[i] > 0. As regras impostas pela ANTT impedem que quaisquer dois
postos de pedágio sejam instalados a uma distância inferior a 5km.
Assim, a empresa deseja instalar pedágios na estrada de forma a obter o maior ganho possível. Por
exemplo, se tivéssemos M = 10 e n = 5, com os valores
〈x〉 = 〈6,7,12,13,14〉
e
〈r〉 = 〈5,6,5,3,1〉,
a melhor das opções seria instalar pedágios nos marcos x[1] e x[3], pois obteríamos um ganho de 10.
Escreva um algoritmo de Programação Dinâmica para resolver esse problema e faça sua análise de
complexidade.