Corso di Studi in Ingegneria Informatica

SCHEDA DELL'INSEGNAMENTO (SI)
SSD ING-INF/01

CORSO DI STUDIO: LAUREA MAGISTRALE IN INGEGNERIA ELETTRONICA

ANNO ACCADEMICO: 2022-2023

INFORMAZIONI GENERALI - DOCENTE

DOCENTE: Antonio G. M. Strollo
TELEFONO: 081-7683125
EMAIL: Questo indirizzo email è protetto dagli spambots. È necessario abilitare JavaScript per vederlo.

INFORMAZIONI GENERALI - ATTIVITÀ

INSEGNAMENTO INTEGRATO (EVENTUALE): 
MODULO (EVENTUALE):
CANALE (EVENTUALE):
ANNO DI CORSO (I, II, III): I
SEMESTRE (I, II): I
CFU: 9

INSEGNAMENTI PROPEDEUTICI

(se previsti dall'Ordinamento del CdS)

...................................................................................................................................................

EVENTUALI PREREQUISITI

Conoscenza di base dei circuiti digitali, delle principali caratteristiche dei dispositivi MOS e delle logiche CMOS.

OBIETTIVI FORMATIVI

Nell’ambito del corso viene studiato il flusso di progetto dei circuiti integrati digitali, a partire dalla descrizione mediante linguaggi per la descrizione dell’hardware fino all’implementazione fisica. L ’insegnamento si pone l’obiettivo di fornire agli studenti le metodologie e le conoscenze utili a disegnare i moderni microcircuiti ad alta scala di integrazione, valutarne le caratteristiche, ottimizzarne le prestazioni e definirne le procedure di verifica.

RISULTATI DI APPRENDIMENTO ATTESI

(Descrittori di Dublino)

Conoscenza e capacità di comprensione

Il percorso formativo intende fornire agli studenti le conoscenze e gli strumenti metodologici necessari a completare il flusso di sviluppo di un sistema digitale integrato. In particolare, lo studente sarà edotto sugli standard utilizzati per realizzare descrizioni sintetizzabili utilizzando linguaggi per la descrizione dell’hardware, sulle tecniche di valutazione ed ottimizzazione dei ritardi e della dissipazione di potenza, sulle varie architetture per implementazione di circuiti aritmetici e sulle principali metodologie di testing. Tali strumenti consentiranno agli studenti di comprendere le principali relazioni che sussistono tra l’implementazione fisica dei sistemi integrati e le loro caratteristiche elettriche.

Capacità di applicare conoscenza e comprensione

Al termine del processo di apprendimento lo studente è in grado di progettare ed analizzare a livello architetturale, circuitale e fisico circuiti e sistemi digitali ad alta scala di integrazione. Egli disporrà degli strumenti metodologici e operativi necessari a descrivere mediate linguaggi HDL un sistema digitale, ad approntarne il test-bench ed a realizzarne la simulazione. Lo studente sarà inoltre in grado di definire gli opportuni vincoli necessari ad effettuare la fase di sintesi, di utilizzare programmi di sintesi automatica e di valutare i risultati forniti dal sintetizzatore.  Il percorso formativo è orientato a trasmettere le capacità e gli strumenti metodologici e operativi necessari ad applicare concretamente le varie tecniche volte ad ottimizzare le prestazioni dei sistemi digitali, in termini di velocità, area occupata e consumo energetico.

Autonomia di giudizio, Abilità comunicative, Capacità di apprendimento

Al termine del corso lo studente deve essere in grado di sapere scegliere in maniera autonoma le possibili metodologie e tecniche da utilizzare nelle varie fasi del ciclo di progettazione di un sistema digitale ad alta scala di integrazione; dovrà inoltre avere la capacità di valutare i risultati derivanti dall’applicazione delle varie tecniche di ottimizzazione ed essere in grado di confrontare le prestazioni di diverse architetture.

Gli studenti saranno in grado di approfondire autonomamente argomenti trattati. La metodologia di verifica ed il confronto con il docente tendono inoltre a sviluppare le abilità comunicative degli studenti che devono dimostrare di saper impostare una relazione scientifica utilizzando terminologia e linguaggio appropriato.

PROGRAMMA-SYLLABUS

Classificazione dei sistemi integrati: full-custom, basati su celle standard e programmabili. Metodologie di progetto di sistemi integrati. Tecniche automatiche di sintesi e di piazzamento e collegamento di celle standard.

Caratteristiche dei transistori MOS di ultima generazione. Tecniche di simulazione switch-level. Valutazione semplificata dei ritardi delle porte logiche.

Analisi statica dei ritardi. Grafi dei ritardi. Caratterizzazione dei ritardi delle celle standard. Livelli di interconnessione e parametri parassiti. Valutazione dei ritardi introdotti dalle interconnessioni mediante la tecnica di Elmore. Ripetitori. Effetti dello scaling tecnologico sui ritardi delle interconnessioni. Cross-talk. Distribuzione delle linee di alimentazione.

Progetto e temporizzazione di sistemi sequenziali. Tempi caratteristici dei registri. Registri avanzati. Tecniche di pipelining. Effetti delle non idealità del clock (skew, jitter) sulla temporizzazione dei sistemi sequenziali. Generazione e distribuzione del clock. Anelli ad aggancio di fase (PLL) e ad aggancio di ritardo (DLL).

Valutazione della dissipazione di potenza nei sistemi VLSI. Fonti di dissipazione di potenza statica e dinamica. Tecniche per la riduzione della dissipazione di potenza a livello tecnologico, circuitale ed architetturale.

Il linguaggio VHDL per la descrizione e la sintesi di sistemi integrati. Statements sequenziali e concorrenti. La simulazione event-driven. Librerie standard per la sintesi di sistemi digitali. Descrizione e sintesi di circuiti aritmetici. Test-bench. Operazioni su file di testo.

Testing dei sistemi integrati CMOS. Modelli di guasto. Algoritmi per il calcolo dei vettori di test. Tecniche di self-test.

Circuiti aritmetici. Addizionatori a selezione del ritardo, carry-skip, parallel-prefix. Addizionatori multi-operando. Moltiplicatori paralleli. Moltiplicatori veloci (Wallace, Dadda).

MATERIALE DIDATTICO

·         Weste, Harris, “CMOS VLSI Design – circuit and systems perspective”, 4th edition, Pearson – Addison Wesley, 2011

·         Appunti delle lezioni

·         Testi delle esercitazioni

MODALITÀ DI SVOLGIMENTO DELL'INSEGNAMENTO

Il corso prevede lezioni frontali, esercitazioni e, compatibilmente con gli aspetti organizzativi, esercitazioni di laboratorio.

Per lo svolgimento delle esercitazioni gli studenti adottano programmi di sviluppo di sistemi integrati della Cadence, resi disponibili grazie alle “Cadence Low-Cost Classroom Teaching Licenses” acquisite mediante Europractice. Gli studenti inoltre utilizzano un simulatore vhdl (ghdl) ed un visualizzatore di forme d’onda (gtkwave) open-source.

VERIFICA DI APPRENDIMENTO E CRITERI DI VALUTAZIONE

a) Modalità di esame:

