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
- - -
