Univesp Eng da Comp. Fundamentos Matematicos para Computador 4ª Semana

Pergunta 1

1 pts

De acordo com o axioma de atribuição, qual é a precondição para o segmento de programa a seguir?  

             {precondição}    

             x = 5 * x + 2  

             {x = y – 5} 

A---- 2x = y

B---- x-y = 7

C-----y-7=x

D-----5x = y-7

E-----x = y-7

Pergunta 2

Considere o trecho de código abaixo: 

                               {n = -4} 

                                Se n > 0 então 

                                     y = -1*n  

                                Senão 

                                     y = n   

                               {y = } 

Assinale a alternativa que contém as expressões para as triplas de Hoare a serem verificadas na correção do trecho de código. 

A----- {n= - 4 ∧ n > 0} y= -1*n {y=4} 

{n=-4 ∧ (n >0)} y=n {y=4} 

B----- {n > 0} y= -1*n {y=-4 ∧ n > 0} 

​{¬(n >0)} y=n {y=4∧ n > 0}

C------ {n= - 4} y= -1*n {y=4} 

{n=-4 } y=n {y=4} 

D-------{n= - 4 ∧ n > 0} y= -1*n {y=4} 

​{n=-4 ∧ ¬(n >0)} y=n {y=4}

E-------- {y= 4 ∧ n > 0} y= -1*n {y=4} 

{n=-4 ∧ ¬(x >0)} y=n {y=4}​ 

Pergunta 3

Considere o trecho de código abaixo:

{i=0,n>0,s=0}

Enquanto (i≠n) faça

         i=i+1

         s=s+(2*i-1)

Assinale a alternativa que contém a expressão para a invariante de laço para o trecho de código.

A------ 2n+1

B-----2n-1

C------ 2n2

D------ n-1

E------- n2

Pergunta 4

Considere o algoritmo abaixo: 

O_q_retorno( n inteiro positivo) 

Início 

 Se n=1 

  retorna 10 

 Senão 

   retorna (O_q_retorno (n-1) + 10) 

Fim 

Assinale a alternativa com os valores retornados pelas chamadas O_q_retorno(5) 

A------ 10, 100, 1000, 1000, 10000

B----- 10, 10, 10, 10, 10, 10

C------ 10, 20, 30, 40, 50

D------10, 11, 12, 13, 14

E------ 10, 30, 50, 60, 70

Pergunta 5

Considere o algoritmo abaixo: 

A( n inteiro positivo) 

Início 

 Se n<1 

  retorna 10 

 Senão 

   retorna (A (n-1)*2 -1) 

Fim 

Assinale a alternativa com a relação de recorrência para esse algoritmo. Seja A(n) a representação do algoritmo com entrada n. 

A----- A(n)=2.A(n-1)-10 para n>1 e A(1)=10

B------ A(n)=2.A(n-1)-1 para n1 e A(0)=10

C------- A(n)=A(n-1)- para n>1 e A(1)=10

D------- A(n)=2.A(n-1) para n>1 e A(0)=10

E------- A(n)=2.A(n-1)-1 para n>1 e A(1)=1

Pergunta 6

Considere a relação de recorrência abaixo: 

T(n) = 2.T(n-1)+5 para n>0 

T(0)=6 

Assinale a alternativa contendo o valor para T(4): 

A----- 171

B------ 165

C------- 211

D------- 141

E--------305

Pergunta 7

Considere a relação de recorrência abaixo: 

T(n) = 2.T(n-1)+5 para n>0 

T(0)=6 

Assinale a alternativa com a expressão que resolve essa relação de recorrência. 

A----- 2n-10

B------ 11.2n-5

C------ 2n+5

D------ 2n-5

E------ 7.2n-5

Pergunta 8

Assinale a alternativa com a solução para a relação de recorrência abaixo: 

                        S(n) = 6S(n – 1) - 5S(n – 2) para n ≥ 3 

                        S(1)=1 

                        S(2)=2 

A------- S(n)= (¼). (5)n-1+ (¾) (3)n-1

B------- S(n)= (¼). (5)n-1+ (¾)

C------- S(n)= (¼). (3)n-1+ (¾) (5)n-1

D--------S(n) = .(5)n-1 +1

E----------S(n)= (¾). (5)n-1 + (¼)  

Pergunta 9

Assinale a alternativa com a solução para a relação de recorrência abaixo: 

T(n) = 4T(n/2) +(3n2) para n > 1 

T(1)=1 

A----n+2.n.log(n)

B---n2+2.n.log(n)

C---n+n.log(n)

D--n2+3.log(n)

E--- n2+3.n2.log(n)

Pergunta 10

Considere as sentenças abaixo: 

 i. ρ uma relação binária em ℚ com xρy↔x + y < 7; os pares (1, 3), (3, 3), (4,4) atendem tal relação.

 ii. ρ uma relação binária em ℤ com x ρ y ↔ x = –y; os pares (1, –1), (–3, 3) atendem tal relação.

 iii. ρ uma relação binária em ℚ, x ρ y ↔ x ≤ 1/y; os pares (–3, –5), (–4, 1/2), (1/2, 1/3) atendem tal relação. 

A -) Apenas ii está correta

B-) Apenas iii está correta

C-) Apenas ii e iii estão corretas

D-) Apenas i está correta

E-) Apenas i e ii estão corretas