Baixe o app para aproveitar ainda mais
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
Compartilhar