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

Informazioni generali (A.A. 2013/14)

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. 2012/13

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 È fortemente consigliato 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-4 (ex aula V) Edificio ex Matematica
  • Giovedì 9 - 11, Aula M1-4 (ex aula V) Edificio ex Matematica

Avvisi (in ordine cronologico inverso)

  • 26 febbraio 2015 - Risultati della prova scritta del 25 febbraio 2015.
    Scaricabili dalla sezione Appelli
  • 23 gennaio 2015 - Risultati "finali" della prova d'esame del 14 gennaio u.s.
    Scaricabili dalla sezione Appelli, con relative indicazioni su correzione, verbalizzazione ed eventuali orali.
  • 14 gennaio 2015 - Risultati della prova scritta di oggi
    Sono scaricabili dalla sezione relativa agli appelli. La seconda prova scritta avrà luogo il giorno 21 gennaio 2015, alle ore 14.30 in aula M1.5.
  • 21 settembre 2014 - Risultati della seconda prova scritta (18 settembre 2014)
    Scaricabili dalla sezione relativa agli esami. Gli studenti devono informare il docente riguardo la decisione di sostenere la prova orale (entro una settimana, dopodich´ verrà chiuso il verbale).
  • 12 settembre 2014 - Risultati della prova scritta del 10 settembre 2014
    Il file con l'elenco dei soli ammessi alla seconda prova è scaricabile dalla sezione relativa agli esami. La seconda prova si terrà il giorno 18 settembre 2014 alle ore 15.00 (aula M1.5 dell'edificio ex. Matematica)
  • 19 luglio 2014 - Risultati finali appello del 17 e 18 luglio 214
    Dalla sezione relativa agli esami sono scaricabili i voti "verbalizzabili" per ciascuno studente. Chi intendesse sostenere l'orale è pregato di contattare il docente via email. In assenza di comunicazioni, in settimana il verbale verrà chiuso.
  • 17 luglio 2014 - Risultati della prova scritta di oggi
    Il file con l'elenco dei soli ammessi alla seconda prova di domani (18 luglio 2014, ore 14.30) è scaricabile dalla sezione relativa agli esami.
  • 27 giugno 2014 - Risultati della seconda prova scritta (26 giugno 2014)
    Scaricabili dalla sezione relativa agli esami. Gli studenti devono informare il docente riguardo la decisione di sostenere la prova orale.
  • 25 giugno 2014 - Risultati della prova scritta di oggi
    Il file con l'elenco dei soli ammessi alla seconda prova di domani (26 giugno 2014) è scaricabile dalla sezione relativa agli esami.
  • 16 giugno 2014 - Risultati della seconda prova scritta del 13 u.s. e voto finale verbalizzabile
    Scaricabile dalla sezione esami. Gli studenti devono informare il docente riguardo la decisione di sostenere la prova orale.
  • 12 giugno 2014 - Esito della prova scritta di questa mattina
    Il file con l'elenco dei soli ammessi alla seconda prova di domani (13 giugno 2014) è scaricabile dalla sezione relativa agli esami.
  • 13 maggio 2014 - Sospensione attività didattica
    Si avvisano gli studenti che la lezione di giovedì 15 maggio 2014 non verrà svolta.
  • 7 marzo 2014 - Orario di ricevimento
    Causa impegno del docente il prossimo ricevimento è spostato. Al riguardo si consulti l'apposita pagina Web. Si ricorda che ricevimenti personalizzati possono essere richiesti da studenti lavoratori via email al docente.

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.

La seguente tabella (in costruzione) elenca nei dettagli gli argomenti in programma. Essi sono tutti trattati nel libro utilizzato dal docente (con minime eccezioni). La tabella illustra comunque in quali testi alternativi sono trattati e se sono previsti appunti da parte del docente (il simbolo ✔ indica che l'argomento è trattato o che gli appunti sono previsti).

Argomento[BM][CLRS][CGGR][DFI]Appunti
Numeri di Fibonacci
Notazione asintotica
Algoritmi aritmetici di base
Aritmetica modulare
Test di primalità/generazione di primi casuali
Crittografia a chiave privata/pubblica
Hashing
Tecnica divide-et-impera
Mergesort e quicksort
Risoluzione di ricorrenze
Moltiplicazione efficiente di interi
Moltiplicazione di matrici

Appunti delle lezioni

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
12 giugno 2014 10.00 Edificio ex Matematica - Aula III Visualizza
25 giugno 2014 10.00 Edificio ex Matematica - Aula III Visualizza
17 luglio 2014 10.00 Edificio ex Matematica - Aula IV Visualizza
10 settembre 2014 15.00 Edificio ex Matematica - Aula III Visualizza
14 gennaio 2015 9.30 Edificio ex Matematica - Aula IV Visualizza
18 febbraio 2015 9.30 Edificio ex Matematica - Aula M2.5 Visualizza