Programma d'esame

• Problemi e algoritmi. Specifica di un algoritmo: pre e post condizioni. Le asserzioni: correttezza parziale e totale. Invarianti di ciclo (ordinamento per inserimento e selezione, ricerca dicotomica). Accumulatori e contatori (moltiplicazione alla russa). La ricorsione: definizioni induttive e funzioni ricorsive. Valutazione di funzioni ricorsive mediante una pila. Uso della ricorsione nella soluzione di problemi: le torri di Hanoi.Ordini ben fondati e l'induzione completa. Le forme della ricorsione: ricorsione sulla dimensione, ricorsione in coda, ricorsione mutua e annidata.
• Tempo di calcolo. La misura di complessità "tempo". La dimensione dell'ingresso. Il caso peggiore, migliore e medio. Tempo degli algoritmi ricorsivi: relazioni di ricorrenza. Il metodo di iterazione. Confronto asintotico tra le funzioni. Le classi O-grande. Inclusioni tra classi e gerarchia delle funzioni. L'algebra di O-grande. Il metodo di sostituzione. Altre nozioni asintotiche: o-piccolo, Omega e Teta..
• Tipi di dato e strutture dati. Specifiche sintattiche e semantiche: ADT. Ruolo delle interfacce in Java. Astrazione dei dati ed incapsulamento. Strutture dati e loro primitive d'accesso. Invarianti di struttura. Realizzazione di ADT con le classi: invarianti di classe (Matrici sparse in Java).
• Le liste. ADT delle liste. Strutture dati per le liste: vettori parzialmente riempiti, lista libera, strutture di puntatori con legame semplice e doppio, liste circolari con sentinella. Inserimento e cancellazione in una lista. Definizione induttiva delle liste. Versioni ricorsive di inserimento e cancellazione. Ordinamento di una lista per inserzione (Insert-Sort).
• Le pile e le code. Accesso LIFO. ADT delle pile. Pile con vettori. Pile con le liste. Inversione di una lista. Accsso FIFO. L'ADT delle code. Realizzazione con vettore "circolare". Realizzazione con le liste. 
• Gli alberi. Definizione. Struttura induttiva degli alberi. Alberi con radice: alberi sorgente ed alberi pozzo. Relazioni padre-figlio, cammini e livelli: l'altezza di un albero.Albri ordinati e posizionali. Alberi k-ari. Un'ADT per gli alberi. Realizzazione on vettore di padri. Alberi binari. Realizzazione di alberi binari con puntatori. Rappresentazione di alberi k-ari con alberi binari, e loro realizzazione con strutture di puntatori. La ricorsione sugli alberi. Visite in profondità ed in ampiezza. Uso di pile e code nelle visite.
• La complessità dei problemi. Confini superiori ed inferiori alla complessità di un problema.. Confini inferiori banali: dimensione dei dati ed eventi contabili. Il problema dell'ordinamento. L'oracolo. Alberi completi e semi-completi. L'albero delle decisioni. L'ordine di grandezza di log(n!). Algoritmi ottimi.
• Code di priorità. ADT delle code di priorità. La struttura heap: heap minimi e massimi. Realizzazione di heap con un vettore. Inserimento ed estrazione del minimo/massimo. Ordinamento di un vettore mediante uno heap. Dimostrazione dell'ottimalità di Heap-Sort.
• Backtracking. Attraversare un labirinto. Lo spazio di ricerca e la sua vista DFS. Il problema del partizionamento. String matching: l'algoritmo ingenuo e quello di Knuth-Morris-Pratt.
• Divide et Impera. Minimo e massimo in un vettore. Divisione e combinazione: la forma della ricorrenza DI. Ordinamento per fusione (Merge-Sort). L'albero della ricorsione. Un metodo ottimo nel caso medio: Quick-Sort.
• Relazioni di ricorrenza. Relazioni lineari a partizione costante. Relazioni lineari a partizione bilanciata. Moltiplicazione veloce di due interi
• Insiemi. Collezioni in Java. L'ADT degli insiemi. Realizzazione con vettori di booleani. Realizzazione con liste ordinate. Partizioni di un insieme. Insiemi con unione e ricerca: MFSET. MFSET con le liste. MFSET con foreste di alberi pozzo.Unione per peso e per rango. La compressione dei cammini.
• Tempo ammortizzato. Analisi di complessità in tempo per strutture dati persistenti. Le sequenze. Tempo ammortizzato con il metodo dell'aggregato. Il metodo del conto in banca. Analisi con una funzione "potenziale". Il tempo ammortizzato delle pile realizzate con liste e con vettori ridimensionanti.
• Dizionari. L'ADT dei dizionari. Dizionari in Java. Le mappe. Tabelle ad accesso con trasformazione di chiave (hashing). Hashing uniforme. Metodo della divisione e della moltiplicazione. Gestione della collisione. Concatenazione separata: liste di trabocco. Indirizzamento aperto: i sondaggi. Inserimento, ricerca e cancellazione col metodo dei sondaggi. Sondaggi lineari, quadratici e con doppio hash. Cenni all'analisi del caso medio. Dizionari con alberi. Alebri binari di ricerca. Inserimento e cancellazione in alberi binari di ricerca. Minimo e successore. Alberi bilanciati. Alberi rosso-neri. Inserimento in un albero rosso-nero: ricolorazione e rotazione.
• Indici su supporti di memoria di massa. Accessi al disco e tempi di latenza. Impaginare un albero binario completo. B-alberi. Analisi dell'altezza di un B-albero in rapporto alla cardinalità. Ricerca in un B-albero. Inserimento e cancellazione in un B-albero: divisione e fusione di nodi.
• I grafi. Definizione: grafi orientati e non. Cammini, cicli e cricche. Rappresentazione dei grafi con matrici e liste di adiacenza. Visita di un grafo. Partizione dei nodi per la visita. Visita in ampiezza (BFS) ed in profondità (DFS). Ordinamento topologico di un grafo.
• Cammini minimi. Problemi di ottimizzazione. Grafi pesati. Peso di un cammino e distanza in un grafo senza cicli a somma negativa. Il problema del cammino minimo da sorgente singola: alberi di copertura e soluzioni ottime. Il teorema di Bellman. Il caso dei pesi non negativi: algoritmo di Dijkstra. Il caso generale: algoritmo di Bellman-Ford.