Esercizio - due elementi più piccoli di una stringa con divide and conquer (simulazione d'esame 2023-24, problema 1)

Teoria usata: Divide and conquer - proprietà di sottostruttura e albero delle chiamateUn algoritmo divide and conquer nasce da una proprietà di sottostruttura (funzioni Divide e Conquer, base n0) con sottoistanze di taglia strettamente minore; l'albero delle chiamate ne descrive l'esecuzione, e il D&C non ha memoria (ripete le sottoistanze uguali). Esempio completo: MAX di un array, con correttezza per induzione, ricorrenza e conteggio esatto n-1 tramite il teorema sugli alberi binari pieni.Divide and conquer - proprietà di sottostruttura e albero delle chiamate →, Albero della ricorrenza e formula generale per le ricorrenzeL'albero della ricorrenza ha la forma dell'albero delle chiamate dell'istanza peggiore e T(n) è la somma dei lavori dei nodi. Per la famiglia T(n) = s(n)T(f(n)) + w(n) con base T0 per n <= n0, contando i nodi per livello con le iterate di f e il livello f*(n,n0) si ottiene la formula chiusa T(n) = somma_l [prodotto_j s(f^(j)(n))] w(f^(l)(n)) + [prodotto s] T0, verificata per induzione e applicata a esempi (merge sort, Hanoi, ricorrenze con radice).Albero della ricorrenza e formula generale per le ricorrenze →, Problemi computazionali - istanze, soluzioni, correttezza e complessitàUn problema computazionale è una relazione totale (non necessariamente univoca) tra istanze e soluzioni; un algoritmo è una funzione dalle istanze alle soluzioni e risolve il problema se la sua uscita è sempre in relazione con l'ingresso. Correttezza = coerenza con la specifica; complessità = costo in funzione della taglia, per default al caso peggiore, con le istruzioni a costo unitario scelte in modo significativo.Problemi computazionali - istanze, soluzioni, correttezza e complessità →.

Il testo avverte di dedicare tempo a capire la traccia: si chiede un algoritmo ricorsivo che restituisce i due valori più piccoli (certamente distinti, perché gli elementi lo sono), con meno di $2n - 3$ confronti. L'algoritmo banale, con due scansioni, fa $(n-1) + (n-2)$ confronti:

for i <- 2 to n do if A[i] < A[1] then SWAP(A[1], A[i])      // n - 1 confronti: A[1] = minimo
for i <- 3 to n do if A[i] < A[2] then SWAP(A[2], A[i])      // n - 2 confronti: A[2] = secondo minimo

Punto 1: proprietà di sottostruttura e pseudocodice

Problema. $I$ = stringhe di $n \ge 2$ interi positivi distinti, $S$ = coppie $(m_1, m_2)$ con $m_1 < m_2$; $\Pi$ associa ad $A$ la coppia dei due più piccoli. Taglia: $n$. Costo unitario: il confronto tra elementi di $A$.

Caso base $n = 2$ (nella traccia $n \ge 2$): $m_1 = \min\{a_1, a_2\}$, $m_2 = \max\{a_1, a_2\}$; basta un confronto.

Divide per $n > 2$: $A^1 = A[1..n/2]$ e $A^2 = A[n/2+1..n]$, due sottoistanze di taglia $n/2$ (ancora potenza di due, $\ge 2$). Siano $(x_1, y_1)$ la coppia restituita per $A^1$ e $(x_2, y_2)$ quella per $A^2$ (con $x_j < y_j$); per ipotesi induttiva sono i due più piccoli di $A^1$ e $A^2$.

Osservazione chiave. I due elementi più piccoli di $A$ stanno certamente in $\{x_1, y_1, x_2, y_2\}$. Infatti ogni altro elemento di $A^1$ è maggiore di almeno due elementi (di $x_1$ e di $y_1$), e ogni altro elemento di $A^2$ è maggiore di $x_2$ e di $y_2$: ha almeno due elementi più piccoli, quindi non può essere tra i due minimi.

Conquer. Si distinguono due casi (nessuna uguaglianza, gli elementi sono distinti):

1. se $x_1 < x_2$: $m_1 = x_1$ e $m_2 = \min\{x_2, y_1\}$;
2. se $x_2 < x_1$: $m_1 = x_2$ e $m_2 = \min\{x_1, y_2\}$.

Prova del caso 1. Se $x_1 < x_2$ allora $x_1 < x_2 < y_2$ e $x_1 < y_1$: $x_1$ è minore degli altri tre candidati, quindi $m_1 = x_1$. Il secondo minimo è il minore dei tre candidati rimasti $\{y_1, x_2, y_2\}$; ma $y_2 > x_2$ (per $A^2$ ordinata), quindi $y_2$ non può essere il minore e $m_2 = \min\{x_2, y_1\}$.

Prova del caso 2. Simmetrica scambiando i ruoli di $A^1$ e $A^2$: $x_2 < x_1 < y_1$ e $x_2 < y_2$ danno $m_1 = x_2$; i candidati per il secondo sono $\{y_2, x_1, y_1\}$ e $y_1 > x_1$ lo esclude, quindi $m_2 = \min\{x_1, y_2\}$.

Correttezza della proprietà (induzione sulla taglia): la base è corretta; per $n > 2$ le sottoistanze hanno taglia $n/2 < n$ e per ipotesi le loro soluzioni sono corrette; le due prove sopra dicono che il Conquer produce i due più piccoli di $A$. $\square$

Pseudocodice.

TWO_SMALLEST(A)                              {n = 2^k, k >= 1, elementi distinti}
n <- |A|
[B]: if n = 2 then
         if A[1] < A[2] then return (A[1], A[2]) else return (A[2], A[1])
[D]: A1 <- A[1..n/2];  A2 <- A[n/2 + 1..n]
[R]: (x1, y1) <- TWO_SMALLEST(A1);  (x2, y2) <- TWO_SMALLEST(A2)
[C]: if x1 < x2 then
         if x2 < y1 then return (x1, x2) else return (x1, y1)      // caso 1
     else
         if x1 < y2 then return (x2, x1) else return (x2, y2)      // caso 2

Esecuzione su $A = \langle 3, 1, 7, 5, 4, 9, 6, 8\rangle$.

                         A = <3 1 7 5 4 9 6 8>                      -> (1, 3)
                  /                                \
        <3 1 7 5>   -> (1, 3)                <4 9 6 8>   -> (4, 6)
        /          \                         /          \
   <3 1> -> (1,3)  <7 5> -> (5,7)      <4 9> -> (4,9)  <6 8> -> (6,8)

Al nodo radice: $x_1 = 1 < x_2 = 4$, caso 1; $x_2 = 4 < y_1 = 3$? No, quindi si restituisce $(x_1, y_1) = (1, 3)$ ✓. Al nodo sinistro: $x_1 = 1$ (da $\langle 3,1\rangle$, coppia $(1,3)$) e $x_2 = 5$ (da $\langle 7,5\rangle$, coppia $(5,7)$): $1 < 5$, e $5 < 3$? No, quindi $(1, 3)$ ✓.

Punto 2: la ricorrenza e la sua soluzione

Ogni istanza non di base fa due confronti nel Conquer (uno tra $x_1$ e $x_2$, uno tra il candidato e $y_1$ oppure $y_2$: sempre esattamente due, qualunque sia l'istanza), il Divide non ne fa. Il caso base ne fa uno. Dunque: $$T(n) = \begin{cases} 1 & n = 2 \\ 2\,T(n/2) + 2 & n > 2. \end{cases}$$ Formula generale con $n_0 = 2$, $T_0 = 1$, $s(n) = 2$ (due sottoistanze nel Divide), $f(n) = n/2$ (taglia), $w(n) = 2$ (due confronti nel Conquer). Si ha $f^\ast(n, 2) = \log_2(n/2) - 1 = \log_2 n - 2$: i livelli non di base sono $\ell = 0, \dots, \log_2 n - 2$, e le foglie, al livello $\log_2 n - 1$, sono $2^{\log_2 n - 1} = n/2$. Il livello $\ell$ ha $2^\ell$ nodi, ciascuno con lavoro $2$: $$T(n) = \sum_{\ell=0}^{\log_2 n - 2} 2^\ell\cdot 2 + 2^{\log_2 n - 1}\cdot 1 = 2\left(2^{\log_2 n - 1} - 1\right) + 2^{\log_2 n - 1} = 3\cdot\frac n2 - 2.$$ $$\boxed{T(n) = \frac{3n}{2} - 2.}$$

Verifica per induzione: base $T(2) = 3 - 2 = 1$ ✓; passo, per $n > 2$: $T(n) = 2\left(\frac{3(n/2)}{2} - 2\right) + 2 = \frac{3n}{2} - 4 + 2 = \frac{3n}{2} - 2$ ✓. Valori: $n = 2, 4, 8, 16$ danno $1, 4, 10, 22$ confronti, contro $2n - 3 = 1, 5, 13, 29$ dell'algoritmo banale: molto meglio ($\frac32 n$ contro $2n$). Con un programma, su $100$ stringhe casuali per ogni $n = 2^k \le 1024$ l'uscita coincide con i due minimi e i confronti sono sempre esattamente $\frac{3n}{2} - 2$.

(Per curiosità: con un "torneo a eliminazione", cercando il minimo con $n - 1$ confronti e poi il minimo tra i $\log_2 n$ elementi che hanno perso direttamente contro il vincitore, si arriva a $n + \log_2 n - 2$ confronti, meglio ancora per $n$ grande: $9$ contro $10$ per $n = 8$. Non era richiesto.)

import random

def due_minimi(A, c):
    n = len(A)
    if n == 2:
        c[0] += 1
        return (A[0], A[1]) if A[0] < A[1] else (A[1], A[0])
    x1, y1 = due_minimi(A[:n // 2], c)
    x2, y2 = due_minimi(A[n // 2:], c)
    c[0] += 2                                      # i due confronti del Conquer
    if x1 < x2:
        return (x1, x2) if x2 < y1 else (x1, y1)
    return (x2, x1) if x1 < y2 else (x2, y2)

for k in range(1, 11):
    n = 2**k
    A = random.sample(range(1, 10 * n), n); c = [0]
    assert due_minimi(A, c) == tuple(sorted(A)[:2]) and c[0] == 3 * n // 2 - 2
c = [0]; print(due_minimi([3, 1, 7, 5, 4, 9, 6, 8], c), c[0])    # (1, 3) 10