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
A causa dell'emergenza sanitaria, è stato necessario modificare la modalità di svolgimento degli esami.
Pertanto negli appelli dell'anno accademico 2019/20, l'esame consisterà in una prova orale con interrogazione su tutto il programma, esercizi da svolgere e discussione di un progetto che può essere sviluppato in piccoli gruppi (2-3 persone). A chi ha superato la prima prova intermedia, non verrà chiesto di svolgere esercizi sugli argomenti della prima parte del programma.
Lo svolgimento degli esercizi servirà per valutare la comprensione del funzionamento delle strutture dati e degli algoritmi visti a lezione, la capacità di analizzare la complessità dei semplici strutture e algoritmi, la capacità di applicare le conoscenze acquisite per la risoluzione di problemi nuovi.
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.
Il voto riportato nella prova orale 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.