ING-INF/05 Algoritmi e Strutture Dati Algorithms and Data Structures

A.A.
CFU Durata (ore)
Periodo Sede
2013/2014 12 96 ore Primo e secondo semestre Collegio Raffaello, Piazza della Repubblica 13, Urbino

Assegnato ai Corsi di Studio

Docente


Valerio Freschi

valerio.freschi@uniurb.it

Obiettivi Formativi
Il Corso ha lo scopo di illustrare le principali tecniche di progettazione di algoritmi e di descrivere ed analizzare gli algoritmi di base più diffusi e le strutture dati in essi utilizzate, con particolare riferimento agli aspetti di complessità computazionale.

Programma
01. Introduzione agli algoritmi e alle strutture dati:
      01.01 Algoritmi e loro tipologie.
      01.02 Correttezza di un algoritmo rispetto ad un problema.
      01.03 Complessità di un algoritmo rispetto all'uso di risorse.
      01.04 Strutture dati e loro tipologie.
 
02. Classi di problemi:
      02.01 Problemi decidibili e indecidibili.
      02.02 Problemi trattabili e intrattabili.
      02.03 Teorema di Cook.
      02.04 NP-completezza.
 
03. Complessità degli algoritmi:
      03.01 Notazioni per esprimere la complessità asintotica.
      03.02 Calcolo della complessità di algoritmi non ricorsivi.
      03.03 Calcolo della complessità di algoritmi ricorsivi.
 
04. Algoritmi per array:
      04.01 Array: definizioni di base e problemi classici.04.02 Algoritmo di visita per array.
      04.03 Algoritmo di ricerca lineare per array.
      04.04 Algoritmo di ricerca binaria per array ordinati.
      04.05 Criteri di confronto per algoritmi di ordinamento per array.
      04.06 Insertsort.
      04.07 Selectsort.
      04.08 Bubblesort.
      04.09 Mergesort.
      04.10 Quicksort.
      04.11 Heapsort.
      04.12 Code con priorità basate su heap binari.
 
05. Algoritmi per liste:
      05.01 Liste: definizioni di base e problemi classici.
      05.02 Algoritmi di visita, ricerca, inserimento e rimozione per liste.
      05.03 Algoritmi di inserimento e rimozione per code.
      05.04 Algoritmi di inserimento e rimozione per pile.
 
06. Algoritmi per alberi:
      06.01 Alberi: definizioni di base e problemi classici.
      06.02 Algoritmi di visita e ricerca per alberi binari.
      06.03 Algoritmi di ricerca, inserimento e rimozione per alberi binari di ricerca.
      06.04 Criteri di bilanciamento per alberi binari di ricerca.
      06.05 Algoritmi di ricerca, inserimento e rimozione per alberi binari di ricerca rosso-nero.
 
07. Algoritmi per grafi:
      07.01 Grafi: definizioni di base e problemi classici.
      07.02 Algoritmi di visita e ricerca per grafi.
      07.03 Algoritmo di ordinamento topologico per grafi diretti e aciclici.
      07.04 Algoritmo delle componenti fortemente connesse per grafi.
      07.05 Algoritmo di Kruskal.
      07.06 Algoritmo di Prim.
      07.07 Proprietà del percorso più breve.
      07.08 Algoritmo di Bellman-Ford.
      07.09 Algoritmo di Dijkstra.
      07.10 Algoritmo di Floyd-Warshall.
 
08. Algoritmi per stringhe:
      08.01 Stringhe: definizioni di base e problemi classici.
      08.02 Algoritmo ingenuo di string matching.
      08.03 Algoritmo per il calcolo della distanza di edit tra stringhe.
      08.04 Algoritmo per il calcolo della massima sottosequenza comune.
 
09. Selezione e statistiche d'ordine:
      09.01 Definizioni di base e problemi.
      09.02 Heapselect.
      09.03 Selezione randomizzata.
      09.04 Selezione deterministica.
 
10. Tecniche algoritmiche:
      10.01 Tecnica del divide et impera.
      10.02 Programmazione dinamica.
      10.03 Tecnica golosa.
      10.04 Tecnica per tentativi e revoche.
 
11. Attività di laboratorio:
       11.01 Elementi di linguaggio C: richiami, editing, compilazione, debugging.
       11.02 Generatori di numeri pseudocasuali: funzioni rand e srand.
       11.03 Valutazione sperimentale della complessità degli algoritmi: timing e contatori.
       11.04 Confronto sperimentale degli algoritmi di ordinamento per array.
       11.05 Confronto sperimentale degli algoritmi di ricerca per alberi binari.
       11.06 Implementazione di algoritmi su grafi: visita in ampiezza e profondità di un grafo, algoritmo di Dijkstra.
       11.07 Implementazione di algoritmi su stringhe: Edit Distance e LCS.

Eventuali Propedeuticità
Non vi sono propedeuticità obbligatorie. Si suggerisce di sostenere l'esame di Algoritmi e Strutture Dati dopo aver sostenuto gli esami di Programmazione Procedurale e Logica e Analisi Matematica e prima di sostenere gli esami di Sistemi Operativi, Basi di Dati, Reti di Calcolatori, Ingegneria del Software.

Modalità Didattiche, Obblighi di Frequenza, Testi di Studio e Modalità di Accertamento
Modalità Didattiche
Lezioni teoriche ed esercitazioni di laboratorio.
Obblighi di Frequenza
Sebbene fortemente consigliata, la frequenza non è obbligatoria.
Testi di Studio
Cormen, Leiserson, Rivest, Stein, "Introduzione agli Algoritmi e alle Strutture Dati", McGraw-Hill, 2010.
(Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", MIT Press, 2009.)

Demetrescu, Finocchi, Italiano, "Algoritmi e Strutture Dati", McGraw-Hill, 2008.

Crescenzi, Gambosi, Grossi, "Strutture di Dati e Algoritmi", Pearson/Addison-Wesley, 2012.

Sedgewick, "Algoritmi in C", Pearson/Prentice Hall, 2002.
(Sedgewick, "Algorithms in C", Addison-Wesley, 1997.)

Modalità di Accertamento
Progetto individuale di laboratorio, prova scritta e prova orale.
Il progetto individuale, da consegnare almeno sette giorni prima della prova scritta, viene valutato in trentesimi ed è ritenuto sufficiente se il relativo voto, che rimane valido per tutti gli appelli dell'anno accademico in cui il progetto viene consegnato, è di almeno 18/30. Qualora il progetto venga riconsegnato in un appello successivo, il voto del progetto precedentemente consegnato viene annullato. Se la riconsegna avviene nella medesima sessione, al voto del nuovo progetto consegnato viene applicata una penale di 5/30.

La prova scritta, che può essere sostenuta solo previo superamento del progetto, viene valutata in trentesimi ed è ritenuta sufficiente se il relativo voto, che rimane valido per il solo appello in cui la prova viene sostenuta, è di almeno 18/30.

La prova orale, che può essere sostenuta solo previo superamento delle altre due prove, comporta un aggiustamento per eccesso o per difetto di al più 5/30 della media aritmetica dei voti delle altre due prove, determinando così il voto finale.

Note
L'insegnamento è erogato sia in presenza che a distanza nel Corso di Laurea in Informatica Applicata.
Materiale didattico e informazioni aggiuntive: http://www.sti.uniurb.it/freschi/Didattica/asd.html