Programma




Prerequisiti

  1. Introduzione alla programmazione (e.g., Fondamenti di Informatica)
  2. Strutture di dati elementari e analisi asintotica (e.g., Dati e Algoritmi 1)

Conoscenze e abilità da acquisire

  1. Competenze di problem-solving computazionale.
  2. Capacità di affrontare il processo di risoluzione di un problema computazionale con strumenti rigorosi basati su alcuni paradigmi algoritmici generali.
  3. Conoscenza di primitive algoritmiche di largo utilizzo nel dominio dell'ingegneria dell'informazione.

Programma del corso

  1. Introduzione agli argomenti del corso. Richiami: definizione di problema e algoritmo; modello computazionale; modello di costo; uso dello pseudolinguaggio

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


  3. 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;


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



Ultimo aggiornamento: 11 Febbraio 2019 Vai alla pagina iniziale