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%

Calendario appelli d'esame su Infostud

Dati statistici relativi ai risultati degli esami

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma