giovedì, 04 marzo 2010
Introduzione al corso.Complessità temporale e spaziale di un algoritmo. Notazioni asintotiche. Serie di Fibonacci come caso di studio. Algoritmi efficienti e non efficienti. Definizioni ricorsive e relazioni di ricorrenza. Albero di ricorsione. Calcolo della serie di Fibonacci in tempo esponenziale e lineare.

lunedì, 08 marzo 2010
Uso delle matrici per ottenere un algoritmo di complessità logaritmica. Calcolo della complessità con il metodo iterativo srotolando la ricorsione. Valutazione dello spazio di memoria occupato da un algoritmo ricorsivo. Notazioni asintotiche per definire l'andamento di funzioni incognite. Notazioni Ο, Ω, Θ per delimitare l'andamento delle funzioni di costo.

giovedì, 11 marzo 2010
Metodi di analisi di un algoritmo: caso migliore, caso medio e caso peggiore. Analisi del caso medio e probabilità. Applicazione al problema della ricerca di un elemento in un insieme. Ricerca sequenziale: caso migliore, medio e peggiore. Ricerca binaria e relazioni di ricorrenza. Risoluzione con il metodo iterativo. Sommatorie notevoli: progressione aritmetica e geometrica, Σ k · 2k-1.

lunedì, 15 marzo 2010
Esercizi sulla soluzione di relazioni di ricorrenza con il metodo iterativo. Esempi di relazioni di ricorrenza risolte con i metodi iterativi e di sostituzione. Analisi di algoritmi ricorsivi. Master Theorem e sua applicabilità: i tre casi.

giovedì, 18 marzo 2010
Dimostrazione del Master Theorem nel caso in cui n sia una potenza esatta del numero di suddivisioni in sottoproblemi. Condizione di regolarità per il caso 3. Generalizzazione del caso 2 quando f(n)=Θ(nlogb(a) · logk(n)).

lunedì, 22 marzo 2010
Esercizi sul Master Theorem per la soluzione di equazioni di ricorrenza. Casi di non applicabilità e soluzione con sostituzione di variabile. Esercizi: dimostrazione della generalizzazione del caso 2 del Master Theorem; dimostrazione della sufficienza della condizione di regolarità per il caso 3 (a·f(n/b)≤ c·f(n) equivalente a f(n)=Ω(nlogba+ε)). Tipo di dato astratto (interfaccia) e struttura dati (rappresentazione). Rappresentazione di collezioni di oggetti. Influenza della rappresentazione sull'efficienza delle operazioni. I tipi di dato dizionario, pila e coda: definizioni funzionali astratte. Rappresentazioni indicizzate (array) e collegate (liste semplici, circolari, doppiamente collegate): pro e contro. Rappresentazioni ordinate e non. Ricerca binaria e sequenziale. Analisi del caso migliore, medio e peggiore delle operazioni di inserimento, ricerca e cancellazione nelle varie rappresentazioni.

giovedì, 08 aprile 2010
Strutture dati gerarchiche: alberi. Operazione sul tipo di dato albero. Rappresentazioni indicizzate di un albero: array di predecessori, array posizionale. Influenza della rappresentazione sull'efficienza delle operazioni di base. Rappresentazione collegata di un albero: record con puntatori ai figli e al genitore. Rappresentazione di un alberi n-ario con la lista dei figli. Rappresentazione di un albero binario. Trasformazione di un albero non binario in uno binario (puntatore al primo figlio e al fratello).Visite iterative di un albero con l'uso di una struttura ausiliaria: in profondità (pila) e in ampiezza (coda). Visite ricorsive di un albero binario: preordine, postordine e simmetrico; da sinistra a destra e viceversa. Algoritmi di ordinamento banali (insertion sort, selection sort, bubble sort) e analisi del loro tempo di esecuzione. Algoritmi di ordinamento ricorsivi basati sulla tecnica del divide et impera. Algoritmo del quicksort.

lunedì, 12 aprile 2010
Algoritmo del quicksort. Partizionamento in loco. Analisi del caso peggiore e del caso medio. Uso della randomizzazione del pivot per migliorare il tempo medio del caso peggiore. Tempo medio del quicksort randomizzato. Algoritmo del mergesort. Fusione (merge) di due array ordinati. Analisi del merge sort.

giovedì, 15 aprile 2010
Struttura dati per la gestione efficiente del massimo (minimo): heap. Operazioni fondamentali: inserimento, eliminazione del massimo, estrazione del massimo, heapify di un array, fixheap. Rappresentazione di un heap con un array posizionale. Tempi di esecuzione delle operazioni. Algoritmo di ordinamento heapsort. Lower bound di un problema. Dimostrazione del lower bound del problema dell'ordinamento basato su confronti con l'utilizzo dell'albero di decisione. Algoritmi ottimali. Algoritmi di ordinamento lineari non basati su confronti: integer sort, bucket sort e radix sort. Stabilità degli algoritmi di ordinamento.

