TEORIA DI 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
- 2022/2023
- Docente
- GUIDO SCIAVICCO
- Crediti formativi
- 6
- 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
- tabelle hash
- 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, ciclicità, alberi di copertura minimi, percorsi minimi
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 Prerequisiti
- Matematica elementare. Aver superato con successo l'esame di Programmazione.
Contenuti del corso
- 1.Presentazione, definizioni essenziali, struttura del corso, struttura dell'esame. (1 ora)
2.Ordini di grandezza e soluzione di ricorrenze. (8 ore)
3.Strutture dati elementari: code, pile, code di priorità. (6 ore)
4.Problema dell'ordinamento: algoritmi elementari, algoritmi non elementari, algoritmi per ordinamento linare, limiti dell'ordinamento basato su confronti. (18 ore)
5.Strutture dati non ad albero: liste, tavole hash, strutture per insiemi disgiunti. (8 ore)
6.Strutture dati ad albero: alberi binari di ricerca, alberi binari auto-bilanciati (red black), alberi B (18 ore)
7.Grafi: visite, ordinamento topologico, componenti fortemente connesse, alberi di copertura minimi, percorsi minimi (18 ore) Metodi didattici
- In caso di ritorno alla normalità didattica, le lezioni saranno frontali, con 5 ore settimanali di teoria/esercizi. Nella versione di questo corso per la Laurea in Matematica, non è previsto laboratorio. In caso di ulteroriore proseguimento dell'emergenza sanitaria, il corso sarà costituito dalle lezioni presenti sul canale YouTube con incontri periodici telematici.
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.5 trentesimi ciascuna. Ogni 5 errori o domande senza risposta si conta -1.5. Il massimo punteggio raggiungibile é 30/30; ulteriori 2 trentesimi vengono assegnati con lo svolgimento di esercizi a consegna libera. 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
- ************
*ATTENZIONE*: le dispense saranno pubblicate sulla piattaforma ClassRoom . Obbligatoria l'iscrizione.
CODICE: gmqon6n
************
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.
