[Algoritmi] Dimostrare correttezza algoritmo

[iggy]

Salve, ho delle difficoltà quando devo dimostrare la correttezza di un algoritmo. Nel senso che so cosa fa l'algoritmo e come funziona, ma non capisco proprio in che modo "formalizzare" la spiegazione.
So che spesso si utilizza l'induzione (quindi un caso base e il passo induttivo) e le inferenza da ciclo.

Un esempio di esercizio:

Dati un albero binario di ricerca T (contenente valori interi distinti) e due valori interi min, max, con min < max, scrivere un algoritmo occurrences(TREE T, integer min, integer max) che restituisca il numero di valori di T che sono compresi fra min e max, estremi inclusi. Discutere correttezza e complessità della soluzione proposta.

L'algoritmo che ho scritto in pseudocodice è :

Codice:

int occurrences(TREE node, integer min, integer max){
    if(node == NULL)
        return 0
    else if(node.key < min)
        return occurrences(node.right, min, max)
    else if(node.key > max)
        return occurrences(node.left, min, max)
    else
        return 1 + occurrences(node.left, min, max) + occurrences(node.right, min, max)
}

La complessità è O(n) perchè deve dovrebbe scandire tutti i nodi dell'albero, ma in realtà scarta i sottoalberi in cui sicuramente non c'è un elemento cercato.

Nella correttezza invece iniziano i dolori: decido di fare un'induzione sul numero di chiamate ricorsive (h).

Devo dimostrare che la funzione, dato un albero BST corretto, ritorna in ogni caso il numero di nodi la cui chiave è compresa fra min e max.

Base: 0 chiamate ricorsive -> l'albero è vuoto -> ritorno 0 ed è corretto;
Ipotesi induttiva: con h-1 chiamate ricorsive l'algoritmo è corretto(?);
Passo: dimostrare che con h chiamate ricorsive, in cui h è l'ultima chiamata prima della terminazione della funzione, l'algoritmo soddisfa le premesse. Ma come?

Grazie.

[apatriarca]

Invece di lavorare sul numero di chiamate ricorsive credo sia più utile lavorare in termini di altezza dell'albero. Il caso base è chiaramente l'albero vuoto come hai già determinato. A questo punto supponi nell'ipotesi induttiva che l'algoritmo funziona per ogni albero di altezza \(h < k\) e di volerlo quindi dimostrare per un albero di altezza \(k\). Il passo induttivo consiste nel rendersi conto che gli alberi destro e sinistro rispetteranno la condizione dell'ipotesi induttiva e quindi devi solo dimostrare che stai sommando correttamente i valori restituiti dalle chiamate ricorsive che sai restituire i valori corretti.

[iggy]

Invece di lavorare sul numero di chiamate ricorsive credo sia più utile lavorare in termini di altezza dell'albero. Il caso base è chiaramente l'albero vuoto come hai già determinato. A questo punto supponi nell'ipotesi induttiva che l'algoritmo funziona per ogni albero di altezza \(h < k\) e di volerlo quindi dimostrare per un albero di altezza \(k\). Il passo induttivo consiste nel rendersi conto che gli alberi destro e sinistro rispetteranno la condizione dell'ipotesi induttiva e quindi devi solo dimostrare che stai sommando correttamente i valori restituiti dalle chiamate ricorsive che sai restituire i valori corretti.

Grazie che non ti sei ancora stufato di rispondermi .

Ma il sotto-albero destro e sinistro rispettano l'ipotesi induttiva perchè l'albero intero è alto k e se non contiamo la radice i sotto-alberi sono alti h<k come per l'ipotesi?

E per dimostrare che sommo correttamente io scriverei qualcosa come "se il nodo <max e >min allora è da contare ed si entrerà nell'ultimo else che somma 1 (il nodo stesso) + i sotto-alberi figli del nodo stesso che verranno analizzati come il nodo appena citato" ma mi sembra una spiegazione troppo alla buona.

[apatriarca]

Se l'albero ha altezza \(k\) i due sottoalberi della radice avranno ovviamente altezza inferiore a \(k\). Almeno uno dei due avrà in effetti altezza \(k-1\). Se il valore alla radice sta tra il minimo e il massimo allora il numero di valori nell'intervallo nell'altro sarà 1 più il numero di valori nei due sottoalberi (che per l'ipotesi induttiva possono essere calcolati dalla tua funzione). In caso contrario puoi usare la proprietà degli alberi di ricerca per escludere uno dei due sottoalberi e quindi cercare valori nell'intervallo solo in uno dei due rami.

[iggy]

Ho capito il ragionamento fatto, ma non riesco a rifarlo da solo.
Ho provato in questo esercizio:

Si consideri un BST completo e si proponga lo pseudocodice di un algoritmo che, dato in input un nodo x, restituisca il nodo y la cui chiave è minima tra quelle che soddisfano la regola key[y] appartiene (key[x], key[x] + 8], se tale y esitste, mentre restituisce NIL altrimenti.

In sostanza, dato un nodo bisogna restituire il nodo più piccolo fra quelli maggiori di tale nodo.

