Insegnamento ALGORITMI E STRUTTURE DATI CON LABORATORIO

Nome del corso di laurea Informatica
Codice insegnamento 55100615
Curriculum Comune a tutti i curricula
Docente responsabile Maria Cristina Pinotti
CFU 12
Regolamento Coorte 2025
Erogato Erogato nel 2026/27
Erogato altro regolamento
Anno 2
Periodo Annuale
Tipo insegnamento Obbligatorio (Required)
Tipo attività Attività formativa integrata
Suddivisione

ALGORITMI E STRUTTURE DATI CON LABORATORIO - MODULO I

Codice 55100609
CFU 6
Docente responsabile Maria Cristina Pinotti
Docenti
  • Maria Cristina Pinotti
Ore
  • 52 Ore - Maria Cristina Pinotti
Attività Caratterizzante
Ambito Formazione scientifico-tecnologica
Settore INF/01
Tipo insegnamento Obbligatorio (Required)
Lingua insegnamento Italiano
Contenuti Progettazione degli algoritmi e analisi della complessità in tempo e spazio. Algoritmi di ordinamento, incluso il problema delle statistiche d'ordine. Heapsort. Binary Search Trees. Tecnica Divide-et-impera.
Testi di riferimento T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST, C. STEIN Introduzione agli algoritmi e strutture dati (terza edizione), McGraw-Hill, 2010, ISBN: 978-88-386-6515-8

I materiali didattici utilizzati durante le lezioni sono, solitamente, resi disponibili anche su Unistudium.
Obiettivi formativi Il corso fornisce le competenze algoritmiche di base, caratterizzanti per il Corso di Studio.
L'obiettivo principale dell’insegnamento consiste nel fornire agli studenti le basi per comprendere, valutare, e proporre algoritmi deterministici, simili a quelli studiati nel corso, ma estesi a nuovi contesti.
Le principali conoscenze acquisite saranno:
la capacità di valutare l'efficienza di un algoritmo; la conoscenza degli algoritmi per l'ordinamento; la conoscenza e l' utilizzo di strutture dati.
Prerequisiti Elementi di Analisi Matematica, Matematica Discreta e un linguaggio di programmazione imperativo.
Metodi didattici Lezioni frontali in classe.
Altre informazioni Frequenza consigliata.
Tuttavia tutti gli argomenti trattati sono rintracciabili sui testi consigliati.
Modalità di verifica dell'apprendimento L'esame è unico per i due moduli. Le modalità di verifica includono una prova scritta e una prova orale su richiesta dello studente.
La prova scritta consiste nella risoluzione di esercizi per valutare la capacità di applicare le conoscenza acquisite e comprenderne il trasferimento a nuovi contesti.

La prova orale verte su tutto il programma e consiste sia in domande di teoria, sia nella risoluzione di
esercizi e ha una durata approssimativa di 20-25 minuti. Il voto finale è composto considerando sia
l'esito della prova scritta sia l'andamento della prova orale. La prova orale non è obbligatoria se il voto dello scritto è sufficiente.

Per gli studenti frequentanti è possibile sostenere due prove scritte in itinere, ciascuna composta da alcuni esercizi.

Nel caso in cui lo studente intenda anticipare l’esame in un anno precedente a quello programmato nel piano di studio, si raccomanda di frequentare il ciclo delle lezioni e
di sostenere l’esame nel primo appello utile dopo che le lezioni medesime siano terminate, nel rispetto quindi del semestre di programmazione dell’insegnamento.

Per informazioni sui servizi di supporto agli studenti con disabilità e/o DSA visita la pagina http://www.unipg.it/disabilita-e-dsa
Programma esteso Algoritmi: correttezza, terminazione, complessità (caso pessimo, caso medio).
InsertionSort: analisi della complessita' in tempo e spazio nel caso pessimo e nel caso medio.
Fondamenti di Matematica: Principio di Induzione, Ordine di grandezza di funzioni. Base, tetto, esponenziali, Logaritmi. Sommatorie e serie.
Metodi di progetto: Divide et Impera. MergeSort e Ricerca Binaria.
Analisi di complessita' di algoritmi ricorsivi. Equazioni di ricorrenza. Il Teorema dell'esperto.
Ordinamento: Quicksort con analisi della complessita' in tempo nel caso pessimo e nel caso medio.
Costruzione di uno heap. HeapSort.
Limiti teorici della complessità di ordinamento per confronto.
CountingSort. Radix Sort.
Limiti inferiori e superiori per la complessità in tempo per il calcolo del minimo e del massimo in una sequenza.
Mediana e statistiche d'ordine.

Grafi:generalità e rappresentazione in memoria. Schema generale di visita di grafi. Alberi di copertura e componenti connesse.Visita in ampiezza (BFS), visita in profondità (DFS) e loro proprietà (classificazione degli archi). Grafi aciclici e ordine topologico. Componenti fortemente connesse. Algoritmo di Djikstra.
Albero di copertura di costo minimo: algoritmo di Kruskal, algoritmo di Prim.
Obiettivi Agenda 2030 per lo sviluppo sostenibile Questo insegnamento concorre alla realizzazione degli obiettivi ONU dell'Agenda 2030 per lo Sviluppo Sostenibile

