Diario delle Lezioni A.A. 2023/24





26 Febbraio 2024
  • 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.
  • Esempi di specifica di problemi computazionali: ordinamento.


28 Febbraio 2024
  • 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


4 Marzo 2024
  • 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.


6 Marzo 2024
  • 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.


11 Marzo 2024
  • 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


13 Marzo 2024

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.


18 Marzo 2024
  • Il Master Theorem: enunciato
  • Il Master Theorem: prova. (Si veda anche CLRS: Sez. 4.6)


20 Marzo 2024
  • 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


25 Marzo 2024
  • Algoritmo ricorsivo cubico.
  • L'algoritmo di Strassen. struttura generale.


27 Marzo 2024
  • 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 2024

Esercitazioni sul paradigma Divide-and-Conquer

  • Algoritmi Divide and Conquer efficienti per matrici supercircolanti
  • L'esponenziazione di operatori associativi: approcci ricorsivi e iterativi


8 Aprile 2024

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.


10 Aprile 2024
  • 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.
  • Radici n-sime: proprietà di gruppo e lemmi di cancellazione, dimezzamento e somma.


Ultimo aggiornamento: 27 marzo 2024 Vai alla pagina iniziale