B4913 - ALGORITMI E STRUTTURE DATI (9 CFU)

Conoscenze e abilità da conseguire

Al termine del corso, lo studente: - conosce gli algoritmi (divide-et-impera, programmazione dinamica, metodo greedy, backtracking, ricerca locale) per risolvere problemi computazionali di base su strutture dati elementari (liste, code, alberi, grafi, etc.); - conosce le tecniche di base (notazione asintotica, ricorrenze) 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

Strutture dati elementari (Liste, Pile, Code, Alberi...)

Costo asintotico degli algoritmi

Algoritmi di ordinamento, selezione e ricerca

Insiemi, Dizionari

Alberi binari di ricerca, alberi RB

Tabelle Hash, Code di priorità

Strutture union-find

Tecniche Algoritmiche: divide et impera, algoritmi greedy, programmazione dinamica

Grafi e visite di grafi: visita in ampiezza e profondità

Algoritmi elementari su grafi, Minimum Spanning Tree, cammini minimi

Cenni alla teoria della NP-completezza

Testi/Bibliografia

Testi adottati:

Alan A. Bertossi, A. Montresor, Algoritmi e Strutture di Dati [https://www.cittastudi.it/catalogo/scienze/algoritmi-e-strutture-di-dati-1802], CittàStudi 2014, ISBN: 9788825173956

Altri testi consigliati:

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e strutture dati 2/ed, McGraw-Hill, 2008, ISBN: 978 88 386 64687

Camil Demetrescu, Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano, Progetto di Algoritmi e Strutture Dati in Java, McGraw-Hill, 2007, ISBN: 9788838663741

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli algoritmi e strutture dati 2/ed, McGraw-Hill, 2005, ISBN: 9788838662515

Metodi didattici

Lezioni frontali e esercitazioni

Modalità di verifica e valutazione dell'apprendimento

Nel corso di ogni anno accademico vengono fissati sei appelli: tre nella sessione estiva (Giugno/Luglio); uno nella sessione autunnale (Settembre) e due nella sessione invernale (Gennaio/Febbraio).

La verifica dell'apprendimento avviene attraverso lo svolgimento di un progetto e di una prova orale. Il progetto mira ad accertare le abilità acquisite nel risolvere problemi computazionali tramite la progettazione e implementazione di algoritmi efficienti, e a verificare l'acquisizione delle conoscenze previste dal programma del corso.

La valutazione dei progetti deve risultare almeno sufficiente (i.e., deve ottenere una valutazione ≥ 18/30) per essere valida ai fini dell'esame. La prova orale, anch'essa valutata in trentesimi, prevede una discussione dei progetti consegnati durante la quale possono essere somministrate domande che mirano a verificare l'acquisizione, da parte dello studente, delle conoscenze previste dall'intero programma del corso.

Il voto finale, espresso in trentesimi, tiene conto delle valutazioni ottenute nei progetti e nella prova orale.

Strumenti a supporto della didattica

Le lezioni frontali prevedono l'uso di lucidi proiettati da un laptop e una lavagna tradizionale, articoli scientifici segnalati agli studenti etc. Il materiale didattico presentato a lezione verrà messo a disposizione dello studente in formato elettronico tramite internet.

Orario di ricevimento

Consulta il sito web di Jocelyne Elias

Consulta il sito web di Davide Rossi