ALGORITMI E STRUTTURE DATI CON LABORATORIO - MODULO II

Codice 55107606
CFU 6
Docente responsabile Francesco Betti Sorbelli
Docenti
  • Francesco Betti Sorbelli
Ore
  • 47 Ore - Francesco Betti Sorbelli
Attività Caratterizzante
Ambito Formazione scientifico-tecnologica
Settore INF/01
Tipo insegnamento Obbligatorio (Required)
Lingua insegnamento Italiano.
Contenuti Grafi orientati e non orientati e loro rappresentazione. Visite in ampiezza e in profondità. Grafi aciclici, ordinamento topologico e componenti fortemente connesse. Alberi di copertura minimi. Cammini minimi da sorgente singola e tra tutte le coppie di vertici nei grafi pesati. Analisi della correttezza e della complessità degli algoritmi.
Testi di riferimento T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduzione agli algoritmi e strutture dati, terza edizione, McGraw-Hill, 2010. M. T. Goodrich, R. Tamassia, Algorithm Design and Applications, Wiley, 2015. Slide, esercizi e materiali integrativi sono messi a disposizione sulla piattaforma UniStudium.
Obiettivi formativi Il modulo fornisce conoscenze e competenze per comprendere, applicare e analizzare i principali algoritmi su grafi. Al termine del modulo lo studente sarà in grado di scegliere una rappresentazione adeguata per un grafo; applicare algoritmi di visita, connettività, ordinamento topologico, copertura minima e cammino minimo; distinguere le condizioni di applicabilità dei diversi algoritmi; analizzarne correttezza e complessità; confrontare soluzioni alternative in relazione alle caratteristiche del grafo. Lo studente saprà inoltre adattare gli algoritmi studiati alla soluzione di problemi in nuovi contesti.
Prerequisiti Conoscenze di programmazione mediante un linguaggio imperativo, matematica discreta e analisi matematica di base. Sono inoltre richieste le conoscenze acquisite nel Modulo I: analisi della complessità, notazione asintotica, ricorrenze, ordinamento, heap, code di priorità e strutture per insiemi disgiunti.
Metodi didattici Il modulo comprende 47 ore di lezioni frontali ed esercitazioni. Le lezioni alternano la presentazione dei concetti teorici, la descrizione degli algoritmi mediante pseudocodice, l’analisi della correttezza e della complessità e lo svolgimento guidato di esercizi. Particolare attenzione è dedicata all’esecuzione passo per passo degli algoritmi e alla scelta della soluzione più appropriata in funzione delle caratteristiche del grafo.
Altre informazioni Il modulo costituisce parte dell’insegnamento integrato “Algoritmi e Strutture Dati con Laboratorio” e non può essere seguito indipendentemente dal Modulo I. I materiali didattici e le comunicazioni sono disponibili sulla piattaforma UniStudium. La frequenza è consigliata.
Modalità di verifica dell'apprendimento La verifica è integrata con quella del Modulo I. L’esame prevede una prova scritta ed eventualmente una prova orale. La prova scritta comprende esercizi finalizzati a valutare la capacità di applicare gli algoritmi studiati, mostrarne i passaggi principali, motivare le scelte effettuate e determinarne la complessità. La prova orale, se sostenuta, verte sul programma dei due moduli e comprende domande teoriche e discussione di esercizi. La valutazione considera la correttezza delle soluzioni, la capacità di applicare le conoscenze a nuovi contesti, la qualità dell’analisi e la chiarezza espositiva.
Programma esteso 1. Definizioni e proprietà fondamentali dei grafi orientati e non orientati. Grafi pesati.
2. Rappresentazione dei grafi mediante liste e matrici di adiacenza. Analisi dei costi delle rappresentazioni.
3. Visita in ampiezza, albero BFS e cammini minimi nei grafi non pesati.
4. Visita in profondità, foresta DFS, tempi di scoperta e fine e classificazione degli archi.
5. Grafi aciclici orientati e ordinamento topologico.
6. Componenti connesse e componenti fortemente connesse.
7. Strutture dati per insiemi disgiunti e loro applicazione agli algoritmi su grafi.
8. Alberi di copertura minimi e proprietà di taglio. Algoritmi di Kruskal e Prim.
9. Cammini minimi da sorgente singola. Sottostruttura ottima, rilassamento e alberi dei cammini minimi.
10. Algoritmo di Bellman-Ford e rilevazione dei cicli di peso negativo.
11. Cammini minimi nei grafi aciclici orientati.
12. Algoritmo di Dijkstra e implementazione mediante code di priorità.
13. Cammini minimi tra tutte le coppie di vertici nei grafi pesati.
14. Algoritmo analogo alla moltiplicazione di matrici e relativa versione accelerata.
15. Algoritmo di Floyd-Warshall e chiusura transitiva.
16. Algoritmo di Johnson per grafi sparsi.
17. Confronto tra gli algoritmi per cammini minimi, condizioni di applicabilità e analisi della complessità.
Obiettivi Agenda 2030 per lo sviluppo sostenibile Obiettivo 4 – Istruzione di qualità. Il modulo contribuisce allo sviluppo di competenze scientifiche, digitali, analitiche e di problem solving.