26 Settembre 2016
- 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.(Controlla il Materiale On-line ).
- Complessità in tempo di un algoritmo su
una singola istanza. Definizione della complessità al caso migliore,
medio e peggiore. Analisi di un algoritmo: correttezza e complessità.
28 Settembre 2016
Il paradigma Divide-and-Conquer.
- Proprietà strutturale dei problemi
risolvibili con Divide-and-Conquer.
- Algoritmo generale per il Divide-and-Conquer.
- Albero delle Chiamate di un algoritmo Divide-and-Conquer.
- Fase di generazione top-down e di risoluzione bottom-up.
- 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.
29 Settembre 2016
- Analisi della correttezza di MAX basata sull'induzione.
- 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.
- Introduzione all'induzione parametrica.
- Induzione parametrica: applicazione a MAX.
- Limiti dell'induzione parametrica.
5 Ottobre 2016
- Analisi dell'albero della ricorrenza.
Formula generale per la risoluzione di
un'ampia classe di ricorrenze Divide-and-Conquer. (Controlla il
Materiale On-line )
- Definizione delle funzioni s(n), f(n), w(n).
- Funzioni iterate: definizione e proprietà.
6 Ottobre 2016
- Informazioni associate ai nodi dell'albero della ricorrenza.
- La formula chiusa.
- Esempi di applicazione.
- Il Master Theorem: enunciato
10 Ottobre 2016
- Il Master Theorem: prova. (Si veda anche CLRS: Sez. 4.6)
- Il Master Theorem: casi di inapplicabilità
- Il Master Theorem: la condizione di regolarità per polinomi.
- L'estensione a valori arbitrari del parametro
12 Ottobre 2016
Algoritmi per aritmetica intera (Controlla il Materiale On-line )
- Istanze e modello di costo.
- Operazioni lineari: somma e sottrazione.
- Prodotto per una potenza della base.
- Algoritimo di moltiplicazione elementare quadratico.
- Algoritmo ricorsivo di moltiplicazione quadratico.
13 Ottobre 2016
- Algoritmo di Karatsuba: implementazione e analisi.
Algoritmi per operazioni tra matrici
- Istanze e modello di costo.
- Algoritmi iterativi di somma e sottrazione.
- Algoritmo di moltiplicazione iterativo
20 Ottobre 2016
- Algoritmo ricorsivo cubico.
- 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.
- Ibridizzazione di due algoritmi. Applicazione a Strassen.
Ricorrenza parametrica per la determinazione del punto di
transizione tra i due algoritmi. (Controlla il Materiale On-line ).
19 Ottobre 2016
I polinomi e la FFT (CLRS, Cap. 30)
- Rappresentazione per coefficienti e rappresentazione per punti.
- Conversioni. Valutazione: regola di Horner.
-
Interpolazione: matrice di Vandermonde. Formula di
Lagrange. Approccio al calcolo della formula di Lagrange (controlla
il Materiale On-line ).
- Somma e prodotto nella rappresentazione per coefficienti. L'operatore di
convoluzione lineare.
20 Ottobre 2016
- Somma e prodotto nella rappresentazione per punti. Rappresentazione
estesa.
- La Discrete Fourier
Transform (DFT): definizione.
- DFT come operazione di
valutazione. DFT inversa. La matrice di Fourier.
- Il teorema di convoluzione lineare
- Le radici n-sime dell'unità. Definizione e
proprietà di gruppo.
24 Ottobre 2016
- Lemma di cancellazione.
- Lemmi di dimezzamento e di somma.
- Proprietà di sottostruttura per il calcolo della DFT: valutazione di un
polinomio di grado n tramite valutazioni di due polinomi di
grado n/2.
- FFT: pseudocodice, correttezza e complessità
- Inversa della matrice di Fourier. La
trasformata inversa di Fourier: espressione analitica.
26 Ottobre 2016
- Approccio al calcolo della trasformata inversa: valutazione
su potenze negative della radice principale n-sima dell'unita'.
- Calcolo della trasformata inversa tramite la FFT.
- L'algoritmo di Cooley-Tukey per trasformate di ordine n = p x q (controlla
il Materiale On-line ).
- Derivazione dell'algoritmo di FFT per n potenza di due
dall'algoritmo di Cooley-Tukey.
- Esercizio: Uso della decomposizione di Cooley-Tukey nel trasformare vettori (n,k)-sparsi.
27 Ottobre 2016
- Definizione di convoluzione ciclica.
- Teorema di convoluzione ciclica (enunciato).
- Relazioni tra convoluzione ciclica e convoluzione lineare.
- Esponenziazione efficiente e applicazione ai polinomi.
2 Novembre 2016
Esercitazioni sulla FFT:
- Prodotto di matrici circolanti.
- Risoluzione di un sistema lineare definito da una matrice circolante.
- Determinazione dell'inversa di una matrice circolante.
3 Novembre 2016
La Programmazione Dinamica (CLRS, Cap. 15)
- Critica al paradigma
divide-and-conquer: problema della mancanza di memoria nella
risoluzione di sottoistanze ripetute. I numeri di Fibonacci:
algoritmo divide-and-conquer esponenziale.
- 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.
Analisi basata sull'albero delle chiamate.
- I problemi di ottimizzazione: definizione algebrica.
7 Novembre 2016
- 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, risoluzione bottom-up e informazione
addizionale.
- Il problema della Matrix Chain Multiplication (MCM).
Definizione, applicazioni, approccio enumerativo esponenziale.
- MCM: Proprietà di sottostruttura ottima.
9 Novembre 2016
- MCM: Ricorrenza sui costi e informazione addizionale.
- MCM: Algoritmo divide-and-conquer esponenziale.
- MCM: Approccio iterativo bottom-up: codifica e analisi.
- MCM: Codice memoizzato: codifica.
10 Novembre 2016
- MCM: Codice memoizzato: analisi.
- MCM: Algoritmo di moltiplicazione a catena ottimo
- Stringhe: alfabeto, sottostringhe, prefissi, suffissi,
sottosequenze.
- Il problema della Longest Common
Subsequence (LCS). Proprietà di sottostruttura
ottima: intuizione e enunciato.
14 Novembre 2016
- LCS: Proprietà di sottostruttura ottima: prova.
- LCS: Ricorrenza e sottoproblemi ripetuti, (CLRS, pagg. 350-355).
- LCS: Informazione addizionale.
- LCS: Codice iterativo bottom-up e stampa della LCS.
- LCS: Codice memoizzato e analisi
17 Novembre 2016
- La Longest Increasing Subsequence (LIS) e la
tecnica del rafforzamento dei sottoproblemi. (Controlla il
Materiale On-line )
- LIS: proprietà di sottostruttura ottima
- LIS: informazione addizionale, codice iterativo e
stampa della LIS.
21 Novembre 2016
Esercitazioni sulla Programmazione Dinamica:
- Ottenere la LIS utilizzando l'algoritmo per la LCS
- La Longest Palindrome Substring di una stringa: proprietà di sottostruttura,
ricorrenza, informazione addizionale, codice bottom-up e risparmio di spazio.
- La Divisione a catena di costo massimo: proprietà di sottostruttura, ricorrenza, informazione addizionale e codice bottom-up.
23 Novembre 2016
Il paradigma Greedy (CLRS, Cap. 16)
- 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. Errata per la seconda edizione del CLRS scarica le
pagine corrette ).
- Selezione delle attività: enunciato e prova delle proprietà di scelta greedy
24 Novembre 2016
- Selezione delle attività: enunciato e prova delle proprietà di di sottostruttura ottima
- Esercizio: Scelte greedy non corrette per la selezione delle attività
- 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.
- Compressione come problema di ottimizzazione su trie.
28 Novembre 2016
- Teorema: un codice prefisso ottimo corrisponde a un albero pieno.
- Codici di Huffman: idea generale e algoritmo.
- Codici di Huffman: Proprietà di scelta greedy.
- Codici di Huffman: Proprietà sottostruttura ottima.
30 Novembre 2016
- Valutazione della didattica in presenza
Esercitazioni sul Paradigma Greedy
- Copertura minima di punti con intervalli unitari: algoritmo greedy e analisi.
- Determinazione del (2,1)-packing ottimo.
1 Dicembre 2016
NP Completezza (CLRS, Cap. 34)
- Classi di problemi:
problemi indecidibili, intrinsecamente esbponenziali, intrattabili, polinomiali.
- Problemi astratti e problemi decisionali. Riduzione da problemi di
ottimizzazione a problemi decisionali. Esempio: SHORTEST UNWEIGHTED PATH.
- Il problema dell'encoding: problemi astratti e problemi concreti.
5 Dicembre 2016
- Encoding ragionevoli.
- Linguaggi formali. Definizioni e operazioni. Problemi concreti e
linguaggi associati.
- Decisione di un linguaggio in tempo polinomiale: la classe P: definizione.
- Verificabilità in tempo polinomiale: introduzione.
- Algoritmo di verifica per HAMILTON.
- Verificabilità in tempo polinomiale: definizione.
7 Dicembre 2016
- La classe NP. Teorema: P è un sottoinsieme di NP.
- Riducibilità in tempo polinomiale.
- Caratteristiche delle funzioni di riduzione.
- Teorema: Se L1 < L2 e L2 è in P, allora L1 è in P.
12 Dicembre 2016
- Le classi NPH e NPC.
- Corollario: se L e' sia in NPC che in P, allora P=NP.
- Il problema BC-SAT. Definizione.
- Il teorema di Cook: 1) Algoritmo di verifica polinomiale per BC-SAT.
2) Riduzione di ogni linguaggio in NP a BC-SAT (idea).
14 Dicembre 2016
- Il problema FORMULA-SAT. Definizione. Riduzione non polinomiale da BC-SAT.
- Definizione e riduzione polinomiale da BC-SAT a FORMULA-SAT.
15 Dicembre 2016
- Il problema 3CNF-SAT. Riduzione da BC-SAT.
- Il problema CLIQUE. Definizione e riduzione da 3CNF-SAT.
19 Dicembre 2016
- Il problema VERTEX-COVER. Definizione e riduzione da CLIQUE.
- Il problema INDEPENDENT-SET. Definizione e riduzione da CLIQUE.
- Il problema SUBSET SUM. Definizione e riduzione da 3CNF-SAT.
21 Dicembre 2016
Esercitazioni su NP completezza
22 Dicembre 2016
Esercitazioni su NP completezza
9 Gennaio 2017
Esercitazioni
- Ricorrenze: uso della formula generale
- Ricorrenze: induzione parametrica
- DFT di vettori z-exp-spaced
- Definizione del problema di Longest Palindrome Subsequence (LPS)
11 Gennaio 2017
Esercitazioni
- LPS: risoluzione con il paradigma di programmazione dinamica
- IL problema dell'epsilon-diradamento: algoritmo greedy
|
