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

Informazioni generali (A.A. 2015/16)

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. 2014/15

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.
  • Algoritmi di ordinamento: insertion-sort, mergesort e quicksort. Tecnica divide-et-impera. 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 minimi 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.
  • Algoritmi di ricerca all'interno di stringhe. Algoritmo a forza-bruta. Algoritmo di Knuth-Morris-Pratt. Automi riconoscitori. Implementazione dell'algoritmo di Knuth-Morris-Pratt in termini di automa. Ricerca di insiemi di pattern: algoritmo di Aho-Corasick.
  • Riconoscimento di pattern descritti mediante espressioni regolari. Automi non deterministici. Costruzione di un automa non deterministico corrispondente ad una data espressione regolare. Simulazione di automi non deterministici.

Orario delle lezioni

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

Avvisi (in ordine cronologico inverso)

  • 22 febbraio 2017 - Risultati della prova scritta di oggi e voti verbalizzabili
    Il file è scaricabile dalla sezione relativa agli esami. Gli studenti che, pur potendo verbalizzare direttamente il voto, intendono sostenere l'orale oppure desiderano ripetere lo scritto sono pregati di contattare il docente con cortese urgenza.
  • 21 febbraio 2017 - Risultati della prova scritta di oggi.
    Il file è scaricabile dalla sezione relativa agli esami. Si rammenta che la seconda prova scritta avrà luogo domani, 22 febbraio 2017, presso l'aula M1.3 con inizio alle ore 9.00.
  • 20 gennaio 2017 - Risultati della seconda prova scritta del 19 gennaio u.s..
    Il file è scaricabile dalla sezione relativa agli esami. Gli studenti che, pur potendo verbalizzare direttamente il voto, intendono sostenere l'orale oppure desiderano ripetere lo scritto sono pregati di contattare il docente con cortese urgenza.
  • 18 gennaio 2017 - Risultati della prova scritta di oggi.
    Il file è scaricabile dalla sezione relativa agli esami.
  • 22 luglio 2016 - Risultati della seconda prova del 21 luglio 2016 e voti verbalizzabili.
    Il file è scaricabile dalla sezione relativa agli esami. Gli studenti interessati a sostenere la prova orale e coloro che vogliono ripetere lo scritto sono pregati di contattare il docente via email con cortese urgenza. In mancanza di comunicazioni, si intenderà che viene accettato il voto verbalizzabile.
  • 20 luglio 2016 - Risultati della prima prova scritta di oggi.
    Il file è scaricabile dalla sezione relativa agli esami.
  • 13 giugno 2016 - Risultati della prima prova scritta di oggi.
    Il file è scaricabile dalla sezione relativa agli esami.
  • 15 giugno 2016 - Risultati della seconda prova scritta e voti verbalizzabili.
    Il file è scaricabile dalla sezione relativa agli esami. Gli studenti interessati a sostenere la prova orale e coloro che vogliono ripetere lo scritto sono pregati di contattare il docente via email. In mancanza di comunicazioni, si intenderà che viene accettato il voto verbalizzabile.

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
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. Può sostenere la seconda prova solo chi abbia conseguito un voto maggiore o uguale a 18/30 nella prima.
  • Lo scritto si intende superato se il voto in entrambe le prove è non inferiore a 18/30. In tal caso il voto complessivo dello scritto è calcolato come la media aritmetica dei voti ottenuti nelle due prove.
  • Chi abbia superato lo scritto può facoltativamente sostenere una prova orale, ovvero verbalizzare direttamente il voto dello scritto.

Iscrizione e risultati

  • È necessario iscriversi alla prima 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 delle prove scritte 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
13 giugno 2016 14.30 Aula M1.2 Visualizza
6 luglio 2016 14.30 Aula M1.2 Visualizza
20 luglio 2016 14.30 Aula M1.2 Visualizza
18 gennaio 2017 14.30 Aula M1.4 Visualizza
21 febbraio 2017 14.30 Aula M1.3 Visualizza