37635 - ALGORITMI E STRUTTURE DI DATI

Scheda insegnamento

SDGs

L'insegnamento contribuisce al perseguimento degli Obiettivi di Sviluppo Sostenibile dell'Agenda 2030 dell'ONU.

Istruzione di qualità

Anno Accademico 2020/2021

Conoscenze e abilità da conseguire

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

Contenuti

Progettazione e analisi di algoritmi. Complessita' computazionale. Ordini di grandezza. Equazioni di ricorrenza lineari di ordine costante e con partizione bilanciata. Limitazioni inferiori. Strutture di dati. Vettori, record e matrici. Liste, pile e code. Alberi. Visite di alberi (anticipata, simmetrica, differita, per livelli.) Insiemi. Dizionari. Ricerca binaria e per interpolazione. Tabelle hash. Code con priorita'. Heap. Alberi bilanciati di ricerca. Alberi red-black. MFSET. Grafi. Visite DFS e BFS. Tecniche di progettazione: divide-et-impera, backtrack, greedy, ricerca locale, programmazione dinamica, randomizzazione. Algoritmi di ordinamento: Mergesort, Countingsort, Heapsort, Quicksort, Shellsort. Algoritmi su grafi: Minimum Spanning Tree (Prim, Kruskal), Cammini Minimi (Bellman-Ford, Dijkstra, Floyd-Wharshall). Complessita'. Le classi P ed NP. NP-completezza.

Il corso include inoltre un modulo di laboratorio durante il quale si implementano e usano le strutture di dati presentate nel modulo di teoria. Si introdurrà inoltre il paradigma di programmazione Object-Oriented e alcune nozioni base sul linguaggio Java.

Testi/Bibliografia

Libro di testo:

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Algoritmi e strutture dati
McGraw-Hill - seconda edizione. 2008.

Libri consigliati:

A.A. Bertossi & A. Montresor, Algoritmi e Strutture di Dati, Citta' Studi Edizioni, Torino. Terza edizione. 2014.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Introduzione agli algoritmi e strutture dati
McGraw-Hill - terza edizione. 2010

 

Metodi didattici

Il corso si svolge nel secondo semestre ed è strutturato in lezioni frontali in aula, comprendenti lezioni ed esrcitazioni. Vengono presentati innanzitutto gli aspetti teorici degli argomenti trattati. In particolare, dopo aver introdotto le nozioni di base, vengono presentate le principali strutture di dati e i piu' comuni problemi computazionali. Per tali problemi, sono progettati algoritmi risolutivi, evidenziando le varie tecniche di progettazione impiegate. Per gli algoritmi proposti, sono enunciati e talvolta dimostrati teoremi che provano la loro correttezza e la loro complessita' temporale. Successivamente ampio spazio viene dedicato alla risoluzione di esercizi. Si svolgeranno inoltre lezioni di laboratorio in cui gli studenti saranno coinvolti nella progettazione e implementazione delle strutture dati presentate durante il corso.

Modalità di verifica dell'apprendimento

La verifica dell'apprendimento avviene attraverso una prova scritta finale di 2 ore e la consegna di un progetto.

Il progetto si svolge in gruppo e si discute con il docente.

Durante la prova scritta non è ammesso l'uso di libri, appunti, calcolatrici, supporti elettronici. La prova scritta consiste di 4 quesiti, alcuni dei quali sono esercizi che mirano ad accertare le abilità acquisite nel risolvere problemi computazionali tramite la progettazione di algoritmi efficienti, mentre altri sono domande aperte che mirano a verificare l'acquisizione delle conoscenze previste dal programma del corso.

Strumenti a supporto della didattica

Videoproiettore.

Orario di ricevimento

Consulta il sito web di Gianluigi Zavattaro

Consulta il sito web di