EXERCÍCIOS ANÁLISE DE PROJETO E ALGORITMOS

1. Para cada item abaixo, responda “certo” ou “errado”. Justifique sua resposta em ambos os casos.
(a) A definição da notação Θ é equivalente à seguinte: sejam f, h funções reais positivas da variável inteira n. Diz-se que f = Θ(h) quando existirem constantes c, d > 0 e um valor inteiro n0, tais que:
n > n0 ⇒ c . h(n) ≤ f(n) ≤ d . h(n).
(b) Se f e g são funções tais que f = O(g) e g = Ω(f), então f = Θ(g).
(c) Se um limite inferior para um problema P é n³, e se A é um algoritmo que resolve P, então a complexidade de A é sempre menor do que O(n³).
(d) Se um limite inferior para um problema P é n², e se A é um algoritmo que resolve P com complexidade de pior caso Ω(n²), então A é um algoritmo ótimo.
(e) Se um algoritmo ótimo que resolve um problema P tem complexidade de pior caso O(f), então f é um limite inferior para P.

2. Considere funções de N em R+ .
(a) Mostre que a relação O é transitiva: se f(n) = O(g(n)) e g(n) =O(h(n)), então f(n)= O(h(n)).
(b) Pode-se afirmar que a relação O é reflexiva, isto é, sempre se tem f(n) = O(f(n))?
(c) A relação O é simétrica, isto é, sempre que f(n)= O(g(n)), tem-se g(n)= O(f(n))?

3. Prove que a relação Θ é de equivalência: reflexiva, simétrica e transitiva.

4. Calcule a complexidade média de uma busca seqüencial não ordenada em um vetor de n=10 posições, onde a probabilidade de sucesso na busca é de 80%, e a probabilidade de sucesso na posição i é o dobro da probabilidade de sucesso na posição i+1 (1 ≤ i ≤ 9).

5. Determinar a expressão da complexidade média de uma busca seqüencial ordenada de 10 chaves, em que a probabilidade de busca da chave i é 20% maior que a probabilidade de busca da chave i-1, i=2,...,10. Supor, ainda, que a probabilidade de a chave procurada se encontrar na lista é 80%.

6. Não é qualquer abordagem gulosa para o problema de seleção de atividades que produz um conjunto de tamanho máximo de atividades mutuamente compatíveis. Forneça um exemplo para mostrar que a abordagem de selecionar a atividade de menor duração entre aquelas que são compatíveis com atividades selecionadas anteriormente não funciona.

7. Para o problema de intercalação de duas listas ordenadas L1 e L2, tais que |L1|= m1 e |L2|= m2, temos que são necessárias, no pior caso, m1 + m2 -1 comparações. Elabore um algoritmo guloso que resolva o problema de intercalação de n listas ordenadas L1, L2, ..., Ln (|L1|= m1 |L2|= m2, ...., |Ln|= mn), realizando o menor número possível de comparações. Como exemplo, seja n=5, |L1|= 10, |L2|= 20, |L3|= 30, | L4|= 40 e | L5|= 50. Qual o número máximo de comparações que seu algoritmo realiza para este conjunto de listas?

8. Desenhar a árvore de Huffman para o seguinte conjunto de chaves e frequências: f1=1, f2=6, f3=2, f4=1, f5=1, f6=9, f7=2, f8=3.