LISTA DE EXERCICIOS COM GABARITO LINGUAGENS FORMAIS E AUTOMATOS

Prévia do material em texto

1.5 EXERCÍCIOS 
 
ATENÇÃO: Sempre usaremos a notação log n como log2 n. Exemplo: log 8 = log2 8 = 3. 
 
1) Para n suficientemente grande, ordene as funções abaixo: 
 
f1(n) = 30 n + 2000 log n f3(n) = n3 f5(n) = 400 n2 + 300 n + 200 
 
f2(n) = 3000 log n + 3001 f4(n) = 2999 log n f6(n) = n log n 
 
 
 
 
 
2) Indique a menor cota assintótica superior para as funções da questão 1, usando a notação O: 
 
f1(n) = O( ) f3(n) = O( ) f5(n) = O( ) 
f2(n) = O( ) f4(n) = O( ) f6(n) = O( ) 
 
3) Encontre um valor de n que satisfaça as inequações abaixo, considerando n natural 
positivo. Basta apenas um valor. Justifique sua resposta. Veja o exemplo a seguir. 
 
10 n  n
2
. Possíveis respostas corretas: n = 10, pois 10×10 = 100  10
2
 = 100 
 n = 11, pois 10×11 = 110  11
2
 = 121 
a) 30 n2 + n  n3 d) 20 n2  2n 
b) 100 log n  n e) n log n + 100  n
2
 
c) 10 n2  2n f) 30 n3 + n  30 n2 
4) Demonstre as cotas superiores abaixo, encontrando um valor n0 e uma constante c. 
Exemplo 1: 10 n
2
 = O(n3) 
Temos que 10 n
2
  n × n2 para todo n  10. Logo, temos n0 = 10 e c = 1 
Exemplo 2: 10 n
3
 + n2 – 5 = O(n3) 
Temos que 10 n
3
 + n2 – 5  10 n3 + n3 – 5 = 11 n3 – 5 
 
 
 
a) 10 n3 + n2 – 5 = O(n4) b) (n + 1)2 + 3n2 = O(n2) 
 
5) Encontre a menor cota superior para a função f(n) abaixo. 
JUSTIFIQUE sua resposta, encontrando dois valores diferentes para c e n0 que satisfaçam as 
inequações correspondentes. 
 
5 n3 + 100 n = O( ) 
 
a) Justifique, encontrando o menor valor natural para c, e seu correspondente n0 
b) Justifique, encontrando o menor valor natural de c para n0 = 1 
 
6) Escreva qual a menor cota assintótica superior das funções abaixo: 
f1(n) = 4 (n + 1)
2
 + n 
 
f3(n) = 4 n (log n + 1) – 3n 
 
f5(n) = 2 n (2 n + log n) 
 
 
 
f2(n) = (2n + 2)
2
 + n f4(n) = (2 n + log n)
2 – 4n2 f6(n) = 4 log n (log n + 1) + n 
 
 
 
 
NOTAS DE AULA – PROFS. JÚLIO SILVEIRA e SÉRGIO MONTEIRO 
COMPLEXIDADE DE ALGORITMOS 28 
 
7) Para o algoritmo abaixo: 
 
ESCREVE_AST (n: inteiro) 
 
1 Para i de 2 até n-1 faça 
2 Escreva '*' 
3 Para i de n até 2 faça 
4 Para j de 1 até i faça 
5 Escreva '*' 
 
Deduza a expressão que caracterize a função f(n) como o número de '*'s impressos. 
 
8) Um problema computacional tem limite inferior Ω(n
2
), e um dado algoritmo que resolva este 
problema tem cota assintótica superior de melhor caso Θ(n2) e de pior caso Θ(n3). Responda 
(JUSTIFIQUE): 
 
a) Este algoritmo é eficiente? b) Este algoritmo é ótimo? 
 
9) Considere o seguinte algoritmo. 
 
SOMAVETOR (vetor, vsoma, n) { vetor[1..n] e vsoma[1..n] } 
 
1 Para i de 1 até n faça 
 
2 vsoma[i] = 0 
 
3 Para j de 1 até i faça 
4 vsoma[i] = vsoma[i] + vetor[j] 
 
a) Para a instância de entrada abaixo, indique os valores armazenados no vetor vsoma. 
 
vetor = 
 
 
[ 
 
 
2
, 
 
 
3
, 
 
 
8
, 
 
 
1
, 
 
 
5
, 
 
 
13
, 
 
 
9 ] 
 
 
vsoma = 
 
[ 
 
, 
 
, 
 
, 
 
, 
 
, 
 
, 
 
] 
 