L'esame si articola in prova:
Scritta e orale
Solo scritta o intercorso a metà
Solo orale
Discussione di elaborato progettuale
Altro

SCHEDA DELL'INSEGNAMENTO (SI)
SSD ING-INF/05

LAUREA MAGISTRALE IN INGEGNERIA INFORMATICA

ANNO ACCADEMICO: 2022-2023

INFORMAZIONI GENERALI - DOCENTE

DOCENTE: NICOLA MAZZOCCA
TELEFONO:
EMAIL: Questo indirizzo email è protetto dagli spambots. È necessario abilitare JavaScript per vederlo.

INFORMAZIONI GENERALI - ATTIVITÀ

INSEGNAMENTO INTEGRATO (EVENTUALE):
MODULO (EVENTUALE):
CANALE (EVENTUALE):
ANNO DI CORSO (I, II, III): I
SEMESTRE (I, II): II
CFU: 9

INSEGNAMENTI PROPEDEUTICI

(se previsti dall'Ordinamento del CdS)

...................................................................................................................................................

EVENTUALI PREREQUISITI

Conoscenza dell’architettura di un calcolatore, dei sistemi operativi e delle reti di comunicazione.

OBIETTIVI FORMATIVI

Il corso si pone l’obiettivo di fornire gli elementi metodologici, progettuali e tecnologici per la realizzazione di sistemi di elaborazione con riferimento alle architetture pipelined, multi-computer, multi-processore, multi-core e multi-threading. Il corso affronta inoltre il funzionamento e dimensionamento dei sistemi di memoria gerarchici, il progetto e la programmazione delle unità di I/O (parallele, seriali, DMA e PIC) con i relativi protocolli di comunicazione, e le problematiche di implementazione dei meccanismi di base per la virtualizzazione delle risorse hardware (meccanismi di gestione dei processi, macchine virtuali e hypervisor). Il corso presenta, infine, le principali tecniche per la realizzazione di sistemi pervasivi, autonomici, IoT e di edge computing, nonché le architetture cloud.
La parte applicativa del corso è dedicata al progetto di driver di I/O e allo sviluppo di sistemi operanti in ambito industriale. Le attività vengono svolte con riferimento ad applicazioni sviluppate e valutate sperimentalmente mediante architetture che prevedono l’impiego di nodi di elaborazione dotati di processori RISC e di diversi dispositivi di I/O opportunamente configurabili.
Con riferimento agli aspetti tecnologici, sono illustrate le architetture di sistemi commerciali per l’implementazione di applicazioni industriali basate su System on Chip o su nodi di elaborazione ottenuti per integrazione di componenti configurabili.

RISULTATI DI APPRENDIMENTO ATTESI

(Descrittori di Dublino)

Conoscenza e capacità di comprensione
Lo studente deve dimostrare di conoscere e comprendere le problematiche relative al progetto di sistemi di elaborazione, con particolare riferimento alla gestione degli hazard derivanti dall’impiego di tecniche di parallelismo interno ed esterno per l’aumento delle prestazioni, al dimensionamento delle memorie, e all’orchestrazione di diversi sottosistemi operanti in concorrenza fra loro e comunicanti mediante diverse interfacce di I/O.
Deve inoltre dimostrare di saper individuare, fra i diversi approcci presentati al corso, quelli che meglio si adattano a specifiche applicazioni o condizioni operative.
Capacità di applicare conoscenza e comprensione
Lo studente deve dimostrare di essere in grado di progettare e sviluppare il software di base (driver assembly) necessario per consentire la comunicazione fra diversi sottosistemi mediante i dispositivi di I/O presentati al corso, anche in presenza di accessi concorrenti a dati comuni, nonché di scheduler per la gestione della concorrenza. Deve inoltre essere in grado di completare il ciclo di sviluppo di applicazioni di media complessità, che richiedano l’utilizzo di uno o più nodi di elaborazione, di diversi dispositivi di I/O, di sensori/attuatori, sui dispositivi hardware in dotazione.

PROGRAMMA-SYLLABUS

Richiami ed approfondimenti sui sistemi di elaborazione: Sistemi general purpose ed embedded. Processori RISC e CISC. Unità di controllo cablata e microprogrammata. Meccanismi di gestione delle interruzioni. Introduzione al parallelismo e al pipelining. Richiami sul processore Motorola 68000. Il processore MIPS: modello di programmazione e pipeline. Il processore ARM. Architetture e applicazioni dei DSP.
Pipelining e hazard: Tecniche di gestione dei conflitti sui dati, dei salti e delle interruzioni in una architettura pipelined. Architetture superscalari.
Sistemi multiprocessore e multicomputer: Architetture parallele, speed up ed efficienza. Algoritmi per la coerenza della memoria.
Periferiche di I/O e driver: Architettura e funzionamento di periferiche parallele, seriali, DMA e PIC, e sviluppo di driver per la loro programmazione.
La gerarchia della memoria: Architettura, indirizzamento e dimensionamento di una cache. Memoria virtuale. Memorie statiche e dinamiche.
Bus e reti di interconnessione: I bus di sistema. Protocolli di comunicazione. Reti di interconnessione: switch multistadio.
Progetto e sviluppo di sistemi basati su microcontrollori: Principi di progetto di sistemi di elaborazione per applicazioni industriali basati su microcontrollori. Architetture e impiego dei System on a Chip (SoC). Dispostivi commerciali e industriali programmabili. Ambienti di progettazione, di simulazione e analisi di sistemi di elaborazione.
Virtualizzazione e cloud computing. Tecniche di virtualizzazione e hypervisor. Introduzione ai sistemi cloud: modelli di servizio e applicazioni.
IoT/Edge computing. Architetture e applicazioni di sistemi IoT e di edge computing. Sviluppo di sistemi edge di tipo commerciale e integrazione di reti di sensori.

MATERIALE DIDATTICO

Libro di testo: Conte, Mazzeo, Mazzocca, Prinetto. Architettura dei calcolatori. Edizioni CittàStudi. 2014. ISBN: 9788825173642.
Dispense e presentazioni fornite dai docenti relative ad argomenti teorici e applicativi trattati al corso.
Manuali e datasheet dei dispositivi utilizzati per l’implementazione delle applicazioni.

MODALITÀ DI SVOLGIMENTO DELL'INSEGNAMENTO

Il corso prevede circa il 70% di lezioni frontali in cui vengono affrontati gli argomenti teorici, mentre il restante 30% è riservato a lezioni pratiche ed esercitazioni riguardanti lo sviluppo di driver di I/O e l’utilizzo degli ambienti di sviluppo.
La parte applicativa del corso si avvale di strumenti di sviluppo professionali di cui è disponibile una licenza ad uso gratuito e di board di sviluppo (dotate di un microcontrollore ARM e di diversi dispositivi di I/O) che vengono distribuiti agli studenti per l’implementazione dei propri progetti.

VERIFICA DI APPRENDIMENTO E CRITERI DI VALUTAZIONE

a) Modalità di esame:

