Lista de Exercícios de Introdução à Análise de Algoritmos

1ª Lista de Exercícios de Introdução à Análise de Algoritmos

Prof. Glauber Cintra – Entrega: 23/set/2019

Equipe: Paulo Henrique de Sousa Braga

Gustavo Mendes de Oliveira

Matthias Lucas Muniz Deusdará Ferreira Lopes

Pedro Gabriel Moreira Feitosa

1. (0,5 pontos) Numere as funções abaixo a partir do 1 em ordem estritamente crescente de dominação assintótica. Se f e g são tais que f ∈ o(g) então f deve ter número menor do que g. Se f ∈ Θ(g) então f e g devem ter o mesmo número.

(7) n!        (1) log n        (6) 3n         (1) 2log n3        (6) 3n+1

(5) fib(n)         (4) n3        (2) nlog n        (3) 6n2        (3) 2n + n2

Para essa numeração foram usadas as propriedades das notações assintóticas, conforme mostrado abaixo:

1) n! = n*(n - 1)*(n - 2) * … *2*1

          Pela propriedade aditiva

   O(n!) = O(nn)

2) 2*(log(n3)) = 6*(log(n))

          Pela propriedade multiplicativa

   O(6*(log(n))) = O(log(n))

3) 3n+1 = 3*(3n)

          Pela propriedade multiplicativa

   O(3*(3n)) = O(3n)

4) 6*(n2)

          Pela propriedade multiplicativa

   O(6*(n2) = O(n2)

5) 2*n+n2

          Pela propriedade aditiva

   O(2n+n2) = O(n2)

6) fib(n)

   fib(n) = (1 /√5)*( (1+√5)/2)n − (1 /√5)*( (1-√5)/2)n

          Pelas propriedades multiplicativa e aditiva:

   O(fib(n)) = O( (1 /√5)*( (1+√5)/2)n )

1. (0,5 pontos) Explique o significado dos termos algoritmo, algoritmo computacional, algoritmo correto, algoritmo eficiente e tamanho da entrada de um algoritmo.

       Sol. Um algoritmo representa uma sequência de instruções que visa resolver instâncias de um problema.

       Um algoritmo computacional é aquele algoritmo constituído apenas de instruções bem definidas, não ambíguas.

       Um algoritmo correto é aquele algoritmo que resolve corretamente todas as instâncias de um problema para o qual foi             desenvolvido. Além disso, cada instância deve ser resolvida em tempo finito.

       Um algoritmo eficiente é aquele algoritmo que requer que seja executada uma quantidade de instruções elementares              limitada por um polinômio do tamanho da entrada.

       O tamanho da entrada de um algoritmo é a quantidade de símbolos usados para codificar os dados de entrada.

1. (1,5 pontos) Indique quais são o melhor caso e o pior caso do algoritmo abaixo e sua região crítica. Qual a complexidade temporal desse algoritmo no melhor e no pior caso? Qual a complexidade espacial desse algoritmo? O algoritmo é eficiente? É de cota inferior? Justifique suas respostas. Finalmente, prove que esse algoritmo é correto.

Algoritmo Contido

Entrada: os vetores A e B com m e n posições, respectivamente

Saída: Sim, se todos os elementos de A estão contidos em B; Não, caso contrário

para i = 0 até m – 1

   j = 0

 enquanto j < n e A[i] ≠ B[j]

    j++

 se j >= n

    devolva Não e pare

devolva Sim

Sol. 

Melhor caso: Quando o primeiro elemento de A não estiver em B, ou seja, A[0] ≠ B[k], para k = 0,1,2..., (n-1).

Pior caso: Quando todos os elementos de A ocorrem em B, ou seja, o vetor A está contido em B.

Região crítica: É a condição do Enquanto (enquanto j < n e A[i] ≠ B[j]), pois ela é executada em todo o vetor B, para cada elemento de A.

Complexidade temporal do melhor caso: O algoritmo terá que percorrer o vetor B para verificar se A[0] ocorre nele. Logo a complexidade temporal é θ(n).

Complexidade temporal do pior caso: O algoritmo terá que percorrer todo o vetor B para cada elemento do vetor A, logo a complexidade temporal é θ(nm).

Complexidade Espacial: Há somente declarações de variáveis para os laços, logo a complexidade espacial é O(1).

Eficiência: O algoritmo não é eficiente, pois o tempo requerido não é delimitado pelo tamanho da entrada.

Cota inferior: Todo algoritmo para resolver esse problema requer tempo Ω(nm) e o algoritmo em questão requer tempo O(nm), logo o algoritmo em questão é de cota inferior.

Teorema: O Algoritmo Contido é correto.

Prova: Suponha que um elemento X de A não ocorra em B. A segunda condição do Enquanto(A[i] ≠ B[j]) sempre será satisfeita e, após o laço percorrer B todo, j será igual a n, e assim, a condição do Se será verdadeira e o algoritmo devolverá Não, o que é correto. Agora, suponha que todos os elementos de A ocorram em B. Seja k a posição de um elemento de x em A e l a posição desse elemento em B. Note que 0 ≤ k ≤ m – 1 e 0 ≤ l ≤ n – 1. Quando i = k e j = l, a segunda condição do Enquanto não será satisfeita, logo a condição do Se também é falsa. Como todos elementos de A ocorrem em B, isso sempre ocorrerá. No final do laço externo, o algoritmo devolverá Sim, o que é correto.