Complessità degli algoritmi. Strutture dati astratte: pile, code, code con priorità, alberi e grafi pesati. Tecniche algoritmiche: divide et impera, greedy. Algoritmi di ricerca: ricerca binaria, alberi binari di ricerca, alberi AVL, alberi 2-3, ricerca hash. Algoritmi di ordinamento: algoritmi quadratici, mergesort, quicksort, heapsort, Algoritmi union-find. Calcolo del Minimo Albero di Ricoprimento di un grafo.
C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e Strutture Dati, McGraw-Hill, 2008.
C. Demetrescu, U. Ferraro Petrillo, I. Finocchi, G.F. Italiano, Progetto di algoritmi e strutture dati in Java, McGraw-Hill, 2007.
Obiettivi Formativi
Conoscenze:
Lo studente acquisisce conoscenze su strutture dati fondamentali (liste, alberi e grafi), algoritmi di ricerca su memoria interna, algoritmi di ordinamento e algoritmi di base sui grafi.
Competenze acquisite:
Lo studente acquisisce le competenze per comprendere le problematiche di progettazione e valutazione degli algoritmi, con particolare riferimento agli algoritmi non numerici. In particolare, dopo aver superato con successo l'esame del corso, dovrà essere in grado di: analizzare un problema; individuare e/o progettare gli algoritmi risolutivi più idonei al problema ed al suo contesto applicativo; stimare il costo computazionale della soluzione proposta; implementare la soluzione in modo corretto ed efficiente.
Capacità acquisite (al termine del corso): Lo studente è capace di analizzare un problema, stabilire le strutture dati astratte ed il metodo algoritmico di soluzione più idoneo al contesto.
Metodi Didattici
CFU: 12
Numero di ore totali del corso: 300
Numero di ore per studio personale e altre attività formative di tipo individuale: 192
Numero di ore relative alle attività in aula: 80
Numero di ore relative ad attività di laboratorio (lezioni in laboratorio): 16
Numero di ore relative ad attività di esercitazioni (in laboratorio e in campo): 0
Numero di ore relative ad attività seminariali: 0
Numero di ore relative ad attività di stage: 0
Numero di ore per prove in itinere: 4
Altre Informazioni
Frequenza delle lezioni ed esercitazioni: Raccomandata
Strumenti a supporto della didattica UniFi E-Learning: http://e-l.unifi.it
Orario di ricevimento:
Prof. M.C. Verri
Previo Appuntamento via e-mail
Dipartimento di Statistica, Informatica, Applicazioni
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 4237439
Fax: 055 4237436
E-Mail: mariacecilia.verri@unifi.it
Prof. A. Bernini
Su appuntamento.
Dipartimento di Matematica e Informatica
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 4237460
Fax: 055 4237436
E-Mail: antonio.bernini@unifi.it
Modalità di verifica apprendimento
Scritta, Pratica e Orale
Programma del corso
Introduzione agli algoritmi
Analisi di complessità degli algoritmi: operazione fondamentale e dimensione del problema, notazione O grande, complessità nel caso peggiore e nel caso medio, complessità in tempo e in spazio, relazioni fondamentali di ricorrenza.
Strutture dati elementari interne: vettori, liste concatenate, complessità delle operazioni principali.
Strutture dati astratte: pile, code, code con priorità, alberi.
Algoritmi di ricerca: ricerca binaria, alberi binari di ricerca, alberi AVL e 2-3, ricerca digitale e trie, ricerca casuale.
Algoritmi di ordinamento: algoritmi elementari, Quicksort, Mergesort, Heap sort, algoritmi di selezione
Grafi: Rappresentazione dei grafi, algoritmi di visita.
Grafi pesati: Minimo albero ricoprente.