ALGORITMI E STRUTTURE DATI
cod. 07563

Anno accademico 2021/22
1° anno di corso - Secondo semestre
Docente
PRATI Andrea, FERRARI Claudio
Settore scientifico disciplinare
Sistemi di elaborazione delle informazioni (ING-INF/05)
Campo
Ingegneria informatica
Tipologia attività formativa
Caratterizzante
48 ore
di attività frontali
6 crediti
sede: PARMA
insegnamento
in ITALIANO

Obiettivi formativi

Conoscenza e Comprensione

Lo scopo del corso è quello di illustrare i principali metodi algoritmici e strutture dati utilizzate nello sviluppo di software, mediante pseudo-codice. Lo studente sarà quindi in grado di valutare propriamente il miglior algoritmo (in termini di costo computazionale e altro) e le migliori strutture dati da utilizzare dato un certo problema da risolvere.


Capacità di applicare conoscenza e comprensione

Lo studente acquisirà la capacità di comprendere le tecniche algoritmiche da applicare per risolvere in modo corretto ed efficiente un problema. Sarà inoltre capace di comprendere e valutare le strutture dati da utilizzare per una risoluzione efficiente (computazionalmente e come memoria utilizzata) il problema.

Prerequisiti

- - -

Contenuti dell'insegnamento

Il corso introduce gli algoritmi e le strutture dati utilizzati nella risoluzione di problemi fondamentali, presentando principi e tecniche che ne permettono l'analisi sistematica. L'obiettivo è fornire allo studente gli strumenti per progettare soluzioni algoritmiche corrette ed efficienti ed individuare, in presenza di varie alternative, la soluzione più adatta ad un problema. Gli argomenti principali trattati sono: analisi della complessità computazionale, tipi di dati astratti elementari, algoritmi di ordinamento, alberi binari di ricerca, tabelle hash, grafi orientati e non.

Programma esteso

Il corso si articola in didattica frontale sui seguenti argomenti (durate indicative):

- Algoritmi e strutture dati: generalità ed esempi. Introduzione alla nozione di costo (tempo e spazio di memoria). (2 ore)
- Notazioni asintotiche per le funzioni di costo e metodi di analisi (caso peggiore, medio, migliore). (2 ore)
- Metodi di analisi di algoritmi ricorsivi: albero della ricorsione, iterazione, sostituzione, Master Theorem. (5 ore)
- Tipi di dato astratto (dizionari, pile, code) e loro implementazioni. (6 ore)
- Alberi: algoritmi di visita (DFT e BFT) (6 ore)
- Algoritmi di ordinamento incrementali (descrizione, implementazione e analisi): SelectionSort, InsertionSort, BubbleSort, HeapSort, MergeSort, QuickSort. Lower bound sul costo dell'ordinamento per modello basato su confronti. (6 ore)
- Algoritmi di ordinamento di interi (descrizione, implementazione e analisi): IntegerSort, BucketSort, RadixSort (3 ore)
- Alberi di ricerca binari, alberi AVL, alberi splay, alberi 2-3, B-alberi, B*-alberi, alberi 2-3-4, alberi rosso-neri (6 ore)
- Tabelle Hash: tabelle ad indirizzamento diretto, problema delle collisioni (3 ore)
- Grafi non orientati e orientati, e loro rappresentazione. Algoritmi di visita (descrizione, implementazione e costo) (3 ore)
- Tecnica algoritmica golosa (greedy). Minimo albero ricoprente e rispettivo calcolo basato su algoritmo greedy. Algoritmi di Kruskal, di Prim e di Boruvka. (3 ore)
- Cammini minimi su grafi e relativi algoritmi (descrizione, implementazione e analisi): calcolo delle distanze, algoritmo di Bellman e Ford, calcolo dei cammini minimi a sorgente singola su grafi aciclici, algoritmo di Dijkstra (7 ore)

Bibliografia

- C. Demetrescu, I. Finocchi, G.F. Italiano, "Algoritmi e strutture dati", 2a ed., McGraw-Hill
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, "Introduzione agli algoritmi e strutture dati", 3a ed., McGraw-Hill
- A. Bertossi, A. Montresor, "Algoritmi e strutture di
dati", 2a ed., Città Studi

Metodi didattici

Il corso prevede lezioni frontali in aula per 48 ore circa, coadiuvate da esercitazioni in preparazione all'esame.

Modalità verifica apprendimento

L'esame consiste in uno scritto con vari esercizi che richiedono la scrittura di algoritmi in pseudo-codice, la spiegazione per passi di algoritmi, l'argomentazione di scelte di algoritmi e/o strutture dati per la risoluzione di un problema dato.

Altre informazioni

- - -