SITE TITLE

LOGO DIETI

Algoritmi e strutture dati I

Titolo insegnamento in inglese:  Algorithms and data structures I

 Lingua: Italiano 

Insegnamento: Algoritmi e strutture dati I

Anno di corso: II

CFU: 9

SSD: INF/01

Ore di lezione: 72

Semestre: 1

Modulo: Nessuno

Codice: 26220

Obiettivi formativi:
Il corso si propone di fornire le conoscenze di base per la progettazione e l'analisi di algoritmi e strutture dati efficienti. In particolare, verranno illustrate le tecniche di base per l'analisi della complessità degli algoritmi e per la valutazione dell'efficienza delle principali strutture dati. Tali concetti verranno illustrati a livello teorico e metodologico e applicati, a titolo esemplificativo, all’analisi di algoritmi specifici per risolvere problemi fondamentali (ad esempio, algoritmi di ordinamenti e di ricerca), di strutture dati elementari (tra cui liste, alberi, grafi) e strutture dati avanzate (come tabelle hash e alberi bilanciati).

Contenuti:
Cenni al calcolo della complessità computazionale degli algoritmi: notazione asintotica; calcolo del tempo di esecuzione di algoritmi iterativi; calcolo del tempo di esecuzione di algoritmi ricorsivi, metodi di soluzione di equazioni di ricorrenza. Analisi di complessità dei principali algoritmi di ordinamento: insertion sort, selection sort, merge sort, heap sort, quick sort; algoritmi di ordinamento in tempo lineare. Strutture dati elementari e algoritmi fondamentali: heap, code a priorità, stack, liste puntate, alberi. Alberi binari di ricerca, alberi bilanciati: algoritmi di ricerca, inserimento, cancellazione in alberi binari di ricerca, alberi AVL e alberi Rossi e Neri. Rappresentazione di grafi e grafi pesati, algoritmi di attraversamento di grafi: algoritmi di visita in ampiezza (BFS) e in profondità. Applicazioni delle visite di grafi: cammini minimi in grafi non pesati, verifica dell'aciclicità di un grafo orientato, ordinamenti topologici di grafi aciclici, componenti fortemente connesse. Problemi su grafi pesati: albero minimo di copertura, cammini minimi su grafi pesati. 

Propedeuticità: Programmazione II

Modalità didattiche: Lezioni frontali. Esercitazioni.

Materiale didattico: 

Libro di testo: T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. “Introduzione agli algoritmi e strutture dati”  3/ed. 

Lucidi utilizzati per le lezioni frontali del corso

Modalità di esame: 

L'esame si articola in prova

Scritta e orale

             

 

In caso di prova scritta i quesiti sono

 

 

 

A risposta libera

 

 

Esercizi numerici

 

Altro

 

Docente: Benerecetti Massimo