Formulario - dati e algoritmi

Nozioni fondamentali

Note: Problemi computazionali e algoritmiProblema computazionale come insieme di coppie (istanza, soluzione); algoritmo e modello di calcolo RAM; pseudocodice; taglia di un'istanza; ADT e struttura dati concreta; esempio svolto con ricerca lineare e binaria in un array ordinato.Problemi computazionali e algoritmi → · 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 → · 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 → · 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 → · 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 →

• Caso pessimo $t_A(n)=\max\{t_{A,i}:i\text{ di taglia }n\}$ nel modello RAMRandom Access Machine: ogni passo elementare costa Θ(1). $O(g)$: ogni istanza costa $\le c\,g(n)$; $\Omega(g)$: esiste un'istanza che costa $\ge c\,g(n)$; $\Theta=O\cap\Omega$ con $g$ tight e semplice.
• $f\in O(g)$: $\exists c>0,n_0$ con $f(n)\le c\,g(n)$ per $n\ge n_0$; $f\in o(g)$: $\lim\frac fg=0$. Polinomio di grado $k$ $\in\Theta(n^k)$; $n^k\in o(a^n)$ ($a>1$); $(\log n)^k\in o(n^h)$; $\log_bn=\log_an\cdot\log_ba$; $O\Rightarrow o$ e $O\Rightarrow\Theta$ sono falsi.
• Sommatorie: $\sum_{i=0}^ni=\frac{n(n+1)}2$, $\sum i^2=\frac{n(n+1)(2n+1)}6\in\Theta(n^3)$, $\sum a^i=\frac{a^{n+1}-1}{a-1}$. In 1 s con operazioni da 1 ns: $n\approx10^9$ (lineare), $n\approx3\cdot10^4$ ($n^2$), $n\approx30$ ($2^n$).

• InsertionSort: $\frac{n(n-1)}2$ confronti sull'array decrescente (caso pessimo), $n-1$ sull'ordinato; prefixAverages1 (doppio ciclo) $\frac{n(n+1)}2\in\Theta(n^2)$ contro prefixAverages2 (somma corrente) $\Theta(n)$.

• Ricerca lineare $\Theta(n)$; binaria $O(\log n)$ con $mid=\lfloor\frac{lo+hi}2\rfloor$ e al più $\lfloor\log_2n\rfloor+1$ iterazioni. Induzione: base $Q(n_0..n_0+k)$, passo da $Q(m)$ per $n_0\le m\le n$ a $Q(n+1)$. Invariante di ciclo: vale prima, si conserva, a fine ciclo implica la tesi (arrayMax: $currMax=\max A[0..i]$).
• Ricorsione: costo = somma sui nodi dell'albero della ricorsione, spazio $\Theta(d)$ per profondità $d$. Power(x,n) con una sola chiamata: $O(\log n)$. Fibonacci ricorsivo: $C(n)=1+C(n-1)+C(n-2)=2F(n+1)-1$ chiamate, esponenziale; con memoizzazione $\Theta(n)$.

Il linguaggio C

Note: 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 → · 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 →

• Lista in C: addHead: aux->next = *l; *l = aux; $\Theta(1)$; addTail ricorsiva su &(*l)->next $\Theta(n)$; pop: salvare val e next, poi free; inversione in loco con prec, cur, succ $O(n)$. Coda con testa e coda: enqueue e dequeue $\Theta(1)$, aggiornando entrambi quando si svuota.

ADT elementari

Note: 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 →

Alberi

Note: 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 → · 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 → · Alberi binariAlbero binario e albero binario proprio; interfaccia; relazioni tra nodi, foglie e altezza (m = n-m+1, h+1 <= m <= 2^h, 2h+1 <= n <= 2^(h+1)-1) con dimostrazioni; visita inorder; parse tree e valutazione di espressioni; heightSum come esempio di calcolo di un'informazione più ricca.Alberi binari →

• $\text{depth}(r)=0$, $\text{depth}(v)=1+\text{depth}(\text{padre})$; $\text{height}(\text{foglia})=0$, $\text{height}(v)=1+\max_w\text{height}(w)$; $\text{height}(T)=\max\{\text{depth}(v):v\text{ foglia}\}$. height in postorder $\Theta(n)$; heightBad (depth da ogni foglia) $\Omega(n^2)$.
• Visite: preorder (nodo, poi figli), postorder (figli, poi nodo); costo $\Theta(n+\sum_ut_u)$ perché $\sum_uc_u=n-1$. LCA in $O(h)$. Albero binario proprio ($n$ nodi, $m$ foglie, altezza $h$): $m=n-m+1$, $h+1\le m\le2^h$, $2h+1\le n\le2^{h+1}-1$, $\log_2(n+1)-1\le h\le\frac{n-1}2$. Inorder in un ABR dà le chiavi crescenti.