n = 7 
 
b) Responda sucintamente o que faz este algoritmo. 
 
 
c) Para um vetor genérico com n elementos, escreva uma fórmula que expresse f(n): a quantidade 
de operações de adição (linha 4). Indique a menor cota superior para f(n). Faça por partes: 
 
Número de iterações da linha 1 (variável i): i = 1, ... (complete)  iterações 
 
Número de iterações da linha 3 (variável j): 
 
 i = 1   operações 
 
 i = 2   operações 
 
 ... 
 
Totalize: 
 
Relembrando: a soma dos k termos iniciais de uma PA = a1, a2, a3, … é dada por 
S
k = 
a1 + ak  k 
 
2 
 
 
Resposta: 
 
i f(n) = 
 
ii. Menor cota superior: f(n) = O( ) 
 
 
NOTAS DE AULA – PROFS. JÚLIO SILVEIRA e SÉRGIO MONTEIRO 
 
COMPLEXIDADE DE ALGORITMOS 29 
 
d) Agora otimize o algoritmo, de forma a obter uma menor cota superior. 
SOMAVETOR2 (vetor, vsoma, n) { vetor[1..n] e vsoma[1..n] } 
 
1 
2 
3 
4 
5 
6 
7 
 
e) Justifique sua resposta, DEMONSTRANDO que f(n) foi otimizado. 
 
Resposta: i f(n) = 
ii. Menor cota superior para f: f(n) = O( ) 
 
10) Seja o algoritmo abaixo: 
 
Procedimento MaxMin (v: vetor; n: inteiro; var max, min: inteiro) 
 
1 max := v[1] 
2 min := v[1] 
 
3 Para i := 2 até n faça 
 
4 Se v[i] > max então max := v[i] 
5Se v[i] < min então min := v[i] 
 
 
a) Indique as funções f(n), que expressem o total de ATRIBUIÇÕES efetuadas (linhas 1, 2, 4 e 5): 
 
i. no melhor caso: f(n) = 
ii. no pior caso: f(n) = 
 
b) Baseado no item a, indique a complexidade (menor cota superior) do algoritmo acima: 
 
i. no melhor caso: f(n) = O( ) 
ii. no pior caso: f(n) = O( ) 
 
11) Considere o problema P, e os algoritmos A1 e A2, que resolvem P, abaixo: 
 
P: Busca ordenada 
ENTRADA: v: vetor ordenado com n elementos, c: chave a ser buscada 
SAÍDA: índice do vetor v onde se 
encontra a chave c, ou 0 se c não está no vetor v 
A1: Busca sequencial em vetor ordenado 
A2: Busca binária em vetor ordenado 
 
a) Seja f(n) o nº de comparações da chave c com elementos do vetor v (de tamanho n), no pior 
caso. Assinale qual a MENOR COTA SUPERIOR de f para cada um dos algoritmos: 
A1: f(n) = Θ ( ) 
A2: f(n) = Θ ( ) 
b) Sabendo–se que um limite inferior para P é dado por: liminf(P) = Ω(log n), responda: 
A1 é um algoritmo eficiente? ( ) SIM 
A2 é um algoritmo eficiente? ( ) SIM 
A1 é um algoritmo ótimo? ( ) SIM 
A2 é um algoritmo ótimo? ( ) SIM 
 
 
( ) NÃO ( ) NADA SE PODE AFIRMAR 
( ) NÃO ( ) NADA SE PODE AFIRMAR 
( ) NÃO ( ) NADA SE PODE AFIRMAR 
( ) NÃO ( ) NADA SE PODE AFIRMAR 
 
NOTAS DE AULA – PROFS. JÚLIO SILVEIRA e SÉRGIO MONTEIRO 
COMPLEXIDADE DE ALGORITMOS 30 
 
12) Em relação ao problema de ORDENAÇÃO de um vetor com n posições, são conhecidos dois 
algoritmos que resolvem este problema: BUBBLE-SORT e MERGE-SORT. 
Responda o que se pede: 
 
a) Qual é o limite inferior máximo do problema de ordenação? 
b) Quais são as complexidades de pior caso dos algoritmos citados? 
c) Os algoritmos são eficientes? Justique. 
d) Os algoritmos são ótimos? Sim, Não, ou Nada se pode afirmar? Justique. 
e) No pior caso de cada um dos algoritmos citados, todos os elementos serão comparados 
entre si? Justique. 
 
