Pagina dell'insegnamento “Algoritmi e strutture dati” (in costruzione)

Informazioni generali (A.A. 2014/15)

Nome dell'insegnamento:Algoritmi e strutture dati
Docente:Mauro Leoncini - Manuela Montangero
Corso di Studio:Laurea triennale in Informatica
Periodo Didattico:Primo anno, secondo ciclo semestrale
SSD:INF/01
CFU:9
Orario di ricevimento

Pagina web dell'insegnamento tenuto nell'A.A. 2013/14

Obiettivi formativi e contenuti

Obiettivi formativi

L'insegnamento introduce i concetti e le tecniche di base per lo sviluppo di algoritmi nonché le principali metodologie per la loro analisi. L'insegnamento viene svolto "in parallelo" (cioè nello stesso semestre) a quello di "Programmazione II", nel quale alcuni dei più significativi algoritmi vengono ripresi in esercitazioni di laboratorio ed implementati utilizzando il linguaggio C++. Il passaggio alla fase implementativa è particolarmente utile per verificare concretamente il grado di padronanza raggiunto nell'uso delle tecniche algoritmiche. Le conoscenze e competenze acquisite tramite i due insegnamenti portano inoltre lo studente ad apprezzare l'importanza di una accurata fase progettuale in cui siano attentamente considerate la correttezza e l'efficienza degli algoritmi.

Prerequisiti: per poter sostenere l'esame è obbligatorio aver superato gli esami di Programmazione I e Analisi matematica.

Contenuti

  • Analisi di algoritmi. Bit- vs word-complexity. Analisi worst-case. Comportamento asintotico degli algoritmi.
  • Algoritmi aritmetici. Aritmetica modulare. MCD, algoritmo di Euclide e algoritmo di Euclide esteso. Test di primalità. Crittografia a chiave pubblica, il protocollo RSA. Funzioni e tabelle hash.
  • Tecnica divide-et-impera. Algoritmi di ordinamento: mergesort e quicksort. Ricorrenze. Master-theorem. Moltiplicazione di interi e di matrici.
  • Esplorazione di grafi. Algoritmo di ricerca in profondità (depth-first search). Ordinamento topologico di grafi diretti aciclici. Componenti fortemente connesse.
  • Algoritmi ingordi (greedy). Minimo albero di copertura. Codifiche Huffman. Copertura di insiemi.
  • Programmazione dinamica. Cammini minima in grafi aciclici. Sottosequenza più lunga di numeri ordinati in senso crescente. Distanza di editing. Problema dello zaino. Moltiplicazione iterata di matrici. Cammini minimi in grafi diretti. Insiemi indipendenti in alberi.
  • Programmazione lineare. Reti di flusso. Matching bipartito. Dualità. Algoritmo del simplesso.
  • Complessità computazionale. Riducibilità. Nozione di completezza. Problemi NP-completi e problemi NP-hard.
  • Approcci alla risoluzione di problemi NP-hard. Ricerca esaustiva “intelligente”. Algoritmi di approssimazione. Ricerca locale.

Orario delle lezioni

  • Martedì 11 - 13, Aula M1-5 (ex aula IV) Edificio ex Matematica
  • Mercoledì 9 - 11, Aula M1-5 (ex aula IV) Edificio ex Matematica
  • Giovedì 11 - 13, Aula M1-5 (ex aula IV) Edificio ex Matematica

Avvisi (in ordine cronologico inverso)

Materiale didattico

Libro utilizzato dal docente.

S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani. Algorithms, McGraw-Hill, 2006.

Ottimi testi alternativi in lingua italiana

  • [BM] A. Bertossi, A. Montresor Algoritmi e strutture dati (seconda edizione), Edizioni Città Studi.
  • [CLRS] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati (terza edizione), McGraw-Hill.
  • [CGGR] P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi. Strutture di dati e algoritmi, Pearson Education Italia S.r.L.
  • [DFI] C. Demetrescu, I. Finocchi, G.F. Italiano. Algoritmi e strutture dati (seconda edizione), McGraw-Hill.

Appunti delle lezioni

Di alcuni argomenti verranno rese disponibili, con il progredire delle lezioni, dispense/trasparenze preparate dai docenti

Altro materiale fornito dal docente.

Reso disponibile come indicato sopra.

Materiale on line di ottima qualità.

Si tratta di materiale scaricabile da siti di insegnamenti attivati presso corsi di laurea in Informatica o Ingegneria informatica di Università italiane che hanno parti in comune con il presente insegnamento.

AteneoDocenteInsegnamentoPagina web
PadovaGeppino PucciDati e algoritmi 2http://www.dei.unipd.it/~geppo/DA2/index.html
Roma “Tor Vergata”Fabrizio GrandoniAlgoritmi e strutture datihttp://www.disp.uniroma2.it/users/grandoni/ASDonline.html
MilanoMassimiliano GoldwurmAlgoritmi e strutture datihttp://homes.di.unimi.it/~goldwurm/algo/
FerraraMaria FedericoAlgoritmi e strutture datihttp://algogroup.unimore.it/people/maria/algoritmi_2013-2014.html

Esami

Modalità d'esame

  • Sono previste due prove scritte ed un orale opzionale.
  • La prima prova, della durata di un'ora circa, è volta a verificare la padronanza tecnica e linguistica degli argomenti presentati a lezione. In essa può venire richiesto di enunciare e/o dimostrare un teorema visto a lezione, di indicare il risultato prodotto da un algoritmo su dati assegnati, di studiare il costo computazionale di un algoritmo, ecc.
  • La seconda prova scritta, della durata massima di due ore, consiste nella risoluzione di un problema di media complessità simile a (ma non coincidente con) un problema visto a lezione.
  • Chi abbia superato lo scritto (cioè ottenuto un voto maggiore o uguale di 18/30) può facoltativamente sostenere una prova orale, ovvero verbalizzare direttamente il voto dello scritto.

Iscrizione e risultati

  • È necessario iscriversi alla prova scritta tramite il sistema esse3 tassativamente entro due giorni dalla data dell'appello (il giorno prima le iscrizioni saranno chiuse). Chi riscontri problemi nell'iscrizione all'esame può inviare una mail al docente
  • L'esito della prova scritta viene comunicato su questa pagina web
  • Ci sono 6 appelli nelle sessioni di un anno accademico. Uno studente può iscriversi e partecipare a qualsiasi appello senza obbligo di consegna dell'elaborato. Tuttavia, si può consegnare l'elaborato stesso al più tre volte in un anno accademico e mai in due appelli consecutivi.

Elenco degli appelli

>>
Data appello Ora Luogo Esiti
18 giugno 2015 11.00 Aula M1.1 Visualizza
1 luglio 2015 15.00 Aula M1.1 Visualizza
22 luglio 2015 15.00 Aula M1.1 Visualizza
16 settembre 2015 15.00 Aula M1.1 Visualizza
20 gennaio 2016 14.30 Aula M1.4 Visualizza
3 febbraio 2016 14.30 Aula M1.4 Visualizza