Algoritmi e Strutture Dati

Obiettivi

Il modulo di Algoritmi e Strutture Dati è suddiviso in due parti. Nella prima verrà illustrata la teoria che permette di valutare la qualità di un algoritmo, che sarà poi approfondita con alcuni esempi pratici. La seconda sarà dedicata alle strutture dati più comuni, utilizzate nell’ambito della programmazione. Per ognuna di queste saranno mostrati gli algoritmi per le operazioni fondamentali, i quali saranno valutati con le tecniche apprese nella prima parte del corso. Quanto discusso durante il corso sarà approfondito con delle lezioni in laboratorio, attraverso le quali gli studenti potranno mettere in pratica quanto appreso.

Contenuti

  1. Complessità Computazionale, limiti asintotici e teorema fondamentale
  2. Algoritmi di ordinamento e metodo “divide et impera”: bubble sort, merge sort e quick sort.
  3. Programmazione dinamica
  4. Collezioni: array, liste, code, stack e tabelle hash
  5. Alberi: alberi binari e heap
  6. Grafi: visite in ampiezza e profondità, alberi di connessione tramite gli algoritmi di Kruskal e di Primm e algoritmo dei cammini minimi di Dijkstra.