11929 - ALGORITMI E STRUTTURE DATI

Scheda insegnamento

Anno Accademico 2017/2018

Conoscenze e abilità da conseguire

Al termine del corso, lo studente: - conosce gli algoritmi per risolvere problemi computazionali di base su strutture 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 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.

Programma/Contenuti

Strutture dati elementari (Liste, Pile, Code, Alberi...)
Costo asintotico degli algoritmi
Algoritmi di ordinamento, selezione e ricerca
Limite inferiore alla complessità del problema dell'ordinamento basato su confronti
Algoritmi di ordinamento in tempo lineare
Alberi binari di ricerca, alberi AVL
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, cammini minimi
Cenni alla teoria della NP-completezza

Testi/Bibliografia

Testi adottati 
Alan A. Bertossi, A. Montresor, Algoritmi e Strutture di Dati, CittàStudi 2010, ISBN: 9788825173567

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 con utilizzo di lucidi, esercitazioni, progetti di laboratorio


Modalità di verifica dell'apprendimento

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

La prova scritta può essere sostituita dallo svolgimento di progetti e da una prova orale. 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, consiste essenzialmente nella discussione dei risultati ottenuti nei progetti e mira a verificare l'acquisizione, da parte dello studente, delle conoscenze previste dal programma del corso. Il voto finale, espresso in trentesimi, tiene conto delle valutazione ottenente nei progetti e nella prova orale.


Strumenti a supporto della didattica

Il materiale didattico (lucidi delle lezioni, esercizi svolti, altre risorse utili) si trovano nella pagina web del corso.

Link ad altre eventuali informazioni

http://www.cs.unibo.it/~donat/

Orario di ricevimento

Consulta il sito web di Lorenzo Donatiello

Consulta il sito web di Gianluigi Zavattaro