ALGORITMI E STRUTTURE DATI
cod. 07563

Anno accademico 2022/23
1° anno di corso - Primo semestre
Docente
- Vincenzo BONNICI - Andrea MUNARO
Settore scientifico disciplinare
Informatica (INF/01)
Field
Attività formative affini o integrative
Tipologia attività formativa
Affine/Integrativa
48 ore
di attività frontali
6 crediti
sede:
insegnamento
in - - -

Obiettivi formativi

L'obiettivo principale del corso è quello di presentare le principali strutture dati e i relativi algoritmi. Inoltre il corso intende fornire allo studente nozioni relative allo studio della complessità computazionale degli algoritmi. Infine il corso mira anche a fornire allo studente la capacità di applicare tecniche di analisi dei problemi per risolvere semplici problemi pratici in modo algoritmico.

Con riferimento agli Indicatori di Dublino:

Conoscenza e capacità di comprensione
Il corso introduce i concetti relativi alle strutture dati e allo studio di algoritmi corretti ed efficienti. Lo studente acquisisce la capacità di studiare la complessità di algoritmi relativi a problemi di varia natura e la capacità di utilizzare strutture dati che permettano una gestione efficiente delle informazioni.

Capacità di applicare conoscenza e comprensione
Le conoscenze teoriche presentate vengono sempre applicate alla risoluzione di problemi specifici. Durante il corso verranno affrontanti esercizi e problemi di natura diversa, con particolare riferimento alla realizzazione di programmi che utilizzino le diverse strutture dati studiate e i relativi algoritmi.

Autonomia di giudizio
Gli esercizi proposti relativamente alla parte teorica svolta a lezione possono essere affrontati individualmente o in gruppo e, spesso, possono essere risolti in modi diversi. Il confronto con i compagni di corso e l'ascolto delle soluzioni proposte da altri, nel lavoro a casa o durante gli svolgimenti in aula, favoriscono lo sviluppo di capacità specifiche per poter chiarire le proprie argomentazioni e individuare strutture comuni tra i diversi approcci.

Abilità comunicative
Le discussioni in aula consentono di migliorare le capacità di comunicazione. Tali discussioni riguardano i metodi per risolvere i problemi proposti, evidenziando vantaggi e svantaggi dei diversi approcci proposti. Lo studente impara a lavorare sia in autonomia che in gruppo.

Capacità di apprendimento
Lo studio delle tecniche algoritmiche di base e la loro applicazione a problemi di natura eterogenea contribuiscono a realizzare negli studenti la capacità di apprendere in modo approfondito e non solo superficiale e ripetitivo. Le conoscenze così acquisite non sono mai rigide e meccaniche, ma sono perfettamente adattabili ad ogni evoluzione e cambiamento di prospettiva e di contesto.

Prerequisiti

Nozioni di base relative all'analisi matematica e alla programmazione.

Contenuti dell'insegnamento

Durante il corso vengono fornite le nozioni di base degli algoritmi e alle strutture dati, con particolare riferimento allo studio della complessità computazionale degli algoritmi e alla progettazione di algoritmi corretti per le diverse strutture dati.

Programma esteso

Introduzione allo studio degli algoritmi e delle strutture dati

Studio della complessità computazionale degli algoritmi e relative nozioni di base

Algoritmi per array più comuni (es. ricerca e ordinamento)

Algoritmi per liste più comuni (es. ricerca e modifica)

Algoritmi per alberi più comuni (es. ricerca, visita e gestione code)

Algoritmi per tavole hash più comuni (es. inserimento e cancellazione)

Algoritmi per statistiche d'ordine e per insiemi disgiunti.

Algoritmi per grafi più comuni (es. visita e componenti connesse)

Cenni all'analisi della correttezza degli algoritmi

Bibliografia

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati, McGraw Hill, 2010.

C. Demestrescu, I. Finocchi, G. F. Italiano. Algoritmi e strutture dati, McGraw Hill, 2008.

P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Pearson, 2006

Metodi didattici

Lezioni frontali ed esercitazioni svolte in aula

Modalità verifica apprendimento

L'esame consiste in una prova scritta in cui viene valuata la conoscenza della parte teorica del corso e la capacità di applicare gli insegnamenti alla risoluzione di problemi pratici.

Altre informazioni

- - -