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
- 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
- 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 e Laboratorio. 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
- 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.
Modalità di verifica dell'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. Testi di riferimento
- ************
*ATTENZIONE*: le dispense saranno pubblicate sulla piattaforma ClassRoom . Obbligatoria l'iscrizione.
************
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.
