Esercizio - domande di prima parte su problemi computazionali, ricorrenze e conteggi (simulazioni d'esame)

Teoria usata: 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à →, 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 →, SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →.

Domanda 1: gli insiemi $I$ ed $S$

Un problema è una relazione $\Pi \subseteq I \times S$ tra istanze e soluzioni (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à →).

• Istanza: un numero complesso non nullo $z$: $I = \mathbb{C} - \{0\}$. Questo esclude la terza alternativa (che ha coppie in ingresso) e la prima ($\mathbb{C}^+$ non descrive i complessi non nulli).
• Soluzione: ogni $z \ne 0$ ha due radici quadrate distinte, $w$ e $-w$, entrambe non nulle. Se la soluzione è la coppia delle due radici, $S = (\mathbb{C} - \{0\}) \times (\mathbb{C} - \{0\}) = (\mathbb{C} - \{0\})^2$. La seconda alternativa ($S = \mathbb{C} - \{0\}$) conterrebbe una sola radice e descriverebbe il problema "trova una radice".

Risposta: quarta alternativa, $I = \mathbb{C} - \{0\}$, $S = (\mathbb{C} - \{0\})^2$.

Nota. Vale anche $\Pi \subseteq I \times S'$ con $S' = \{(w, -w) : w \in \mathbb{C},\ w \ne 0\} \subset S$. La relazione non è univoca: per ogni $z$ ci sono due coppie ordinate, $(w, -w)$ e $(-w, w)$, entrambe soluzioni. Variante: per le radici cubiche sarebbe $S = (\mathbb{C} - \{0\})^3$ (tre radici distinte e non nulle).

Domanda 2: $T(12)$

Con l'albero. Si osserva che la ricorrenza ha lo stesso albero di MAX (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 →): ogni istanza di taglia $n > 1$ si divide in due sottoistanze di taglie $\lfloor n/2\rfloor$ e $\lceil n/2\rceil$, e le foglie sono $n$ (una per ogni elemento: i due sottoinsiemi sono disgiunti e si arriva a taglia $1$). Il lavoro è nullo ai nodi interni (nella ricorrenza non c'è nessun termine oltre alle due $T$) e $12$ a ogni foglia ($T(1) = 12$). Quindi $$T(n) = 12\cdot n, \qquad T(12) = 144.$$

          n                      lavoro 0
        /   \
  floor(n/2) ceil(n/2)           lavoro 0
     ...     ...
   (1)(1)(1) ... (1)             n foglie, lavoro 12 ciascuna

Per induzione (conferma di $T(n) = 12n$ per ogni $n \ge 1$): base $T(1) = 12$; passo, per $n > 1$: $T(n) = 12\lfloor n/2\rfloor + 12\lceil n/2\rceil = 12(\lfloor n/2\rfloor + \lceil n/2\rceil) = 12n$, essendo $\lfloor n/2\rfloor + \lceil n/2\rceil = n$.

Alternativa a mano, senza la formula: $T(12) = T(6) + T(6) = 2T(6) = 2\bigl(2T(3)\bigr) = 4T(3)$, e $T(3) = T(1) + T(2) = T(1) + \bigl(T(1) + T(1)\bigr) = 3T(1)$, quindi $T(12) = 12\,T(1) = 12\cdot 12 = 144$.

Risposta: $144$.

Domanda 3: conteggio con due cicli

Il numero di esecuzioni del corpo è il numero di coppie $(i, j)$ del ciclo: $$T(n) = \sum_{i=2}^{n-1}\ \sum_{j=n-i+2}^{n} 1.$$ Ciclo interno. Per $i$ fissato, $j$ va da $n - i + 2$ a $n$: sono $n - (n - i + 2) + 1 = i - 1$ valori (la somma di $1$ su un intervallo di indici vale ultimo estremo $-$ primo estremo $+ 1$; è $\ge 1$ perché $i \ge 2$). Ciclo esterno. $$T(n) = \sum_{i=2}^{n-1}(i - 1) = \sum_{i'=1}^{n-2} i' = \frac{(n-2)(n-1)}{2},$$ con il cambio di indice $i' = i - 1$ (per $i = 2, \dots, n-1$, $i'$ va da $1$ a $n - 2$) e la somma di Gauss $\sum_{i'=1}^{m} i' = \frac{m(m+1)}{2}$ con $m = n - 2$ (SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →). Per $n = 18$: $$T(18) = \frac{16\cdot 17}{2} = 8\cdot 17 = 136.$$

Risposta: $136$. (La formula vale per $n \ge 2$: per $n = 2$ il ciclo esterno è vuoto e $T(2) = \frac{0\cdot1}{2} = 0$. Verificata con un conteggio diretto per $n = 2, \dots, 59$.)

def T(n):
    return sum(1 for i in range(2, n) for j in range(n - i + 2, n + 1))

assert T(18) == 136 and all(T(n) == (n - 2) * (n - 1) // 2 for n in range(2, 60))

Varianti per allenarsi

Tutte controllate con un programma.

1. $T(1) = 7$, stessa ricorrenza della domanda 2: $T(n) = 7n$, quindi $T(25) = 175$.
2. $T(1) = 0$, $T(n) = T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + 3$: stesso albero di MAX con lavoro $3$ per ognuno degli $n - 1$ nodi interni, $T(n) = 3(n - 1)$, quindi $T(10) = 27$.
3. for i = 1 to n: for j = i to n (corpo eseguito $n - i + 1$ volte per ogni $i$): $\sum_{i=1}^{n}(n - i + 1) = \frac{n(n+1)}{2}$, quindi $55$ per $n = 10$.
4. for i = 1 to n: for j = 1 to i: for k = 1 to j: $\sum_{i=1}^{n}\frac{i(i+1)}{2} = \frac{n(n+1)(n+2)}{6}$, quindi $56$ per $n = 6$.