Prerequisiti
|
- Introduzione alla programmazione (e.g., Fondamenti di Informatica)
- Strutture di dati elementari e analisi asintotica (e.g., Dati e Algoritmi 1)
|
Conoscenze e abilità da acquisire
|
- Competenze di problem-solving computazionale.
- Capacità di affrontare il processo di risoluzione di un problema computazionale con strumenti rigorosi basati su alcuni paradigmi algoritmici generali.
- Conoscenza di primitive algoritmiche di largo utilizzo nel dominio dell'ingegneria dell'informazione.
|
Programma del corso
|
- 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 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:
- Problemi su stringhe: Longest Common Subsequence.
- Moltiplicazione ottima di catene di matrici rettangolari;
- 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.
|
