Dettagli sull'Insegnamento per l'A.A. 2012/2013
Nome:
Laboratorio di Algoritmi e Strutture Dati / Lab. of Algorithms and Data Structures
Informazioni
Erogazione:
Laurea Base in Informatica 2° anno curriculum Generale Obbligatorio
Lingua:
Italiano
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.
Aggiornamenti alla pagina del corso
Le informazioni sulle editioni passate di questo corso sono disponibili per i seguenti anni accademici:
Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo.
Ultimo aggiornamento delle informazioni sul corso: 24 aprile 2013, 16:09