Algoritmi per l'Ingegneria
Formulario della materia 52 definizioni e teoremi in una pagina
Argomenti
1Problemi computazionali e analisi degli algoritmi
2Il paradigma divide & conquer
- Divide and conquer - proprietà di sottostruttura e albero delle chiamate
- Induzione parametrica - limitazioni esatte delle ricorrenze
- Albero della ricorrenza e formula generale per le ricorrenze
- Master Theorem - enunciato, casi e applicazioni
Esercizi svolti
- Esercizio - algoritmo ibrido con soglia ottima e confronto con la versione ricorsiva (compito del 4 settembre 2024, es. 1) Esame
- Esercizio - algoritmo ibrido e valore ottimo della soglia (compito del 27 gennaio 2025, es. 1) Esame
- Esercizio - due elementi più piccoli di una stringa con divide and conquer (simulazione d'esame 2023-24, problema 1)
- Esercizio - induzione parametrica con parti intere e limite lineare (compito del 9 luglio 2025, es. 1) Esame
- Esercizio - ricorrenza con parti intere, Master Theorem e induzione parametrica (simulazione d'esame 2025-26, es. 1)
- Esercizio - ricorrenza con sottoistanze di taglia metà e un quarto, forma chiusa e profondità delle foglie (compito del 5 settembre 2025, es. 1) Esame
3Moltiplicazione di matrici
- Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchi
- Algoritmo di Strassen e ibridazione
- Matrici circolanti e supercircolanti - algoritmi divide and conquer
- Esponenziazione veloce per quadrature successive
Esercizi svolti
- Esercizio - algoritmo di Strassen sulle matrici supercircolanti (esercizi su supercircolanti e circolanti, es. SC 6)
- Esercizio - domande di prima parte su moltiplicazione di matrici (simulazioni d'esame) Esame
- Esercizio - elemento (h,k) di una matrice supercircolante (esercizi su supercircolanti e circolanti, es. SC 5)
- Esercizio - matrici ARB, prodotto con tre chiamate ricorsive (compito del 19 giugno 2024, es. 1) Esame
- Esercizio - matrici RCA, somma e prodotto matrice-vettore (compito del 18 giugno 2026, es. 1) Esame
- Esercizio - matrici SIR, somma, prodotto e inversa (compito del 29 gennaio 2026, es. 1) Esame
- Esercizio - prodotto di matrici circolanti e convoluzione ciclica con la DFT (esercizi su supercircolanti e circolanti, es. CR 10)
- Esercizio - prodotto di matrici complesse, ricorrenza e induzione parametrica (compito del 8 luglio 2024, es. 1) Esame
4Polinomi e FFT
- Polinomi - rappresentazione per coefficienti e per valori e convoluzione
- DFT, matrice di Fourier e radici n-esime dell'unità
- Fast Fourier Transform - algoritmo ricorsivo e trasformata inversa
- Trasformate notevoli ed esponenziazione di polinomi con la FFT
Esercizi svolti
- Esercizio - convoluzione con il vettore delle potenze di due in tempo lineare (compito del 5 settembre 2025, es. 2) Esame
- Esercizio - domande di prima parte su polinomi, DFT e FFT (simulazioni d'esame) Esame
- Esercizio - matrice di Fourier per una matrice generica a sinistra e a destra e per aI + bU (compito del 27 gennaio 2025, es. 2) Esame
- Esercizio - matrice V per V trasposta con V di Vandermonde, formula degli elementi e calcolo in tempo quadratico (compito del 4 settembre 2024, es. 2) Esame
- Esercizio - polinomio con tutte le radici dell'unità tranne 1 e -1, valutazione e DFT dei coefficienti (compito del 26 giugno 2025, es. 1) Esame
5Programmazione dinamica
- Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma
- Longest Common Subsequence - ricorrenza, tabella e ricostruzione
- Matrix Chain Multiplication - parentesizzazione ottima
Esercizi svolti
- Esercizio - costo alternato minimo e massimo di una sottosequenza (simulazione d'esame 2025-26, es. 2)
- Esercizio - domande di prima parte su programmazione dinamica (simulazioni d'esame) Esame
- Esercizio - funzione g(n) definita per ricorrenza, calcolo memoizzato e formula chiusa (compito del 19 giugno 2024, es. 2) Esame
- Esercizio - ricorrenza c(i,j) con bordi dati da due array, calcolo iterativo e spazio lineare (compito del 18 giugno 2026, es. 2)
- Esercizio - ricorrenza c(i,j) con valore di default e conteggio delle operazioni (simulazione d'esame 2023-24, problema 2)
- Esercizio - ricorrenza t(i,j) con calcolo memoizzato e conteggio esatto (compito del 26 giugno 2025, es. 2)
6Programmazione dinamica su stringhe
7Il paradigma greedy
- Paradigma greedy - scelta golosa, sottostruttura e selezione delle attività
- Codifica di Huffman - codici prefissi, algoritmo e ottimalità
- Esercitazione greedy - tracce su CD, scheduling shortest-first e (2,1)-boxing
Esercizi svolti
- Esercizio - (2,1)-boxing di oggetti, scelta greedy e ottimalità (esercitazione greedy, es. 10.3)
- Esercizio - codice di Huffman con frequenze in progressione geometrica, trie e codeword (compito del 29 gennaio 2026, es. 2) Esame
- Esercizio - domande di prima parte su greedy e Huffman (simulazioni d'esame) Esame
- Esercizio - masterizzazione compatta di tracce su CD, scelta greedy e ottimalità (esercitazione greedy, es. 10.1)
- Esercizio - shortest-first job scheduling, proprietà SJF e sottostruttura (esercitazione greedy, es. 10.2)