13) (ENADE adaptado) 
Suponha que se queira utilizar o algoritmo de busca binária para pesquisar a chave 287 em um vetor 
ordenado, contendo chaves entre 1 e 1000. Durante uma pesquisa como essa, uma sequência de 
chaves é examinada. Cada sequência abaixo é uma suposta sequência cronológica de chaves 
(pertencentes ao vetor considerado) que foram examinadas na pesquisa da chave 287. 
 
I. 7, 342, 199, 201, 310, 258, 287 
II. 110, 132, 133, 156, 289, 288, 287 
III. 252, 266, 271, 294, 295, 289, 287 
IV. 715, 112, 530, 249, 406, 234, 287 
 
De todas as sequências acima, são válidas: 
 
a) I. 
b) III. 
c) I e II. 
d) II e IV. 
e) III e IV. 
 
14) Em relação a ordem de complexidade, pode-se afirmar que as menores cotas superiores para as 
funções f1(n) = 4 n
2
 + n (log n + 3) e f2(n) = (n + log n)
2
 – n2 são, respectivamente: 
a. f1(n) = O( n
2 log n ) e f2(n) = O( n log n ) 
b. f1(n) = O( n
2
 ) e f2(n) = O( n log n ) 
c. f1(n) = O( n log n ) e f2(n) = O( n
2
 ) 
d. f1(n) = O( n
2 ) e f2(n) = O( n
2 ) 
e. f1(n) = O( n log n ) e f2(n) = O( n log n ) 
 
15) (ENADE 2005) 
No processo de pesquisa binária em um vetor ordenado, os números máximos de comparações 
necessárias para se determinar se um elemento faz parte de vetores com tamanhos 50, 1.000 e 
300 são,respectivamente, iguais a: 
 
a) 5, 100 e 30. 
b) 6, 10 e 9. 
c) 8, 31 e 18. 
d) 10, 100 e 30. 
e) 25, 500 e 150 
NOTAS DE AULA – PROFS. JÚLIO SILVEIRA e SÉRGIO MONTEIRO 
COMPLEXIDADE DE ALGORITMOS 31 
 
16) Considere f(n) = 15n2 (n + 9). Podemos provar que f(n) = O(n3), mostrando que f(n) ≤ 20 
n3 para todo n ≥ n. 
Qual é o menor valor possível para n neste caso? 
 
a) 2 
b) 3 
c) 4 
d) 6 
e) 9 
 
17) Seja o algoritmo BUSCASEQORD abaixo, que realiza uma busca sequencial em um vetor ordenado 
de forma crescente, contendo n elementos. 
 
BUSCASEQORD(vetor, n, chave) { vetor[1] < vetor[2] < vetor[3] … } 
 
1 Para i de 1 até n faça 
2 Se chave <= vetor[i] então 
3 Se chave = vetor[i] então 
4 Retorne i 
5 Senão 
6 Retorne 0 
 
7 Retorne 0 
 
Para a instância de entrada abaixo, indique a saída gerada pelo algoritmo, e a quantidade de 
comparações efetuadas pela linha 2 - "chave <= vetor[i]": 
 
vetor: [2, 3, 8, 15, 25, 31, 40] 
n: 7 
chave: 35 
 
Complete: nº de comparações = 
valor retornado = 
 
Considerando o mesmo vetor acima, complete a tabela abaixo, indicando as quantidades mínima 
(sucesso e insucesso) e máxima (sucesso e insucesso) de comparações realizadas pela linha (2) 
do algoritmo. Em cada caso, forneça um valor para o parâmetro chave que corresponda às 
quantidades de comparações indicadas. 
 
 chave = Nº de comparações 
 
MELHOR CASO SUCESSO 2 
(mínimo de comparações) INSUCESSO 
 
PIOR CASO SUCESSO 
(máximo de comparações) INSUCESSO 
 
 
Considere agora o caso de um vetor genérico com n valores: vetor[1..n], ordenado de forma 
crescente. Preencha a tabela abaixo, indicando quais valores genéricos de chave que irão 
produzir as comparações indicadas. 
 
 chave = Nº de comparações 
 
MELHOR CASO SUCESSO vetor[1] 
(mínimo de comparações) INSUCESSO 
 
PIOR CASO SUCESSO 
(máximo de comparações) INSUCESSO 
 
 
NOTAS DE AULA – PROFS. JÚLIO SILVEIRA e SÉRGIO MONTEIRO 
COMPLEXIDADE DE ALGORITMOS 32 
 
18) Considere um dado problema computacional P tem limite inferior Ω(n2). Isto significa que: 
 
