Anno di corso: 1

Crediti: 8
Crediti: 8
Crediti: 8
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale
Crediti: 3
Tipo: Lingua/Prova Finale

Anno di corso: 2

Anno di corso: 3

ANALISI E PROGETTO DI ALGORITMI

Scheda dell'insegnamento

Anno accademico di regolamento: 
2016/2017
Anno di corso: 
3
Anno accademico di erogazione: 
2018/2019
Tipo di attività: 
Obbligatorio
Lingua: 
Italiano
Crediti: 
8
Ciclo: 
Primo Semestre
Ore di attivita' didattica: 
76
Prerequisiti: 

Nozioni base di programmazione, algoritmi e strutture dati

Moduli

Metodi di valutazione

Modalita' di verifica dell'apprendimento: 

Esame scritto, consistente in:

- esercizi che richiedono sviluppo di un algoritmo per la soluzione di un problema assegnato

- domande aperte relative alle nozioni teoriche presentate a lezione

Sono previste anche due prove parziali in sostituzione dell'esame completo, ognuna delle quali relativa solo ad una parte degli argomenti presentati a lezione.

Valutazione: 
Voto Finale

Obiettivi formativi

Gli studenti acquisiranno la conoscenza delle principali tecniche di progetto e analisi degli algoritmi e la capacità di individuare le più idonee tecniche algoritmiche per la soluzione efficiente di specifici problemi computazionali.

Contenuti

L'insegnamento intende introdurre le principali tecniche algoritmiche (programmazione dinamica, greedy), con particolare attenzione agli aspetti di efficienza degli algoritmi, con i relativi strumenti di analisi. Verranno illustrati i principali algoritmi per la ricerca su grafi, la ricerca di cammini minimi, la costruzione di alberi di copertura minimi.

Programma esteso

1. Strumenti matematici

Crescita delle funzioni, notazioni asintotiche
Calcolo del tempo di esecuzione per algoritmi iterativi
Richiami sulla ricorsione: calcolo del fattoriale
Ricorrenze e tempi di calcolo di algoritmi ricorsivi
Ricerca dicotomica, calcolo altezza di un albero binario

2. Tecniche algoritmiche: Programmazione Dinamica (DP)

Esempi introduttivi
Caratteristiche principali - Ricorsione
Implementazione con matrici

3. Tecniche algoritmiche: il metodo Greedy (goloso)

Esempi introduttivi
I codici di Huffman
Matroidi
Teorema di Rado

4. Algoritmi su grafi

Rappresentazione dei grafi.
Visita in ampiezza dei grafi
Visita in profondità dei grafi

5. Alberi di copertura minimi

Algoritmo di Kruskal
Algoritmo di Prim

5. Problemi di cammino minimo

Algoritmo di Dijkstra
Algoritmo di Bellman-Ford
Algoritmo di Floyd-Warshall

6. Problemi di flusso massimo

Algoritmo di Ford-Fulkerson

7. NP completezza e riducibilità

P versus NP
dimostrazioni di NP completezza
Problemi NP completi

Bibliografia consigliata

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture dati, Ed. Mc. Graw Hill

Materiale integrativo (lucidi ed esercizi) disponibili sul sito e-learning.

Metodi didattici

Lezioni frontali, esercitazioni e approfondimenti in laboratorio. Attivita' di studio individuali supportate da materiali didattici in E-learning.