L'esame si articola in prova:
Scritta e orale
Solo scritta
Solo orale
Discussione di elaborato progettuale
Altro

In caso di prova scritta i quesiti sono (*):
A risposta multipla
A risposta libera
Esercizi numerici

La verifica dell’apprendimento prevede una prova scritta consistente in esercizi di progetto di sistemi basati su dispositivi di I/O e una prova orale orientata alla verifica della comprensione dei concetti teorici del corso e alla discussione degli esercizi implementati su board di sviluppo.

b) Modalità di valutazione:

SCHEDA DELL'INSEGNAMENTO (SI)
SSD MAT/09

LAUREA MAGISTRALE IN INGEGNERIA INFORMATICA

ANNO ACCADEMICO: 2022-2023

INFORMAZIONI GENERALI - DOCENTE

DOCENTE: MAURIZIO BOCCIA
TELEFONO: 081 7683247
EMAIL: Questo indirizzo email è protetto dagli spambots. È necessario abilitare JavaScript per vederlo.

INFORMAZIONI GENERALI - ATTIVITÀ

INSEGNAMENTO INTEGRATO (EVENTUALE): 
MODULO (EVENTUALE):
CANALE (EVENTUALE):
ANNO DI CORSO (I, II, III): I
SEMESTRE (I, II): II
CFU: 9

