11929 - ALGORITMI E STRUTTURE DATI

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.

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, 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 e valutazione dell'apprendimento

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, 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 Jocelyne Elias