Lezione 3  -   Esercizio 1

Il testo dell'esercizio è stato tratto dal libro consigliato Ausiello et al. "Teoria e Progetto di Algoritmi Fondamentali"

2.2. Generazione di tutti i sottoinsiemi di un insieme

Ci occuperemo ora di un algoritmo capace di generare una ed una sola volta tutti i sottoinsiemi di un insieme finito   S = {al, al, ..., an}.

Questo algoritmo può essere utilizzato per ottenere algoritmi di ricerca esausti va per quei problemi la cui soluzione è un sotto- insieme di un insieme dato.

L'algoritmo è basato sulla possibilità di definire una corrispondenza biunivoca tra i sottoinsiemi di un insieme di cardinalità n e le stringhe binarie di lunghezza n. Dato un sottoinsieme X di S, ad esso è possibile associare la stringa bn bn-l, ..., bl dove bi è 1 se e solo se ai EX.

Poiché ogni stringa binaria di lunghezza n rappresenta un numero binario compreso tra O e 2n -1 abbiamo definito in tal modo un ordinamento sui sottoinsiemi di S.

L'algoritmo A.3 sfrutta questa corrispondenza e, partendo dal- l'insieme vuoto, cui corrisponde la stringa 000...0, genera tutti i sottoinsiemi fino a quando non è stato generato l'insieme S, cui corrisponde la stringa 111.. .1.

Al generico passo le operazioni che permettono di modificare il sottoinsieme SOL ottenuto nell'iterazione precedente per ottenere un insieme non ancora generato, sono in tutto e per tutto analoghe alle operazioni che permettono di contare in base 2. Più precisamente si ricerca il più piccolo indice i per cui aÎSOL e si aggiunge a SOL ai. Se un tale elemento non esiste, allora SOLº S e, quindi, tutti i sottoinsiemi sono stati generati. Successivamente 1 si eliminano da SOL tutti quegli elementi a_j tali che j < i.

L'algoritmo A.3 utilizza un insieme cui è stato aggiunto un nuovo elemento an + 1 per poter verificare la condizione di termi- nazione: l'inserimento di an + 1 in SOL indica che tutti i sotto- insiemi di al, al, ..., an sono stati generati e l'algoritmo termina. Si può verificare che l'algoritmo A.3 genera e stampa tutti i sottoinsiemi di un insieme di n elementi in tempo O(n.2ⁿ).  Un problema nel quale la ricerca della soluzione può essere effettuata esaminando tutti i sottoinsiemi di un insieme dato è il problema PARTIZIONAMENTO. Dato un insieme Y={y1, y2, ..., yn} di n interi positivi la cui somma è 2 M, vogliamo sapere se esiste un sottoinsieme di Y la cui somma risulta esattamente pari a M.