INSEGNAMENTI PROPEDEUTICI

(se previsti dall'Ordinamento del CdS)

...................................................................................................................................................

EVENTUALI PREREQUISITI

...................................................................................................................................................

OBIETTIVI FORMATIVI

Il corso ha l’obiettivo di fornire agli studenti gli strumenti metodologici per analizzare e risolvere problemi di programmazione matematica con particolare riferimento ai problemi di ottimizzazione combinatoria e di ottimizzazione su rete. Vengono presentate metodologie risolutive sia per taluni problemi "di base" dell'ottimizzazione su reti, sia per problemi "difficili" di ottimizzazione combinatoria e su reti. Al termine del corso lo studente avrà acquisito la capacità di formulare un modello astratto di un problema di ottimizzazione combinatoria, la capacità di individuare le strutture presenti su cui articolare un approccio risolutivo di tipo euristico, oppure, di applicare un algoritmo ad hoc per la sua soluzione esatta.

RISULTATI DI APPRENDIMENTO ATTESI

(Descrittori di Dublino)

Conoscenza e capacità di comprensione
Il percorso formativo ha l’obiettivo di fornire agli studenti le metodologie di ottimizzazione combinatoria e di ottimizzazione su rete necessarie per la modellazione e la risoluzione esatta e/o euristica di problemi decisione che possono presentarsi in ambito ingegneristico e industriale. Al termine del corso, lo studente dovrà dimostrare di conoscere e di saper utilizzare gli strumenti necessari a formulare un problema di ottimizzazione combinatoria e di ottimizzazione su reti. Deve inoltre essere in grado di decidere, in relazione alle caratteristiche e alla complessità del problema, se la risoluzione del problema possa avvenire mediante l’utilizzo dei pacchetti software e delle librerie di ottimizzazione più diffusi, oppure occorra sviluppare un algoritmo ad hoc per la sua soluzione. Deve quindi dimostrare di conoscere le principali metodologie meta-euristiche per la risoluzione di problemi di ottimizzazione combinatoria e saper scegliere la metodologia più adatta al problema da affrontare.

Capacità di applicare conoscenza e comprensione
Il percorso formativo è orientato a trasmettere agli studenti gli strumenti metodologici e operativi necessari alla formulazione e alla soluzione di problemi di ottimizzazione combinatoria e di problemi di ottimizzazione su reti. In particolare, lo studente deve dimostrare di saper formulare un problema di ottimizzazione. Deve inoltre dimostrare di saperlo risolvere, quando possibile, in maniera esatta utilizzando una delle principali librerie di ottimizzazione, oppure in maniera approssimata utilizzando un approccio di tipo euristico. Infine, deve essere in grado di implementare e sperimentare i diversi approcci euristici e meta-euristici allo scopo di decidere l’approccio più adatto al particolare problema.

PROGRAMMA-SYLLABUS

I Modelli della Ricerca Operativa
­ L’approccio modellistico
­ Modelli di Ottimizzazione

Programmazione Lineare continua e intera
­ Introduzione alla Programmazione Lineare
­ Esempi di modelli di programmazione lineare
­ Rappresentazione grafica di un problema di P.L.
­ Formulazioni.
­ Il metodo Branch and Bound
­ Il metodo dei piano di taglio
­ Il metodo Branch and Cut

Software per la Programmazione Matematica
­ Utilizzo della libreria Gurobi per la soluzione di problemi di PL e PLI.
­ Esempi d’utilizzo della libreria: pianificazione della produzione, gestione delle scorte, problemi su reti, problemi di localizzazione, problemi di distribuzione.

Euristiche per la soluzione di problemi di ottimizzazione combinatoria
­ L’ottimizzazione combinatoria
­ Euristiche di tipo greedy
­ Ricerca locale e tabù search
­ Algoritmi genetici

Elementi di teoria dei grafi
­ Forme di rappresentazione di un grafo
­ Algoritmi di visita di un grafo

Il problema di instradamento e flussi su rete
­ Classificazione dei problemi e degli algoritmi di minimo percorso
­ Il modello del minimo percorso
­ Algoritmi per il calcolo dei minimi percorsi
­ Problemi di flusso Single e Multi-Commodity
­ Politiche di instradamento e bilanciamento di una rete

Problemi di design, localizzazione e clustering
­ Problemi di localizzazione su nodi e su archi
­ Euristica costruttive e migliorative
­ Il problema di clustering
­ Algoritmo k-means per il problema di clustering

Il problema del Commesso Viaggiatore (TSP)
­ Complessità del problema
­ Un algoritmo di row generation
­ Euristiche greedy e di ricerca locale
­ Il problema di orienteering come variante del TSP

Il problema di Vehicle Routing
­ Definizione del problema e delle sue varianti
­ Euristiche greedy e di ricerca locale

MATERIALE DIDATTICO

- M. Caramia, S. Giordani, F. Guerriero, R. Musmanno, D. Pacciarelli, "Ricerca Operativa", Isedi, Italia, 2014.
- H. Paul Williams, Model Building in Mathematical Programming, John Wiley & Sons, Ltd.
- F. S. Hillier, G. J. Lieberman, Ricerca operativa - Fondamenti, 9/ed., McGraw-Hill, 2010.
- A. Sforza, Modelli e Metodi della Ricerca Operativa, 3a ed., ESI, Napoli, 2018.
- G. Bruno, Operations Management. Modelli e metodi per la logistica, ESI – Edizioni Scientifiche Italiane.
- Materiale didattico integrativo fornito durante il corso.

MODALITÀ DI SVOLGIMENTO DELL'INSEGNAMENTO

Il docente utilizzerà: lezioni frontali (65%), seminari (5%), esercitazioni di tipo numerico (10%), esercitazioni di utilizzo di librerie di ottimizzazione (25%). Il materiale del corso sarà reso disponibile on-line agli studenti.

VERIFICA DI APPRENDIMENTO E CRITERI DI VALUTAZIONE

a) Modalità di esame:

