Ingegneria degli Algoritmi

Anno Accademico 2020/2021

Informazioni generali

Il corso verrà tenuto dai Proff. Salvatore Filippone e Alessandro Pellegrini.

A causa delle restrizioni sull’utilizzo delle aule, il corso verrà erogato a distanza sulla piattaforma Teams di ateneo. Per accedere al team del corso, fare clic su Crea e partecipa al team sotto all’elenco dei team e cercare la scheda Partecipa a un team con un codice. Il codice del corso è sv1ehq1.

Per problemi o malfunzionamenti, inviare una mail al Prof. Alessandro Pellegrini.

News

• Orari delle lezioni:
  • Lunedì, 14.00-15.30
  • Mercoledì, 9.30-11.00
• Nell’anno accademico 2019/2020 il corso è passato da 9 CFU a 6 CFU. Chi avesse la necessità di sostenere l’esame da 9 CFU (unicamente per gli studenti degli anni accademici precedenti) contatti via email il docente.

Obiettivi del corso

• Prendere confidenza con la progettazione e l’analisi di algoritmi
• Capire come si misura l’efficienza degli algoritmi e delle strutture dati
• Imparare a scegliere quale algoritmo è più conveniente utilizzare per risolvere problemi del mondo reale
• Implementare algoritmi e strutture dati in Python

Regole d’esame

• L’esame consiste in una prova scritta
• La prova scritta conterrà sia domande teoriche che domande pratiche

Libro di testo consigliato

Alan A. Bertossi, Alberto Montresor. Algoritmi e strutture di dati.
CittàStudi, 2014.
ISBN: 978-8825173956

Programma del corso (preliminare)

Le slide e gli esempi di codice verranno pubblicati sul canale Teams durante il corso

• Introduzione
  • Definizioni di base
  • Esempi di applicazioni di algoritmi
  • Problema del sottovettore di somma massimale
  • Efficienza di un algoritmo
• Analisi della complessità e tecniche algoritmiche
  • Modelli di calcolo
  • Ricorsione e relazioni di ricorrenza
  • Divide et impera
  • Analisi asintotica
  • Analisi delle ricorrenze
  • Analisi ammortizzata
  • Programmazione dinamica
  • Algoritmi Greedy
  • Backtracking
• Il problema dell’ordinamento
  • Stupid sort, selection sort, bubble sort, insertion sort, merge sort, bucket sort, quick sort, radix sort
  • Proprietà degli algoritmi di ordinamento
  • Complessità computazionale del problema dell’ordinamento
• Strutture dati di base
  • Tipi di dato astratto e Abstract Base Classes
  • Liste
  • Pile
  • Code
• Strutture dati avanzate
  • Coda di priorità
  • Alberi
  • Heap
• Tecniche di Hashing
• Grafi e algoritmi sui grafi
  • Visita di un grafo
  • Ordinamento topologico
  • Cammini minimi
  • Minimo albero ricoprente