27 Febbraio 2023
- Introduzione al corso:
iscrizioni, modalità di esame.
- Presentazione del libro di testo
(CLRS).
- Obiettivi del corso: paradigmi
algoritmici e algoritmi per problemi notevoli.
- Ricapitolazione:
prerequisiti da ripassare (App. A e B e Capp. 1, 2 e 3 del CLRS).
- Definizione di problema, istanza,
taglia di un'istanza e algoritmo che risolve un problema.
- Esempi di specifica di problemi computazionali: somma di interi, raggiungibilità su grafi diretti
28 Febbraio 2023
- Esempi di specifica di problemi computazionali: ordinamento.
- Analisi di un algoritmo: correttezza e complessità
- Complessità in tempo di un algoritmo su
una singola istanza. Metriche riassuntive di complessità: caso peggiore, migliore, medio .
Il paradigma Divide-and-Conquer.
- Proprietà di sottostruttura
6 Marzo 2023
- Algoritmo generale per il Divide-and-Conquer.
- Albero delle Chiamate
- Analisi della correttezza di un algoritmo Divide-and-Conquer con l'induzione (Sez. 4.1, 4.3-4.5 del CLRS)
- Specifica dell'algoritmo MAX per calcolare il massimo di un array di interi.
7 Marzo 2023
- Analisi della correttezza di MAX
- Analisi della complessità di un algoritmo Divide-and-Conquer: ricorrenze.
- Applicazione a MAX della tecnica dell'unfolding.
- Verifica di una ricorrenza e cenni alla tecnica del guess e
induzione parametrica.
13 Marzo 2023
- Induzione parametrica: applicazione a MAX.
- Limiti dell'induzione parametrica.
- Analisi dell'albero della ricorrenza.
Esercitazione su ricorrenze
- Unfolding, induzione parametrica e analisi dell'albero delle chiamate della ricorrenza di Mergesort
14 Marzo 2023
Formula generale per la risoluzione di
un'ampia classe di ricorrenze Divide-and-Conquer.
- Definizione delle funzioni s(n), f(n), w(n).
- Funzioni iterate: definizione e proprietà.
- Informazioni associate ai nodi dell'albero della ricorrenza.
- La formula chiusa.
- Formula generale: esempi di applicazione.
20 Marzo 2023
- Il Master Theorem: enunciato
- Il Master Theorem: prova. (Si veda anche CLRS: Sez. 4.6)
21 Marzo 2023
- Il Master Theorem: estensione a valori arbitrari del parametro
- Il Master Theorem: casi di inapplicabilità
- Il Master Theorem: la condizione di regolarità per polinomi.
Algoritmi per operazioni tra matrici
- Istanze e modello di costo.
- Algoritmi iterativi di somma e sottrazione.
27 Marzo 2023
- Algoritmo di moltiplicazione iterativo
- Algoritmo ricorsivo cubico.
28 Marzo 2023
- L'algoritmo di Strassen. Definizione dei sottoprodotti. Correttezza e
studio della complessità asintotica. (CLRS, Sez. 4.2)
- Risoluzione esatta della ricorrenza associata al'algoritmo di Strassen.
Confronto con l'algoritmo basato sulla definizione.
- Algoritmi ibridi. Applicazione a Strassen.
Ricorrenza parametrica per la determinazione del punto di
transizione tra i due algoritmi. (Controlla il Materiale On-line ).
3 Aprile 2023
Esercitazioni sul paradigma Divide-and-Conquer
- Algoritmi Divide and Conquer efficienti per matrici supercircolanti
- L'esponenziazione di operatori associativi: approcci ricorsivi e iterativi
4 Aprile 2023
I polinomi e la FFT (CLRS, Cap. 30)
- Rappresentazione per coefficienti e rappresentazione per punti.
- Somma e prodotto nella rappresentazione per coefficienti. L'operatore di
convoluzione lineare.
- Somma e prodotto nella rappresentazione per punti.
- Conversioni: valutazione e interpolazione.
- Valutazione: regola di Horner.
- Interpolazione: sistema lineare a matrice di Vandermonde.
17 Aprile 2023
- Interpolazione: formula di
Lagrange. Approccio al calcolo della formula di Lagrange (controlla
il Materiale On-line ).
- La Discrete Fourier
Transform (DFT): definizione.
- Il teorema di convoluzione.
- DFT come operazione di valutazione. DFT inversa. La matrice di Fourier.
- Le radici n-sime dell'unità. Definizione.
18 Aprile 2023
- Radici n-sime: proprietà di gruppo e lemmi di cancellazione, dimezzamento e somma.
- Proprietà di sottostruttura per il calcolo della DFT:
valutazione di un
polinomio di grado limitato da n tramite valutazioni di due polinomi di
grado limitato da n/2.
- FFT: pseudocodice, correttezza e complessità
- Inversa della matrice di Fourier. La
trasformata inversa di Fourier: espressione analitica.
- Approccio al calcolo della trasformata inversa: valutazione
su potenze negative della radice principale n-sima dell'unita'.
2 Maggio 2023
- Calcolo della trasformata inversa tramite il reverse della DFT.
- Calcolo della convoluzione lineare in tempo O(nlog n)
Esercitazioni sulla Trasformata Discreta di Fourier
- Trasformate notevoli.
- Trasformata di vettori (n,k)-sparsi.
- Esponenziazione di polinomi
8 Maggio 2023
La Programmazione Dinamica
- Critica al paradigma divide-and-conquer: problema della mancanza di memoria nella risoluzione di sottoistanze ripetute.
-
Utilizzo di tabelle e risoluzione bottom-up. I numeri di Fibonacci: algoritmo iterativo lineare.
- La memoizzazione di un algoritmo divide-and-conquer: sviluppo e analisi. I numeri di Fibonacci: algoritmo memoizzato.
-
I problemi di ottimizzazione: definizione algebrica.
Caratteristiche generali dei problemi risolvibili con programmazione dinamica: sottostruttura ottima, sottoproblemi ripetuti, spazio dei sottoproblemi ristretto.
- Paradigma generale per lo sviluppo di un algoritmo di programmazione dinamica: proprietà di sottostruttura ottima, scrittura della ricorrenza sui costi, informazione addizionale, risoluzione bottom-up o memoizzata.
9 Maggio 2023
- Stringhe: alfabeto, sottostringhe, prefissi, suffissi, sottosequenze.
- Il problema della Longest Common Subsequence (LCS).
- LCS: Proprietà di sottostruttura ottima
15 Maggio 2023
- LCS: Ricorrenza e sottoproblemi ripetuti, (CLRS, pagg. 350-355).
- LCS: Informazione addizionale.
- LCS: Codice iteratvo bottom-up: sviluoppo e analisi
- LCS: Stampa della LCS.
- LCS: Codice memoizzato e analisi
16 Maggio 2023
- Il problema della Matrix Chain Multiplication (MCM). Definizione, applicazioni, approccio enumerativo esponenziale. (CLRS, pp. 370-378)
- MCM: Proprietà di sottostruttura ottima.
- MCM: Ricorrenza sui costi e informazione addizionale.
- MCM: Sottoproblemi ripetuti
- MCM: Approccio iterativo bottom-up: codifica e analisi.
- MCM: Uso dell'informazione addizionale
22 Maggio 2023
Esercitazioni sulla Programmazione Dinamica
- Allineamento di stringhe di DNA
- Sottosequenza palindroma di lunghezza massima
- Memoizzazione (solo enunciato, da risolvere a casa)
23 Maggio 2023
Il Paradigma Greedy
- Critica alla programmazione dinamica e idea dell'approccio greedy: scelta greedy e risoluzione top-down di un solo sottoproblema.
- Selezione delle attività: Algoritmo ricorsivo top-down lineare e eliminazione della tail recursion: algoritmo iterativo lineare. (Si studi anche l'approccio alternativo di CLRS, pp.415-418.)
29 Maggio 2023
- Selezione delle attività: enunciato e prova delle proprietà di scelta greedy
- Selezione delle attività: enunciato e prova delle proprietà di di sottostruttura ottima
- Introduzione alla compressione dei dati: codici a lunghezza fissa, codici a lunghezza variabile, codici liberi da prefissi (prefix codes).
- Rappresentazione ad albero (trie) dei codici prefissi e formulazione del problema di ottimizzazione su trie
30 Maggio 2023
- Codici di Huffman: idea generale e algoritmo (CLRS, pp. 428-437)
- Codici di Huffman: Proprietà di scelta greedy
- Codici di Huffman: Proprietà di sottostruttura ottima
5 Giugno 2023
Esercitazioni sul Paradigma Greedy
- Masterizzazione compatta di tracce su CD
- (2,1)-boxing
- Shortest-first job scheduling (solo enunciato, da risolvere a casa)
6 Giugno 2023
- Correzione della simulazione di esame
|
