Considerando o recurso de inversão apresentado, descreva como um algoritmo de complexidade O(nlog(n)), tanto no melhor como no pior casos, pode ser projetado para contar o número de inversões existent

Prévia do material em texto

ATIVIDADE 3.0 (A3)
09.1 (ANÁLISE DE ALGORITMOS)
Caro(a) aluno(a),
O entendimento dos algoritmos de ordenação apresentados nesta unidade é essencial para o desenvolvimento das 
habilidades necessárias para projetar soluções computacionais em cenários variados. De fato, saber empregar um 
algoritmo já conhecido para modelar um dado problema pode agregar eficiência e precisão ao processo de 
obtenção de uma resposta.
Um recurso muito utilizado em vários sistemas e bibliotecas computacionais é o de inversão. Para um dado 
vetor A[1 ... n ] de n números reais, um par (A[ i ], A[j]) é dito ser uma inversão se esses números estão fora de 
ordem, ou seja, quando i < j, temos que A[i] > A[j]. Por exemplo, um vetor com os elementos:
1, 3, 5, 2, 4, 6
Tem as seguintes inversões:
(3, 2), (5, 2) e (5, 4)
Proposta
Considerando o recurso de inversão apresentado, descreva como um algoritmo de complexidade O(nlog(n)), 
tanto no melhor como no pior casos, pode ser projetado para contar o número de inversões existentes em um vetor 
de n números reais. Tome como base os pseudocódigos apresentados na unidade.
Submeta o arquivo de sua resposta para avaliação docente.
9 SEMESTRE DE 2024 (BLOCO 1) – 1o PROVA
ATIVIDADE 3.2 (ANÁLISE DE ALGORITMOS)
9 SEMESTRE DE 2024 (BLOCO 1) - 1o PROVA
RESPOSTA
Prezado professor,
Com base no estudo dos materiais da terceira unidade e na tarefa proposta, gostaria de apresentar minha abordagem para o cálculo do 
número de inversões em um vetor de números reais. Optei por utilizar o algoritmo Merge Sort, que é eficiente e possui complexidade 
O(nlog(n)) tanto para os melhores quanto para os piores casos.
O Merge Sort divide o vetor em duas partes, ordena cada uma delas e, em seguida, as combina novamente, resultando em um vetor 
ordenado. Durante a etapa de combinação, é possível contar as inversões.
Segue o pseudocódigo do algoritmo que desenvolvi:
MergeSort(A, p, r)
1. Se p < r
2. q = (p + r) / 2
3. MergeSort(A, p, q)
4. MergeSort(A, q + 1, r)
5. Merge(A, p, q, r)
Merge(A, p, q, r)
1. n1 = q - p + 1
2. n2 = r - q
3. Crie arrays L[1 ... n1 + 1] e R[1 ... n2 + 1]
4. Copie A[p ... q] para L[1 ... n1] e A[q+1 ... r] para R[1 ... n2]
5. L[n1 + 1] = ∞ e R[n2 + 1] = ∞
6. i = 1 e j = 1
7. para k = p até r
8. se L[i] ≤ R[j]
9. A[k] = L[i]
10. i = i + 1
11. senão
12. A[k] = R[j]
13. j = j + 1
14. inversões = inversões + (n1 - i + 1)
ContarInversoes(A, p, r)
1. inversões = 0
2. Se p < r
3. q = (p + r) / 2
4. ContarInversoes(A, p, q)
5. ContarInversoes(A, q + 1, r)
6. inversões += Merge(A, p, q, r)
7. return inversões
No método Merge, incluí uma modificação para contabilizar as inversões. Quando um elemento do subvetor direito (R[j]) é copiado 
para o vetor A, isso indica que todos os elementos restantes no subvetor esquerdo (L[i … n1]) são maiores que R[j] e, portanto, cada um 
deles forma uma inversão com R[j]. Assim, o contador de inversões é incrementado pelo número de elementos remanescentes no 
subvetor esquerdo.
Espero que esta solução atenda às expectativas da atividade e estou aberto a discussões e sugestões para aprimorá-la.
Atenciosamente, Ângelo
9 SEMESTRE DE 2024 (BLOCO 1) – 1o PROVA
ATIVIDADE 3.3 (ANÁLISE DE ALGORITMOS)
9 SEMESTRE DE 2024 (BLOCO 1) - 1o PROVA
RESPOSTA DO PROFESSOR
Avaliação final do texto: 10 
Comentários
Wow, seu texto está fantástico
Você atende os principais critérios da escrita clara, objetiva e coerente. Para continuar com este 
desempenho você pode:
a) Ampliar informações sem fragmentar seu texto. 
b) Desenvolver itens que lhe ajudem a voltar a ideia central do texto. 
c) Atualizar-se sempre mais sobre as regras gramaticais da Língua Portuguesa. Isto ajudará nas próximas 
produções textuais.
Congrats
Bons estudos
; 
9 SEMESTRE DE 2024 (BLOCO 1) – 1o PROVA