Loop Invariant in funzione ricorsiva

Question

Loop Invariant in funzione ricorsiva

#1 da (1 voti)
#2 da (0 voti)

0

Durante la lettura di Introduction to Algorithms (3a edizione, P188), c'è un algoritmo chiamato Tail-Recursive-QuickSort e dobbiamo dimostrare la correttezza di questo algoritmo.

TAIL-RECURSIVE-QUICKSORT(A, p, r)
1 while p < r
2     // Partition and sort left subarray.
3     q = PARTITION(A, p, r)
4     TAIL-RECURSIVE-QUICKSORT(A, p, q - 1)
5     p = q + 1

Il problema è che, quando ho provato ad utilizzare l'invariante di loop, ho trovato difficile per me spiegare chiaramente la manutenzione a causa della funzione ricorsiva all'interno del corpo del loop. Il ciclo invariante che utilizzo è:

Before each iteration, A[0:p-1] are sorted.

Il caso iniziale è banale, ma la manutenzione implica dimostrare che TAIL-RECURSIVE-QUICKSORT non cambia l'invarianza del ciclo. C'è un modo per spiegarlo chiaramente?

Grazie.

algorithms algorithm-analysis

posta fois 11.09.2016 - 18:31

fonte

2 risposte

Leggi altre domande sui tag algorithms algorithm-analysis

Architettura per l'ispezione dei pacchetti distribuiti Esiste comunque la possibilità di memorizzare statico: i vettori di puntatori di tutte le mie classi derivate nella mia classe base?

score 1 · Answer 1

Ok, forse lo snippet è troppo piccolo. Non vedo la ricorsione della coda, solo una funzione con "TAIL" nel nome.

Ma quando un linguaggio o un compilatore si avvantaggia della ricorsione in coda, il codice viene eseguito come se non fosse ricorsivo in coda, tranne che per non utilizzare lo stesso spazio di stack.

Durante l'ottimizzazione della chiamata di coda, lo stato variabile nel frame corrente viene sostituito nella sua interezza con il nuovo stato della nuova chiamata (proprio come se la nuova chiamata fosse stata resa non ottimizzata con un nuovo stack frame). Nessuno stato del chiamante sopravvive eccetto dove tornare.

Quindi, se puoi dimostrare il normale caso ricorsivo, puoi applicare quella prova al caso ricorsivo della coda.

La ricorsione di coda è una tecnica di ottimizzazione e, le tecniche di ottimizzazione non modificano il tuo algoritmo (nonostante il compilatore danneggiato o danneggiato)

Per quanto riguarda la dimostrazione dell'invarianza della ricorsione, penso che sia un esercizio accademico; ad esempio, vedi qui: link

Before each iteration, A[0:p-1] are sorted.

Non penso che ci sia l'invariante quicksort che richiede che l'input sia ordinato, ma piuttosto che sia partizionato, che è una condizione verificabile ma non uguale a quella ordinata.

Inoltre, un quicksort ricorsivo, un livello superiore, non opera in termini di iterazioni , poiché non esiste un ciclo esterno, ma in termini di invocazioni in quanto vi è ricorsione.

score 0 · Answer 2

Hai una funzione ricorsiva. Il metodo di base per dimostrare che una funzione ricorsiva funzionerà correttamente è per induzione completa: si dimostra che la funzione funziona correttamente se un valore n è 0 (si avrebbe n = r -p, ad esempio), e quindi si prova che funziona correttamente per n > 0 se funziona correttamente per tutti i più piccoli valori di n.

Quindi per prima cosa leggi il tuo codice e verifica che sia corretto se r-p = 0. Quindi prova che q-1 < r, perché questo significa che nella chiamata ricorsiva r -p sarà più piccolo, e quindi puoi assumere per induzione che funzioni. E per il resto della dimostrazione, hai ancora bisogno di un ciclo invariante. E una specifica su cosa dovrebbe fare PARTITION e una prova che fa ciò che dovrebbe fare.

Il tuo invariante ciclo non può funzionare, ad esempio se hai mai avuto p = 3, e sei elementi dell'array 11, 12, 13, 1, 2, 3, quindi tuo "loop invariant" è vero prima del ciclo ma non in seguito perché 11, 12 e 13 all'inizio dell'array non verrebbero più toccati.