Scheda insegnamento
Algoritmi e strutture dati
anno accademico: | 2013/2014 |
docente: | Alessandro Panconesi |
corso di laurea: | Matematica - DM 270/04 (triennale), III anno |
tipo di attività formativa: | affine e integrativa |
crediti formativi: | 6 (48 ore di lezione) |
raggruppamento disciplinare: | INF/01 Informatica |
lingua di insegnamento: | italiano |
periodo: | II sem (03/03/2014 - 13/06/2014) |
Aula ed orario di lezione
Frequenza: consigliata
Obiettivi del corso:
Al giorno d'oggi è difficile sottostimare l'importanza del concetto di algoritmo. Da WallStreet a Internet, passando per una miriade di manufatti computerizzati, gli algoritmi ormai governano, nel bene e nel male, aspetti fondamentali della nostra vita. Lo scopo di questo corso è quello di illustrare il concetto fondamentale di algoritmo efficiente e di sviluppare le basi della sofisticata teoria matematica che ne permette la progettazione.
Programma di massima del corso: Visite su grafi: BFS, DFS Algoritmi greedy: algoritmo di Dijkstra, Minimum Spanning Trees Strutture dati: heaps, union-find Divide et impera. Programmazione dinamica: edit distance, cammini minimi (Bellman-Ford) Problema del massimo flusso: Ford-Fulkerson, Preflow-push (push relabel), teorema max flow - min cut e sue applicazioni NP-completezza (cenni) Algoritmi probabilistici: minimo taglio, quicksort
Testi consigliati:
- Kleinberg-Tardos, Algorithm design-- Pearson international
- Ci sono numerosi testi che coprono lo stesso materiale come ad esempio il Cormen, Leiserson, Rivest: "Introduction to Algorithms" ma il Kleinberg-Tardos mi sembra il migliore al momento. Consiglio vivamente di acquistare le versioni in lingua originale.
Modalità di erogazione: convenzionale
Prerequisiti:
Informatica Generale
Risultati di apprendimento - Conoscenze acquisite:
implementare un qualunque algoritmo progettato, nonché le strutture dati relative, in un linguaggio di programmazione strutturata, quale ad esempio il C++, e di mandarlo in esecuzione sotto diversi sistemi operativi.
Risultati di apprendimento - Competenze acquisite:
implementare un qualunque algoritmo progettato, nonché le strutture dati relative, in un linguaggio di programmazione strutturata, quale ad esempio il C, e di mandarlo in esecuzione sotto diversi sistemi operativi.
Studio personale: la percentuale prevista di studio personale sul totale dell'impegno richiesto è del 65%