11929 - ALGORITMI E STRUTTURE DATI (CL.A)

Conoscenze e abilità da conseguire

Al termine del corso, lo studente conosce: - gli algoritmi per risolvere problemi computazionali di base su strutture dati elementari; - le tecniche di base per calcolare il costo computazionale degli algoritmi; - le classi di complessità computazionale P, NP e NP-hard. In particolare, lo studente è in grado di: - progettare algoritmi efficienti per risolvere semplici problemi computazionali; - stimare in ordine di grandezza il costo computazionale degli algoritmi; - analizzare la complessità computazionale di problemi computazionali di base; - dare una valutazione circa l'efficienza e la correttezza di un algoritmo; - elaborare e presentare un progetto per la risoluzione di problemi computazionali di base.

Contenuti

- matematica discreta elementare per calcolare gli ordini di grandezza; - Algoritmi di ordinamento; - Mediano e selezione; - Strutture dati elementari: pile, code, alberi, grafi - algoritmi di visita su grafi - algoritmi di base su grafi -classi P e NP -problemi NP-Hard

Testi/Bibliografia

Introduzione agli Algoritmi e Strutture Dati. Terza Edizione

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein

McGraw-Hill

Metodi didattici

Lezioni ed esercitazioni frontali

Modalità di verifica e valutazione dell'apprendimento

Prova scritta obbligatoria e prova orale facoltativa. Lo studente o la studentessa possono sempre scegliere di sostenere la prova orale facoltativa e il docente può richiedere il sostenimento della prova orale quando lo ritenga opportuno per una accurata verifica dell’apprendimento.
Per accedere alla prova scritta è obbligatorio lo svolgimento ed il superamento (senza attribuzione di un punteggio) di una prova pratica di laboratorio assegnata durante il corso e da svolgere a casa. Su Virtuale è possibile trovare i dettagli relativi alla esecuzione e consegna delle prove pratiche.
La frequenza delle lezioni non influenza il voto finale e non è obbligatoria per sostenere le prove di verifica.
La prova scritta consiste nella risoluzione di un numero di esercizi che va da 2 a 4. Il voto finale sarà la somma dei voti ottenuti nei singoli esercizi. Per ogni esercizio sarà esplicitamente indicato il punteggio massimo ottenibile. Se il voto finale risulterà maggiore di 30 si otterrà la lode. La durata della prova varia a seconda della difficoltà di risoluzione degli esercizi da 2 a 3 ore. Durante la prova scritta è ammesso l’utilizzo di qualunque materiale cartaceo (libri, dispense, appunti). Non è ammesso accedere al web con dispositivi elettronici. Per svolgere la prova scritta è necessario iscriversi entro i termini indicati su almaesami.
Lo scopo della prova pratica, dello scritto e dell’eventuale prova orale è verificare la capacità dello studente o della studentessa di progettare algoritmi efficienti per risolvere semplici problemi computazionali, di stimare in ordine di grandezza il costo computazionale degli algoritmi, di analizzare la complessità computazionale di problemi computazionali di base e di dare una valutazione circa l'efficienza e la correttezza di un algoritmo. La gradazione del voto sarà proporzionale alle capacità dimostrate dallo studente durante le prove di verifica e potrà variare da 0 a 30 e lode. Lo studente che ottiene un voto inferiore al 18 non avrà superato la prova e lo studente che ottiene un voto superiore a 17 ha comunque la possibilità di rifiutarlo e di ripresentarsi all’appello di esame successivo.

Strumenti a supporto della didattica

Lucidi e Libro di testo

Orario di ricevimento

Consulta il sito web di Luciano Margara

Consulta il sito web di Moreno Marzolla