ProgrammaDelCorso < Intro

Tags: view all tags

---++ Libri di testo
Ogni libro di introduzione agli algoritmi, che non faccia riferimento ad un particolare linguaggio di programmazione va bene.

Testi suggerimenti:
   * [DFI] Demetrescu, Finocchi, Italiano: Algoritmi e strutture dati, Mc Graw Hill.
   * [CLRS] Cormen, Leiserson, Rivest, Stein: Introduzione agli algoritmi e strutture dati, Mc Graw Hill.
   * [CLR] Cormen, Leiserson, Rivest: Introduzione agli algoritmi (vecchia edizione in tre volumi), vol. 1, Jackson Libri.

Altri testi interessanti:
   *[AP] Ausiello, Petreschi, "L'informatica invisbile", Sapienza-Mondadori edizioni.


---++ Programma A.A. 2019-2020

*INTRODUZIONE*
Algoritmo: significato, proprietà, ed etimologia.
Algoritmi nella vita quotidiana.
Studio di algoritmi: progetto, validazione e analisi.
Introduzione all'efficienza computazionale. Diversi approcci allo stesso problema.
Primi esempi di algoritmi: divisibilità per 3, ricerca di un elemento in un array ordinato e non.
Eseguire un algoritmo simulando le operazioni svolte dal calcolatore.


*COMPLESSITA' COMPUTAZIONALE*
Analisi della complessità computazione di un algoritmo: approccio sperimentale e teorico.
Modello di costo uniforme, operazioni elementari di costo costante.
Definizione di tempo di esecuzione: caso migliore, caso peggiore e caso medio.
Efficienza asintotica degli algoritmi: limite asintotico superiore, inferiore e stretto: notazione O grande, notazione Omega, notazione Theta.
Algebra della notazione asintotica. Proprietà delle operazioni in notazione asintotica.
Un polinomio di grado d è un Theta(n^d) con dimostrazione.
Algoritmo per la valutazione di un polinomio, tre versioni e confronti di efficienza.
Calcolo del costo computazione di un algoritmo: conteggio delle iterazioni in Theta(n) e Theta(n log n).
Tecnica del raddoppio per calcolare x^n.
Valutazione di algoritmi iterativi con uno o due cicli innestati.
Confronto tra vari algoritmi per il calcolo dei numeri di Fibonacci.


*ALGORITMI DI ORDINAMENTO:*
Il problema dell'ordinamento: ordinare un mazzo di carte.
_InsertionSort_: pseudocodice, esempio di esecuzione, proprietà, analisi asintotica nel caso peggiore, migliore e medio.
_SelectionSort_: pseudocodice, esempio di esecuzione, proprietà, analisi asintotica, versione ricorsiva.
_BubbleSort_: pseudocodice, esempio di esecuzione, proprietà, analisi asintotica, variante migliorata ccon verifica sugli scambi.
Alberi di decisione per algoritmi basati su confronti e loro proprietà.
Teorema sulla limitazione inferiore per la complessità di un algoritmo di ordinamento basato su confronti.
Algoritmo di fusione di due array ordinati.
_MergeSort_: pseudocodice, esempio di esecuzione, proprietà, albero della ricorsione, analisi asintotica, risoluzione dell'equazione di ricorrenza, versione iterativa.
Partizionamento di un array in base a un valore pivot semplice, randomizzato e mediano.
_QuickSort_: pseudocodice, proprietà, analisi asintotica nel caso peggiore, migliore e medio, risoluzione dell'equazione di ricorrenza.
_HeapSort_: struttura dati Heap rappresentata con vettore, funzioni fixHeap e heapify, ordinamento tramite Heap, proprietà, analisi asintotica.
_Ordinamenti in tempo lineare_: limiti degli ordinamenti non basati su confronti, !IntegerSort e !CountingSort, pseudocodice, proprietà, analisi asintotica.


*EQUAZIONI DI RICORRENZA:*
Analisi asintotica di funzioni ricorsive.
Risoluzione di equazioni di ricorrenza per sostituzione.
Risoluzione di equazioni di ricorrenza con il metodo iterativo.
Risoluzione di equazioni di ricorrenza analizzando l'albero della ricorsione.
Enunciato del Teorema Principale (senza dimostrazione).
Confronto tra i metodi di risoluzione delle equazioni di ricorrenza.
Ricostruzione di un albero a partire dalla sue visite inorder e preorder.


*STRUTTURE DATI ELEMENTARI ED ALBERI:*
Organizzazione logica dell'informazione: strutture dati astratte.
Implementazione delle strutture dati astratte: strutture dati concrete.
Implementazione con strutture ad accesso diretto e ad accesso sequenziale.
Pile, code e alberi.
Computo della complessità di operazioni di interrogazione e manipolazione su diverse strutture dati.
Rappresentazioni in memoria di alberi binari.
Visite di alberi binari: preordine, postordine, inordine, in profondità, in ampiezza.
Calcolo dell'equazione di ricorrenza relativa agli algoritmi ricorsivi di visita.


*DIZIONARI:*
La struttura dati Dizionario.
Implementazioni banali: vettori ordinati e liste collegate.
_Alberi Binari di Ricerca (ABR)_.
Ricerca ricorsiva su un ABR.
Inserimento e cancellazione su un ABR.
Calcolo del minimo e del massimo in un ABR.
Calcolo del predecessore e del successore in un ABR.
Problemi di sbilanciamento.
_Alberi AVL_: fattori di bilanciamento e rotazioni.
Dimostrazione del limite di altezza di un albero AVL, alberi di Fibonacci.
Inserimento e ri-bilanciamento in un albero AVL: casi SS e SD.
Cancellazione e ri-bilanciamento in un albero AVL.