lunedì, 19 aprile 2010
Selezione e statistiche d'ordine. Estrazione del mediano di un insieme come caso peggiore delle statistiche d'ordine. Algoritmi banali basati sull'ordinamento. Algoritmi, basati sulla tecnica divide et impera, che utilizzano il partizionamento del quick sort. Quickselect randomizzato e tempo medio di esecuzione. Quickselect deterministico (Tarjan e altri) e analisi del caso peggiore. Ricorrenza del tipo T(n)=T(α·n) + T(β·n) + n con α+β < 1. Esercizi: ricerca del mediano su 5 elementi con 6 confronti: uso dell'albero di decisione; risoluzione dei problemi delle pesate con l'albero di decisione.

giovedì, 22 aprile 2010
Alberi binari di ricerca (BST). Rappresentazione di dizionari. Operazioni di inserimento, eliminazione e ricerca di una chiave. Casi degeneri. Bilanciamento in altezza di un BST. Alberi AVL. Mantenimento del bilanciamento durante l'inserimento e la cancellazione con le operazioni di rotazione. Altezza di un albero AVL. Alberi di Fibonacci come caso peggiore di alberi AVL (alberi con il maggior sbilanciamento possibile a parità di nodi). Tempi di esecuzione delle operazioni in un AVL.

lunedì, 26 aprile 2010
Strutture dati auto adattive. Ricerca di un elemento con modifica della struttura per migliorare le operazioni successive: liste con riporto dell'elemento in testa (move to front). Splay tree: euristiche di rotazione. Costi logaritmici (in senso ammortizzato) delle operazioni sugli splay tree. B-tree per la gestione di grosse quantità di informazioni. Proprietà di un B-tree.

giovedì, 29 aprile 2010
Proprietà di un B-tree. Altezza di un B-tree. Relazione tra numero delle chiavi ed altezza massima di un B-tree. Generalizzazione del BST. Algoritmi di ricerca, inserimento (con split dei nodi) e cancellazione (con fusione di nodi). Inserimento con split preventivo. Cancellazione con riorganizzazione/fusione preventiva. Dizionari rappresentati con array: chiave coincidente con l'indice. Tavole hash. Funzione di hashing. Problema delle collisioni.

lunedì, 03 maggio 2010
Dizionari rappresentati con array: chiave coincidente con l'indice. Tavole hash. Funzione di hashing. Hashing perfetto. Hashing non perfetto e problema delle collisioni. Proprietà di uniformità della funzione hash. Risoluzione del problema delle collisioni con le liste di collisione: tempo di ricerca, inserimento e cancellazione di una chiave.

giovedì, 06 maggio 2010
Risoluzione delle collisioni nelle tavole hash. Metodo dell'indirizzamento aperto. Sequenze di scansione per l'indirizzamento aperto: scansione lineare, scansione quadratica, hashing doppio. Agglomerazione primaria e secondaria. Cancellazione di un elemento: problema del mantenimento della sequenza di scansione. Valore speciale canc. Dipendenza dell'efficienza delle operazioni dal fattore di carico. Code con priorità. Operazioni del tipo di dato astratto. Implementazione con d-heap. Proprietà strutturali del d-heap. Rappresentazione con array posizionale. Efficienza delle operazioni.Alberi binomiali e loro proprietà strutturali.

lunedì, 10 maggio 2010
Heap binomiale come foresta di alberi binomiali. Proprietà strutturali. Relazione con la rappresentazione binaria del numero di nodi. Heap binomiali: legame tra le proprietà strutturali ed efficienza delle operazioni di insert, deleteMin, findMin, decreaseKey, delete, increaseKey, merge, ristrutturazione. Heap binomiali rilassati. Rilassamento sull'unicità degli alberi in un heap. Influenza sull'efficienza delle operazioni. Approccio lazy alla ristrutturazione. Analisi ammortizzata: assegnazione dei crediti alle radici degli alberi di un heap binomiale rilassato. Efficienza ammortizzata delle operazioni. Rilassamento sulla struttura degli alberi binomiali (numero di nodi) di un heap binomiale rilassato (heap di Fibonacci). Relazione tra il grado e il numero di nodi di un albero appartenente ad un heap di Fibonacci. Implementazione dell'operazione decreaseKey: limitazione alla perdita dei figli di un nodo. Assegnazione dei crediti alle radici e ai nodi in lutto. Tempo ammortizzato costante della decreaseKey.

giovedì, 13 maggio 2010
Il problema Union-find. Tipo di dato astratto Union-find: operazioni makeset, union e find. Implementazione con insiemi di alberi. Versione che privilegia le find (QuickFind). Versione che privilegia le union (QuickUnion).

