CARLO SARTIANI | ALGORITMI E STRUTTURE DATI

Italiano

L’obiettivo principale del corso consiste nel fornire formalmente la nozione di algoritmo e di strutture dati. Caratterizzare i dati da elaborare, organizzandoli e strutturandoli nel modo più opportuno al fine di agevolarne l'uso da parte degli algoritmi. Progettare algoritmi corretti ed efficienti attraverso l'esame di diversi paradigmi.
• Conoscenza e capacità di comprensione: lo studente deve dimostrare di conoscere e comprendere il concetto di algoritmo, di saper dimostrare la sua correttezza e calcolarne l’efficienza. Devi inoltre aver compreso i principali algoritmi e le strutture dati di base per poter progettare velocemente nuovi ed efficienti algoritmi;
• Capacità di applicare conoscenza e comprensione: al termine del corso lo studente avrà acquisito una libreria di algoritmi e strutture dati che potrà utilizzare per progettare nuovi algoritmi ma anche per acquisire maggiore consapevolezza nell’uso di librerie che utilizzerà durante la programmazione di un algoritmo. La comprensione degli argomenti fornirà capacità di progettare nuovi algoritmi ma anche approfondimento verso algoritmi più sofisticati;
• Autonomia di giudizio: lo studente deve essere in grado in maniera autonoma di saper progettare e valutare in termini di correttezza ed efficienza un algoritmo;
• Abilità comunicative: lo studente deve avere la capacità di presentare in maniera chiara, utilizzando, se necessario, un linguaggio comprensibile anche a persone non esperte, il funzionamento di un algoritmo o di una struttura dati utilizzando gli strumenti illustrati a lezione per dimostrare la sua correttezza ed efficienza;
• Capacità di apprendimento: lo studente deve essere in grado di consultare in maniera autonoma testi e articoli scientifici al fine di estendere le conoscenze di base acquisite nel corso.

Conoscenza della Programmazione Procedurale ed in particolare una conoscenza approfondita di un linguaggio procedurale come il C.

Ruolo degli algoritmi nell’elaborazione dei dati (2 ore di lezione): algoritmi, insertion sort, analisi degli algoritmi, progettazione degli algoritmi;

Crescita delle funzioni (2 ore di lezione): notazione asintotica, Notazioni standard e funzioni comuni;

Strutture dati elementari (2 ore di lezione): stack e code, liste concatenate, implementare puntatori e oggetti.

Divide et impera (4 ore di lezione): metodo di sostituzione per risolvere le ricorrenze, metodo dell’albero di ricorsione per risolvere le ricorrenze, metodo dell’esperto per risolvere le ricorrenze;

Heapsort (4 ore di lezione): heap, proprietà dell’heap, costruire un heap, algoritmo heapsort, code di priorità;

Quicksort (4 ore di lezione): descrizione di quicksort, prestazioni di quicksort, versione randomizzata di quicksort, analisi di quicksort;

Ordinamento in tempo lineare (2 ore di lezione): limiti inferiori per l’ordinamento, counting sort, radix sort, bucket sort;

Hashing (4 ore di lezione): tavole a indirizzamento diretto, tavole hash, funzioni hash;

Alberi binari di ricerca (6 ore di lezione): definizione di albero binario di ricerca, interrogazione di un albero binario di ricerca, inserimento e cancellazione;

Programmazione dinamica (6 ore di lezione): taglio delle aste, moltiplicare una sequenza di matrici, elementi della programmazione dinamica, più lunga sottosequenza comune (LCS);

Algoritmi golosi (6 ore di lezione): problema della selezione di attività, elementi della strategia golosa, codici di Huffman;

Algoritmi sui grafi (8 ore di lezione): concetti fondamentali di teoria dei grafi, algoritmi di visita, sorting topologico.

L’occasione didattica principale sarà la lezione in classe; durante la lezione saranno presentati i principali contenuti del programma del corso. Insieme agli aspetti teorici, verranno presentati anche degli esercizi per invogliare lo studente a mettere in pratica immediatamente i concetti introdotti a lezione. Saranno fornite anche delle domande di riepilogo per facilitare l'autovalutazione dell'apprendimento sui temi delle lezioni. Le domande saranno di difficoltà eterogenea, dalle semplici definizioni, a richieste di confronto di soluzioni/tecniche, fino ad arrivare a domande che cercano di motivare lo studente a dimostrare le soluzioni trovate. Si consiglia fortemente la frequenza.

L'esame consiste in una prova scritta con sei domande aperte di carattere teorico o di risoluzioni di esercizi. Per ogni sono previsti massimo 5 punti. Superata la prova scritta è possibile chiedere una integrazione al voto scritto attraverso una prova orale con domande di approfondimento su tutto il programma del corso.
In alternativa sono previste due prove scritte intermedie solo e soltanto durante il corso. La prima prova scritta sarà svolta durante la pausa didattica e riguarderà solo gli argomenti della prima parte del corso. La seconda al termine del corso e riguarderà la rimanente parte del corso. In entrambe le prove sono previsti sei esercizi dove per ogni esercizio sono previsti massimo 3 punti.

Introduzione agli algoritmi e strutture dati 3/ed. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.

All’inizio del corso il docente descrive obiettivi, programma e metodi di verifica del corso, indicando dove reperire il materiale didattico on line. L’orario di ricevimento è fissato per Martedì e Mercoledì dalle ore 14:00 alle ore 16:00 presso lo studio del docente. Oltre all’orario di ricevimento settimanale, il docente è disponibile in ogni momento per un contatto con gli studenti, attraverso la propria e-mail o alla fine della lezione.

6/2/2024,200/2/2024,14/5/2024,2/7/2024,16/7/2024,24/9/2024,17/12/2024

No