Diario delle Lezioni A.A. 2020/21





1 Marzo 2021
  • 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.


3 Marzo 2021
  • Esempi di specifica di problemi computazionali: somma di interi, raggiungibilità su grafi diretti, 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 .


8 Marzo 2021

Il paradigma Divide-and-Conquer.

  • Proprietà strutturale dei problemi risolvibili con Divide-and-Conquer.
  • 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.
  • Analisi della correttezza di MAX


10 Marzo 2021
  • 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.
  • Induzione parametrica: applicazione a MAX.
  • Limiti dell'induzione parametrica.
  • Analisi dell'albero della ricorrenza.


15 Marzo 2021

Esercitazione su ricorrenze

  • Unfolding, induzione parametrica e analisi dell'albero delle chiamate della ricorrenza di Mergesort


17 Marzo 2021

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.


22 Marzo 2021
  • Il Master Theorem: enunciato
  • Il Master Theorem: prova dei tre casi. (Si veda anche CLRS: Sez. 4.6)


24 Marzo 2021
  • 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.
  • Algoritmo di moltiplicazione iterativo


29 Marzo 2021
  • 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.


31 Marzo 2021
  • Algoritmi ibridi. Applicazione a Strassen. Ricorrenza parametrica per la determinazione del punto di transizione tra i due algoritmi. (Controlla il Materiale On-line ).

Esercitazioni su operazioni tra matrici

  • Algoritmi Divide and Conquer efficienti per matrici supercircolanti


7 Aprile 2021

Esercitazioni sul paradigma Divide-and-Conquer

  • L'esponenziazione di operatori associativi: approcci ricorsivi e iterativi

I polinomi e la FFT (CLRS, Cap. 30)

  • Rappresentazione per coefficienti e rappresentazione per punti.
  • Conversioni: valutazione e interpolazione.


12 Aprile 2020
  • Somma e prodotto nella rappresentazione per coefficienti. L'operatore di convoluzione lineare.
  • Somma e prodotto nella rappresentazione per punti.
  • Valutazione: Regola di Horner.
  • Interpolazione: Sistema lineare a matrice di Vandermonde. Formula di Lagrange. Approccio al calcolo della formula di Lagrange (controlla il Materiale On-line ).
  • La Discrete Fourier Transform (DFT): definizione.


14 Aprile 2020
  • Il teorema di convoluzione.
  • DFT come operazione di valutazione. DFT inversa. La matrice di Fourier.
  • Le radici n-sime dell'unità. Definizione.
  • Lemma di cancellazione.
  • Lemma di dimezzamento.
  • Lemma di somma.


19 Aprile 2021
  • 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'.
  • Calcolo della trasformata inversa tramite il reverse della DFT.
  • Teorema di convoluzione lineare e calcolo in tempo O(nlog n)


21 Aprile 2021

Esercitazioni sulla Trasformata Discreta di Fourier

  • Trasformate notevoli.
  • Trasformata di vettori (n,k)-sparsi.
  • Esponenziazione di polinomi


26 Aprile 2021

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.


28 Aprile 2021
  • Stringhe: alfabeto, sottostringhe, prefissi, suffissi, sottosequenze.
  • Il problema della Longest Common Subsequence (LCS).
  • LCS: Proprietà di sottostruttura ottima


3 Maggio 2021
  • 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


5 Maggio 2021
  • 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


10 Maggio 2021

Esercitazioni sulla Programmazione Dinamica

  • Allineamento di stringhe di DNA
  • Sottosequenza palindroma di lunghezza massima
  • Memoizzazione


12 Maggio 2021

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.)


17 Maggio 2021
  • 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


19 Maggio 2021
  • 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.


24 Maggio 2021

Esercitazioni sul Paradigma Greedy

  • Masterizzazione compatta di tracce su CD
  • Shortest-first job scheduling
  • (2,1)-boxing


31 Maggio 2021

Correzione della simulazione di esame





Ultimo aggiornamento: 18 maggio 2021 Vai alla pagina iniziale