Algoritmos e Estruturas de dados para Engenharia Elétrica - Poli - P3 2016

Prévia do material em texto

Solução
PCS3110 - Algoritmos e Estrutura de Dados para Engenharia Elétrica Prova 3 - 02/12/2016
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
Utilize caneta azul ou preta para marcar as caixas e preencha a caixa totalmente
para correta interpretação. Exemplo: �. Não use �.
1 Anna 2 Fábio 3 Romero 4 Anarosa
Marque as caixas ao lado para formar o seu número USP e escreva seu nome
abaixo.
Nome (completo):
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Instruções para a prova
1 Esta prova contém 2 questões dissertativas e 8 testes. Verifique atentamente se todas elas estão presentes. Em
caso de dúvida chame o professor.
2 Preencha seu nome e número USP. Provas não identificadas não serão corrigidas.
3 Resolva as questões dissertativas apenas no espaço a elas reservado. Respostas fornecidas fora do local a elas
destinadas não serão corrigidas.
4 A duração total da prova é de 100 minutos.
5 É proibido o uso de calculadoras e qualquer outro aparelho eletrônico.
6 É proibido retirar o grampo da prova.
7 A interpretação da questão faz parte da avaliação dos alunos. Caso considere alguma hipótese que não esteja
explicitada no enunciado, indique claramente na resposta.
8 A prova é SEM CONSULTA.
Solução
[2,6 pontos] Questão 1
Ordenação por contagem pode ser aplicada a uma entrada formada por um conjunto de n números inteiros positivos
limitados a um valor máximo k. O algoritmo abaixo executa essa ordenação, com duas características importantes: 1.
permite repetição de números; 2. preserva, no vetor ordenado, a ordem entre si de eventuais números repetidos que
se encontrem no conjunto de entrada (ordenação estável).
OrdenaPorContagem (A, B, k)
// A[1..n]: vetor de entrada
// B[1..n]: vetor de saída
// 1 ≤ A[i] ≤ k, para 1 ≤ i ≤ n
1 seja C[1..k] um novo vetor
2 for i = 1 to k
3 C[i] = 0
4 for j = 1 to A.tamanho
5 C[ A[j] ] = C[ A[j] ] + 1
6 for i = 2 to k
7 C[i] = C[i] + C[i-1]
8 for j = A.tamanho downto 1
9 B[ C[ A[j] ] ] = A[j]
10 C[ A[j] ] = C[ A[j] ] - 1
Solução
a [1,3 ponto] Para o arranjo A = [3, 1, 3, 1, 4], responda o que se pede:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 4 5 7 8 10 13
a.1) Qual o menor valor possível de k para a chamada de OrdenaPorContagem(A, B, k)?
k = 4
a.2) Preencha no arranjo C45 a configuração do arranjo C ao final da execução do laço de linhas 4 e 5 e no
arranjo C67 a configuração do arranjo C ao final da execução do laço de linhas 6 e 7. Caso alguma posição
do arranjo C não seja usada, deixe-a em branco.
C45 2
1 2
2
3
1
4 5
C67 2
1
2
2
4
3
5
4 5
a.3) Preencha nos arranjos B e C suas configurações ao final de cada iteração do laço de linhas 8 a 10. Caso
alguma posição do arranjo C não seja usada, deixe-a em branco.
Arranjo B
1 2 3 4
4
5
1 4
1 3 4
1 1 3 4
1 1 3 3 4
Arranjo C
2
1
2
2
4
3
4
4 5
1 2 4 4
1 2 3 4
0 2 3 4
0 2 2 4
b [0,5 ponto] Se os números são iguais qual seria a utilidade de uma ordenação estável, que preserva a ordem de
eventuais números repetidos entre si?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 4 5
Quando esses números representarem chaves de objetos, por exemplo, mesmo sendo iguais podem possuir dados
satélites diferentes. Neste caso preservar a ordem original faz diferença.
Solução
c [0,8 ponto] O que precisa ser alterado no algoritmo OrdenaPorContagem(A,B,k), para que os números a
ordenar possam incluir o zero ( 0 ≤ A[i] ≤ k )? Escreva o algoritmo modificado no espaço reservado ao lado do
OrdenaPorContagem(A,B,k). Faça o mínimo de alterações possível. Linhas inalteradas devem ser deixadas
em branco. Importante: os arranjos devem permanecer iniciando na posição 1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4 5 6 7 8
Para responder a questão 1.c
// 0 ≤ A[i] ≤ k, para 1 ≤ i ≤ n
1 seja C[1..k+1] um novo vetor
2 for i = 1 to k+1
3
4
5 C[ A[j] + 1 ] = C[ A[j] + 1 ] + 1
6 for i = 2 to k + 1
7
8
9 B[ C[ A[j] + 1 ] ] = A[j]
10 C[ A[j] + 1 ] = C[ A[j] + 1] - 1
OrdenaPorContagem (A, B, k)
// A[1..n]: vetor de entrada
// B[1..n]: vetor de saída
// 1 ≤ A[i] ≤ k, para 1 ≤ i ≤ n
1 seja C[1..k] um novo vetor
2 for i = 1 to k
3 C[i] = 0
4 for j = 1 to A.tamanho
5 C[ A[j] ] = C[ A[j] ] + 1
6 for i = 2 to k
7 C[i] = C[i] + C[i-1]
8 for j = A.tamanho downto 1
9 B[ C[ A[j] ] ] = A[j]
10 C[ A[j] ] = C[ A[j] ] - 1
Solução
[2,6 pontos] Questão 2
Dada uma sequência de números, um problema interessante consiste em encontrar o comprimento da subsequência
crescente mais longa (LIS – longest increasing subsequence). Os elementos da LIS são ordenados, do menor para
o maior, e não necessariamente são contíguos na sequência original. Considere não haver números duplicados na
sequência de números. Por exemplo, para a sequência {10, 22, 15, 33, 21, 50, 41, 60, 80}, o comprimento da LIS é 6 e
uma LIS poderia ser {10, 22, 33, 50, 60, 80} (outra LIS de mesmo comprimento poderia ser {10, 15, 21, 41, 60, 80}). Este
problema pode ser formulado por Programação Dinâmica (PD).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 4 8 12 17 22
a [1,4 pontos] Considere o pseudo-código Comprimento-LIS dado a seguir, sendo X uma indicação de que não
há predecessor na LIS. Efetue o rastreamento do mesmo e preencha a Tabela 1 na terceira linha, CompLIS; na
quarta linha, Pred; max e iMax finais para n = 10 e Seq dada na segunda linha da Tabela 1.
Comprimento-LIS (n, Seq)
1 Sejam CompLIS[1...n] e Pred[1...n] arranjos
2 for i = 1 to n
3 CompLIS[i] = 1; Pred[i] = X
4 max = 0; iMax = 0
5 for i = 2 to n
6 for j = 1 to i− 1
7 if Seq[j] < Seq[i] and (CompLIS[j] + 1) > CompLIS[i]
8 CompLIS[i] = 1 + CompLIS[j]; Pred[i] = j
9 for i = 1 to n
10 if max < CompLIS[i]
11 max = CompLIS[i]; iMax = i
12 return max, iMax, Seq, Pred
Tabela 1:
i 1 2 3 4 5 6 7 8 9 10
Seq 7 6 10 3 4 1 8 9 5 2
CompLIS 1 1 2 1 2 1 3 4 3 2
Pred X X 1 X 4 X 5 7 5 1
max 4
iMax 8
b [0,9 pontos] Complete o pseudo-código Max-Subseq a seguir para que possamos recuperar a subsequência que
forneceu o maior comprimento de subsequência crescente (use as linhas necessárias e idente apropriadamente).
Max-Subseq (max, iMax, Seq, Pred)
1. Seja Subseq[1...max] um arranjo
2. for i = max downto 1
3. Subseq[i] = Seq[iMax]
4. iMax = Pred[iMax]
5. return Subseq
Solução
c [0,3 pontos] Forneça a LIS resultante para a entrada especificada na Tabela 1.
LIS = {3, 4, 8, 9}
Solução
Insertion-Sort (A)
1 for j = 2 to A.tamanho
2 chave = A[j]
3 i = j - 1
4 while i > 0 and A[i] > chave
5 A[i+1] = A[i]
6 i = i - 1
7 A[i+1] = chave
Heapsort (A)
1 Constroi-Max-Heap(A)
2 for i = A.tamanho downto 2
3 temp = A[1]
4 A[1] = A[i]
5 A[i] = temp
6 A.heap-size=A.heap-size-1
7 Max-Heapify(A, 1)
Mergesort (A, i, f)
1 if i < f
2 m = b(i + f)c / 2
3 Mergesort(A, i, m)
4 Mergesort(A, m + 1, f)
5 Merge(A, i, m, f)
Quicksort (A, i, f)
1 if i < f
2 p = Partition(A, i, f)
3 Quicksort(A, i, p – 1)
4 Quicksort(A, p + 1, f)
Merge (A, ini, fim1, fim2)
1 n1 = fim1 - ini + 1
2 n2 = fim2 - fim1
3 E[1 .. n1+1] e D[1 .. n2+1] arranjos4 for i = 1 to n1
5 E[i] = A[ini + i - 1]
6 for j = 1 to n2
7 D[j] = A[fim1 + j]
8 E[n1 + 1] = ∞; D[n2 + 1] = ∞
9 i = 1 ; j = 1
10 for k = ini to fim2
11 if E[i] <= D[j]
12 A[k] = E[i]; i = i + 1
13 else
14 A[k] = D[j]; j = j + 1
Partition (A, inicio, fim)
1 pivo = A[fim]
2 i = inicio - 1
3 for j = inicio to fim - 1
4 if A[j] <= pivo
5 i = i + 1
6 temp = A[i]
7 A[i] = A[j]
8 A[j] = temp
9 A[fim] = A[i + 1]
10 A[i + 1] = pivo
11 return i + 1
Inserir-Maxheap (A, chave)
1 A.heap-size = A.heap-size + 1
2 A[A.heap-size] = chave
3 i = A.heap-size
4 while i > 1 and A[Pai(i)] < A[i]
5 temp = A[i]
6 A[i] = A[Pai(i)]
7 A[Pai(i)] = temp
8 i = Pai(i)
Extrair-Maior (A)
1 if A.heap-size < 1
2 erro “underflow do heap”
3 maior = A[1]
4 A[1] = A[A.heap-size]
5 A.heap-size = A.heap-size - 1
6 Max-Heapify(A, 1)
7 return maior
Constroi-Max-Heap (A)
1 A.heap-size = A.tamanho
2 for i = bA.tamanho/2c downto 1
3 Max-Heapify(A, i)
Max-Heapify (A, i)
1 esq = Filho-Esquerda(i)
2 dir = Filho-Direita(i)
3 if esq <= A.heap-size and A[esq] > A[i]
4 maior = esq
5 else maior = i
6 if dir <= A.heap-size and A[dir] > A[maior]
7 maior = dir
8 if maior != i
9 temp = A[i]
10 A[i] = A[maior]
11 A[maior] = temp
12 Max-Heapify(A, maior)
Solução
[4,8 pontos] Testes
Teste 1 Para os algoritmos Repetidos-1(A) e Repetidos-2(A) podemos afirmar que:
Repetidos-1(A)
1 Insertion-Sort(A)
2 for i = 1 to A.tamanho - 1
3 if A[i] == A[i + 1]
4 return TRUE
5 return FALSE
Repetidos-2(A)
1 MergeSort(A)
2 for i = 1 to A.tamanho - 1
3 if A[i] == A[i + 1]
4 return TRUE
5 return FALSE
A Ambos algoritmos têm mesma complexidade.
B Ambos algoritmos contam quantos valores repetidos aparecem em A.
C Ambos usam outros algoritmos que fazem uso de estruturas auxiliares.
D Repetidos-1(A) é sempre mais eficiente (em tempo de execução) que Repetidos-2(A).
E Repetidos-2(A) tem complexidade de melhor caso igual à complexidade de pior caso.
Teste 2 Considere as seguintes afirmações e assinale a alternativa correta:
I Se um algoritmo A é Θ(nlgn), ele também é Ω(nlgn) e O(nlgn).
II Seja C um algoritmo com função de cálculo de tempo de execução T (n) = 3n2 + n3. Então C é O(n2) e Ω(n3).
III Θ(f(n) + g(n)) = Θ(f(n)) + Θ(g(n)).
A As afirmações I, II e III são verdadeiras.
B Apenas a afirmação III é verdadeira.
C Apenas I e III são afirmações verdadeiras.
D Apenas a afirmação I é verdadeira
E Apenas as afirmações II e III são verdadeiras.
Teste 3 Assinale a alternativa que apresenta o tempo de execução, em notação Θ, para o algoritmo Z apresentado
a seguir:
A Θ(lgn)
B Θ(n)
C Θ(n3)
D Θ(n2)
E Θ(nlgn)
Z(n)
1 if n <= 1
2 return 1
3 x = 1
4 for i = 1 to n
5 x = x + 1
6 return x + Z(n - 2)
Solução
Teste 4 Como devem ser as linhas 2 e 3 do algoritmo Partition-Pivo-Inicio, que usa o valor na primeira posição
do arranjo como pivô? Assim como no algoritmo visto em aula, esse algoritmo deve particionar o arranjo em dois
subarranjos com valores menores ou iguais que o pivô no começo do arranjo e valores maiores que o pivô no final.
A 2 i = fim
3 for j = inicio to fim - 1
B 2 i = inicio - 1
3 for j = fim downto inicio + 1
C 2 i = fim + 1
3 for j = inicio to fim - 1
D 2 i = fim + 1
3 for j = fim downto inicio + 1
E 2 i = inicio - 1
3 for j = inicio to fim - 1
Partition-Pivo-Inicio (A, inicio, fim)
1 pivo = A[inicio]
2
3
4 if A[j] > pivo
5 i = i - 1
6 temp = A[i]
7 A[i] = A[j]
8 A[j] = temp
9 A[inicio] = A[i - 1]
10 A[i - 1] = pivo
11 return i - 1
Teste 5 Dado o vetor A = [ 16, 15, 14, 13, 12, 11, 10 ], podemos afirmar sobre a configuração de A, durante
a execução de Heapsort(A) e imediatamente após a execução do laço for para i = A.tamanho - 1 que:
A A = [ 14, 13, 11, 12, 10, 15, 16 ]
B A = [ 14, 11, 13, 10, 12, 15, 16 ]
C A = [ 14, 11, 13, 12, 10, 15, 16 ]
D A = [ 14, 13, 11, 10, 12, 15, 16 ]
E Nenhuma das outras alternativas é correta.
Teste 6 Considere uma fila de prioridade P, implementada com um Max-Heap, e uma fila comum Q. Considere
que, para a fila de prioridade, Enqueue significa Inserir-Maxheap e que Dequeue significa Extrair-Maior. Assinale
a alternativa que apresenta o conteúdo de P e Q após as seguintes operações nas filas:
Enqueue 5, Enqueue 6, Enqueue 4, Enqueue 3, Dequeue, Enqueue 7, Dequeue
A P e Q são iguais.
B P = [5, 4, 3]; Q = [4, 3, 7]
C P = [5, 3, 4]; Q = [5, 6, 4]
D P = [5, 4, 3]; Q = [5, 6, 4]
E P = [5, 3, 4]; Q = [4, 3, 7]
Solução
Teste 7 Os computadores atuais possuem processadores com diversos núcleos, o que permite que algoritmos sejam
executados em paralelo. Cada núcleo pode ser responsável por executar uma chamada do algoritmo ou uma parte
dele. A respeito do uso da paralelização de algoritmos de ordenação, assinale a alternativa incorreta.
A Não é possível executar as iterações do laço do Heapsort em paralelo, da forma como ele está, pois a ordem em
que as iterações são executadas é importante.
B No caso da paralelização do Mergesort, é preciso esperar que as duas execuções recursivas do Mergesort termi-
nem para que seja executado o algoritmo Merge.
C O cálculo do tempo de execução em notação assintótica precisa ser revisto caso o algoritmo possa ser paralelizado.
D Cada chamada recursiva do Quicksort pode ser executada em paralelo, já que cada uma processa subarranjos
que não possuem intersecção.
E Exatamente duas chamadas do Mergesort podem ser executadas em paralelo por vez, ainda que o processador
possua mais de dois núcleos.
Teste 8 Sobre o algoritmo MergeSort(A,inicio,fim), considere as afirmações e assinale a alternativa correta:
I Sua complexidade de pior caso é Ω(A.tamanho).
II A função Merge(A,inicio, meio, fim) tem complexidade Θ(A.tamanho).
III O algoritmo usa o método de projeto Dividir para Conquistar, sendo que a divisão acontece na execução de
Merge(A, inicio, meio, fim) e a conquista na execução das chamadas recursivas de MergeSort(A, inicio,
meio) e MergeSort(A, meio+1, fim)
A As afirmações I, II e III são verdadeiras.
B Apenas a afirmação II é verdadeira.
C Apenas I e II são afirmações verdadeiras.
D Apenas as afirmações II e III são verdadeiras.
E Apenas a afirmação I é verdadeira