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

Informazioni generali (A.A. 2016/17)

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. 2015/16

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 L1.3 Edificio ex Fisica
  • Mercoledì 9 - 11, Aula L1.3 Edificio ex Fisica
  • Giovedì 11 - 13, Aula L1.3 Edificio ex Fisica

Avvisi (in ordine cronologico inverso)

  • 14 giugno 2017 - Elenco dei teoremi (o comunque dei risultati) dei quali potrà essere chiesta dimostrazione formale come parte della seconda prova d'esame.

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ù quattro volte in un anno accademico.

Elenco degli appelli

Data appello Ora Luogo Esiti