Laboratorio di algoritmi e strutture dati

Obiettivo del corso è familiarizzare lo studente con la progettazione e l'implementazione di algoritmi e strutture dati. In particolare si vuole dare allo studente la capacità di produrre codice chiaro, modulare, generale ed efficiente attraverso i seguenti passi: analisi del problema, individuazione di una soluzione generale ed efficiente, stesura del codice, documentazione delle scelte effettuate e del codice prodotto.

Dopo un richiamo alle principali strutture dati di base, si procederà allo studio delle rappresentazioni e implementazioni di tipi di dati astratti quali Liste, Pile, Alberi e una panoramica sui Contenitori. Verrà di seguito affrontate la progettazione di librerie di base per Alberi Binari di Ricerca e Code a Priorità, che siano indipendenti dal tipo dei dati in essi contenuti (strutture dati generiche). Verranno illustrate le loro possibili implementazioni, anche in relazione alle Librerie Standard. Successivamente, si tratterà sistematicamente la rappresentazione e implementazione dei grafi e delle tecniche di visita associate. Verranno, inoltre, introdotti e implementati alcuni algoritmi che operano su grafi pesati, come ad esempio l'algoritmo di Dijkstra, quello di Bellman-Ford e tecniche di visita euristica, in particolare l’algoritmo A*. In questo contesto, l'obiettivo generale è quello di progettare e implementare algoritmi e, più in generale, librerie che operino in maniera il più indpendente possibile dalla struttura dati concreta impiegata.