Code con priorità e heap

Note: Code con prioritàEntry chiave-valore; ADT coda con priorità (insert, min, removeMin) con chiave minima = priorità massima; esempio di esecuzione; applicazioni; implementazioni con lista non ordinata e ordinata e relativi costi; ordinamento tramite coda con priorità.Code con priorità → · HeapAlbero binario completo e sua altezza floor(log2 n); heap = albero completo con heap-order property; proprietà (radice minima, cammini non decrescenti); rappresentazione su array con level numbering; insert con up-heap bubbling, removeMin con down-heap bubbling, rimozione di una entry qualsiasi; invarianti e costi Theta(log n); esempio svolto.Heap → · Costruzione di uno heapCostruire uno heap da un array di n entry: approccio top-down con n-1 insert, Theta(n log n); approccio bottom-up con down-heap dalle foglie verso la radice, Theta(n), con dimostrazione della somma; esempi svolti, in loco; unione di due alberi con heap-order.Costruzione di uno heap →

• Heap = albero completo con $\text{key}(v)\ge\text{key}(\text{padre})$; $h=\lfloor\log_2n\rfloor$. Array $P[1..n]$: figli $2i,2i+1$, padre $\lfloor\frac i2\rfloor$, $\text{last}=n$. insert in $P[\text{last}+1]$ poi up-heap; removeMin: $P[1]\leftarrow P[\text{last}]$, $\text{last}--$, down-heap col figlio minore; removeEntry: up-heap o down-heap.
• Costruzione: top-down (up-heap per $j=2..n$) $\Theta(n\log n)$; bottom-up (down-heap per $j=\lfloor\frac n2\rfloor..1$) $\Theta(n)$ perché $\sum_{\ell=1}^h\frac\ell{2^\ell}<2$.

Mappe e tabelle hash

Note: Mappe e dizionariADT mappa (chiavi distinte) con get, put, remove, keySet/values/entrySet; famiglia mappa/mappa ordinata/dizionario (multimappa); applicazioni; implementazioni semplici ma poco efficienti (lista, array indicizzato dalle chiavi); dizionario realizzato con una mappa di liste.Mappe e dizionari → · Tabelle hashTabella hash per implementare una mappa: funzione hash = hash code + compression function, bucket array, separate chaining; hash code per numeri e stringhe (polynomial, cyclic shift), division e MAD; load factor, complessità al caso pessimo Theta(n) e medio O(1+lambda), rehashing; esempio svolto con inserimenti e collisioni.Tabelle hash →

• Mappa: get(k), put(k,v) (restituisce il vecchio valore o null), remove(k); lista non ordinata $\Theta(n)$, array indicizzato dalle chiavi $\Theta(1)$ ma spazio $\Theta(|U|)$. Dizionario: chiavi ripetute, remove(k,v) costa $s=|L_k|$ in più.
• Hash: $h$ = hash code + compressione. Divisione $i\bmod N$ ($N$ primo); MAD $[(ai+b)\bmod p]\bmod N$ con $p>N$ primo; stringhe: polinomiale $\sum s_ia^{k-1-i}$ ($a=31$). Concatenamento separato con $\lambda=\frac nN$: caso pessimo $\Theta(n)$, medio $O(1+\lambda)$ sotto uniform hashing; rehashing se $\lambda$ supera una soglia (es. $0{,}75$): $N'\ge2N$, nuova $h$, reinserimento in $\Theta(n)$ ammortizzato.

Alberi di ricerca

Note: Alberi binari di ricercaAlbero binario di ricerca come albero binario proprio con entry nei nodi interni e foglie vuote; inorder crescente; TreeSearch; get, put e remove (due casi, con predecessore inorder) in Theta(h); altezza fino a n-1; esempi di inserimenti; alberi aumentati con campi size e max e algoritmi di conteggio e interrogazione in O(h).Alberi binari di ricerca → · Multi-way search tree e alberi (2,4)Multi-way search tree (nodi con più entry, d figli e d-1 chiavi ordinate), ricerca in O(d_max h), un MWS tree con n entry ha n+1 foglie; albero (2,4): nodi con 2-4 figli e tutte le foglie alla stessa profondità, altezza Theta(log n) con dimostrazione, operazioni in Theta(log n); idea di overflow e underflow; tabella di confronto con gli alberi binari di ricerca.Multi-way search tree e alberi (2,4) →