L'esame si articola in prova:
Scritta e orale
Solo scritta
Solo orale
Discussione di elaborato progettuale
Altro

In caso di prova scritta i quesiti sono (*):
A risposta multipla
A risposta libera
Esercizi numerici

 b) Modalità di valutazione:
La prova scritta è volta a verificare le capacità di formulazione di problemi di ottimizzazione e la comprensione degli algoritmi di risoluzione di problemi PL e PLI. Lo studente ha a disposizione 2 ore per la prova scritta. L’esame prevede inoltre lo svolgimento di un elaborato progettuale in cui lo studente deve implementare e sperimentale un algoritmo esatto e/o euristico per la soluzione di un problema di ottimizzazione combinatoria. Il colloquio orale avrà come oggetto sia la discussione dell’elaborato progettuale che l’accertamento dell’acquisizione dei concetti e delle metodologie illustrati durante le lezioni.

c) Modalità di valutazione:
L’esito della prova scritta è vincolante ai fine dell’accesso alla prova orale. La prova scritta e quella orale con la descrizione dell’elaborato finale contribuiscono rispettivamente per il 40% e il 60% della valutazione finale. Il superamento della prova scritta non è sufficiente per il superamento dell’esame.

SCHEDA DELL'INSEGNAMENTO (SI)
SSD ING-INF/05

