25 Febbraio 2026
- 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.
26 febbraio 2026
- 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 2026
- 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.
5 marzo 2026
- 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 2026
- 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
12 marzo 2026
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 2026
- Il Master Theorem: enunciato
- Il Master Theorem: prova. (Si veda anche CLRS: Sez. 4.6)
19 marzo 2026
- 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 2026
- Algoritmo ricorsivo cubico.
- L'algoritmo di Strassen. struttura generale.
26 marzo 2026
- 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 ).
1 aprile 2026
Esercitazioni sul paradigma Divide-and-Conquer
- Algoritmi Divide and Conquer efficienti per matrici supercircolanti
- L'esponenziazione di operatori associativi: approcci ricorsivi e iterativi
2 aprile 2026
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.
|
