A Correte de Algoritmos
Por: arthurvff • 15/2/2022 • Trabalho acadêmico • 443 Palavras (2 Páginas) • 73 Visualizações
Prove a corretude do algoritmo MergeSort. Use invariante de laço para provar a corretude da função merge e, em seguida, prove a corretude da recursão usando prova por indução.
[pic 1]
Vamos provar que a função Merge de fato ordenará o array A se os subarrays A [inicio..meio] e A [meio+1..fim] estiverem ordenados, para qualquer tamanho de vetor.
Invariante de laço:
No começo de cada iteração do nosso loop principal, o nosso subarray A[i..k-1] contém os k - i menores elementos de L e R em ordem.
L [i] e R [j] são os menores elementos de L e R que ainda não foram copiados para A.
Inicialização:
Antes da primeira iteração, A [i..k-1] está vazio, ambos i e j são iguais a 1 e L [1] e R [1] são os menores elementos de L e R não copiados para A.
Manutenção:
Considerando que L [i] ≤ R [j], o array A contém i - k menores elementos de L e R em ordem, L [i] e R [j] são os menores elementos de L e R ainda não copiados para A, resultando que A contém i - k + 1 menores componentes, em ordem. Incrementando i e k restabelece a nossa Invariante de Laço para a próxima iteração.
Finalização:
Finalizando, k é igual a f + 1, o array A contém k - i = f - i + 1 menores elementos de L e R em ordem e todos os elementos com exceção das sentinelas foram copiados para A.
Corretude do Merge-Sort
O que eu quero provar:
O Merge-Sort (A, i, f) ordena A[inicio..fim] para qualquer vetor.
Caso base:
Se n = 0, 0 = fim-inicio+1 → inicio = fim+1, ou inicio > fim Se n = 1, 1 = fim-inicio+1 → inicio = fim
Hipótese indutiva:
Seja n > 1 e supondo que Merge-Sort ordena vetores com tamanho k, para 0 ≤ k < n.
Passo indutivo:
Tendo que 𝑛 = 𝑓𝑖𝑚 − 𝑖𝑛𝑖𝑐𝑖𝑜 + 1 > 1 → 𝑓𝑖𝑚 > 𝑖𝑛𝑖𝑐𝑖𝑜 .
O algoritmo calcula e faz duas chamadas recursivas.[pic 2]
A primeira é sobre A[inicio..meio] e aqui percebemos que
[pic 3]
quando n > 1.
Então, essa chamada, por hipótese, funciona.
Como 𝑓𝑖𝑚 − (𝑚𝑒𝑖𝑜 + 1) + 1 < 𝑛 , a segunda chamada também funciona.
E como vimos que o Merge também funciona quando A[inicio..meio] e A[meio+1..fim] estão ordenados, então a chamada atual ordena A[inicio..fim].
...