• ABR: sinistra $<$ chiave $<$ destra; $n$ entry $\Rightarrow$ $n$ nodi interni e $n+1$ foglie. remove con due figli interni: si copia l'entry del predecessore inorder (massimo del sottoalbero sinistro) e si elimina quel nodo. Multi-way: $d$-nodo con $d-1$ chiavi, MWTreeSearch $O(d_{max}h)$. (2,4): 2-4 figli e foglie tutte alla stessa profondità; overflow (5-nodo) si spezza e la terza chiave sale.

Alberi e heap in C

Note: Alberi e heap in CAlbero binario in C con nodo struct e figli left/right; funzioni ricorsive (conteggio, altezza, visita inorder, liberazione in postorder); inserimento in un albero binario di ricerca con Nodo **; min-heap su array con indici da 1 (insert, removeMin, bottomUp).Alberi e heap in C →

• Nodo struct nodo { int val; struct nodo *left, *right; }; altezza con NULL $\to-1$ e 1 + max(altezza(left), altezza(right)); liberaAlbero in postorder; addBST(Nodo **r, v) $\Theta(h)$. Heap su array da indice 1 con last passato per puntatore: insert (while (i > 1 && h[i/2] > h[i]) scambia) $\Theta(\log n)$, downHeap (while (2*i <= last)), bottomUp da last/2 a 1 in $\Theta(n)$.

Algoritmi di ordinamento

Note: Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →

• Limite inferiore per i confronti: albero di decisione con $\ge n!$ foglie, altezza $\ge\log_2n!\ge\frac n2\log_2\frac n2$, quindi $\Omega(n\log n)$; merge sort e heap sort sono ottimi.

Grafi: definizioni e visite

Note: 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à → · Rappresentazione dei grafiStrutture di base (lista dei vertici LV, lista degli archi LE), liste di adiacenza, matrice di adiacenza; operazioni incidentEdges, opposite, areAdjacent; spazio e tempi a confronto; esempio con un grafo di 5 vertici.Rappresentazione dei grafi → · 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 →

• $G=(V,E)$, $n=|V|$, $m=|E|$ (semplice non diretto). P1 $\sum\text{degree}(v)=2m$; P2 $m\le\binom n2$; P3 albero $m=n-1$; P4 connesso $m\ge n-1$; P5 foresta $m\le n-1$. Spanning forest con $k$ componenti: $n-k$ archi.

• BFS: livelli $L_{i+1}$ = nuovi vicini di $L_i$, archi DISCOVERY/CROSS; $v\in L_i\Rightarrow d(s,v)=i$. DFS: archi DISCOVERY/BACK, cammini non minimi. Costo $\Theta(n+m)$ con liste di adiacenza (ogni arco visto due volte); per grafi non connessi si rilancia da ogni vertice con ID = 0. Con la BFS: connettività, componenti, spanning tree, cammino minimo con parent.

Cammini minimi, alberi di copertura e ordinamento topologico

Note: Cammini minimi e algoritmo di DijkstraGrafi pesati, lunghezza di un cammino e distanza; sottocammini di un cammino minimo; problema SSSP; algoritmo di Dijkstra con cloud e priority queue, rilassamento degli archi, esempio svolto; correttezza (due lemmi) e complessità O(min(n^2, (n+m) log n)) con lista non ordinata o heap; pesi non negativi.Cammini minimi e algoritmo di Dijkstra → · Minimum spanning treeMinimum spanning tree di un grafo pesato connesso; proprietà del taglio (cut property) con dimostrazione; algoritmo di Kruskal con partizioni (union-find) e algoritmo di Prim con coda con priorità; esempio svolto sullo stesso grafo di Dijkstra; complessità O(m log n).Minimum spanning tree → · Grafi diretti e ordinamento topologicoGrafi diretti (archi orientati, grado entrante e uscente, cammini e cicli diretti), visite su grafi diretti e tipi di archi; DAG; ordinamento topologico con l'algoritmo basato sui gradi entranti e con la DFS (reverse postorder), correttezza e costo Theta(n+m); esempio svolto.Grafi diretti e ordinamento topologico →

• MST: spanning tree di peso minimo, $n-1$ archi; proprietà del taglio: l'arco minimo che attraversa un taglio non attraversato da $F\subseteq$ MST può essere aggiunto. Cammini minimi: sottocammini di cammini minimi sono minimi; pesi tutti 1 $\Rightarrow$ BFS. Ordine topologico: per ogni $(u\to v)$, $u$ prima di $v$; esiste $\iff$ DAG $\iff$ nessun back edge; con ordine di meno di $n$ vertici c'è un ciclo.