11929 - ALGORITMI E STRUTTURE DATI (CL.B)

Scheda insegnamento

Anno Accademico 2020/2021

Conoscenze e abilità da conseguire

Al termine del corso, lo studente conosce: - gli algoritmi per risolvere problemi computazionali di base su strutture dati elementari; - le tecniche di base per calcolare il costo computazionale degli algoritmi; - le classi di complessità computazionale P, NP e NP-hard. In particolare, lo studente è in grado di: - progettare algoritmi efficienti per risolvere semplici problemi computazionali; - stimare in ordine di grandezza il costo computazionale degli algoritmi; - analizzare la complessità computazionale di problemi computazionali di base; - dare una valutazione circa l'efficienza e la correttezza di un algoritmo; - elaborare e presentare un progetto per la risoluzione di problemi computazionali di base.

Contenuti

-matematica discreta elementare per calcolare gli ordini di grandezza;

- Algoritmi di ordinamento;

- Mediano e selezione;

- Strutture dati elementari: pile, code, alberi, grafi

- algoritmi di visita su grafi

- algoritmi di base su grafi

-classi P e NP

-problemi NP-Hard

Testi/Bibliografia

T. Cormen, C. Leiserson, R. Rivest. Introduction to algorithms. MIT Press.

Metodi didattici

Lezioni frontali ed eserciitazioni in aula.

Modalità di verifica dell'apprendimento

Esame scritto e orale opzionale aggiuntivo. Progetto.

La verifica si compone di due prove, progetto e scritto (orale opzionale). Il progetto deve essere consegnato e approvato prima dello scritto e non concorre al giudizio finale ma abilita solo all'iscrizione alla prova scritta.

La frequenza alle lezioni è molto consigliata ma non indispensabile.

La prova scritta, della durata di 1 1&2h, è composta di tre esercizi, un quiz a scelta multipla e una doanda teorica riferite alla verifica di conoscenze (sapere) e un esercizio riferito alle abilità (saper fare), declinate nel quadro “conoscenze ed abilità da conseguire”.

Non sono ammessi o meno durante le prove strumenti quali ausili di calcolo, vocabolari, codici, ecc.

Variazioni coronavirus: durante il periodo di eccezionalità dovuto alle restrizioni sanitarie, e solo fino a quando gli esami non potranno riprendere in modalità normale, l'esame consisterà solo di una prova quiz a scelta multipla e di una prova scritta. Orale opzionale. 

Strumenti a supporto della didattica

Dispense a cura del docente.

Orario di ricevimento

Consulta il sito web di Vittorio Maniezzo

Consulta il sito web di Moreno Marzolla