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
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.

Programma dettagliato

Argomento Riferimenti al libro di testo Ore previste
Ruolo degli algoritmi nell'elaborazione dei dati Capitolo 1 3
Introduzione alle tecniche di analisi e di progettazione Capitolo 2 3
Forme asintotiche Capitolo 3 1
Ricorrenze Capitolo 4, escluso il paragrafo 4.4 2
Analisi probabilistica e algoritmi randomizzati Capitolo 5 e Appendice C (solo cenni) 3
Esercizi sulla prima parte del corso 4
Heapsort Capitolo 6 3
Quicksort Capitolo 7 3
Ordinamento in tempo lineare Capitolo 8 3
Mediane e statistiche d'ordine Capitolo 9 3
Esercizi sulla seconda parte del corso 4
Grafi e alberi: definizioni e proprietà Appendici B.4 e B.5 2
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 6
Alberi binari di ricerca Capitolo 12, escluso il paragrafo 12.4 3
Esercizi sulla terza parte del corso 3
Programmazione dinamica Capitolo 15 6
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 5
Strutture dati per insiemi disgiunti Capitolo 21, escluso il paragrafo 21.4 3
Alberi di connessione (o copertura) minimi Capitolo 23 3
Cammini minimi da sorgente unica Capitolo 24, esclusi i paragrafi 24.5 e 24.6 5
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)

  • 27 dicembre 2010 - Date appelli
    Nella sezione relativa agli esami sono state inserite le date degli appelli della sessione invernale. Si ricorda agli studenti che è necessario prenotarsi utilizzando il sistema esse3. Si ricorda altresì che è possibile iscriversi un massimo di tre volte in un anno. Per evitare equivoci, questo vuol dire che dal giorno del primo appello sostenuto fino al giorno del (l'eventuale) quarto "tentativo" devono passare più di 365 giorni.
  • 20 settembre 2010 - Risultati dello scritto del 16 settembre 2010
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. La prova orale, per gli studenti ammessi, si terrà domani, martedì 21 settembre 2010, con inizio alle ore 16.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione (primo piano).
  • 27 agosto 2010 - Appello di settembre
    L'appello si svolgerà il giorno giovedì 16 settembre 2010, alle ore 15.00, nell'aula V del Dipartimento di Matematica.
  • 22 luglio 2010 - Risultati dello scritto del 21 luglio 2010
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. La prova orale, per gli studenti ammessi, si terrà lunedì prossimo (26 luglio 2010), con inizio alle ore 10.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione (primo piano).
  • 1 luglio 2010 - Risultati dello scritto del 30 giugno 2010
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. La prova orale, per gli studenti ammessi, si terrà mercoledì prossimo (7 luglio 2010), con inizio alle ore 10.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
  • 20 giugno 2010 - Risultati dello scritto del 16 giugno 2010
    Nella sezione relativa agli esami sono stati inseriti i risultati della prova scritta. La prova orale, per gli studenti ammessi, si terrà mercoledì prossimo (23 giugno 2010), con inizio alle ore 15.00, nello studio del docente presso il dip. di Ingegneria dell'Informazione.
  • 21 maggio 2010 - Date appelli
    Nella sezione relativa agli esami sono state inserite le date degli appelli della sessione estiva. Si ricorda agli studenti che è necessario prenotarsi utilizzando il sistema esse3. Si ricorda altresì che è possibile iscriversi un massimo di tre volte in un anno. Per evitare equivoci, questo vuol dire che dal giorno del primo appello sostenuto fino al giorno del (l'eventuale) quarto "tentativo" devono passare più di 365 giorni.
  • 26 marzo 2010 - Lezione/esercitazione di recupero
    La lezione in oggetto si terrà il giorno lunedì 29 marzo 2010 alle ore 14 in aula V.
  • 10 marzo 2010 - Sospensione lezioni
    A causa della nevicata, e dei comprensibili disagi per raggiungere il dip. di Matematica, la lezione di oggi è sospesa.
  • 27 febbraio 2010 - Orario di ricevimento
    Si consulti l'apposita pagina

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
Lezione introduttiva zip,   tgz
Testi d'esame relativi ad anni precedenti zip,   tgz
Hashing zip,   tgz
Codici Huffman: aspetti implementativi zip,   tgz
Componenti fortemente connesse zip,   tgz
Dijkstra e Bellman-Ford zip,   tgz

Esami

Data appello Ora Luogo Esito scritto
16 giugno 2010 15.00 Dipartimento di Matematica, Aula V Visualizza
30 giugno 2010 10.00 Dipartimento di Matematica, Aula V Visualizza
21 luglio 2010 10.00 Dipartimento di Matematica, Aula V Visualizza
16 settembre 2010 15.00 Dipartimento di Matematica, aula V Visualizza
2 febbraio 2011 10.00 Dipartimento di Matematica, Aula V
23 febbraio 2011 10.00 Dipartimento di Matematica, Aula V