FormularioDati e Algoritmi: definizioni, teoremi e formule delle note, in ordine di capitolo

I. Nozioni fondamentali

Problemi computazionali e algoritmi

Definizione (problema computazionale). Un problema computazionaleDice quali risposte sono corrette per ogni possibile input, senza dire come trovarle. Esempio: per la somma, all'input (3, 4) corrisponde la risposta 7. Il modo di calcolare la risposta è l'algoritmo. $\Pi$ è un insieme di coppie $(i, s)$ con $i \in I$ (istanza, dominio delle istanze) e $s \in S$ (soluzione, dominio delle soluzioni). Si richiede che ogni istanza abbia almeno una soluzione, cioè che per ogni $i \in I$ esista almeno un $s \in S$ con $(i, s) \in \Pi$. Le coppie stanno in $I \times S$, quindi $\Pi \subseteq I \times S$. Il simbolo $I \times S$ è il prodotto cartesianoInsieme di tutte le coppie ordinate (i, s) con i in I e s in S. dei due insiemi (vedi Operazioni tra insiemiUnione, intersezione, differenza, complementare e prodotto cartesiano, con le leggi di De Morgan e il legame con la logica.Operazioni tra insiemi →): $\Pi$ ne è un sottoinsieme, cioè una relazione tra istanze e soluzioni. Se ogni istanza avesse una sola soluzione, $\Pi$ sarebbe il grafico di una funzioneUna funzione associa a ogni elemento del dominio un solo valore: dominio naturale, grafico, immagine, antimmagine e metodo grafico.Funzioni - definizione, dominio e grafico → da $I$ a $S$; qui si ammette il caso più generale, con più soluzioni possibili per la stessa istanza.

Definizione (macchina RAM). Il modello usato è la macchina RAMRandom Access Machine: input, output, dati intermedi e programma stanno in memoria, e ogni accesso a una cella costa un passo. Non c'entra la memoria RAM del PC.: i passi elementari sono assegnamento, operazioni logiche e aritmetiche, indicizzazione di array, restituzione di un valore da un metodo; ciascuno costa $\Theta(1)$ (la notazione è in Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →: significa "un numero di operazioni limitato da una costante che non dipende dalla taglia dell'input"). Il modello rispecchia un vero elaboratore, in cui processore e memoriaModello di von Neumann: CPU, memoria centrale, bus e periferiche; ciclo fetch-decode-execute e gerarchia di memoria.Struttura di un elaboratore → leggono o scrivono una cella con una sola istruzione e la memoria è indirizzabile per posizione; i casi in cui questa semplificazione non regge (accessi lenti fuori dalla cache) sono in Gerarchia di memoria e principio di localitàCaratteristiche delle memorie (posizione, capacità, unità di trasferimento, metodo di accesso, prestazioni, volatilità); compromesso costo-capacità-velocità e gerarchia a livelli; località temporale e spaziale con esempi; hit, miss e tempo medio di accesso con calcolo svolto.Gerarchia di memoria e principio di località →.

Definizione (taglia di un'istanza). La taglia è una funzione che associa a ogni istanza uno o più numeri che ne misurano la grandezza: la lunghezza di un array, il numero di nodi di un albero, il numero di vertici e archi di un grafo ($n$ ed $m$). La complessità si esprime in funzione della taglia (vedi Complessità in tempo e caso pessimoPerché lo studio sperimentale non basta; complessità al caso pessimo come massimo sul numero di operazioni tra le istanze di una data taglia; stima con limiti superiore e inferiore senza trovare l'istanza peggiore; esempi arrayMax, prefixAverages e InsertionSort; efficienza asintotica e limiti dell'analisi.Complessità in tempo e caso pessimo →).

Proprietà (ricerca binaria: invariante e complessità)

• Invariante: se $x$ è in $A$, allora la sua posizione sta in $[lo, hi]$. Vale all'inizio ($[0, n-1]$ è tutto l'array) e si conserva: se $A[mid] < x$, per l'ordine crescente tutti gli elementi in posizione $\le mid$ valgono al più $A[mid] < x$, quindi $x$ può stare solo a destra di $mid$ e si pone $lo \leftarrow mid+1$; il caso $A[mid] > x$ è simmetrico. Al termine del ciclo ($lo > hi$) l'intervallo è vuoto, quindi per l'invariante $x$ non c'è in $A$ e si restituisce $-1$. Il metodo dell'invariante è spiegato in Dimostrazioni, induzione e invariantiTecniche di dimostrazione (esempio, controesempio, assurdo), induzione con casi base multipli, invarianti di ciclo (inizializzazione, conservazione, uso alla fine), schema generale per provare la correttezza; esempi svolti su arrayMax, sequenza di bit e numeri di Fibonacci.Dimostrazioni, induzione e invarianti →.
• Complessità: l'intervallo dimezza a ogni iterazione, quindi ci sono al più $\lfloor \log_2 n \rfloor + 1$ iterazioni di costo costante: $O(\log n)$.

Complessità in tempo e caso pessimo

Definizione (complessità in tempo al caso pessimo). Sia $t_{A,i}$ il numero di operazioni eseguite da $A$ sull'istanza $i$. La complessità in tempo al caso pessimo è

