Algoritmi e strutture dati

Informazioni generali sull'insegnamento

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

Obiettivi formativi e programma dettagliato

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. Tale introduzione viene fatta seguendo quasi tutti gli argomenti classici per un corso introduttivo di algoritmica: strutture dati di base, algoritmi di ordinamento, strutture dati per la ricerca, tecniche algoritmiche (divide-et-impera, greedy e programmazione dinamica), algoritmi su grafo, metodologie per la valutazione del consumo delle risorse spazio-tempo. 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.

Scarica il documento che riassume gli obiettivi formativi, gli argomenti e le modalità d'esame dell'insegnamento.

Programma "previsto" in dettaglio

Argomento Riferimenti al libro di testo Ore previste
Ruolo degli algoritmi nell'elaborazione dei dati Capitolo 1 2
Introduzione alle tecniche di analisi e di progettazione Capitolo 2 2
Forme asintotiche Capitolo 3 1
Ricorrenze Capitolo 4, escluso il paragrafo 4.4 2
Esercizi sulla prima parte del corso 4
Heapsort Capitolo 6 3
Quicksort Capitolo 7 2
Ordinamento in tempo lineare Capitolo 8 2
Mediane e statistiche d'ordine Capitolo 9 2
Esercizi sulla seconda parte del corso 4
Grafi e alberi: definizioni e proprietà Appendici B.4 e B.5 1
Strutture dati elementari Capitolo 10, esclusi i paragrafi 10.2 e 10.3 2
Hashing Capitolo 11, esclusi i paragrafi 11.3.3 e 11.5 4
Alberi binari di ricerca, algoritmi di visita di alberi Capitolo 12, escluso il paragrafo 12.4 3
Alberi rosso-neri Capitolo 13 4
Esercizi sulla terza parte del corso 3
Programmazione dinamica Capitolo 15 5
Algoritmi greedy Capitolo 16, solo i paragrafi 16.1, 16.2 e 16.3 4
Esercizi sulla quarta parte del corso 2
Algoritmi elementari per grafi Capitolo 22, escluso il paragrafo 22.5 4
Strutture dati per insiemi disgiunti Capitolo 21, escluso il paragrafo 21.4 2
Alberi di connessione (o copertura) minimi Capitolo 23 3
Cammini minimi da sorgente unica Capitolo 24, esclusi i paragrafi 24.5 e 24.6 4
Flusso massimo Capitolo 26, esclusi i paragrafi 26.4 e 26.5 4
Esercizi sulla quinta parte del corso 3

Orario delle lezioni

  • Martedì 11 - 13 (Aula V Dip. Matematica)
  • Mercoledì 11 - 13 (Aula V Dip. Matematica)
  • Giovedì 9 - 11 (Aula V Dip. Matematica)

Avvisi (in ordine cronologico inverso)

  • 19 febbraio 2012 - Risultati della prova scritta del 15 febbraio 2012
    Dalla sezione relativa agli esami è scaricabile il file dei risultati, con elencati gli studenti ammessi alla prova orale; prova che si terrà martedì prossimo (21 febbraio 2012) con inizio alle ore 15.00 presso l'ufficio del docente.
  • 15 settembre 2011 - Risultati della prova scritta di ieri
    Nella sezione relativa agli appelli sono stati inseriti i risultati della prova scritta di ieri. Gli esami orali si svolgeranno il giorno 20 settembre 2011, alle ore 10.45 presso l'ufficio del docente (primo piano del dipartimento di Ingegneria dell'informazione).
  • 26 agosto 2011 - Appello di settembre
    L'appello si terrà il giorno 14 settembre 2011, con inizio alle ore 15.00, presso l'aula I del Dipartimento di Matematica.
  • 15 luglio 2011 - Risultati della prova scritta di ieri
    Nella sezione relativa agli appelli sono stati inseriti i risultati della prova scritta di ieri. Gli esami orali si svolgeranno il giorno 19 luglio 2011, alle ore 10.30 presso l'ufficio del docente (primo piano del dipartimento di Ingegneria dell'informazione).
  • 24 giugno 2011 - Variazione data orale
    L'esame orale previsto per il giorno 29 giugno 2011 (avviso del 24 giugno u.s.) spostato al giorno 30 giugno 2011, a partire dalle ore 9.00, stesso luogo.
  • 24 giugno 2011 - Risultati della prova scritta di ieri
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta del 23 giugno 2011. Gli esami orali si terranno il giorno 29 giugno 2011, a partire dalle ore 15.00, presso lo studio del docente (primo piano del Dipartimento di Ingegneria dell'Informazione).
  • 9 giugno 2011 - Risultati dello scritto di oggi
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta di oggi. Gli esami orali si terranno il giorno 10 giugno 2011, alle ore 11.00, presso lo studio del docente (primo piano del Dipartimento di Ingegneria dell'Informazione).
  • 13 marzo 2011 - Rinvio lezione del 15 marzo 2011
    La lezione di martedì 15 marzo 2011 è rinviata per impedimento del docente. Riguardo il giorno e l'ora del recupero verrà data comunicazione con ampio anticipo sia a voce sia mediante avviso sul sito Web.

Materiale didattico

Libro di testo

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein
Introduzione agli algoritmi e strutture dati
McGraw-Hill

Libri di consultazione

P. Crescenzi, G. Gambosi, R. Grossi
Strutture di dati e algoritmi
Pearson Education Italia S.r.L.

C. Demetrescu, I. Finocchi, G.F. Italiano
Algoritmi e strutture dati
McGraw-Hill

Altro materiale didattico

Argomento File download
Testi d'esame relativi ad anni precedenti zip,   tgz
Indel in alberi rosso-neri zip,   tgz
Hash su stringhe zip,   tgz
Breve introduzione alla crittografia zip,   tgz

Esami

Data appello Ora Luogo Esito scritto
9 giugno 2011 9.00 Dip. di Matematica, aula V Visualizza
23 giugno 2011 9.00 Dip. di Matematica, aula I Visualizza
14 luglio 2011 9.30 Dip. di Matematica, aula III Visualizza
14 settembre 2011 15.00 Dip. di Matematica, aula I Visualizza
15 febbraio 2012 10.00 Dipartimento di Matematica, Aula V Visualizza