- Docente: Gianluigi Zavattaro
- Crediti formativi: 12
- SSD: INF/01
- Lingua di insegnamento: Italiano
- Moduli: Gianluigi Zavattaro (Modulo 1) Pietro Di Lena (Modulo 2)
- Modalità didattica: Convenzionale - Lezioni in presenza (Modulo 1) Convenzionale - Lezioni in presenza (Modulo 2)
- Campus: Bologna
-
Corso:
Laurea in
Informatica (cod. 8009)
Valido anche per Laurea Magistrale in Matematica (cod. 5827)
-
Orario delle lezioni (Modulo 1)
dal 31/03/2025 al 15/05/2025
-
Orario delle lezioni (Modulo 2)
dal 17/02/2025 al 20/03/2025
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 analizzare la complessità computazionale di problemi computazionali di base; - è in grado 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. Algoritmi di ordinamento: SelectionSort, InsertionSort, MergeSort, QuickSort, CountingSort, RadixSort. Strutture dati elementari: liste, pile e code. Alberi. Visite di alberi (pre-ordine, in-ordine, post-ordine, in ampiezza). Alberi binari di ricerca e alberi binari bilanciati di ricerca. Dizionari. Tabelle hash. Heaps: HeapSort e Code con priorita'. Strutture Union-Find. Tecniche di progettazione: divide-et-impera, greedy, programmazione dinamica. Grafi. Visite DFS e BFS. Algoritmi su grafi: Minimum Spanning Tree (Prim, Kruskal), Cammini Minimi (Bellman-Ford, Dijkstra, Floyd-Warshall). Complessita'. Le classi P ed NP. NP-completezza.
Il corso include inoltre lezioni pratiche durante le quale si implementano e usano le strutture di dati presentate durante le lezioni 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 e valutazione dell'apprendimento
La verifica dell'apprendimento avviene attraverso una prova scritta finale di 2 ore e la consegna facoltativa di un progetto di programmazione Java da svolgersi singolarmente.
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 Pietro Di Lena
SDGs

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