$$t_A(n) = \max\{\, t_{A,i} : i \in I,\ i \text{ ha taglia } n \,\}.$$

Proprietà (stima con limiti superiore e inferiore). Trovare l'istanza peggiore e contare i passi esatti è difficile e inutile. Si cercano due funzioni semplici:

• limite superiore $t_A(n) \in O(g(n))$: si argomenta che per ogni $n$ abbastanza grande, ogni istanza di taglia $n$ costa al più $c\,g(n)$ operazioni;
• limite inferiore $t_A(n) \in \Omega(g(n))$: si argomenta che per ogni $n$ abbastanza grande esiste un'istanza di taglia $n$ che costa almeno $c\,g(n)$ (a volte è comodo mostrare che tutte le istanze costano tanto).

Se coincidono si ha $\Theta(g(n))$ (stima stretta; le definizioni di $O$, $\Omega$ e $\Theta$ con le costanti $c$ ed $n_0$ sono in Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →). La funzione $g$ deve essere la più vicina possibile al vero andamento (tight) e la più semplice (niente costanti, niente termini di ordine inferiore).

Notazione asintotica

Definizione (notazioni $O$, $\Omega$, $\Theta$ e $o$)

Notazione	Definizione	Si legge
$f \in O(g)$	$\exists\, c > 0,\ n_0 \ge 1$ : $f(n) \le c\,g(n)$ per ogni $n \ge n_0$	$f$ cresce al più come $g$
$f \in \Omega(g)$	$\exists\, c > 0,\ n_0 \ge 1$ : $f(n) \ge c\,g(n)$ per ogni $n \ge n_0$	almeno come $g$
$f \in \Theta(g)$	$f \in O(g)$ e $f \in \Omega(g)$, cioè $c' g \le f \le c'' g$ definitivamente	come $g$
$f \in o(g)$	$\forall\, c > 0\ \exists\, n_0$ : $f(n) \le c\,g(n)$ per $n \ge n_0$; equivale a $\lim f/g = 0$	strettamente meno di $g$

Proprietà (polinomio contro esponenziale, logaritmo contro potenza)

2. Polinomio contro esponenziale: $n^k \in o(a^n)$ se $k > 0$, $a > 1$ (limite $n^k/a^n \to 0$; è la gerarchia degli infiniti di Limiti notevoli e gerarchia degli infinitiI limiti di base per sciogliere le forme indeterminate delle successioni: potenze, polinomi, il numero e, esponenziali, la gerarchia logaritmi < potenze < esponenziali < fattoriale < n^n e la razionalizzazione.Limiti notevoli e gerarchia degli infiniti →, che si può giustificare con il criterio del rapporto: $\dfrac{(n+1)^k/a^{n+1}}{n^k/a^n} = \dfrac{(1+1/n)^k}{a} \to \dfrac1a < 1$, quindi il rapporto tende a $0$, vedi Criteri del rapporto e della radice per successioniPer a_n > 0: se a_(n+1)/a_n oppure la radice n-esima di a_n tende a un limite minore di 1 la successione tende a 0, se maggiore di 1 tende a +∞; con limite 1 non si conclude.Criteri del rapporto e della radice per successioni →).
3. Logaritmo contro potenza: $(\log_b n)^k \in o(n^h)$ per $b > 1$, $k, h > 0$. Si pone $m = \log_b n$: $n^h = (b^h)^m$ con $a = b^h > 1$ e $m^k \in o(a^m)$ per il punto 2.

Proprietà (legami tra le notazioni)

5. Legami tra notazioni:
   • $f \in o(g) \Rightarrow f \in O(g)$ (si prende $c = 1$);
   • $f \in O(g) \iff g \in \Omega(f)$ (si divide per $c$);
   • $f \in O(g)$ e $g \in O(f) \Rightarrow f \in \Theta(g)$;
   • $f \in O(g) \Rightarrow f + g \in \Theta(g)$ (perché $g \le f + g \le (c+1)g$);
   • non valgono: $O \Rightarrow o$ ($f = g = n$) né $O \Rightarrow \Theta$ ($f = n$, $g = n^2$).

Formula (sommatorie notevoli)

$$\sum_{i=0}^{n} i = \frac{n(n+1)}{2}, \qquad \sum_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \in \Theta(n^3), \qquad \sum_{i=0}^{n} a^i = \frac{a^{n+1} - 1}{a - 1}\ (a \ne 1).$$

Dimostrazioni, induzione e invarianti

Teorema (principio di induzione). Per provare che $Q(n)$ vale per ogni $n \ge n_0$:

1. si sceglie $k \ge 0$ (di solito $k = 0$);
2. base: si dimostra $Q(n_0), Q(n_0+1), \dots, Q(n_0+k)$;
3. passo: si fissa $n \ge n_0 + k$ arbitrario e, assumendo $Q(m)$ vera per ogni $m$ con $n_0 \le m \le n$ (ipotesi induttiva), si dimostra $Q(n+1)$.

