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.
Analisi di complessità degli algoritmi. Strutture dati astratte: pile, code, code con priorità, alberi e grafi. Algoritmi di ricerca: sequenziale, binaria, alberi binari di ricerca, alberi 2-3, hash. Algoritmi di ordinamento quadratici, Quicksort, Heapsort, Mergesort. Algoritmi union-find. Grafi e alberi di ricoprimento. Tecniche algoritmiche: divide et impera, greedy. Implementazione in Java delle principali strutture di dati e di alcuni tra i più comuni algoritmi che di esse fanno uso.
Prerequisiti
Nessuno
Metodi Didattici
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
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.
Libri di testo consigliati
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
Altre Informazioni
Orario di ricevimento
Mercoledi', dalle 10.00 alle 11.00 oppure previo appuntamento via e-mail