- Introduzione agli argomenti del corso. Richiami: definizione di
problema e algoritmo; modello computazionale; modello di costo; uso
dello pseudolinguaggio
- Il paradigma divide-and-conquer:
- Caratteristiche generali e strumenti per l'analisi;
- Casi di studio:
- Moltiplicazione di interi: algoritmo di Karatsuba;
- Moltiplicazione di matrici: algoritmo di Strassen;
- Moltiplicazione di polinomi: la Fast Fourier Trasform.
- Il paradigma dynamic programming:
- Caratteristiche generali: sottoproblemi ripetuti e tecniche di risoluzione;
- Casi di studio:
- Algoritmo di Matrix-chain multiplication;
- Problemi su stringhe: Longest Common Subsequence.
- Il paradigma greedy:
- Problemi risolvibili con l'approccio greedy e tecniche di risoluzione;
- Casi di studio:
- Il problema della selezione di attività
- I codici di Huffman per la compressione dei dati.
- La teoria della NP-Completezza:
- Classi di complessità P, NP, co-NP e NPC;
- Tecniche di riducibilità in tempo polinomiale e riduzioni notevoli.
|