La mia soluzione è questa, che mi sa che non è fra le più eleganti ma funziona:

Codice:

//flag è inizializzata a 0 nella chiamata e min a +inf
int piuOtto(TREE node, TREE x, integer min, integer flag){
    if(node != NULL){
        if(node.key > x.key + 8)
            piuOtto(node.left, x, min, flag);
        else if(node.key <= x.key)
            piuOtto(node.right, x, min, flag);
        else if(node.key > x.key && node.key < x.key+8){
            if(node.key < min)
                min = node.key;
                flag = 1;
                piuOtto(node.left, x, min, flag);
        }
    }
    else if(flag != 1)
        return NULL;
    else
        return min;
}


Spero si capisca qual è l'idea di fondo, cioè scartare gli elementi più piccoli e più grandi dell'intervallo e confrontare quale è il più piccolo fra quelli rimasti.
La complessità e teta(logn).

La correttezza dovrebbe essere un po' il ragionamento di prima:
Base: albero vuoto -> return NULL
Ipotesi: l'algoritmo funziona per ogni albero h - 1 (perchè l'albero è completo)
tesi: se sono in un albero alto k allora sono in una foglia e l'albero è stato già analizzato fino al penultimo livello. Se sono su una foglia vuol dire che != NULL quindi controllo se la chiave è compresa nell'intervallo cercato. Se non lo è, richiamo la funzione su un nodo NULL; altrimenti confronto la chiave con il minimo trovato fino al penultimo livello. Sè è minore sarà il nuovo nodo da salvare. Una volta che tutte le chiamate ricorsive sono terminate, se flag=1 allora ho trovato almeno un nodo da salvare quindi ritorno quest'ultimo, se flag!=1 non ci sono nodi che rispettano la regola e ritorno NULL.

È vagamente corretta come dimostrazione? Grazie.

[apatriarca]

La tua soluzione mi sembra più complicata del necessario. Siccome gli elementi di un BST sono ordinati, devi semplicemente trovare il nodo con la chiave più piccola tra quelli maggiori della radice e vedere se la differenza è minore di 8. Gli elementi più grandi della radice si trovano nel ramo destro e l'elemento più piccolo si ottiene "andando sempre a sinistra". Qualcosa come segue insomma:

Codice:

int smallest(TREE x) {
    if (x == NULL) { return NULL; }
    else if (x.left == NULL) { return x.key; }
    else { return smallest(x.left); }
}

int piuOtto(TREE x) {
    int s = smallest(x.right);
    if (s == NULL || s > (x.key + 8)) { return NULL; }
    else { return s; }
}


Ovviamente a questo punto la dimostrazione avverrebbe in due parti. La prima è che questo ragionamento ha senso. Non c'è alcun bisogno dell'induzione. Nel secondo passaggio devi invece dimostrare che smallest restituisce effettivamente il valore più piccolo dell'albero e puoi quindi ragionare per induzione come prima.

[iggy]

Se però richiamo la tua soluzione sul nodo di chiave 7 dell'albero:

Codice:

       22
  14       24
7   15   23    30

se non sbaglio mi ritorna NULL anzichè 14, perchè cerca l'elemento solo nei sotto-alberi.
Comunque in questo momento mi interesserebbe la correttezza di un algoritmo piuttosto che la sua efficienza.

Data una max-heap A, di dimensione n, si vogliono ordinare i suoi elementi tramite la seguente procedura:
-si copino gli elementi di A in un vettore ausiliario B,
-si costruisca la min-heap B,
-si iteri bn=2c volte sulle due heap estraendo il massimo da A e il minimo da B (attraverso le procedure Heap-Extract-Max
e Heap-Extract-Min, rispettivamente) e riportandoli in un terzo vettore C.

La procedura dovrebbe essere una cosa del genere:

Codice:

proc(a, n){
    b = newArray(n)
    for(i = 0 to n)
        b[i] = a[i]
    Build_Min_Heap(b)
    c = newArray(n)
    for(i = 0 to n/2){
        c[i] = Extract_Min_Heap(a)
        c[n-i-1] = Extract_Max_Heap(b)
    }
    return c

}

Tralasciando i controlli se la lunghezza è pari o dispari, la complessità è data dall'ultimo ciclo quindi teta(nlogn)
Per la correttezza: in base alle regole di max-min heap so che alla radice ci sarà sempre l'elemento più grande e più piccolo quindi posso estrarre tali elementi e posizionarli nel vettore alle estremità. Basta questo?
Però mi ricordo che quando ci sono cicli c'è anche di mezzo l'inferenza.

[apatriarca]

Ciao, scusa.. Avevo letto velocemente e pensavo che il nodo passato fosse la radice. In caso contrario devi cercare il nodo dell'albero. Se ha un nodo destro allora segui la procedura che ho scritto sopra. Se non ha un ramo destro allora devi salire nell'albero in cerca del genitore che lo segue (se non sbaglio, non ci ho pensato troppo). Di fatto devi trovare il nodo successivo nella visita in ordine dell'albero.