Le successioni supercrescenti

Una successione di interi positivi $ a_1, a_2, a_3, ... , a_n $ è detta successione supercrescente se ogni termine è maggiore della somma di tutti i termini precedenti. $$ a_2 > a_1 \\ a_3 > a_1 + a_2 \\ a_4 > a_1 + a_2 + a_3 \\ \vdots \\ a_n > a_1+ a_2 + ... + a_{n-1} $$

Ad esempio, questa sequenza di numeri è super crescente perché ogni numero dopo il primo è maggiore della somma di tutti i numeri che lo precedono:

$$ 2,3,6,13,27,… $$

Il secondo termine (3) è maggiore del termine che lo precede (2)

$$ 3>2 $$

$$ 2,\color{red}3,6,13,27,… $$

Il terzo termine (6) è maggiore della somma dei termini precedenti (2+3=5)

$$ 6>2+3 $$

$$ \underbrace{2,3}_{5},\color{red}6,13,27,… $$

Il quarto termine (13) è maggiore della somma dei termini che lo precedono (2+3+6=11).

$$ 13>2+3+6 $$

$$ \underbrace{2,3,6}_{11},\color{red}{13},27,… $$

Il quinto termine (27) è maggiore della somma dei termini precedenti (2+3+6+13=24)

$$ 27>2+3+6+13 $$

$$ \underbrace{2,3,6,13}_{24},\color{red}{27},,… $$

A cosa serve una successione supercrescente?

Questo tipo di successione ha diverse applicazioni pratiche in molti ambiti.

In particolar modo, nella teoria della complessità computazionale è utilizzata per trovare una soluzione in tempo polinomiale ad alcuni casi del problema dello zaino.

Nella crittografia è usata per realizzare la codifica di un messaggio tramite il cifrario di Merkle-Hellman (knapsack cryptosystem).

Esempio di risoluzione del problema dello zaino con una successione super crescente

Ho un insieme di numeri $N = \{27, 2, 6, 13, 3\}$ e un limite di capacità per lo zaino pari a 30. L'obiettivo è riempire lo zaino completamente, senza superare questa capacità, utilizzando il maggior numero possibile di oggetti dall'insieme. Ogni oggetto ha un "volume" corrispondente ai numeri dati: 27, 2, 6, 13 e 3. Voglio trovare la combinazione di questi oggetti che occupa esattamente tutto il volume disponibile dello zaino, ovvero 30.

Per prima cosa ordino gli elementi l'insieme in modo crescente ottenendo una successione di termini

$$ a = \{2, 3, 6, 13, 27\} $$

Questa è una successione super crescente. Ciò significa che ogni elemento della sequenza è maggiore della somma di tutti gli elementi precedenti. Quindi, posso risolvere il problema con un algoritmo polinomiale. Definisco una combinazione lineare di pesi $x_i$, che possono assumere il valore 0 oppure 1, tali che:

$$ x_1 \cdot a_1 + x_2 \cdot a_2 + x_3 \cdot a_3 + x_4 \cdot a_4 + x_5 \cdot a_5 = m $$

Dove $a_1 = 2$, $a_2 = 3$, $a_3 = 6$, $a_4 = 13$, $a_5 = 27$, e il totale da raggiungere è $m = 30$.

$$ x_1 \cdot 2 + x_2 \cdot 3 + x_3 \cdot 6 + x_4 \cdot 13 + x_5 \cdot 27 = 30 $$

L'algoritmo parte dall'ultimo elemento e continua a ritorso fino al primo termine o all'esaurimento dello spazio disponibile nello zaino.

Per assegnare l'ultimo peso x_n confronta il volume dell'oggetto con lo spazio disponibile nello zaino e assegna x_n=1 se lo spazio nello zaino è superiore al volume dell'oggetto $ m > a_n $ e quindi può contenerlo, oppure x_n=0 in caso contrario. $$ x_n = \begin{cases} 1 \ \ se \ m \ge a_n \\ \\ 0 \ \ se \ m < a_n \end{cases} $$
Per trovare i pesi precedenti x_i l'algoritmo ragiona con la stessa logica ma confrontando lo spazio "residuo" nello zaino con il volume dell'oggetto da inserire. $$ x_i = \begin{cases} 1 \ \ se \ m - \sum_{k=i+1}^n x_k \cdot a_k \ge a_n \\ \\ 0 \ \ se \ m - \sum_{k=i+1}^n x_k \cdot a_k < a_n \end{cases} $$

Ecco tutti i passaggi necessari per risolvere il problema:

Inizio dall'elemento più grande $ a_5 = 27 $ e assegno $ x_5 = 1 $ se $a_5 \leq m$ altrimenti $x_5 = 0$. In questo caso, $27 < 30$, quindi $x_5 = 1$. Questo vuol dire che l'oggetto può entrare nello zaino. $$ x_1 \cdot 2 + x_2 \cdot 3 + x_3 \cdot 6 + x_4 \cdot 13 + \color{red}{1} \cdot 27 = 30 $$
Aggiorno il valore dello spazio residuo $ m = m - 27 = 3 $ considerando il volume che ho già inserito.
Procedo con l'elemento successivo $ a_4 = 13 $ e confronto il volume dell'oggetto ( $ 13 $ ) con lo spazio residuo nello zaino ( $ m = 3 $ ). Poiché $13 > 3$ assegno il peso $x_4 = 0$ perché lo zaino non può contenere anche questo oggetto. $$ x_1 \cdot 2 + x_2 \cdot 3 + x_3 \cdot 6 + \color{red}{0} \cdot 13 + 1 \cdot 27 = 30 $$
Continuo con l'elemento successivo $ a_3 = 6 $. Il volume dell'oggetto ( $ 6 $ ) è maggiore dello spazio residuo ( $ m = 3 $ ), quindi assegno un peso nullo $ x_3 = 0 $ a questo oggetto perché non c'è spazio sufficiente per inserirlo nello zaino. $$ x_1 \cdot 2 + x_2 \cdot 3 + \color{red}{0} \cdot 6 + 0 \cdot 13 + 1 \cdot 27 = 30 $$
Procedo con l'elemento successivo $ a_2 = 3 $. In questo caso il volume dell'oggetto ( $ 3 $ ) è minore-uguale allo spazio residuo nello zaino ( $ m = 3 $ ). Quindi, assegno il peso $ x_2 = 1 $ perché posso inserirlo nello zaino.
Aggiorno lo spazio residuo nello zaino $ m = 30 - 27 \cdot 1 - 13 \cdot 0 - 6 \cdot 0 - 3 \cdot 1 = 0 $
Lo spazio residuo è nullo $ m = 0 $ e l'algoritmo termina l'elaborazione assegnando tutti i restanti pesi a zero. $$ 0 \cdot 2 + \color{red}{1} \cdot 3 + 0 \cdot 6 + 0 \cdot 13 + \color{red}{1} \cdot 27 = 30 $$

Alla fine, l'algoritmo ha determinato che gli oggetti con volumi $27$ e $3$ possono essere inseriti nello zaino per occupare esattamente lo spazio disponibile di $30$. Quindi, la soluzione ottimale è:

$$ 0 \cdot 2 + 1 \cdot 3 + 0 \cdot 6 + 0 \cdot 13 + 1 \cdot 27 = 30 $$

ovvero

$$ 3 + 27 = 30 $$

Questo algoritmo è specifico per successioni super crescenti e sfrutta la loro proprietà unica per trovare la soluzione in modo efficiente. Non funziona se la successione non è supercrescente.

E così via.