ID:
76978
Tipo Insegnamento:
Opzionale
Durata (ore):
48
CFU:
6
Url:
MATEMATICA/Percorso Comune Anno: 2
Anno:
2025
Dati Generali
Periodo di attività
Secondo Semestre (23/02/2026 - 05/06/2026)
Syllabus
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
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 e tecniche di programmazione di base, includendo la gestione dei puntatori.
Aver superato con successo l'esame di Programmazione.
Aver superato con successo l'esame di Programmazione.
Metodi didattici
lezioni frontali. 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. Obbligatorio consegnare almeno uno degli esercizi richiesti per il laboratorio per essere ammessi all'esame. 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.
- 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.
Testi
************
*ATTENZIONE*: le dispense saranno pubblicate sulla piattaforma ClassRoom . Obbligatoria l'iscrizione.
CODICE: fp4rwqs
************
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.
*ATTENZIONE*: le dispense saranno pubblicate sulla piattaforma ClassRoom . Obbligatoria l'iscrizione.
CODICE: fp4rwqs
************
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 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. (14 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 (10 ore)
7.Grafi: visite, ordinamento topologico, componenti fortemente connesse, alberi di copertura minimi, percorsi minimi (10 ore)
8. Classi di complessità e problemi hard (4 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.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 (10 ore)
7.Grafi: visite, ordinamento topologico, componenti fortemente connesse, alberi di copertura minimi, percorsi minimi (10 ore)
8. Classi di complessità e problemi hard (4 ore)
Lingua Insegnamento
ITALIANO
Corsi
Corsi
MATEMATICA
Laurea Magistrale
2 anni
No Results Found
Persone
Persone
Docenti di ruolo di IIa fascia
No Results Found