ALGORITMI E STRUTTURE DATI
Anno accademico e docente
Non hai trovato la Scheda dell'insegnamento riferita a un anno accademico precedente?
Ecco come fare >>
- English course description
- Anno accademico
- 2016/2017
- Docente
- GUIDO SCIAVICCO
- Crediti formativi
- 10
- Periodo didattico
- Primo Semestre
- SSD
- INF/01
Obiettivi formativi
- Il corso introduce le principali metodologie per la specifica, l'analisi e la realizzazione di algoritmi e strutture dati statiche e dinamiche.
Argomenti trattati (Conoscenze):
- introduzione all'analisi di algoritmi
- notazione O, Theta, Omega, per gli ordini di grandezza delle funzioni di complessitá
- algoritmi ricorsivi, ricorrenze e soluzione di ricorrenze con diversi metodi
- algoritmi di ordinamento (InsertionSort,SelectionSort,Mergesort,Quicksort,HeapSort)
- algoritmi di ordinamento lineare (es.: CountingSort)
- strutture dati elementari come liste e code
- alberi binari di ricerca ed operazioni su di essi
- alberi binari bilanciati (Red-Black trees) ed operazioni su di essi
- alberi B ed operazioni su di essi
- grafi orientati, non orientati, pesati e non pesati
- visita su grafi in ampiezza e in profonditá
- ordinamento topologico
- percorsi minimi su grafi pesati
- string matching
Al termine del corso lo studente sará capace di (Abilitá):
- Analizzare un algoritmo per la risoluzione di un problema in termini della sua complessitá asintotica, e confrontare due soluzioni diverse
- Riconoscere un problema di ordinamento e scegliere o progettare il miglior algoritmo di ordinamento per risolverlo
- Progettare ed analizzare una struttura dati elementare o non elementare a supporto di un algoritmo, offrendo opportuni metodi di accesso ed analizzandone la complessitá asintotica
- Progettare ed analizzare una struttura dati di tipo albero, offrendo opportuni metodi di accesso ed analizzandone la complessitá asintotica
- Progettare ed analizzare una struttura dati di tipo grafo, offrendo opportuni metodi di accesso ed analizzandone la complessitá asintotica
- Riconoscere e risolvere il problema del pattern matching Prerequisiti
- matematica elementare e tecniche di programmazione di base, includendo la gestione dei puntatori.
Aver superato con successo l'esame di Programmazione e Laboratorio. Contenuti del corso
- 1.Presentazione
Definizioni essenziali
Il problema dell'ordinamento con algoritmi semplici
Il problema della ricerca su un insieme ordinato
Il problema dell'ordinamento con MergeSort
2.Lo schema Divide and Conquer
Ordini di grandezza
Risoluzione di ricorrenze
3.La struttura dati heap.
Il problema dell'ordinamento con HeapSort
Code di prioritá ed applicazioni
L'algoritmo QuickSort per il problema dell'ordinamento
Il problema dell'ordinamento in tempo lineare
4.Introduzione alle Strutture Dati
Stack, Code e Liste
Tavole Hash e conflitti
Calcolo della complessitá di accesso a una tavola Hash
5.Alberi binari di ricerca ed operazioni di base su di essi
Alberi binari red-black ed operazioni di base su di essi
6.Gli alberi B e le operazioni di base su di essi.
Introduzione ai grafi e visita in ampiezza di un grafo
7.Visita in profonditá di un grafo
Grafi diretti aciclici e ordinamento topologico
Componenti fortemente connesse di un grafo diretto
Costruzione del grafo delle componenti
8.Strutture dati avanzate: Insiemi Disgiunti ed analisi ammortizzata della complessita
Alberi di copertura minima
Algoritmo di Kruskal per l'albero di copertura minimo
Algoritmo di Prim per l'albero di copertura minimo
9.Percorsi minimi con sorgente singola in grafi diretti pesati
Algoritmo di Belmann-Ford
Algoritmo per percorsi minimi con sorgente singola in grafi diretti pesati aciclici
Algoritmo di Dijkstra
10.Il problema del pattern matching
Un algoritmo semplice per il patter matching
L'algoritmo di Rabin-Karp per il pattern matching
L'algoritmo DFA per il patter matching Metodi didattici
- Lezioni frontali e esercitazioni.
La lezione settimanale é divisa in 5 ore di teoria e 2 di laboratorio. Durante il laboratorio vengono proposti degli esercizi da svolgere personalmente. Verranno valuati in date precise, comunicate in classe. Modalità di verifica dell'apprendimento
- Esame scritto tipo test. Un esame scritto é composto da 20 domande, ognuna con 4 possibili risposte, di peso uguale e di valore 1.2 trentesimi ciascuna. Ogni 4 errori o domande senza risposta si conta -1.2. Il massimo punteggio raggiungibile é 24/30. La parte di laboratorio si valuta in forma continua e personale durante le lezioni di laboratorio e somma da 0 a 6 punti al massimo. Il minimo per poter essere ammessi allo scritto é 3. La somma dei due voti é il voto finale a meno di un eventuale orale di integrazione, deciso dal docente, che puó variare il voto finale in minima parte - massimo 3 trentesimi.
Le domande nel test - con una sola risposta esatta di 4 possibili - variano su tutto il programma e puntano a controllare che gli studenti abbiano raggiunto una conoscenza di tipo:
- base, con domande relative alla conoscenza pura
- applicativo, con domande relative all'esecuzione di algoritmi, il loro comportamento, possibili variazioni, ed uso
- di compresione profonda, con domande relative alla soluzione di problemi piú complessi o che richiedono un certo grado di intuizione. Testi di riferimento
- 1)Introduzione agli algoritmi, 3/ed
Autori: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
ISBN: 9788838665158
Data: Giugno 2010
Pagine: 1030
2)The Algorithm Design Manual, 2nd Edition
Steven Skiena
ISBN: 9781848000698
Pub Date: 2012.
Consigliata la versione originale non tradotta.
3)Dispense fornite dal docente.