lunedì, 17 maggio 2010
Strutture Union-find. Euristica di bilanciamento sull'altezza (by rank) e sulla dimensione (by size) per migliorare l'efficienza dell'operazione di find. Equivalenza delle due euristiche. Ulteriori euristiche per la compressione dei cammini durante l'operazione di find: path compression, path splitting, path halving e risultati dell'analisi ammortizzata di una sequenza di m find e n makeset. Funzione logaritmo iterato.

giovedì, 20 maggio 2010
Tecniche algoritmiche. Divide-et-impera. Suddivisione non banale di un problema in sottoproblemi. Applicazione alla moltiplicazione tra interi lunghi. Algoritmo di costo O(n1.59). Programmazione dinamica. Caratteristiche di un problema di p.d.: suddivisione in sottoproblemi, sottostruttura ottima dei sottoproblemi, necessità di ripetizione dello stesso sottoproblema. Memorizzazione delle soluzioni dei sottoproblemi in una matrice e approccio bottom-up. Sottovettore di somma massima. Cammini di valore minimo su matrici. Parentesizzazione ottima del prodotto di n matrici per minimizzare il numero di moltiplicazioni. Formula ricorsiva per il valore degli elementi della matrice. Determinazione del'ottimo.

lunedì, 24 maggio 2010
Parentesizzazione ottima del prodotto matriciale: determinazione e stampa dell'espressione. Esempi di problemi di programmazione dinamica: distanza di editing tra due stringhe; formula ricorsiva per il valore degli elementi della matrice; calcolo della distanza di editing e determinazione della sequenza di operazioni. Problema della sottosequenza comune più lunga (LCS). Impostazione della matrice e determinazione della LCS e della sua lunghezza.

giovedì, 27 maggio 2010
Tecnica Greedy. ottimo locale e ottimo globale. Caratteristiche di un problema risolubile con la tecnica greedy. Analogie e diversità con la p.d. Irreversibilità della scelta greedy. Es: macchina distributrice del resto, sequenziamento di attività, ricoprimento di punti con intervalli unitari, numero minimo di rifornimenti su un tratto stradale.

lunedì, 31 maggio 2010
Grafi. Definizioni e terminologia. Grafi orientati e non orientati. Rappresentazione di un grafo con liste di archi, liste di adiacenza, liste di incidenza, matrice di adiacenza e matrice di incidenza. Prestazioni delle operazioni fondamentali in funzione della rappresentazione. Visita di un grafo. Algoritmo iterativo generico. Marcatura dei nodi. Albero della visita. Visita in ampiezza (BSF) e utilizzo della coda nella visita generica. Proprietà della visita in ampiezza: distanza minima in termini di numero di archi. Classificazione degli archi del grafo. Visita in profondità (DSF) e utilizzo della pila nella visita generica. Versione ricorsiva. Classificazione degli archi del grafo.

giovedì, 03 giugno 2010
Grafi non orientati pesati sugli archi. Alberi ricoprenti di costo minimo (Minimum Spanning Tree). Tagli e cicli. Approccio greedy al calcolo del MST mediante colorazione degli archi. Regola del taglio (blu). Regola del ciclo (rossa). Invariante di appartenenza degli archi blu ad un MST. Mantenimento dell'invariante dopo l'applicazione delle regole. Algoritmo di Kruskal e colorazione degli archi. Tempo di esecuzione con l'ausilio delle strutture Union-Find. Algoritmo di Prim e visita di un grafo. Tempi di esecuzione con l'ausilio di una coda con priorità (Fibonacci heap) per la gestione della frangia. Algoritmo di Borůvka e vincolo sull'unicità dei pesi. Tempo di esecuzione.

lunedì, 07 giugno 2010
Cammini minimi in un grafo. Problemi sui cammini minimi: singola sorgente, singola coppia, tutte le coppie. Problema dei cicli di peso negativo. Proprietà dei cammini minimi. Distanza tra i vertici. Alberi dei cammini minimi e sue proprietà. Calcolo dei cammini minimi a partire dalle distanze. Operazione di rilassamento. Algoritmo generico basato sul rilassamento. Algoritmo di Bellman-Ford (c.m. a sorgente singola) e sua complessità. Ordinamento topologico e dag. Algoritmo di Bellman-Ford per dag e sua complessità. Proprietà di estensione dell'albero dei c.m. Algoritmo di Dijkstra per grafi con pesi positivi. Implementazione come algoritmo di visita greedy utilizzando code con priorità. Somiglianze con l'algoritmo di Prim. Complessità dell'algortimo di Dijkstra. Applicazione della programmazione dinamica al calcolo dei c.m. tra tutte le coppie di nodi: algoritmo di Floyd-Warshall e sua complessità. Cammini (minimi) vincolati. Relazione tra distanze vincolate. Occupazione di memoria.