Dettagli sull'Insegnamento per l'A.A. 2012/2013

Prerequisiti

Si assume che lo studente abbia acquisito le nozioni di base della programmazione e sia in grado di implementare semplici algoritmi in linguaggio C. Tali prerequisiti sono parte del programma dei corsi di Fondamenti di Programmazione, Laboratorio di Programmazione I e II.

Obiettivi

Il corso di Laboratorio di algoritmi e strutture dati (LASD) si concentra sugli aspetti e sui problemi specifici relativi al progetto di algoritmi e di strutture dati e sullo studio delle diverse tecniche per la loro implementazione ed il loro uso in C. Conoscenze: Strutture dati elementari ed (alcune) avanzate e loro definizione nel linguaggio di programmazione C; principali tecniche di progettazione degli algoritmi; uso delle tecniche per la progettazione di algoritmi e strutture dati per risolvere problemi e implementare soluzioni efficienti in C. Abilità: Al completamento del corso ci si aspetta che lo studente sia in grado di utilizzare le tecniche per la progettazione di algoritmi e strutture dati per risolvere problemi e sappia analizzare le soluzioni (in termini di complessità computazionale e correttezza) ed implementarle in C. Comportamento atteso: Interesse nell'uso del linguaggio C per risolvere problemi e testare le soluzioni al calcolatore.

Sillabo

• Strutture dati fondamentali: liste, stack, code. Implementazione delle operazioni fondamentali per la loro manipolazione. Strutture dati per insiemi disgiunti
• Alberi: rappresentazione in C mediante array e mediante strutture e puntatori; implementazione delle operazioni per la loro manipolazione; visite in ampiezza e profondità
• Implementazione di algoritmi di ricerca ed ordinamento fondamentali su array e liste
• Code con priorità: la struttura dati heap, rappresentazione in C ed implementazione delle operazioni di costruzione e ripristino di uno heap; implementazione mediante heap e loro uso per l'ordinamento
• Alberi binari di ricerca (BST): rappresentazione in C ed implementazione delle operazioni di costruzione e ripristino. BST bilanciati: alberi di ricerca 2-3-4 top-down; alberi red-black
• Grafi: rappresentazioni, implementazione in C di algoritmi di visita e di algoritmi elementari su grafi

Testi di riferimento

• Robert Sedgewick, Algoritmi in C , Addison-Wesley. 2002. terza edizione    
• P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi, Strutture dei dati e algoritmi: Progettazione, analisi e programmazione , Pearson. 2012. seconda edizione    

Modalità d'esame

L'esame consiste in una prova scritta e in un eventuale colloquio orale (a discrezione della docente). Gli studenti immatricolati nell'A.A. 2006/07, o che hanno nel proprio piano di studi il corso integrato da 12 CFU, dovranno sostenere l'esame scritto integrato di Algoritmi e Strutture Dati con Laboratorio.

Risorse Internet

Aggiornamenti alla pagina del corso

• A.A. 2010/2011
• A.A. 2011/2012
• A.A. 2012/2013
• A.A. 2013/2014
• A.A. 2014/2015
• A.A. 2015/2016
• A.A. 2016/2017
• A.A. 2017/2018
• A.A. 2018/2019
• A.A. 2019/2020