Com base no conhecimento sobre a engenharia de requisitos, assinale a alternativa CORRETA.

São algoritmos de ordenação, EXCETO:

Sobre as estruturas de dados, especificamente a estrutura de dados pilha, assinale a alternativa CORRETA.

Qual é a estrutura de controle básica de seleção?

Acerca do Teorema mestre, sejam a ≥ 1 e b > 1 constantes, seja f(n) uma função e seja T(n) definida no domínio dos números inteiros não negativos pela recorrência

T(n) = aT(n/b) + f(n),

onde interpretamos que n/b significa n/b ou n/b. Então, T(n) tem os seguintes limites assintóticos:

I. Se f(n) = O(n_{logb a}-) para alguma constante > 0, então T(n) = Θ(n_{log b a}).

II. Se f(n) = Θ(n_{logb a}), então T(n) = Θ(n_{logb a} lg n).

III. Se f(n) = (n_{logb a}+) para alguma constante >0, e se af(n/b) ≤ cf(n) para alguma constante c < 1 e todos os n suficientemente grandes, então T(n) = Θ(f(n)).

Nesse sentido, assinale a alternativa CORRETA.

Observe o seguinte algoritmo direto baseado na paralelização dos laços no procedimento SQUARE - MATRIX - MULTIPLY:

P-SQUARE-MATRIX-MULTIPLY (A,B)

1 __ n = A.rows

2 __ seja C uma nova matriz n x n

3__ parallel for i = 1 to n

4 __ __ __ parallel for j = 1 to n

5 __ __ __ __ c_ij = 0

6 __ __ __ __ for k =1 to n

7 __ __ __ __ __ __ c_ij = c_ij + a_ik . b_kj

8 __ return C

Pode-se afirmar que a duração é T∞(n) = (n), devido às descidas dos laços parallel for e for comum, resultando em uma duração total de (lg n) + (lg n) + (n) = (n). Desse modo, qual é o paralelismo?

Observe o pseudocódigo abaixo demonstrado, o qual se trata de uma ordenação por inserção.

INSERTION-SORT(A)

1 for j = 2 to A • comprimento

2 __ chave =A [j]

3 __ // Inserir A [j] na sequência ordenada A [1 .. j -1].

4__ i = j - 1

5 __ while i > 0 e A [i] > chave

6 __ __ __ A [i + 1] = A [i]

7 __ __ __ i = i - 1

8 __ A [i + 1] = chave

Existem determinadas convenções que são praticadas em pseudocódigos, como é o caso do uso representativo de laços, em for e while. Versando somente acerca do segundo dos laços citados, é possível afirmar que ele começa em que linha, e contém qual(is) outra(s), respectivamente?

O procedimento FIND-MAX-CROSSING-SUBARRAY, pela técnica de divisão e conquista, toma como entrada o arranjo A e os índices low, mid e high, e retorna uma tupla que contém os índices que demarcam um subarranjo máximo que cruza o ponto médio, juntamente com a soma dos valores em um subarranjo máximo.

Analise a estrutura a seguir.

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)

1 left-sum = -∞

2 sum = 0

3 for i = mid downto low

4 ___ sum = sum + A[i]

5 ___ if sum > left-sum

6 ___ ___ left-sum = sum

7 ___ ___ max-left = i

8 right-sum = -∞

9 sum = 0

10 for j = mid+ 1 to high

11 ___ sum = sum + A[i]

12 ___ if sum > right-sum

13 ___ right-sum = sum

14 ___ max-right = j

15 return (max-left, max-right, left-sum + right-sum)

Acerca das funções descritas acima, assinale a alternativa CORRETA.

Pode-se compreender uma recorrência como sendo uma equação ou uma desigualdade que descreve uma função em termos de seu valor para entradas menores Dentre os métodos existentes para a resolução de situações com recorrência, aquele no qual arrisca-se um palpite para determinado limite e através de indução matemática para provar que o palpite está correto é:

Considere em um algoritmo o tempo de execução T(n) do pior caso da ordenação por intercalação para n números. Sabe-se que há a demora de um tempo constante para a ordenação por intercalação de um único elemento. Nas situações em que n > 1, o tempo de execução deve ser detalhado. Em uma das etapas, calcula-se o ponto médio do arranjo, o que demora um tempo constante, ou seja: