Esercizio - costo alternato minimo e massimo di una sottosequenza (simulazione d'esame 2025-26, es. 2)

Fonte: simulazione d'esame 2025-26 di Algoritmi per l'Ingegneria, Ing. Informatica UniPD, seconda parte, esercizio 2 (17 punti).

Testo

Data una stringa $Z = \langle z_1, z_2, \dots, z_k \rangle$ di interi distinti (positivi, negativi o nulli), il suo costo alternato è definito come

$$\text{alt}(Z) = \sum_{i=1}^{k} (-1)^{i-1} z_i = z_1 - z_2 + z_3 - z_4 \dots$$

(si pone $\text{alt}(\varepsilon) = 0$). Per esempio, se $Z = \langle 1, -3, -1 \rangle$ allora $\text{alt}(Z) = +(1) - (-3) + (-1) = 3$. Data in ingresso una stringa $X$ di $n$ interi, si vogliono determinare il costo alternato minimo e il costo alternato massimo delle sue sottosequenze.

• (a) [7 punti] Si formulino e si dimostrino due proprietà di sottostruttura ottima (per il problema di minimo e per quello di massimo) sullo spazio di sottoproblemi $\mathcal{S} = \{X^i : 1 \le i \le n + 1\}$ formato da tutti i suffissi di $X$ (si ricorda che $X^i = \langle x_i, \dots, x_n \rangle$ e che $X^{n+1}$ denota convenzionalmente il suffisso vuoto). Si derivino le associate ricorrenze sui costi, denotando con $m(i)$ il costo alternato minimo e con $M(i)$ quello massimo per il sottoproblema $X^i$. (Suggerimento: potrebbe essere necessario formulare proprietà "intrecciate".)
• (b) [6 punti] Si scriva lo pseudocodice di un algoritmo iterativo per il calcolo dei costi alternati minimo e massimo di sottosequenze di $X$.
• (c) [4 punti] Si determini il numero esatto $T(n)$ di confronti e operazioni aritmetiche tra interi eseguite dall'algoritmo.

Soluzione

Un'identità sul costo alternato

Aggiungere un elemento davanti a una stringa inverte il segno di tutti gli altri termini:

$$\text{alt}(\langle x, w_1, \dots, w_k \rangle) = x - w_1 + w_2 - \dots = x - (w_1 - w_2 + \dots) = x - \text{alt}(\langle w_1, \dots, w_k \rangle).$$

Questa identità vale anche per $W = \varepsilon$ ($\text{alt}(\langle x \rangle) = x - 0$). È il motivo per cui le due proprietà sono "intrecciate": il minimo per $X^i$ che inizia con $x_i$ si ottiene sottraendo $x_i$ a un massimo, e il massimo a un minimo. Per lavorare con i suffissi si aggiunge sempre davanti, quindi la scelta di includere o no $x_i$ dipende da una sottoistanza più corta, $X^{i+1}$.

(a) Sottostruttura ottima

Sia $Z^*_m(i)$ una sottosequenza di $X^i$ di costo alternato minimo e $Z^*_M(i)$ una di costo massimo (esistono: le sottosequenze di $X^i$ sono finite).

Proprietà.

1. Per $i = n + 1$: $Z^*_m(n+1) = Z^*_M(n+1) = \varepsilon$.
2. Per $1 \le i \le n$: $Z^*_m(i)$ è la più "piccola" (per costo alternato) tra $Z^*_m(i+1)$ e $\langle x_i, Z^*_M(i+1) \rangle$.
3. Per $1 \le i \le n$: $Z^*_M(i)$ è la più "grande" tra $Z^*_M(i+1)$ e $\langle x_i, Z^*_m(i+1) \rangle$.

Dimostrazione. Il punto 1 è banale: l'unica sottosequenza di $\varepsilon$ è $\varepsilon$.

Punto 2. Sia $1 \le i \le n$ e sia $Z = Z^*_m(i) = \langle x_{j_1}, \dots, x_{j_k} \rangle$, con $i \le j_1 < \dots < j_k \le n$. Due casi.

• (2.a) $Z = \varepsilon$ oppure $j_1 > i$. Allora $Z$ è anche una sottosequenza di $X^{i+1}$. Ogni sottosequenza di $X^{i+1}$ è anche sottosequenza di $X^i$, quindi $Z$ ha costo minimo anche tra le sottosequenze di $X^{i+1}$: è una $Z^*_m(i+1)$.
• (2.b) $j_1 = i$. Allora $Z = \langle x_i, W \rangle$ con $W = \langle x_{j_2}, \dots, x_{j_k} \rangle$ sottosequenza di $X^{i+1}$, e per l'identità $\text{alt}(Z) = x_i - \text{alt}(W)$. Per minimizzare $\text{alt}(Z)$ bisogna massimizzare $\text{alt}(W)$: se $W$ non fosse una $Z^*_M(i+1)$, sostituendo $W$ con $Z^*_M(i+1)$ (cut-and-paste) si otterrebbe una sottosequenza di $X^i$ di costo strettamente minore, contraddicendo la minimalità di $Z$. Quindi $W$ è una $Z^*_M(i+1)$.

In entrambi i casi $Z^*_m(i)$ è uno dei due candidati $Z^*_m(i+1)$ e $\langle x_i, Z^*_M(i+1) \rangle$, che sono entrambi sottosequenze ammissibili di $X^i$; poiché $Z^*_m(i)$ è la migliore in assoluto, è la migliore delle due.

Punto 3. Simmetrico (si scambiano minimo e massimo). $\square$

Ricorrenze sui costi. Con $m(i) = \text{alt}(Z^*_m(i))$ e $M(i) = \text{alt}(Z^*_M(i))$, l'identità sul costo dà

$$m(i) = \begin{cases} 0 & i = n + 1 \\ \min\{\, m(i+1),\ x_i - M(i+1) \,\} & 1 \le i \le n \end{cases} \qquad M(i) = \begin{cases} 0 & i = n + 1 \\ \max\{\, M(i+1),\ x_i - m(i+1) \,\} & 1 \le i \le n \end{cases}$$

Si vuole $m(1)$ e $M(1)$ (essendo $X = X^1$). Poiché $\varepsilon$ è una sottosequenza, $m(i) \le 0 \le M(i)$ per ogni $i$. L'ipotesi che gli interi siano distinti non serve alla correttezza.

(b) Algoritmo

$m(i)$ e $M(i)$ dipendono solo da $x_i$ e dai valori $m(i+1)$ e $M(i+1)$: si calcolano per $i$ decrescente da $n + 1$ a $1$ e basta conservare gli ultimi due valori, invece di due vettori.

MIN_MAX_ALT(X)
  n <- |X|
  curr_m <- 0; curr_M <- 0                  { m(n+1) = M(n+1) = 0 }
  for i <- n downto 1 do
    temp <- curr_m                          { salva m(i+1) prima di sovrascriverlo }
    curr_m <- MIN(temp, x_i - curr_M)       { m(i) = min{m(i+1), x_i - M(i+1)} }
    curr_M <- MAX(curr_M, x_i - temp)       { M(i) = max{M(i+1), x_i - m(i+1)} }
  return (curr_m, curr_M)

L'uso di temp è essenziale: il nuovo $M(i)$ vuole il vecchio $m(i+1)$, ma curr_m è già stato aggiornato a $m(i)$. Senza temp si userebbe il valore sbagliato (errore classico). La correttezza segue dalle ricorrenze del punto (a) e dall'ordine di calcolo, che parte dal caso base $i = n + 1$ e usa a ogni passo solo valori già calcolati.

Esempio

$X = \langle 3, -1, 4, -2, 5 \rangle$ ($n = 5$). Si parte da $m(6) = M(6) = 0$ e si scende:

Risultato: $m(1) = -12$, $M(1) = 15$. Sottosequenze: il minimo è $\text{alt}(\langle -1, 4, -2, 5 \rangle) = -1 - 4 + (-2) - 5 = -12$; il massimo è $\text{alt}(\langle 3, -1, 4, -2, 5 \rangle) = 3 + 1 + 4 + 2 + 5 = 15$ (ogni elemento in posizione pari è negativo e la sottrazione lo rende positivo). Entrambi i valori coincidono con quelli ottenuti enumerando tutte le $2^5$ sottosequenze; l'algoritmo è stato verificato in Python con $400$ stringhe casuali di interi distinti, lunghezza fino a $9$.

Se serve anche la sottosequenza, si salva per ogni $i$ un bit: quale dei due candidati realizza il minimo e quale il massimo (informazione addizionale, passo $2'$ dello schema in Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigmala programmazione dinamica (DP) evolve il divide and conquer: invece di risolvere di nuovo le stesse sottoistanze, le salva in una tabella. Fibonacci ricorsivo costa F_n - 1 addizioni (esponenziale), quello con tabella n - 1. Tre condizioni: sottostruttura, sottoistanze ripetute, spazio dei sottoproblemi ristretto. Bottom-up o memoizzazione (ricorsione + tabella globale). Per i problemi di ottimizzazione lo schema è: sottostruttura ottima, ricorrenza sui costi, informazione addizionale, calcolo della tabella, ricostruzione.Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma →).

(c) Numero esatto di operazioni

Il ciclo ha $n$ iterazioni. Ognuna esegue due sottrazioni ($x_i - \text{curr\_M}$ e $x_i - \text{temp}$) e due confronti (uno in MIN, uno in MAX); gli assegnamenti non si contano. Quindi

$$T(n) = \sum_{i=1}^{n} 4 = 4n.$$

Per $n = 5$ sono $20$ operazioni. L'algoritmo è lineare, e lo spazio ausiliario è $O(1)$.