PRESENTAZIONE

Il corso si propone di introdurre lo studente alla progettazione e all'analisi degli algoritmi. Mediante la presentazione delle principali strutture dati e degli algoritmi ad essi relative lo studente maturerà la comprensione del funzionamento degli algoritmi e delle principali tecniche ad essi collegate. Un progetto realizzato in C++ su Unreal Engine permette di mettere in pratica alcuni dei concetti esposti.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

Il corso introduce le principali strategie di progettazione di algoritmi e gli strumenti per valutarne la correttezza e le prestazioni. L'obiettivo è lo sviluppo della capacità di formalizzare e risolvere problemi per via algoritmica, e della capacità di analisi e valutazione delle soluzioni.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

Il corso introduce le principali strategie di progettazione di algoritmi:

• Forza Bruta: soluzione del problema a partire dalla sua definizione formale
• Dividi e Conquista: approccio che prevede il frazionamento in sottoproblemi (solitamente di eguale diimensione) e la ricombinazione delle soluzionie parziali
• Diminuisci e Conquista: soluzione del problema mediante riduzione iterativa delle dimensioni (di una costante, di un fattore costante o di un fattore variabile)
• Trasforma e Conquista: approccio che prevede la riformulazione del problema in modo da semplificarne la soluzione
• Compremesso Spazio-Tempo: incremento delle prestazioni per lo svolgimento di operazioni mediante utilizzo di overhead in termini di memoria
• Algoritmi Golosi: strumenti di ottimizzazione combinatoria che prevedono l'utilizzo di strategia "greedy" (scelte localmente ottime si rivelano anche globalmente tali)

Il corso introduce anche i fondamentali della programmazione in Unreal Engine per lo sviluppo di applicazioni grafiche e interattive.

Complessivamente, l'obiettivo è quello di realizzare una buona conoscenza dei principali algoritmi facenti parte di ogni famiglia, avente come risultato la capacità di impostare la soluzione a problemi computazionali per via algoritmica e analizzarne la correttezza e la complessità per via analitica o empirica. 

PREREQUISITI

E' richiesta una buona conoscenza di almeno un linguaggio di programmazione, preferibilmente della famiglia C/C++/Java.

Conoscenze preliminari di calcolo combinatorico, algebra e informatica teorica sono utili per una migliore comprensione del materiale del corso.

MODALITA' DIDATTICHE

Lezioni frontali ed esercitazioni, eventualmente erogate in modalità online.

PROGRAMMA/CONTENUTO

Progettazione ed analisi di algoritmi

• Introduzione: definizione di algoritmo; aspetti fondamentali nella soluzione di problemi mediante algoritmi; tipologie di problemi e strategie di soluzione; specifica degli algoritmi mediante diagrammi di flusso e pseudocodifica; sintassi e semantica relative alle convenzioni di pseudocodifica.
   
• Strutture dati fondamentali: strutture lineari (array, stringhe, pile, code e liste); grafi (definizioni fondamentali e strutture dati); alberi (definizioni fondamentali e strutture dati); insiemi, dizionari e mappe  (definizioni fondamentali).
   
• Elementi di base: efficienza degli algoritmi, risorse computazionali e modello RAM; notazione asintotica (proprietà e classi fondamentali); tipologie di analisi di algoritmi (caso pessimo, ottimo e medio); limiti inferiori nell'analisi di algoritmi e ottimalità; efficienza ammortizzata.
   
• Strategia "Forza Bruta": metodologia ed esempi di analisi di algoritmi non ricorsivi (ricerca del massimo, unicità degli elementi e moltiplicazione fra matrici). Algoritmi di ordinamento elementare su vettori (Selection Sort); ricerca sequenzale su vettori; insiemi, dizionari e mappe con array dinamici e liste linkate; ricerca all'interno di stringhe (string matching).
   
