Corso di Studi in Ingegneria Informatica

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

 

LAUREA MAGISTRALE IN INGEGNERIA INFORMATICA

ANNO ACCADEMICO: 2022-2023

 

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

 

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

 

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

 

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

 

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.

 

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.

 

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.

 

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.

 

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.

 

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