Materiale scaricabile¶
Le dispense e gli eserciziari in PDF, aggiornati a ogni pubblicazione del sito, con la stessa numerazione di definizioni, teoremi, esempi ed esercizi del sito. Testi e figure sono sotto licenza CC BY 4.0.
Dispense¶
-
Dispensa, volume 1 · Algoritmi di base
La rappresentazione dei numeri e lo pseudocodice, il linguaggio in cui sono scritti tutti gli algoritmi del corso; i primi algoritmi: ordinamento (insertion, exchange e selection sort), ricerca lineare e binaria, algoritmi numerici (cambio di base, test di primalità, crivello di Eratostene, massimo comune divisore). Ogni algoritmo con lo pseudocodice ed esempi eseguiti passo per passo.
-
Dispensa, volume 2 · Linguaggi di programmazione
Dallo pseudocodice ai programmi: tre linguaggi di programmazione, C++ (compilato), Python (interpretato) e Java (compilato in bytecode ed eseguito da una macchina virtuale). Per ciascuno: variabili e tipi di dato, input e output, operatori, istruzioni condizionali, cicli, array e liste, funzioni, operatori bit a bit e un algoritmo completo, con il confronto fra i tre linguaggi.
-
Dispensa, volume 3 · Notazione e crescita asintotica
Come si confrontano le funzioni di variabile naturale che contano i passi di un algoritmo: le notazioni asintotiche Theta, O grande, Omega, o piccolo e omega, le loro proprietà e il criterio del limite; poi le famiglie di funzioni crescenti (logaritmi, potenze, esponenziali, fattoriale), la gerarchia degli infiniti e il confronto degli ordini di crescita scritto con i simboli. Limiti e funzioni di variabile naturale si danno per noti dal corso di Analisi Matematica 1.
-
Dispensa, volume 4 · Analisi degli algoritmi
L'analisi degli algoritmi: la dimensione dell'input, il tempo di esecuzione nel caso migliore, peggiore e medio, e la correttezza dimostrata con le invarianti di ciclo.
-
Dispensa, volume 5 · Ricorsione
La ricorsione: algoritmi ricorsivi classici, equazioni di ricorrenza, il Master theorem, algoritmi ricorsivi (somma di un array, merge sort, ricerca binaria, sotto-array di somma massima) e il confronto fra versioni ricorsive e iterative.
Esercizi¶
-
Esercizi, volume 1 · Algoritmi di base
Esercizi svolti sui capitoli 1--5: rappresentazione dei numeri, pseudocodice, ordinamento, ricerca e algoritmi numerici. Ogni esercizio ha la soluzione completa.
-
Esercizi, volume 2 · Linguaggi di programmazione
Esercizi svolti sui capitoli 6--8: programmi in C++, Python e Java, dallo pseudocodice al codice. Ogni esercizio ha la soluzione completa.
-
Esercizi, volume 3 · Notazione e crescita asintotica
Esercizi svolti sui capitoli 9--10: notazioni asintotiche Theta, O grande, Omega, o piccolo e omega, e confronto degli ordini di crescita. Ogni esercizio ha la soluzione completa.
-
Esercizi, volume 4 · Analisi degli algoritmi
Esercizi svolti sui capitoli 11--13: dimensione dell'input, tempo di esecuzione, correttezza. Ogni esercizio ha la soluzione completa.
-
Esercizi, volume 5 · Ricorsione
Esercizi svolti sui capitoli 14--18: ricorsione, equazioni di ricorrenza, Master theorem, algoritmi ricorsivi, ricorsivo e iterativo a confronto. Ogni esercizio ha la soluzione completa.