a) Existe um algoritmo que resolve P cuja complexidade de pior caso é O(n2). 
b) Não existe algoritmo que resolve P cuja complexidade de pior caso é O(n2). 
c) Não existe algoritmo de complexidade de pior caso menor do que O(n2) que resolva P. 
d) Um algoritmo de complexidade menor do que O(n2) que resolva P é ótimo. 
e) Todo algoritmo que resolve P terá complexidade de pior caso maior que O(n2). 
 
 
RESPOSTAS 
 
1) Resp.: f2  f4  f1  f6  f5  f3 
 
2) f1 = O(n) f2 = O(log n) f3 = O(n
3
) f4 = O(log
2 n) f5 = O(n
2
) f6 = O(n log n) 
 
3) Possíveis soluções: 
 
a) 30 n2 + n  30 n2 + n2 = 31 
n2. Ou seja, 30 n2 + n  31 n2 
Resolvemos a inequação 31 n2  n3 dividindo ambos os termos por n2: 31 n2 
 n3  n  31 
Resposta: n  31 
 
b) 100 log n  n 
Solução: testemos n como potências de 2 
Para n = 32: 100 log 32 = 100 × 5 = 500  32  Falso 
Para n = 1024: 100 log 1024 = 100 × 10 = 1000  1024 
Resposta: n = 1024 
 
c) 10 n2  2n 
Solução: para n = 10, temos 10 × 100 = 100  1024 
Resposta: n = 10 
 
d) 20 n2  2n 
Solução: similar à solução do item c) 
 
e) n log n + 100  n
2
 
 Solução: testemos n como potências de 2 
 Para n = 8: 8 log 8 + 100 = 8 × 3 + 100 = 124  64  Falso 
 Para n = 16: 16 log 16 + 100 = 16 × 4 + 100 = 164  256 
 Resposta: n = 16 
f) 30 n
3
 + n  30 n2 
Solução: para todo n natural positivo, temos 30 n3 + n  30 n3  30 n2 
Resposta: Nenhum valor é possível 
 
4) Possíveis soluções: 
 
a) 10 n3 + n2 – 5 = 
O(n4) Solução: 
10 n3 + n2 – 5  10 n4 + n4 – 5 = 11 n4 – 5  11 n4, para todo n  1 
Resposta: n0 = 1 e c = 11 
NOTAS DE AULA – PROFS. JÚLIO SILVEIRA e SÉRGIO MONTEIRO 
COMPLEXIDADE DE ALGORITMOS 33 
 
b) (n + 1)2 + 3n2 = O(n2) 
Primeiro: (n + 1)2 + 3n2 = n2 + 2 n + 1 + 3n2 = 4n2 + 2n + 1 
Solução: 
4 n2 + 2 n + 1 ≤ 4 n2 + 2 n2 + n2 = 7 n2 ≤ 7 n2, para todo n ≥ 1 
Resposta: n0 = 1 e c = 7 
 
5) 5 n3 + 100 n = O( n3 ) 
 
a) Solução: 
5 n3 + 100 n ≤ 6 n3 6 n3 
– 5 n3 ≥ 100 n 
n3 ≥ 100 n (dividindo por n, o que é válido para n∈ IN*) n2 ≥ 
100 
n ≥ 10 
Resposta: c = 6 n0 = 10 
b) Solução: 
5 n3 + 100 n ≤ 5 n3 + 100 n3 5 n3 
+ 100 n ≤ 105 n3 Resposta: c = 
105 n0 = 1 
 
6) 
 
f1(n) = O ( n
2 ) 
 
 
f3(n) = O ( n log n ) 
 
f5(n) = O ( n
2 ) 
 
 
 
f2(n) = O ( n
2 ) f4(n) = O ( n log n ) f6(n) = O ( n ) 
 
7) 
 
Linha 2: i = 2,3,…,n-1  n-2 escritas 
 
Linha 3: i = n,n-1,n-2,…,2 
 
Linha 4: i = n j = 1,2,3, 3,…,n  n escritas 
 
 i = n-1 j = 1,2,3, 3,…,n-1  n-1 escritas 
 
 i = n-2 j = 1,2,3, 3,…,n-2  n-2 escritas 
 
 … 
 
 i = 3 j = 1,2,3  3 escritas 
 
 i = 2 j = 1,2  2 escritas 
 
 
f(n) = n–2 + [ 2 + 3 + 4 + … + n ] = n–1 + S Onde 
S é a soma dos termos da PA em que: 
 
 
 
a1 = 2 (primeiro termo) 
ak = n (último termo) 
k = n–1 (nº de termos) 
 
Resposta: f (n) = n − 2 + 
2 + nn − 1 
= (desenvolva) 
2 
 
 
 
 
8) Problema: com limite inferior, já provado, de Ω(n2). Algoritmo: melhor caso Θ(n2) e pior caso Θ(n3) 
 
