Algoritmi¶
Materiale didattico ideato e sviluppato da Fabio Furini, professore associato al DIAG, Sapienza Università di Roma.
Le dispense del corso, online, in cinque parti: algoritmi di base (rappresentazione dei numeri, pseudocodice, ordinamento, ricerca, algoritmi numerici), linguaggi di programmazione (C++, Python e Java), notazione e crescita asintotica, analisi degli algoritmi (tempo di esecuzione e correttezza) e ricorsione (equazioni di ricorrenza, Master theorem e algoritmi ricorsivi), con definizioni, teoremi con le loro dimostrazioni, pseudocodice, esempi eseguiti passo per passo, notebook Colab in Python, C++ e Java ed esercizi con le soluzioni.
Comincia dagli algoritmi di base Gli esercizi Esplora il laboratorio interattivo Scarica le dispense (PDF)
Come è organizzato ogni capitolo¶
Ogni capitolo è una delle note del corso, con gli stessi numeri e gli stessi colori della dispensa: sul sito e nel PDF trovi tutto allo stesso posto.
Definizione
Il significato preciso di un concetto nuovo.
Teorema, proposizione, osservazione
Un risultato da ricordare, con le sue ipotesi.
Esempio
Un calcolo svolto per intero, un passo alla volta.
In verde il punto chiave da portare a casa.
Algoritmo
Lo pseudocodice, con le righe numerate come nella dispensa.
Codice
I programmi in C++, Python e Java nei capitoli dei linguaggi; gli algoritmi si eseguono nei notebook Colab, con i pulsanti sotto lo pseudocodice.
Dimostrazione — si apre con un clic
Le dimostrazioni ci sono tutte, ma chiuse: prima leggi l'enunciato, poi apri la dimostrazione quando vuoi studiarla. Lo stesso vale per le soluzioni degli esercizi.
Le parti del corso¶
-
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.
1. Rappresentazione dei numeri · 2. Pseudocodice · 3. Algoritmi di ordinamento · 4. Ricerca lineare e binaria · 5. Algoritmi numerici
-
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.
6. Introduzione a C++ · 7. Introduzione a Python · 8. Introduzione a Java
-
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.
9. Notazione asintotica · 10. Crescita asintotica
-
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.
11. Dimensione dell'input · 12. Tempo di esecuzione · 13. Correttezza
-
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.
14. Ricorsione · 15. Equazioni di ricorrenza · 16. Il Master theorem · 17. Algoritmi ricorsivi · 18. Algoritmi ricorsivi e iterativi a confronto
Da non perdere¶
-
Esercizi con le soluzioni
Esercizi per ogni capitolo, ciascuno con la soluzione svolta che si apre con un clic.
-
Laboratorio interattivo
Esegui gli algoritmi un passo alla volta: ordinamento, ricerca, Euclide e crivello, bit dei numeri, crescita delle funzioni, alberi di ricorsione e Master theorem.
-
Notebook in Python, C++ e Java
Gli algoritmi di ogni capitolo da eseguire in Google Colab, nel linguaggio che preferisci.
-
Dispense ed eserciziari in PDF
Cinque volumi di dispense e cinque eserciziari, con la stessa numerazione del sito.
-
Indice completo
Tutti i capitoli con le loro sezioni, in una pagina.
Dello stesso autore:
- Programmazione lineare — poliedri, algoritmo del simplesso, dualità e simplesso duale, con il laboratorio interattivo;
- Ottimizzazione convessa — insiemi e funzioni convesse, problemi di ottimizzazione convessa, con grafici interattivi;
- Programmazione lineare intera — rilassamento continuo, disuguaglianze valide, piani di taglio, branch-and-bound e branch-and-cut;
- Ottimizzazione combinatoria — zaino, bin packing, colorazione, TSP, scheduling e lot sizing, risolti in tutti i modi;
- Ottimizzazione su reti — grafi, alberi ricoprenti, cammini minimi, flussi su reti, simplesso su reti e gestione dei progetti;
- Modellazione MIP — modelli di programmazione lineare a variabili intere, dalla formulazione alla soluzione con i solver;
- Laboratorio di Ricerca Operativa — modellazione e risoluzione di problemi di ottimizzazione con Python e i solver;
- Analisi Matematica 1 — numeri reali, funzioni, limiti, derivate e serie, con i grafici interattivi;
- Algebra lineare — vettori, matrici, determinanti, sistemi lineari e autovalori, con il laboratorio di calcolo.
Materiale didattico di Fabio Furini — DIAG, Sapienza Università di Roma.
This website is also available in English.
Ulteriori materiali didattici, incluse le slide delle lezioni, saranno disponibili a breve.