Insegnamento ALGORITMI E STRUTTURE DATI

Nome del corso di laurea Programmazione e gestione di sistemi informatici
Codice insegnamento 55000606
Curriculum Comune a tutti i curricula
Docente responsabile Francesco Betti Sorbelli
Docenti
  • Francesco Betti Sorbelli
Ore
  • 42 Ore - Francesco Betti Sorbelli
CFU 6
Regolamento Coorte 2026
Erogato Erogato nel 2026/27
Erogato altro regolamento
Attività Caratterizzante
Ambito Tecnologie informatiche e dell'informazione
Settore INFO-01/A
Anno 1
Periodo Secondo Semestre
Tipo insegnamento Obbligatorio (Required)
Tipo attività Attività formativa monodisciplinare
Lingua insegnamento Italiano.
Contenuti Fondamenti di analisi degli algoritmi e notazione asintotica. Tecniche divide et impera e algoritmi di ordinamento. Heap e code di priorità. Strutture dati elementari, tabelle hash, alberi binari di ricerca, alberi rosso-neri e insiemi disgiunti. Rappresentazione dei grafi, visite, alberi di copertura minimi e cammini minimi.
Testi di riferimento T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduzione agli algoritmi, quarta edizione. Slide, esercizi e materiali integrativi messi a disposizione dal docente sulla piattaforma UniStudium.
Obiettivi formativi Il corso fornisce le conoscenze fondamentali per comprendere, progettare e analizzare algoritmi e strutture dati. Al termine del corso lo studente sarà in grado di descrivere algoritmi mediante pseudocodice; valutarne correttezza e complessità temporale; risolvere semplici ricorrenze; scegliere strutture dati appropriate; applicare algoritmi di ordinamento, ricerca e gestione di insiemi dinamici; rappresentare grafi e applicare i principali algoritmi di visita, copertura minima e cammino minimo. Lo studente saprà inoltre motivare le scelte algoritmiche e confrontare soluzioni alternative in termini di correttezza ed efficienza.
Prerequisiti Conoscenze di base di programmazione: variabili, tipi di dato, espressioni, strutture di controllo, funzioni, ricorsione e array. Sono inoltre richieste conoscenze matematiche di base, capacità di ragionamento logico e familiarità con insiemi, funzioni, sommatorie e logaritmi.
Metodi didattici Il corso comprende 42 ore di lezioni frontali. Le lezioni alternano la presentazione dei concetti teorici alla descrizione mediante pseudocodice, all’analisi della correttezza e della complessità e allo svolgimento guidato di esempi ed esercizi. Particolare attenzione è dedicata alla simulazione passo per passo degli algoritmi e al confronto tra strutture dati e soluzioni alternative.
Altre informazioni Le slide, gli esercizi e le comunicazioni relative al corso sono disponibili sulla piattaforma UniStudium. La frequenza delle lezioni è consigliata.
Modalità di verifica dell'apprendimento L’esame consiste in una prova scritta individuale della durata massima di due ore, senza consultazione di materiale. La prova comprende esercizi riguardanti l’analisi degli algoritmi, l’esecuzione delle principali operazioni sulle strutture dati e l’applicazione degli algoritmi studiati, nonché domande teoriche di approfondimento. Negli esercizi può essere richiesto di mostrare i passaggi principali, motivare le scelte effettuate, indicare le strutture ausiliarie utilizzate e determinare la complessità asintotica. La valutazione considera la correttezza dei risultati, la completezza del procedimento, la capacità di analisi e l’uso appropriato della terminologia.
Programma esteso 1. Algoritmi, pseudocodice, modello RAM, correttezza e invarianti di ciclo. Analisi del caso peggiore e tasso di crescita.
2. Insertion Sort, Merge Sort e paradigma divide et impera. Ricerca binaria.
3. Notazioni asintotiche O, O e T. Funzioni di crescita. Ricorrenze, metodo di espansione e Teorema del Master.
4. Heap binari, Heapify, costruzione di heap, Heap Sort e code di priorità.
5. Quick Sort: partizionamento e analisi. Limite inferiore per gli ordinamenti per confronto. Counting Sort, Radix Sort e Bucket Sort.
6. Array, matrici, pile, code, liste concatenate e alberi radicati.
7. Indirizzamento diretto e tabelle hash. Concatenamento, indirizzamento aperto, ispezione lineare e doppio hashing.
8. Alberi binari di ricerca: visite, ricerca, minimo, massimo, successore, predecessore, inserimento e cancellazione.
9. Alberi rosso-neri: proprietà, rotazioni e inserimento.
10. Insiemi disgiunti: Make-Set, Find-Set e Union; implementazioni mediante liste e foreste, unione per rango e compressione dei cammini.
11. Grafi e loro rappresentazione. Visita in ampiezza e cammini minimi non pesati.
12. Visita in profondità, classificazione degli archi, ordinamento topologico e componenti fortemente connesse.
13. Alberi di copertura minimi, proprietà di taglio, algoritmi di Kruskal e Prim.
14. Cammini minimi da sorgente singola, rilassamento, Bellman-Ford, cammini minimi nei DAG e algoritmo di Dijkstra.
Obiettivi Agenda 2030 per lo sviluppo sostenibile Obiettivo 4 – Istruzione di qualità. Il corso contribuisce allo sviluppo di competenze scientifiche, digitali e di problem solving.