ALGORITMI E STRUTTURE DATI - MOD.1

L'insegnamento è uno dei corsi fondamentali del corso di studio e fornisce un'introduzione agli algoritmi, ovvero alla formalizzazione dei problemi, all'individuazione di soluzioni computazionali, e all'analisi di tali soluzioni, dal punto di vista della correttezza e dell'efficienza nell'uso di risorse. Inoltre presenta varie strutture dati fondamentali e tecniche di base per la progettazione e l'analisi degli algoritmi.

Conoscenza e comprensione:
- conoscenza e comprensione dei principali algoritmi e strutture dati;
- comprensione e valutazione della complessità dei problemi informatici e capacità di selezionare metodi adeguati per la modellazione e risoluzione del problema.

Capacità di applicare conoscenza e comprensione:
- capacità logico-deduttive e di problem solving;
- capacità di formalizzare e implementare soluzioni per problemi reali e identificazione di pattern di soluzione appropriati;

Capacità di giudizio
- Sapere formulare ed argomentare soluzioni, sviluppando anche un approccio critico alla valutazione di soluzioni alternative.

Familiarità con i concetti di base della matematica discreta e dell'analisi matematica.

Algoritmi, modelli di calcolo e metodologie di analisi: Introduzione informale agli algoritmi. Modelli di calcolo. Notazione asintotica. Ricorrenze.

Tecniche fondamentali per il progetto di algoritmi: Tecnica divide et impera. Programmazione dinamica. Algoritmi golosi (o greedy).

Algoritmi su grafi: Rappresentazione di grafi. Visite in ampiezza e in profondita. Alberi di copertura minimi (Kruskal e Prim). Cammini minimi (Dijkstra, Bellman-Ford, Floyd-Warshall).

Problemi NP-completi: Classi di complessita P e NP. Riducibilita polinomiale e NP-completezza. Esempi di problemi NP-completi.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.
Introduction to algorithms (3rd Edition), MIT Press, 2009.
(Traduzione italiana a cura di Livio Colussi edita da McGraw-Hill, Milano, 2010.)

C. Demetrescu, I. Finocchi, G. F. Italiano.
Algoritmi e strutture dati (seconda edizione), McGraw-Hill, 2008.

La verifica dell'apprendimento avviene attraverso una prova scritta e una prova orale. La prova scritta ha durata di 3 ore ed è divisa in due parti. La prima parte consiste di 3 quesiti da svolgere in 30 minuti. Tali quesiti richiedono una risposta rapida su argomenti affrontati a lezione e mirano a verificare l'acquisizione dei concetti di base del corso. La seconda parte consiste di 4 esercizi, alcuni dei quali hanno lo scopo di accertare le abilità acquisite nel risolvere problemi computazionali tramite la progettazione di algoritmi efficienti, mentre altri mirano a verificare l'acquisizione delle conoscenze previste dal programma del corso. La prova scritta può essere sostituita dal superamento di due prove intermedie, ciascuna delle quali ha una durata di 2 ore e consiste di 3 esercizi, aventi le stesse tipologie degli esercizi della seconda parte della prova scritta. Durante la prova scritta non è ammesso l'uso di libri, appunti, supporti elettronici. Per svolgere la seconda prova intermedia è necessario aver superato la prima prova intermedia e la seconda prova intermedia può essere sostenuta solo al primo appello della sessione estiva.

Durante la prova orale lo studente deve dimostrare di conoscere gli argomenti svolti durante il corso e di saperli esporre in modo formale.

La prova scritta dà origine ad un punteggio espresso in trentesimi e si ritiene superata se si raggiunge un punteggio almeno pari a 17.
Lo studente che ha superato la prova scritta dovrà sostenere una prova orale che, se superata, dà origine ad un punteggio aggiuntivo, compreso tra -3 e 3, che andrà sommato a quello ottenuto nella prova scritta.
L’esame si considera superato se si superano entrambe le prove ed il punteggio complessivo è almeno pari a 18.

scritto e orale

Il/la docente ha il dovere di vigilare affinché siano rispettate le regole di autenticità e originalità delle prove d'esame. Di conseguenza, nei casi in cui vi sia il sospetto di un comportamento irregolare, l'esame può prevedere un ulteriore approfondimento, contestuale alla prova d'esame, che potrà essere realizzato anche in modalità differente rispetto alle modalità sopra riportate.

La gradazione del voto è stabilita come segue:

A. I punteggi nell'intervallo 18-22 verranno assegnati in presenza di:
- conoscenza sufficiente del programma
- limitata capacità di risolvere gli esercizi proposti all'esame
- sufficiente esposizione orale

B. I punteggi nell'intervallo 23-26 verranno assegnati in presenza di:
- buona conoscenza del programma
- discreta capacità di risolvere gli esercizi proposti all'esame
- adeguata esposizione orale

C. I punteggi nell'intervallo 27-30 verranno assegnati in presenza di:
- ottima conoscenza di tutte le tematiche del programma
- buona capacità di risolvere gli esercizi proposti all'esame
- esposizione orale pienamente appropriata

La lode verrà assegnata in presenza di un esame perfetto, in cui vengono fornite soluzioni ottimali per ciascun esercizio e a fronte di una esposizione orale brillante.

Verrano utilizzate lavagna e (all'occorrenza) slide.