Definizione (invariante di ciclo). Un invarianteProprietà sulle variabili del ciclo che descrive lo stato a ogni iterazione. è una proprietà delle variabili usate nel ciclo che:

1. vale all'inizio del ciclo, come conseguenza dello stato iniziale (inizializzazione);
2. vale alla fine di ogni iterazione, assumendo che valesse all'inizio di quella iterazione (conservazione);
3. alla fine dell'ultima iterazione, insieme alla condizione di uscita, implica la correttezza del ciclo (uso).

Algoritmi ricorsivi

Definizione (algoritmo ricorsivo). Un algoritmo ricorsivo invoca se stesso su istanze sempre più piccole. La soluzione di un'istanza di taglia $n$ si ottiene:

• direttamente per i casi base $n = n_0, \dots, n_0 + k$;
• altrimenti usando le soluzioni di una o più istanze di taglia $< n$.

Formula (potenza in tempo logaritmico). $x^n = 1$ se $n = 0$; $x \cdot (x^{(n-1)/2})^2$ se $n$ dispari; $(x^{n/2})^2$ se $n$ pari e positivo.

Formula (numero di chiamate di fib). Il numero di chiamate $C(n)$ soddisfa $C(0) = C(1) = 1$ e $C(n) = 1 + C(n-1) + C(n-2)$, cioè $C(n) = 2F(n+1) - 1$: $1, 1, 3, 5, 9, 15, 25, 41, \dots$ ($n = 0, 1, 2, 3, 4, 5, 6, 7$; per $\mathrm{fib}(5)$ sono $15$ chiamate, verificato eseguendo il codice). Cresce come $\Phi^n$: esponenziale. Lo spreco è nei sottoproblemi ripetuti ($\mathrm{fib}(3)$ è ricalcolato più volte).

