76978 - TEORIA DI ALGORITMI E STRUTTURE DATI

insegnamento

ID:

76978

Tipo Insegnamento:

Opzionale

Durata (ore):

48

CFU:

Url:

Dettaglio Insegnamento:

MATEMATICA/PERCORSO COMUNE Anno: 3

Anno:

2024

Periodo di attività

Secondo Semestre (24/02/2025 - 06/06/2025)

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.

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.

Verifica 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

************
*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.

Contenuti

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)