a) O algoritmo é eficiente, pois sua complexidade de pior caso é O(n3), ou seja, 
limitada superiormente pelo polinômio n3; 
 
b) Este algoritmo é ótimo? 
 
Nada se pode afirmar, pois 
NOTAS DE AULA – PROFS. JÚLIO SILVEIRA e SÉRGIO MONTEIRO 
COMPLEXIDADE DE ALGORITMOS 34 
 
 O algoritmo pode ser ótimo, o que só será sabido se (e quando) alguém conseguir 
provar que o novo valor para o limite inferior do problema é Ω(n3)

 O algoritmo pode não ser ótimo, o que só será sabido se (e quando) alguém 
conseguir desenvolver um algoritmo de complexidade menor do que O(n3)
 
9) 
a) vetor = [ 2, 3, 8, 1, 5, 13, 9 ] 
 
vsoma = [ 2, 5, 13, 14, 19, 32, 41 ] 
 
n = 7 
 
c) 
 
Número de iterações da linha 1 (variável i): i = 1,2,...,n  n iterações 
 
Número de iterações da linha 3 (variável j): 
 
i = 1  1 operação 
 
i = 2  2 operações 
 
i = 3  3 operações 
 
... 
 
i = N  n operações 
 
Totalize: 
 
1 + 2 + 3 + … + (n-1) + n = 
1  nn 
⋯ n 
2
 
 
n 
 
1 
n 2  
 1 
n 
 
 
2 
 
2 2 2 
 
2 
 
 
 
 
Resposta: i f(n) = 
1 
n 2 + 
 1 
n 
 
 
2 2 
 
 
ii. Menor cota superior para f: f(n) = O(n2) 
 
d) 
SOMAVETOR2 (vetor, vsoma, n) { vetor[1..n] e vsoma[1..n] } 
 
1 vsoma[1] = vetor[1] 
 
2 Para i de 2 até n faça 
 
3 vsoma[i] = vsoma[i-1] + vetor[i] 
 
e) Resposta (tem que justificar) 
 
i f(n) = n 
 
ii. Menor cota superior para f: f(n) = O(n) 
 
10) 
 
a) i. no melhor caso: 
b) i. no melhor caso: 
 
f(n) = 2 ii. 
f(n) = O( 1 ) 
 
no pior caso: 
 
f(n) = n 
ii. 
 
+ 1 
no pior caso: 
 
 
f(n) = O( 
 
 
 
n 
 
 
) 
 
11) 
 
a) A1: 
 
 
f(n) = Θ 
 
 
( 
 
 
n 
 
 
) 
 
 
A2: 
 
 
f(n) = Θ 
 
 
( log 
 
 
n 
 
 
) 
 
b) A1 é um algoritmo eficiente? 
 
SIM 
A2 é um algoritmo eficiente? 
 
SIM 
A1 é um algoritmo ótimo? 
 
NÃO 
A2 é um algoritmo ótimo? 
 
SIM 
NOTAS DE AULA – PROFS. JÚLIO SILVEIRA e SÉRGIO MONTEIRO 
COMPLEXIDADE DE ALGORITMOS 35 
 
12 
a) O(n log n) 
b) Bubble: O(n2) e Merge: O(nlog n) 
c) Ambos são eficientes, pois são limitados superiormente pelo polinômio n2. 
d) O BubbleSort não é ótimo; o MergeSorte é ótimo. Justique! 
e) No BubbleSort, serão. No MergeSort não. Justique! 
 
13) letra c 
 
14) letra b 
 
15) letra b 
 
16) letra b 
 
17) nº de comparações = 7 
valor retornado = 0 
 
 
 
 chave = Comparações 
 
 
 
MELHOR CASO SUCESSO 2 1 
 
(mínimo de comparações) INSUCESSO chave < 2 1 
 
 
 
PIOR CASO SUCESSO 40 7 
 
(máximo de comparações) INSUCESSO 31 < chave < 40 ou chave > 40 7 
 
 
 
 
 
 chave = Comparações 
 
 
 
MELHOR CASO SUCESSO chave = vetor[1] 1 
 
(mínimo de comparações) INSUCESSO chave < vetor[1] 1 
 
 
 
 SUCESSO chave = vetor[N] N 
 
PIOR CASO 
 
 
 vetor[N-1] < chave < vetor[N] 
 
(máximo de comparações) INSUCESSO ou N 
 
 chave > vetor[N] 
 
 
 
 
18) letra c