LAUREA MAGISTRALE IN INGEGNERIA INFORMATICA

ANNO ACCADEMICO: 2022-2023

INFORMAZIONI GENERALI - DOCENTE

DOCENTE: ROBERTO PIETRANTUONO
TELEFONO: 0817683880
EMAIL: Questo indirizzo email è protetto dagli spambots. È necessario abilitare JavaScript per vederlo.

INFORMAZIONI GENERALI - ATTIVITÀ

INSEGNAMENTO INTEGRATO (EVENTUALE):
MODULO (EVENTUALE):
CANALE (EVENTUALE):
ANNO DI CORSO (I, II, III): I
SEMESTRE (I, II): I
CFU: 9

INSEGNAMENTI PROPEDEUTICI

(se previsti dall'Ordinamento del CdS)

...................................................................................................................................................

EVENTUALI PREREQUISITI

...................................................................................................................................................

OBIETTIVI FORMATIVI

L’insegnamento si propone di fornire le nozioni necessarie per la progettazione e l'analisi di algoritmi e strutture dati nello sviluppo delle applicazioni informatiche. Tali nozioni includono i fondamenti teorici e le tecniche avanzate di progettazione ed analisi di algoritmi la cui applicazione spazia su tutti gli aspetti relativi ad un sistema di elaborazione, da quelli hardware a quelli software, dai sistemi operativi alle reti di elaboratori, dalle basi di dati ai sistemi informativi, dai linguaggi di programmazione all'ingegneria del software, dall'interazione uomo-macchina al riconoscimento dei segnali e delle immagini, all'elaborazione multimediale, all'ingegneria della conoscenza, all'intelligenza artificiale ed alla robotica.

RISULTATI DI APPRENDIMENTO ATTESI

(Descrittori di Dublino)

Conoscenza e capacità di comprensione
Al termine del corso, lo studente deve dimostrare di aver acquisito familiarità con una ampia varietà di strutture dati ed algoritmi noti che risolvono problemi di carattere fondamentale, di aver compreso le tecniche per la sintesi di nuovi algoritmi e di padroneggiare i metodi per analizzare la correttezza e la complessità asintotica degli algoritmi.

Capacità di applicare conoscenza e comprensione
Al termine del corso, lo studente deve dimostrare di sapere applicare e combinare le principali tecniche di progettazione, nonché strutture dati avanzate, per la sintesi di algoritmi corretti ed efficienti per la risoluzione di problemi nello sviluppo delle applicazioni informatiche, e di saperne analizzare formalmente la correttezza e la complessità asintotica. Il percorso formativo è orientato a fornire le capacità e gli strumenti necessarie a risolvere problemi nuovi o non familiari negli ampi contesti relativi ai sistemi di elaborazione dell’informazione.

PROGRAMMA-SYLLABUS

Concetti introduttivi: algoritmi e strutture dati, ricorsione, analisi e progettazione degli algoritmi.
Tecniche di analisi e strutture dati elementari.
Analisi di correttezza: invariante di ciclo, correttezza di algoritmi ricorsivi.
Analisi di complessità: analisi asintotica, notazioni O, Ω, Θ; analisi di algoritmi ricorsivi.
Strutture dati elementari: dizionari; pile e code; code di priorità; liste; tabelle hash e stringhe; alberi binari di ricerca.
Tecniche di progettazione. Classificazione di problemi, caratteristiche della soluzione.

DIVIDE et IMPERA. Problemi ed algoritmi comuni. Ordinamento: merge sort, heap sort, quick sort, ordinamento in tempo lineare (counting sort, radix sort, bucket sort), mediane e statistiche d'ordine.

RICERCA COMBINATORIALE E METODI EURISTICI. Ricerca esaustiva, ricerca combinatoriale; backtracking, pruning della ricerca.
Metodi euristici, ricerca locale ed algoritmi golosi (“greedy”). Cenni ad algoritmi meta-euristici. Problemi ed algoritmi comuni.
Problemi combinatoriali (costruzione di subset e permutazioni), copertura minima di un insieme. Il problema della selezione di attività

PROGRAMMAZIONE DINAMICA. Introduzione alla programmazione dinamica. Ricerca esaustiva vs. ricerca greedy vs. programmazione dinamica. Applicazioni. Problemi ed algoritmi comuni. Problema di string matching, edit distance, longest increasing sequence. Fibonacci. Problema dello zaino. Ulteriori esempi.

Strutture dati e tecniche di analisi avanzate: alberi RB, alberi auto-aggiustanti. B-alberi. Grafi. Rappresentazione, esplorazione in ampiezza e profondità, ordinamento topologico. Applicazioni. Cammini minimi. Tecniche di analisi di algoritmi avanzate: analisi ammortizzata.

Problemi ed algoritmi comuni, esempi applicativi. Problemi di teoria dei numeri (es.: algoritmi DES ed RSA). Problemi su grafi: ricerca di cammini minimi. Multithreading e parallelismo: progettazione di algoritmi multithread, algoritmi paralleli e distribuiti. Esempi (Fibonacci, ordinamento). Analisi e confronto con algoritmi sequenziali. Traduttori ed interpreti: analisi lessicale, analisi sintattica, analisi semantica, interpreti, strutture dati usate nei traduttori.

Problemi intrattabili. Introduzione a problemi NP ed NP-completi. Riducibilità. Esempi di problemi NP-completi.

Parte Esercitativa: Prevalentemente in C.

MATERIALE DIDATTICO

LIBRO DI TESTO ADOTTATO:
1) Cormen, Thomas, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms. 3rd ed. MIT Press, 2009. ISBN: 9780262033848.

