Complessità degli algoritmi. Strutture dati astratte: pile, code, code con priorità, alberi, grafi 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. Algoritmi di visita di grafi. Algoritmi per il 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
Al termine dell’insegnamento lo studente:
• conosce le strutture dati fondamentali (liste, alberi e grafi), ne ha compreso l’utilizzo, le possibili implementazioni e le operazioni fondamentali ed è in grado di valutare la complessità computazionale di tali operazioni;
• conosce gli algoritmi di ricerca su memoria interna, gli algoritmi di ordinamento e gli algoritmi di base sui grafi e sui grafi pesati;
• ha compreso il funzionamento di tali algoritmi e lo sa riprodurre;
• sa calcolare la complessità computazionale dei suddetti algoritmi nel caso ottimo e nel caso medio;
• sa analizzare un problema;
• sa individuare e/o progettare le strutture dati e l’algoritmo più idonei a risolvere il problema ed al suo contesto applicativo;
• sa stimare il costo computazionale della soluzione proposta;
• sa implementare la soluzione in modo corretto ed efficiente;
• sa motivare le scelte fatte argomentandole ed utilizzando un linguaggio tecnico corretto.
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 per prove in itinere: 4
Il corso è organizzato in lezioni frontali, didattica di laboratorio e attività da svolgere on line. Le lezioni frontali prevedono, oltre alla spiegazione degli argomenti in programma, esercitazioni con simulazione del funzionamento delle principali strutture dati e degli algoritmi, discussioni e confronto sulle principali caratteristiche degli oggetti trattati e valutazione della loro efficienza.
La didattica in laboratorio prevede principalmente l’implementazione in Java di alcuni algoritmi visti durante le lezioni frontali e la simulazione di alcune strutture dati astratte tramite strutture dati interne opportune. Sono anche proposti alcuni esercizi da svolgere in aula al calcolatore.
Le attività on line includono esercizi con soluzione, test a risposta multipla, documenti di approfondimento e di inquadramento storico e forum di discussione.
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) e una prova orale con interrogazione su tutto il programma e la discussione di un progetto da sviluppare in piccoli gruppi (2-3 persone).
Nella prova scritta verrà valutata la comprensione del funzionamento delle strutture dati e degli algoritmi visti a lezione, la capacità di analizzare la complessità di semplici strutture e algoritmi, la capacità di applicare le conoscenze acquisite per la risoluzione di problemi nuovi. Per accedere alla prova orale è necessario superare la prova scritta.
Nella prova orale verrà valutata la conoscenza degli argomenti presentati, l’acquisizione del linguaggio tecnico adeguato al contesto, la capacità di mettere in relazione fra loro argomenti diversi del programma.
La media aritmetica del voto della prova orale e della prova scritta incide del 90% sulla votazione finale.
Il progetto deve essere svolto in Java e l'argomento verrà assegnato dopo lo svolgimento del 70% delle esercitazioni di laboratorio. Relativamente allo sviluppo del progetto verranno valutate le strategie utilizzate per la risoluzione e lo svolgimento del progetto dal punto di vista algoritmico e delle strutture dati usate. Gli studenti durante la discussione devono dare prova della consapevolezza delle scelte fatte e delle strategie messe in pratica.
La valutazione del progetto incide del 10% sulla valutazione finale
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.