• Strategia "Dividi e conquista": metodologia di analisi di algoritmi ricorsivi; teorema dell'esperto (Master Theorem). Algoritmi di ordinamento su vettori (Merge Sort e Quick Sort); limiti inferiori per gli algoritmi di ordinamento basati su confronti; alberi binari (definizione, calcolo dell'altezza, visite); analisi sintattica di linguaggi formali (definizione di linguaggio, grammatiche context-free, automi a pila); parsing ricorsivo top-down.
   
• Strategia "Diminuisci e conquista": algoritmo di Euclide; algoritmi di ordinamento su vettori (Insertion Sort e Shell Sort); visita di grafi non diretti in profondità e in ampiezza; componenti connesse su grafi non diretti; visita in profondità e in ampiezza su grafi diretti; ordinamento topologico; componenti fortemente connesse; ricerca binaria nei vettori, potenze di interi e matrici; alberi binari di ricerca (BST - Binary Search Tree).
   
• Strategia "Trasforma e conquista": struttura dati heap; utilizzo degli heap per l'ordinamento di vettori (Heap Sort); utilizzo degli heap per la gestione di code di priorità; confronto sperimentale fra ordinamenti asintoticamente ottimi; metodo di Horner per il calcolo di polinomi; insiemi disgiunti e problemi "Union-Find"; BST bilanciati: 2-3 alberi e alberi LLRB;  tries. 
   
• Strategia "Compromesso spazio-tempo": ordinamento di vettori in tempo lineare (Counting Sort); tabelle ad indirizzamento diretto, tabelle hash (separate chaining); funzioni hash;
   
• Strategia "Greedy" (golosa): algoritmi di Prim e Kruskal per il minimo albero ricoprente (MST - Minimum Spanning Tree), algoritmo di Dijkstra per la ricerca di cammini minimi; codici di Huffman per la compressione dei dati.

Progettazione e sviluppo in Unreal Engine:

• Introduzione al framework
• Strutturazione di un'applicazione in Unreal Engine
• Elementi fondamentali 
• Esempio di applicazione: Tic-Tac-Toe

TESTI/BIBLIOGRAFIA

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein ‐ Introduzione agli algoritmi e strutture dati ‐ 3a Edizione ‐ McGraw ‐ Hill;

R. Sedgewick ‐ Algorithms ‐ 4th edition ‐  Addison Wesley

A. Levitin ‐ Introduction to The Design and Analysis of Algorithms ‐ 2nd edition ‐ Addison ‐ Wesley;

S. Skiena ‐ The Algorithm Design Manual ‐ 2nd edition – Springer;

DOCENTI E COMMISSIONI

Commissione d'esame

ARMANDO TACCHELLA (Presidente)

MASSIMO NARIZZANO

ENRICO GIUNCHIGLIA (Presidente Supplente)

LEZIONI

INIZIO LEZIONI

https://corsi.unige.it/8719/p/studenti-orario

Orari delle lezioni

L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy

ESAMI

MODALITA' D'ESAME

Progetto di fine corso (1 progetto, massimo 10 punti), Prova scritta (massimo 20 punti).

Gli studenti con certificazione di DSA, di disabilità o di altri bisogni educativi speciali devono contattare il docente all’inizio del corso per concordare modalità didattiche e d’esame che, nel rispetto degli obiettivi dell’insegnamento, tengano conto delle modalità di apprendimento individuali e forniscano idonei strumenti compensativi. Si ricorda che la richiesta di misure compensative/dispensative per gli esami dovrà essere inviate al docente del corso, al referente della Scuola e al “Settore servizi per l'inclusione degli studenti con disabilità e con DSA” (dsa@unige.it) almeno 10 giorni lavorativi prima della prova, come da linee guida disponibili al link: https://unige.it/disabilita-dsa

MODALITA' DI ACCERTAMENTO

Capacità di impostare la soluzione a problemi computazionali per via algoritmica implementando la soluzione con il linguaggio di programmazione C++
capacità di analizzarne la correttezza e la complessità delle soluzioni trovate per via analitica.Capacità di impostare la soluzione a problemi computazionali per via algoritmica e, analizzarne la correttezza e la complessità per via analitica.