TRASPARENZE DALLE LEZIONI ED ESERCITAZIONI disponibili sul sito web docenti di Ateneo sulla piattaforma Microsoft Teams.

LIBRO CONSIGLIATO:
2) S. Skiena. The Algorithm Design Manual, 3rd ed, Springer, 2020. ISBN-13: 978-3030542559, ISBN-10: 3030542556.

MODALITÀ DI SVOLGIMENTO DELL'INSEGNAMENTO

Il docente utilizzerà: a) lezioni frontali per circa l’80% delle ore di lezione totali, b) esercitazioni per circa il 20% delle ore di lezione totali. E’ prevista l’assegnazione di esercizi da svolgere autonomamente e consegnare al docente. Le lezioni sono registrate e rese disponibili tramite la piattaforma Microsoft Teams.

VERIFICA DI APPRENDIMENTO E CRITERI DI VALUTAZIONE

a) Modalità di esame:

L'esame si articola in prova:
Scritta e orale
Solo scritta
Solo orale
Discussione di elaborato progettuale
Altro

In caso di prova scritta i quesiti sono (*):
A risposta multipla
A risposta libera
Esercizi numerici

L’esame si articola in n. 3 prove scritte ed in una prova orale che include una discussione sugli esercizi assegnati durante il corso. La parte scritta si articolata in n.2 prove intercorso più n.1 prova finale. Le prove richiedono, per uno o più problemi, di implementare algoritmi per la loro risoluzione ed analizzarne la complessità asintotica.
La prova orale consta di un colloquio sostenuto dopo l’ultima prova scritta (prova finale). Esso include anche la discussione sulla risoluzione degli esercizi assegnati durante il corso.

b) Modalità di valutazione:
Le n.3 prove scritte pesano ciascuna il 20% sul giudizio finale (per un totale del 60%). La prova orale pesa per il restante 40% sul giudizio finale (con un peso del 30% per la valutazione e discussione degli esercizi e del 10% per l’interrogazione sulla parte del programma non coperta dalle prove e dagli esercizi).