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à.
• Informazioni associate ai nodi dell'albero della ricorrenza.
• La formula chiusa.
• Esempi di applicazione.

• Il Master Theorem: enunciato
• 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

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.
• Algoritmo di Karatsuba: implementazione e analisi.

• Algoritmo di moltiplicazione iterativo
• 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 ).

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.
• 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.
• Lemma di cancellazione.
• Lemma di dimezzamento.
• Lemma 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.
• 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.
• Definizione di convoluzione ciclica.
• Teorema di convoluzione ciclica (enunciato).
• Relazioni tra convoluzione ciclica e convoluzione lineare.

Esercitazioni sulla FFT:

• Tecnica di Bluestein per il calcolo di trasformate di ordine non potenza di due.
• Prodotto di matrici circolanti.
• Risoluzione di un sistema lineare definito da una matrice circolante.

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.
• Caratteristiche generali dei problemi risolvibili con programmazione dinamica: sottostruttura ottima, sottoproblemi ripetuti, spazio dei sottoproblemi ristretto.

• 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.
• 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
• La Longest Increasing Subsequence (LIS) e la tecnica del rafforzamento dei sottoproblemi. (Controlla il Materiale On-line )

• 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.
• 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.
• 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).
• Il problema FORMULA-SAT. Definizione. Riduzione non polinomiale da BC-SAT.

• Riduzione polinomiale da BC-SAT a FORMULA-SAT.
• Il problema 3CNF-SAT. Riduzione da BC-SAT.

• Il problema CLIQUE. Definizione e riduzione da 3CNF-SAT.
• 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.

Esercitazioni su NP completezza

Esercitazioni su NP completezza