Corso di Algoritmi e Strutture Dati, A.A. 2011/2012

| Orario Ricevimento Studenti | Orario Lezioni | Contenuti del Corso | Esami del Corso | Materiale del Corso | FAQs |

Orario delle lezioni del corso di Algoritmi e Strutture Dati, A.A. 2011/2012

Le informazioni sull'orario definitivo sono pubblicate sul portale del Dipartimento e, per quello che riguarda il corso di Algoritmi e Strutture Dati, anche in questa pagina. Le lezioni inizieranno regolarmente Martedi 27 Settembre 2011. Il calendario definitivo per l'A.A. 2011/2012 è il seguente (I semestre):

Martedi (Tuesday), ore 13.30-15.30, Aula Ercolani 1 (E1), Mura Anteo Zamboni 7,

Venerdi (Friday), ore 11.30-13.30, Aula Ercolani 1 (E1), Mura Anteo Zamboni 7,

Torna all'inizio pagina

Contenuti del corso di Algoritmi e Strutture Dati

Il corso subirà qualche lieve variazione dei contenuti rispetto ai temi trattati lo scorso anno accademico. Ciò non avrà ripercussioni per chi debba sostenere l'esame avendo seguito il corso durante gli anni precedenti.

Il programma del corso riguarda aspetti metodologici e pratici per la definizione della migliore sinergia tra tecniche di programmazione e algoritmi efficienti e scalabili e il supporto fornito dalla progettazione di strutture dati opportune per gli obiettivi di efficienza di esecuzione, ridotto consumo delle risorse di memoria e di calcolo.

In particolare i temi principali che compongono il corso sono i seguenti: Complessità asintotica degli algoritmi, Strutture dati elementari (Liste, Pile, Code, Alberi...), Algoritmi di ordinamento e ricerca (Insertion Sort, Selection Sort, Bubble Sort, Merge Sort, Quick Sort, Heap Sort), Limite inferiore alla complessità del problema dell'ordinamento basato su confronti, Algoritmi di ordinamento in tempo lineare (Counting Sort, Pigeonhole Sort, Radix Sort, Bucket Sort), Algoritmi di selezione (QuickSelect), Alberi binari di ricerca, alberi AVL, B-Trees, Tabelle Hash, analisi della risoluzione delle collisioni mediante indirizzamento aperto o concatenazione, Code di priorità, Strutture union-find; euristiche quick-union e quick-find, Tecniche Algoritmiche: divide et impera, algoritmi greedy, programmazione dinamica, Grafi e visite di grafi: visita in ampiezza e profondità, Algoritmi su grafi: albero minimo di copertura, cammini minimi da singola sorgente (algoritmo di Dijkstra), distanze minime tra tutte le coppie di vertici, Cenni alla teoria della NP-completezza.

Ciò condurrà idealmente lo studente ad acquisire:

• conoscenza degli algoritmi per risolvere problemi computazionali di base su strutture dati elementari;

• conoscenza delle tecniche di base per calcolare il costo computazionale degli algoritmi;

• conoscenza delle classi di complessità computazionale P, NP e NP-hard;

• capacità di progettare algoritmi efficienti per risolvere semplici problemi computazionali;

• capacità di stimare in ordine di grandezza il costo computazionale degli algoritmi;

• capacità di analizzare la complessità computazionale di problemi computazionali di base;

• valutare circa l'efficienza e la correttezza di un algoritmo;

• elaborare e presentare un progetto per la risoluzione di problemi computazionali di base.

Esami del corso di Sistemi e Reti Wireless

L'esame del corso consiste in una serie di prove parziali e in un esame scritto finale, oltre a un progetto di laboratorio. Maggiori dettagli saranno forniti durante il corso.

Ad ogni prova di esame ci si deve sempre presentare muniti di un documento valido corredato da una foto recente che permetta l'identificazione del candidato.
Torna all'inizio pagina

Materiale del corso di Sistemi e Reti Wireless

Questa sezione della pagina del corso raccoglierà le notizie e il materiale relativo alle lezioni iniziali. Il materiale qui raccolto non costituisce un indice esaustivo degli argomenti trattati, ma semplicemente una raccolta di slide e strumenti usati a lezione. Alcuni dei concetti presentati a lezione vengono integrati dal materiale fornito. Le slide utilizzate sono tratte dalle slide definite dal Dott. Moreno Marzolla.

In questa pagina, in continuo aggiornamento, sono raccolte le risposte alle domande frequenti che mi sono state rivolte via e-mail (Frequently Asked Questions, FAQs).

Alcuni testi consigliati (utili per approfondire temi specifici, ma non necessariamente da acquistare) per il corso sono i seguenti (maggiori informazioni saranno fornite a lezione).

• Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e strutture dati 2/ed, McGraw-Hill, 2008, ISBN: 978 88 386 64687 (Testo adottato come principale riferimento)

• Alan A. Bertossi, A. Montresor, Algoritmi e strutture di dati, CittàStudi, 2010, ISBN: 9788825173567. Questo é un ottimo testo didattico sugli algoritmi e strutture dati. Esso copre essenzialmente gli stessi argomenti del libro di Demetrescu et al.

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli algoritmi e strutture dati, 2nd edition, McGraw-Hill, 2005, ISBN: 9788838662515. Questo é uno dei testi classici sugli algoritmi, offre una trattazione piuttosto approfondita di tutti gli argomenti principali. Si noti che questo libro include molto più materiale rispetto a quanto verrà svolto a lezione, e richiede buone basi matematiche per comprendere le dimostrazioni. Questo libro é pertanto consigliato a coloro che desiderano approfondire gli argomenti svolti, oppure a chi sia particolarmente appassionato alla materia.

• Camil Demetrescu, Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano, Progetto di Algoritmi e Strutture Dati in Java, McGraw-Hill, 2007, ISBN: 9788838663741. Questo libro é il complemento del testo adottato, poiché contiene la descrizione delle implementazioni Java degli algoritmi descritti tramite pseudocodice nel libro di Demetrescu et al. Attenzione: questo volume NON sostituisce il libro di Demetrescu, Finocchi, Italiano, perché non contiene la parte di teoria che vedremo a lezione.

• altri eventuali testi e documentazione su Web sarà indicata in seguito

Torna all'inizio pagina