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.
Prerequisiti
nessuno
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): 24
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. Cecilia Verri
Previo Appuntamento via e-mail
Dipartimento di Statistica, Informatica, Applicazioni
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 2751513
E-Mail: mariacecilia.verri@unifi.it
Prof. A. Bernini
Su appuntamento.
Dipartimento di Matematica e Informatica
Viale Morgagni, 65
50134 - Firenze (FI)
E-Mail: antonio.bernini@unifi.it
Modalità di verifica apprendimento
L'esame si compone di una prova scritta su esercizi di simulazione di algoritmi e strutture dati, una prova orale su tutto il programma e un progetto da sviluppare in piccoli gruppi (2-3 persone).
Il progetto deve essere svolto in Java e l'argomento verrà assegnato dopo lo svolgimento del 70% delle esercitazioni di laboratorio.
Si può ottenere l'esonero dalla prova scritta superando le due prove intermedie che si tengono durante lo svolgimento del corso.
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.