Laboratorio di Algoritmi e Strutture Dati + Laboratorio - a.a. 2011/12

a.a. 2011-2012
Calendario delle lezioni
27/09/2011 Introduzione al corso
29/09/2011 Progettazione di algoritmi. Proprietà di programmi. Principio di astrazione.
04/10/2011 Astrazione funzionale e astrazione di dati. Specifica e realizzazione. Algebre di dati.
06/10/2011 Strutture dati lineari: Liste
06/10/2010 Lab: Introduzione al laboratorio di ASD; Il processo di compilazione di un programma C/C++.
11/10/2011 Pile e code.
11/10/2011 Lab: Object Oriented, dal C al C++. Primi programmi in C++.
13/10/2011 Complessità e algoritmi.
18/10/2011 ComplessitÓ dei problemi. Classi P e NP
18/10/2011 Lab: cenni su implementazione struttura dati lista.
20/10/2011 Quicksort, complessitÓ degli algoritmi di ordinamento, ordinamento di lista
25/10/2011 GeneralitÓ sui Grafi. Alberi radicati. ProprietÓ di alberi. Alberi binari. Algoritmi di visita. alberi binari di ricerca
25/10/2011 Lab: Implementaizone di liste con puntatori
27/10/2011 Alberi AVL. Inserimento e cancelazione con rotazioni
02/11/2011 Alberi n-ari. Algortimi di visita. Esercizi su alberi
03/11/2011 Lab: Liste, code, cenni su alberi binari di ricerca
08/11/2011 Code con prioritÓ. Realizazione con albero e con vettore heap
08/11/2011 Lab: Template e funzioni virtuali, dizionario
10/11/2011 Lab: dizionario implementato con albero binario
17/11/2011 Prova in itinere
22/11/2011 Tabelle hash. Vari esempi di funzioni hash. Discussione della prova in itinere e di altri esercizi.
29/11/2011 Grafi con liste di adiacenza, liste di incidenza, matrice di adiacenza.
29/11/2011 Lab: Grafi.
01/12/2011 Lezione.
06/12/2011 Lezione.
06/12/2011 Lab: strutture dati su SVN.
13/12/2011 Lab: organizzazione repository.
15/12/2011 Lezione.
20/12/2011 Lab.

 

materiale didattico
Informazioni sulla prova d'esame

In questa sezione sono riportate alcune informazioni utili per lo svolgimento della prova d'esame.
Modalità di svolgimento della prova di labortorio: la prova di laboratorio dura 90 minuti. Lo studente deve risolvere un problema che richiede l'uso delle strutture dati studiate durante il corso, suddiviso solitamente in quattro sottoproblemi.
Strumenti per lo svolgimento: lo studente può avvalersi dell'ausilio di libri di testo e deve portare con sé il codice delle librerie che ha creato a casa e/o durante lo svolgimento del corso.
Ambiente di sviluppo e linguaggio: il linguaggio adottato nel corso è il C++. L'ambiente di sviluppo utilizzato in laboratorio per l'esame è Dev C++ ver 4.9.9.2. Per lo sviluppo del repository è consigliato l'uso di Eclipse CDT (dotato di strumenti di sviluppo per il C++), in quanto è necessario disporre di compilatori che supportino il subversioning. Dev C++ non lo supporta.
Valutazione: la valutazione tiene conto dell'implementazione della struttura dati e di come si sono risolti i sottoproblemi. La votazione del laboratorio può essere integrata con domande relative al codice che lo studente presenta all'esame. Per sostenere la prova di laboratorio è opportuno che lo studente porti con sé il codice su penna USB e/o supporto ottico (CD).
Validità del voto: il voto di laboratorio è valido per un massimo di 90 giorni.
Repository e valutazione: gli studenti che collaborano allo sviluppo del repository possono avere un punteggio che si aggiunge al voto di laboratorio.
Prova orale: Per sostenere la prova orale si richiede allo studente di presentare, su carta, il codice delle librerie realizzate comprensivo dei test di funzionamento delle librerie, delle tecniche algoritmiche che si è realizzato per l'esame, e di quanto si ritiene utile per dimostrare che si sono appresi i concetti richiesti per questo corso. È importante stampare le prove di esecuzione dei programmi realizzati per dimostrare il loro funzionamento.

materiale didattico
Dispense
materiale didattico
Codice discusso in aula (si consiglia di accedere al repository per consultare la versione più aggiornata del codice)