{"tipo":"funzione","titolo":"Chiamate di fib(n): senza memoizzazione crescono come 2Φ^(n+1)/√5 − 1 (C(5) = 15, C(10) = 177), con memoizzazione sono 2n − 1 (9 per n = 5, 19 per n = 10)","curve":[{"espressione":"2*((1+sqrt(5))/2)^(x+1)/sqrt(5)-1","etichetta":"senza memoizzazione: C(n)"},{"espressione":"2*x-1","etichetta":"con memoizzazione: 2n−1"}],"x":[1,12],"y":[0,500],"punti":[{"x":5,"y":15,"etichetta":"15"},{"x":10,"y":177,"etichetta":"177"}],"assi":{"x":"n","y":"chiamate"}}
``` Con la **memoizzazione** (si salva ogni risultato in una tabella e lo si riusa) per $\mathrm{fib}(5)$ le chiamate scendono a $9$ e in generale a $\Theta(n)$ (ciascun $\mathrm{fib}(k)$ è calcolato una volta sola). Per $\mathrm{fib}(5)$: la discesa $\mathrm{fib}(5),\mathrm{fib}(4),\mathrm{fib}(3),\mathrm{fib}(2),\mathrm{fib}(1),\mathrm{fib}(0)$ fa $6$ chiamate e riempie la tabella; poi $\mathrm{fib}(3)$ chiama $\mathrm{fib}(1)$ (caso base, una chiamata), $\mathrm{fib}(4)$ chiama $\mathrm{fib}(2)$ (già in tabella) e $\mathrm{fib}(5)$ chiama $\mathrm{fib}(3)$ (già in tabella): $6+3=9$. In generale $n+1$ chiamate di discesa più $n-2$ chiamate che trovano già il risultato, circa $2n$. La memoizzazione usa $\Theta(n)$ di memoria per la tabella: è lo scambio tempo contro spazio.

*Esempio.* $C(5)=2F(6)-1=2\cdot8-1=15$ chiamate per `fib(5)`.

## Correttezza per induzione

Sia $n$ la taglia. Si dimostra la correttezza per i casi base $n \in [n_0, n_0 + k]$; poi, assumendo che l'algoritmo risolva correttamente tutte le istanze di taglia $m \in [n_0, n]$, si dimostra che risolve quelle di taglia $n + 1$.

**LinearSum.** Base $n = 1$: restituisce $A[0]$ ✓. Passo: per ipotesi `LinearSum(A, n)` $= \sum_{i=0}^{n-1} A[i]$, quindi `LinearSum(A, n+1)` $= \sum_{i=0}^{n-1} A[i] + A[n] = \sum_{i=0}^{n} A[i]$ ✓.

**Power.** Base $n = 0$: $x^0 = 1$ ✓. Passo: si assume che `Power` sia corretta per **tutti** gli esponenti da $0$ a $n$ (ipotesi forte: serve perché la chiamata ricorsiva è su circa la metà dell'esponente, non su $n$). Se $n+1$ è pari, la chiamata è su $(n+1)/2 \le n$ (vero per $n\ge1$), quindi per ipotesi $y = x^{(n+1)/2}$ e $y\cdot y = x^{n+1}$. Se $n+1$ è dispari, la chiamata è su $n/2 \le n$, quindi $y = x^{n/2}$ e $x \cdot y \cdot y = x \cdot x^{n} = x^{n+1}$ ✓ (si usa $x^a x^b = x^{a+b}$, vedi <a class="wiki glossa" href="/analisi-1/appunti/funzioni-potenza/" aria-describedby="sp-17">Funzioni potenza<span class="spiega" role="tooltip"><span class="spiega-testo" id="sp-17">Le potenze x^alfa al variare dell&#39;esponente: domini, grafici, radici n-esime e proprietà delle potenze con base positiva.<span class="spiega-vai">Funzioni potenza →</span></span><span class="graffa" aria-hidden="true"><i class="g-l"></i><i class="g-linea"></i><i class="g-punta"></i><i class="g-linea"></i><i class="g-r"></i></span></span><!--/spiega--></a>).

## Errori comuni

- Dimenticare un caso base, o una chiamata che non riduce la taglia (non termina): in `ReverseArray` serve $i < j$.
- Contare il costo di un nodo **includendo** le chiamate figlie (le conta due volte).
- Ricalcolare più volte la stessa sottoistanza (`Power` con due chiamate, `fib` senza memoizzazione).
- Dimenticare che la ricorsione consuma stack: profondità $d$ ⇒ spazio $\Theta(d)$.

II. Il linguaggio C

Puntatori, struct e memoria dinamica in C

Definizione (puntatore). Un puntatore è una variabile che contiene un indirizzo di memoria. &x è l'indirizzo di x, *p è il valore puntato da p (dereferenziazione), NULL è il puntatore che non punta a nulla.

Proprietà (passaggio dei parametri per valore). C passa i parametri per valore: la funzione riceve una copia. Per modificare una variabile del chiamante si passa il suo indirizzo.

Proprietà (array e aritmetica dei puntatori). Un array è un blocco contiguo; il suo nome si comporta come puntatore al primo elemento, quindi v[i] equivale a *(v + i) (la somma avanza di i elementi, non di i byte). Un array passato a una funzione arriva come puntatore: la lunghezza non si conserva e va passata a parte (int n). Nessun controllo sui limiti: v[n] è un errore silenzioso.

Definizione (stringa in C). Una stringa è un array di char terminato da '\0': char nome[64] contiene al più 63 caratteri più il terminatore. Si copia con strcpy, si confronta con strcmp, mai con = o ==.

Definizione (operatori . e ->). . si usa su una struct, -> su un puntatore a struct. Una struct che contiene un puntatore a se stessa permette le strutture collegate:

typedef struct nodo {
    int val;
    struct nodo *next;   /* dentro la definizione serve il nome "struct nodo" */
} Nodo;

Definizione (memoria dinamica con malloc e free). Le variabili locali vivono nello stack e spariscono quando la funzione termina; malloc alloca nello heap un blocco che dura finché non lo si libera con free.

Proprietà (puntatore a puntatore). Un puntatore passato per valore è una copia: assegnarlo dentro la funzione non cambia quello del chiamante. Per modificarlo (tipicamente la testa di una lista o la radice di un albero) si passa il suo indirizzo, cioè un Nodo **.

Liste concatenate in C

Definizione (lista concatenata). Una lista concatenata è una sequenza di nodi allocati nello heap, ciascuno con un valore e un puntatore al successivo; la lista è identificata dal puntatore alla testa (NULL = lista vuota). Premessa: Puntatori, struct e memoria dinamica in CPuntatori e passaggio per riferimento in C, array e aritmetica dei puntatori, stringhe, struct e typedef con l'operatore ->, malloc e free, puntatore a puntatore per modificare una testa; compilazione con Makefile; errori tipici (puntatori pendenti, perdite di memoria, off-by-one).Puntatori, struct e memoria dinamica in C →. È l'implementazione concreta degli ADT di Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code →. La stessa struttura è presentata, in versione più elementare, in Liste concatenateLista concatenata semplice: nodi allocati dinamicamente collegati da puntatori; inserimento e rimozione in testa, scorrimento, ricerca, inserimento ordinato, deallocazione; confronto dei costi con l'array; versione in Python.Liste concatenate → e Pila e codaPila (LIFO) e coda (FIFO) come ADT: operazioni e costi; realizzazione in Python con list e collections.deque; realizzazione in C con array e indici, coda circolare; applicazioni (parentesi bilanciate, stack delle chiamate, visite).Pila e coda → (Fondamenti di Informatica); i puntatori usati qui sono quelli di Puntatori in CUn puntatore contiene un indirizzo di memoria; operatori & e *, NULL, puntatori come parametri per modificare variabili del chiamante, aritmetica dei puntatori, legame tra array e puntatori, const, puntatori a puntatori.Puntatori in C → e i blocchi di malloc vivono nello heap (Gestione della memoria in CSegmenti di memoria di un processo (codice, dati statici, stack, heap); durata delle variabili; allocazione dinamica con malloc, calloc, realloc e free; errori classici: memory leak, dangling pointer, double free, buffer overflow; strumenti di controllo.Gestione della memoria in C →).

Proprietà (testa passata per riferimento). Ogni funzione che può cambiare la testa riceve un Nodo **l (puntatore alla variabile testa del chiamante).

Definizione (inversione in loco). Inversione in loco, $O(n)$ e senza nodi nuovi: si ritorcono i puntatori scorrendo la lista.

Definizione (coda con puntatori a testa e coda). Per rendere $O(1)$ anche l'inserimento in fondo si tengono due puntatori, in una struct:

typedef struct { Nodo *testa; Nodo *coda; } Coda;     /* estrae da testa, inserisce in coda */

void enqueue(Coda *q, int v) {
    Nodo *n = malloc(sizeof(Nodo));
    n->val = v; n->next = NULL;
    if (q->coda == NULL) q->testa = n;     /* coda vuota */
    else q->coda->next = n;
    q->coda = n;
}

int dequeue(Coda *q) {                     /* precondizione: non vuota */
    Nodo *n = q->testa;
    int v = n->val;
    q->testa = n->next;
    if (q->testa == NULL) q->coda = NULL;  /* si e' svuotata */
    free(n);
    return v;
}

int isEmpty(const Coda *q) { return q->testa == NULL; }

Proprietà (costi delle operazioni sulle liste concatenate)

Operazione	Lista semplice	Con puntatore alla coda
addHead, pop	$\Theta(1)$	$\Theta(1)$
addTail	$\Theta(n)$	$\Theta(1)$
ricerca di un valore	$\Theta(n)$	$\Theta(n)$
accesso al nodo $i$-esimo	$\Theta(i)$	$\Theta(i)$

III. ADT elementari

Liste, pile e code

Definizione (lista index-based). L'elemento si identifica con l'indice $i \ge 0$ = numero di elementi che lo precedono.

Metodo	Effetto
size(), isEmpty()	numero di elementi, lista vuota
get(i)	elemento in posizione $i$, senza toglierlo
set(i, e)	sostituisce l'elemento in $i$ con e e restituisce il vecchio
add(i, e)	inserisce e all'indice $i$ spostando a destra i successivi
remove(i)	toglie e restituisce l'elemento in $i$, spostando a sinistra i successivi

Proprietà (array estendibile con raddoppio). Si realizza con un array: get, set, size in $O(1)$; add e remove in $O(n)$ per gli spostamenti. Se l'array è pieno si alloca un array di taglia doppia e si copiano gli elementi: il costo $\Theta(n)$ della copia è ammortizzato dai $n$ inserimenti precedenti, quindi l'inserimento in fondo costa $O(1)$ ammortizzato.

Definizione (lista position-based con doppia lista e sentinelle). Si realizza con una lista doppiamente concatenata: ogni nodo punta a predecessore e successore, e due nodi sentinella (senza elemento) delimitano inizio e fine, così nessun inserimento o rimozione ha casi particolari. Tutti i metodi costano $O(1)$, ma la lista si scandisce solo in sequenza (arrivare al nodo $i$ costa $\Theta(i)$). L'implementazione in C con puntatori è in Liste concatenate in CLista singolarmente concatenata in C con nodo struct e testa passata per riferimento (Nodo **); addHead, addTail ricorsiva e iterativa, pop, inversione in loco, liberazione; coda con puntatori a testa e coda; ricorsione sulle liste; costi.Liste concatenate in C → e i puntatori in Puntatori in CUn puntatore contiene un indirizzo di memoria; operatori & e *, NULL, puntatori come parametri per modificare variabili del chiamante, aritmetica dei puntatori, legame tra array e puntatori, const, puntatori a puntatori.Puntatori in C →.

Definizione (pila LIFO). Inserimenti e rimozioni secondo LIFO (last in, first out): push(e) inserisce in cima, top() legge la cima senza togliere, pop() toglie e restituisce la cima, più size() e isEmpty(). Con un array e un indice t di cima, o con una lista concatenata con inserimento e rimozione in testa, tutti i metodi sono $O(1)$ (con array estendibile, ammortizzato). Esempi: stack delle chiamate di una funzione (i record di attivazione di Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi → e Stack e chiamata di funzioni in ARMChiamata con BL e ritorno con BX LR; convenzione di chiamata AAPCS (argomenti in r0-r3, risultato in r0, registri da preservare r4-r11); stack discendente pieno con PUSH e POP; record di attivazione; funzioni foglia e non foglia; esempio ricorsivo del fattoriale con evoluzione dello stack.Stack e chiamata di funzioni in ARM →), annulla/ripeti, controllo delle parentesi.

Definizione (coda FIFO e buffer circolare). Secondo FIFO (first in, first out): enqueue(e) inserisce in fondo, first() legge il primo, dequeue() toglie e restituisce il primo. Con una lista concatenata con puntatori a testa e coda, tutto in $O(1)$. Con un array si usa un buffer circolare: indice f del primo e size; enqueue scrive in (f + size) mod N, dequeue avanza f = (f + 1) mod N. Usata dalla visita in ampiezza dei grafi (vedi Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →).

Definizione (deque). La deque (double-ended queue) permette inserimento e rimozione sia in testa sia in coda: unisce pila e coda.

IV. Alberi

Alberi

Definizione (albero radicato). Un albero radicato $T$ è una collezione di nodi che, se non vuota, soddisfa:

• esiste un nodo speciale $r$, la radice;
• ogni $v \ne r$ ha un unico padre $u$ ($v$ è figlio di $u$);
• risalendo di padre in padre da ogni nodo si arriva a $r$.

Definizione ricorsiva: $T = \{r\} \cup T_1 \cup \dots \cup T_k$ con $k \ge 0$, dove $T_1, \dots, T_k$ sono alberi non vuoti le cui radici sono figlie di $r$.

Definizione (terminologia degli alberi)

Termine	Significato
antenato di $y$	$x = y$ oppure $x$ antenato del padre di $y$
discendente di $y$	$x$ tale che $y$ è antenato di $x$
nodo interno	nodo con almeno un figlio
nodo esterno o foglia	nodo senza figli
sottoalbero $T_v$	$v$ con tutti i suoi discendenti
albero ordinato	per ogni nodo interno è fissato un ordine lineare tra i figli

Definizione (profondità, livello e altezza)

• Profondità $\text{depth}(v)$ = numero di antenati di $v$ meno 1; ricorsivamente: $\text{depth}(r) = 0$, altrimenti $1 + \text{depth}(\text{padre}(v))$.
• Livello $i$ = insieme dei nodi a profondità $i$.
• Altezza di un nodo: $\text{height}(v) = 0$ se $v$ è foglia, altrimenti $1 + \max_{w \text{ figlio di } v} \text{height}(w)$. Altezza dell'albero: $\text{height}(T) = \text{height}(r)$.

Proposizione (altezza e profondità delle foglie). Se $T$ non è vuoto, $\text{height}(T) = \max\{\text{depth}(v) : v \text{ foglia}\}$.

Visite di alberi

Definizione (visite in preorder e postorder). Chiamata iniziale: preorder(T, T.root()). Preorder: prima il padre, poi i sottoalberi dei figli. Postorder: prima i sottoalberi dei figli, poi il padre.

Formula (complessità di una visita). L'albero della ricorsione (vedi Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi →) ha un nodo per ogni nodo di $T$. Sia $t_u$ il costo della visita di $u$ e $c_u$ il numero di figli. La chiamata su $u$ costa $\Theta(1 + c_u) + t_u$ (il ciclo sui figli, escluse le chiamate ricorsive, più la visita). Poiché $\sum_u c_u = n - 1$ (vedi AlberiAlbero radicato (definizione per padre e ricorsiva), terminologia (antenati, discendenti, nodi interni ed esterni, sottoalbero, albero ordinato), profondità, livello, altezza; altezza = massima profondità delle foglie; algoritmi depth e height con costo; somma dei figli = n-1; esempio di algoritmo Omega(n^2) (heightBad).Alberi →: ogni nodo non radice ha un solo padre, quindi gli archi sono $n-1$):

$$t(n) = \sum_{u \in T} \big(\Theta(1 + c_u) + t_u\big) = \Theta\Big(n + \sum_{u \in T} t_u\Big).$$

Se ogni visita costa $\Theta(1)$ si ha $\Theta(n)$; se $t_u \in \Theta(\log n)$ per ogni $u$ si ha $\Theta(n \log n)$.

Definizione (antenato comune più basso, LCA). Dati $v, w$ in $T$, $\text{LCA}(v, w)$ è l'antenato comune più profondo. Algoritmo: si calcolano $d_v = \text{depth}(v)$ e $d_w = \text{depth}(w)$ risalendo; si porta il nodo più profondo a salire di $|d_v - d_w|$ passi, poi si salgono insieme $v$ e $w$ finché coincidono. Costo $O(\text{depth}(v) + \text{depth}(w)) = O(h)$, al caso pessimo $O(n)$ e senza strutture di appoggio. La differenza di profondità è un valore assolutoIl valore assoluto è la distanza di un numero da zero: definizione, proprietà, disuguaglianza triangolare e disequazioni con i moduli.Valore assoluto (modulo) → perché non si sa quale dei due nodi sia più profondo. Perché funziona: dopo aver portato i due nodi alla stessa profondità, i loro antenati alla stessa profondità sono confrontabili e il primo in comune che si incontra salendo è, per definizione, il più profondo tra quelli comuni.

Alberi binari

Definizione (albero binario e albero binario proprio). Un albero binario è un albero ordinato (vedi AlberiAlbero radicato (definizione per padre e ricorsiva), terminologia (antenati, discendenti, nodi interni ed esterni, sottoalbero, albero ordinato), profondità, livello, altezza; altezza = massima profondità delle foglie; algoritmi depth e height con costo; somma dei figli = n-1; esempio di algoritmo Omega(n^2) (heightBad).Alberi →) in cui ogni nodo interno ha al più 2 figli, ogni nodo non radice è etichettato come figlio sinistro o destro del padre, e il figlio sinistro precede il destro. Se c'è un solo figlio si assume sia il sinistro. Il sottoalbero sinistro (destro) di $v$ è quello radicato nel suo figlio sinistro (destro).

Un albero binario è proprio (o pieno, full) se ogni nodo interno ha esattamente 2 figli. Un albero binario è un caso particolare di albero (AlberiAlbero radicato (definizione per padre e ricorsiva), terminologia (antenati, discendenti, nodi interni ed esterni, sottoalbero, albero ordinato), profondità, livello, altezza; altezza = massima profondità delle foglie; algoritmi depth e height con costo; somma dei figli = n-1; esempio di algoritmo Omega(n^2) (heightBad).Alberi →) e di grafo senza cicli (Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →); le interfacce sono ADT (Tipi di dato astrattiUn ADT è definito dalle operazioni e dal loro comportamento, non dalla rappresentazione; interfaccia e implementazione; realizzazione in Python con le classi e in C con header e tipo opaco; esempio di un ADT Frazione.Tipi di dato astratti →).

Teorema (relazioni in un albero binario proprio)

#	Relazione
1	$m = (n - m) + 1$
2	$h + 1 \le m \le 2^h$
3	$h \le n - m \le 2^h - 1$
4	$2h + 1 \le n \le 2^{h+1} - 1$
5	$\log_2(n+1) - 1 \le h \le \frac{n-1}{2}$

Definizione (visita inorder). Oltre a preorder e postorder (vedi Visite di alberiVisite in preorder e postorder come schemi generali (template) da adattare; complessità Theta(n + somma dei costi di visita) perché la somma dei figli è n-1; esempi (indice di un libro, spazio occupato in un file system); profondità con il preorder, altezza con il postorder; antenato comune più basso.Visite di alberi →), negli alberi binari si ha la visita inorder: prima il figlio sinistro, poi il padre, poi il figlio destro.

Definizione (parse tree di un'espressione). Un'espressione fully parenthesized in notazione infissa è una costante/variabile $a$ oppure $(E_1\ \text{Op}\ E_2)$ con $E_1, E_2$ fully parenthesized e Op binario. Il parse tree è l'albero binario proprio che ha nelle foglie costanti e variabili, nei nodi interni gli operatori, con sottoalbero sinistro e destro uguali ai parse tree di $E_1$ ed $E_2$; le parentesi sono implicite nella struttura. Con operatori unari l'albero non è più proprio. Le espressioni aritmetiche e la precedenza degli operatori sono quelle di Tipi numerici ed espressioniint, float, complex e bool; operatori aritmetici con divisione intera e modulo; precedenza; conversioni di tipo; modulo math e arrotondamenti.Tipi numerici ed espressioni → (Fondamenti di Informatica); la costruzione del parse tree è una fase della compilazione (Paradigmi di programmazione e linguaggiAlgoritmo e programma; paradigmi imperativo, procedurale, a oggetti, funzionale e dichiarativo; compilazione e interpretazione; confronto tra Python e C.Paradigmi di programmazione e linguaggi →, Dal programma C all'eseguibile ARMCatena di traduzione compilatore, assemblatore, linker e loader; file oggetto, tabella dei simboli e rilocazione; collegamento statico e dinamico; organizzazione della memoria di un processo; chiamare funzioni assembly da C e viceversa, con esempio.Dal programma C all'eseguibile ARM →).

Definizione (heightsum). La heightsum di un albero binario proprio è la somma delle altezze di tutti i suoi nodi. Con la sola somma restituita da ogni sottoalbero non si potrebbe calcolare l'altezza del padre; si restituisce quindi una coppia (somma, altezza):

Algoritmo heightSum(T, v)
Input: v in T      Output: (somma delle altezze dei nodi di T_v, altezza di v)
if T.isExternal(v) then return (0, 0)
(sL, hL) <- heightSum(T, T.left(v))
(sR, hR) <- heightSum(T, T.right(v))
h <- max(hL, hR) + 1
return (sL + sR + h, h)

V. Code con priorità e heap

Code con priorità

Definizione (coda con priorità). Una coda con priorità (priority queue) è una collezione di entry le cui chiavi, non necessariamente distinte, rappresentano priorità e provengono da un universo totalmente ordinato (due chiavi qualunque sono sempre confrontabili con $\le$, come per i numeri reali: Campi ordinati (Q e R)Gli assiomi di somma, prodotto e ordine comuni a Q e R, da cui derivano le regole di equazioni e disequazioni.Campi ordinati (Q e R) →). Ingressi e uscite si alternano in modo arbitrario, le priorità in ingresso non sono ordinate, le uscite avvengono in ordine di priorità.

interfaccia PriorityQueue<K,V>:
    size(), isEmpty()
    insert(k, v)   inserisce e restituisce la nuova entry (k, v)
    min()          restituisce una entry con chiave minima, senza toglierla
    removeMin()    restituisce e toglie una entry con chiave minima

Per convenzione chiave minima = priorità massima. Una coda basata sul massimo ha max() e removeMax() al posto di min() e removeMin().

Proprietà (code con priorità su liste: costi). Lista non ordinata. insert: si aggiunge in coda, $\Theta(1)$. min: si scorre tutta la lista tenendo la chiave minore, $\Theta(n)$. removeMin: si trova il minimo e lo si toglie, $\Theta(n)$.

Lista ordinata (per chiave crescente). min e removeMin: si guarda/toglie il primo nodo, $\Theta(1)$. insert: si scorre fino alla prima chiave $\ge k$ e si inserisce prima di essa, $\Theta(n)$.

Proprietà (ordinamento con una coda con priorità). Per ordinare $n$ chiavi: si fanno $n$ insert e poi $n$ removeMin, che restituiscono le chiavi in ordine crescente. Il costo dipende dall'implementazione:

• lista non ordinata: $n \cdot \Theta(1) + n \cdot \Theta(n) = \Theta(n^2)$ (è il selection sort);
• lista ordinata: $n \cdot \Theta(n) + n \cdot \Theta(1) = \Theta(n^2)$ (è l'insertion sort);
• heap: $n \cdot \Theta(\log n) + n \cdot \Theta(\log n) = \Theta(n \log n)$ (è l'heap sort).

Heap

Definizione (albero binario completo). Un albero binario di altezza $h$ è completo se:

• per ogni livello $i$ con $0 \le i \le h - 1$ ci sono $2^i$ nodi (livello pieno);
• al livello $h$ i nodi sono tutti a sinistra delle eventuali mancanze: nessun buco, e al più l'ultimo nodo interno ha solo il figlio sinistro.

Proposizione (altezza di un albero binario completo). Un albero binario completo con $n$ nodi ha altezza $h = \lfloor \log_2 n \rfloor$.

Definizione (heap). Uno heap è un albero binario completo i cui nodi memorizzano entry e che soddisfa la heap-order property: per ogni nodo $v$ diverso dalla radice, $\text{key}(v) \ge \text{key}(\text{padre}(v))$. Equivale a: ogni nodo ha chiave $\le$ quella dei figli. (Un max-heap inverte la disuguaglianza.) Il nodo last è il più a destra del livello $h$.

Proprietà (heap con $n$ entry). Proprietà (heap con $n$ entry):

1. la radice contiene una entry con chiave minima;
2. le chiavi lungo un cammino dalla radice a una foglia formano una sequenza non decrescente;
3. con chiavi distinte, se $e_i$ è l'entry con $i$-esima chiave più piccola ($e_1$ = radice) e sta a profondità $d$, allora $d < i$ (gli $d$ antenati di $e_i$ sono altrettante entry con chiave minore, più $e_i$ stessa);
4. con chiavi distinte, l'entry con chiave massima sta in una foglia (per assurdo: se fosse in un nodo interno, un suo figlio avrebbe chiave maggiore);
5. per ogni nodo $v$ e ogni nodo $u$ nel sottoalbero $T_v$, $\text{key}(u) \ge \text{key}(v)$ (per transitività lungo il cammino).

Formula (level numbering di uno heap su array). Un heap sta in un array $P[1..n]$ numerando i nodi per livelli, da sinistra a destra: la radice è $P[1]$, i figli di $P[i]$ sono $P[2i]$ e $P[2i+1]$, il padre di $P[i]$ è $P[\lfloor i/2 \rfloor]$ e $\text{last} = n$. I collegamenti padre-figlio sono impliciti (struttura dati implicita): nessun puntatore, spazio $\Theta(n)$. (Nel testo adottato la numerazione parte da 0: figli $2i+1$, $2i+2$, padre $\lfloor (i-1)/2 \rfloor$.)

Proprietà (insert e up-heap bubbling). Si pone la nuova entry in posizione $\text{last} + 1$ (la completezza è salva) e si ripristina l'heap-order risalendo.

Proprietà (removeMin e down-heap bubbling). Si toglie la radice, si porta in radice l'ultima entry e si ripristina scendendo, scambiando sempre con il figlio di chiave minore.

Proprietà (rimozione di una entry qualsiasi). removeEntry(P, j): si pone $P[j] \leftarrow P[\text{last}]$ e si decrementa $\text{last}$. Sia $e = (k, v)$ l'entry spostata, $e_0$ il nuovo padre, $e_1, e_2$ i figli. Tre casi:

1. $k_0 \le k \le \min(k_1, k_2)$: l'heap è già valido;
2. $k < k_0$: up-heap bubbling a partire da $P[j]$;
3. $k > \min(k_1, k_2)$: down-heap bubbling a partire da $P[j]$.

Costruzione di uno heap

Definizione (costruzione top-down con inserimenti successivi). Si considera $P[1]$ uno heap di un elemento e si inserisce $P[2], P[3], \dots, P[n]$ con l'up-heap bubbling.

Formula (costo della costruzione top-down). Costo. L'iterazione $j$ costa $O(\log j)$, quindi $O\big(\sum_{j=2}^{n} \log j\big) = O(n \log n)$. È anche $\Omega(n \log n)$: se $P$ è in ordine decrescente ogni nuova chiave è minore di tutte le precedenti e sale fino alla radice, e

$$\sum_{j=\lfloor n/2 \rfloor}^{n} \log_2 j \ \ge\ \frac n2 \log_2 \Big\lfloor \frac n2 \Big\rfloor \in \Omega(n \log n).$$

Quindi $\Theta(n \log n)$ (anche $n$ insert consecutive in uno heap vuoto, vedi Esercizio 13 · costruzione di uno heap top-down e bottom-up).