46859 - ALGORITMI E STRUTTURE DATI

insegnamento

ID:

46859

Tipo Insegnamento:

Obbligatorio

Durata (ore):

80

CFU:

Url:

Dettaglio Insegnamento:

INFORMATICA/Percorso Comune Anno: 2

Anno:

2024

Periodo di attività

Secondo Semestre (24/02/2025 - 30/05/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)
- algoritmi di pattern matching
- strutture dati elementari come liste e code
- tabelle hash
- alberi binari di ricerca (BST) ed operazioni su di essi
- alberi binari bilanciati (RBT) ed operazioni su di essi
- grafi, alberi e foreste di visita, ordinamento topologico, ciclicità, e componenti fortemente connesse
- grafi pesati non orientati e alberi di copertura minima
- grafi pesati orientati e alberi di cammini minimi da una sorgente
- grafi pesati orientati e matrici di cammini minimi tra coppie di nodi
- accenni di teoria di complessità e di calcolabilità

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

- Valutare almeno superficialmente la complessità di un problema e la sua fattibilità

Prerequisiti

matematica elementare e tecniche di programmazione di base, includendo la gestione dei puntatori.

Aver superato con successo l'esame di Programmazione e Laboratorio.

Metodi didattici

lezioni frontali sia per la parte di teoria che per la parte di laboratorio. In agguinta, lo studente può utilizzare il canale YouTube del docente con le lezioni della parte di teoria registrate e disponibili.

Verifica Apprendimento

Esame scritto tipo misto test-risposta aperta. 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.

Non ci sono penalizzazioni per risposta errata o mancante.

Per la parte di laboratorio, si organizza un sistema di verifica delle capacità di programmazione algoritmica competitiva; obbligatorio partecipare, e il risultato della verifica contribuisce a formare il voto finale.

Testi

************
*ATTENZIONE*: le dispense saranno pubblicate sulla piattaforma ClassRoom . Obbligatoria l'iscrizione.

CODICE: p62v7z7

************

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. (2 ore)

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. (14 ore)

5.Problema del pattern matching. (4 ore)

5.Strutture dati non ad albero: liste, tavole hash, strutture per insiemi disgiunti. (6 ore)

6.Strutture dati ad albero: alberi binari di ricerca, alberi binari auto-bilanciati (red black), alberi B (8 ore)

7.Grafi: visite, ordinamento topologico, componenti fortemente connesse, alberi di copertura minimi, percorsi minimi (8 ore)

8. Classi di complessità e problemi hard (4 ore)

9. Attività di laboratorio (20 ore)