Studiare

In questa sezione è possibile reperire le informazioni riguardanti l'organizzazione pratica del corso, lo svolgimento delle attività didattiche, le opportunità formative e i contatti utili durante tutto il percorso di studi, fino al conseguimento del titolo finale.

Queste informazioni sono destinate esclusivamente agli studenti e alle studentesse già iscritti a questo corso.
Se sei un nuovo studente interessato all'immatricolazione, trovi le informazioni sul percorso di studi alla pagina del corso:

Laurea magistrale in Ingegneria e scienze informatiche - Immatricolazione dal 2025/2026

Il piano didattico è l'elenco degli insegnamenti e delle altre attività formative che devono essere sostenute nel corso della propria carriera universitaria.
Selezionare il piano didattico in base all'anno accademico di iscrizione.

CURRICULUM TIPO:

1° Anno 

InsegnamentiCreditiTAFSSD
12
B
ING-INF/05
12
B
INF/01
12
B
ING-INF/05
6
B
ING-INF/05
InsegnamentiCreditiTAFSSD
12
B
ING-INF/05
12
B
INF/01
12
B
ING-INF/05
6
B
ING-INF/05
Insegnamenti Crediti TAF SSD

Legenda | Tipo Attività Formativa (TAF)

TAF (Tipologia Attività Formativa) Tutti gli insegnamenti e le attività sono classificate in diversi tipi di attività formativa, indicati da una lettera.




S Stage e tirocini presso imprese, enti pubblici o privati, ordini professionali

Codice insegnamento

4S02709

Crediti

12

Coordinatore

Roberto Posenato

Lingua di erogazione

Italiano

Offerto anche nei corsi:

L'insegnamento è organizzato come segue:

ALGORITMI AVANZATI

Crediti

4

Periodo

I semestre

COMPLESSITÀ

Crediti

4

Periodo

I semestre

INTELLIGENZA ARTIFICIALE

Crediti

4

Periodo

I semestre

Obiettivi formativi

Modulo: ALGORITMI AVANZATI
-------
Acquisire un'adeguata conoscenza dei principali paradigmi avanzati di algoritmi per problemi di ottimizzazione combinatorica con particolare attenzione per i paradigmi che permettono di determinare soluzione approssimante per problemi di ottimizzazione combinatoria difficili.

Modulo: COMPLESSITÀ
-------
Il corso è costituito da un'introduzione alla complessità strutturale con particolare attenzione alla teoria del NP-completezza e da un'introduzione alla analisi di complessità dei problemi rispetto alla loro approssimabilità computazionale.

Scopo di tale introduzione è fornire agli studenti gli strumenti necessari per comprendere e affrontare la difficoltà nel risolvere alcuni problemi comuni da un punto di vista computazionale.

Modulo: INTELLIGENZA ARTIFICIALE
-------
Il modulo presenta paradigmi e tecniche principali della rappresentazione simbolica e soluzione automatica di problemi. L'obbiettivo è dare allo studente strumenti per ideare, applicare e valutare algoritmi per problemi difficili, nel senso che la loro soluzione meccanica cattura aspetti di intelligenza artificiale o razionalità computazionale.

Programma

Modulo: ALGORITMI AVANZATI
-------
Richiamo dei principali concetti inerenti ai problemi computazionali.
Richiamo dei principali concetti inerenti agli algoritmi: risorse computazionali, codifica dell'input, dimensione dell'input, definizione di tempo computazionale. Analisi caso peggiore e caso medio. Tempo di calcolo e ordini di grandezza: possibili insidie.
Tempi di calcolo e miglioramenti hardware: relazioni principali. Algoritmi efficienti e problemi trattabili.

Paradigma divide et impera
Richiamo struttura. Analisi complessità. Esempi di applicazione: prodotto tra due numeri, Prodotto fra due matrici.
Introduzione al problema della mediana e, generalizzazione, al problema della selezione. Risoluzione del problema della selezione.

Paradigma greedy
Richiamo struttura. Esempio di applicazione per il problema dell'albero minimo di ricoprimento. Richiamo sulla struttura dati per insiemi disgiunti. Esempio di applicazione per il problema dei cammini minimi da sorgente singola (algoritmo di Dijkstra).
Introduzione ai matroidi: definizione, proprietà fondamentali. Problema del Massimo di un matroide pesato. Dimostrazione che la tecnica greedy determina sempre la soluzione ottima per il problema del Massimo di un matroide pesato.
Uso dei matroidi per la risoluzione del problema di programmazione di task unitari su singolo processore. Limiti della rappresentazione con i matroidi. Esempi di problemi risolvibili con tecnica greedy che non sono rappresentabili da matrodidi.

Tecnica backtracking
Introduzione. Schema generale. Aspetti cruciali.
Applicazione della tecnica al problema dello zaino con ripetizione. Analisi correttezza e complessità.
Introduzione uso della tecnica al problema dell'inviluppo convesso: algoritmo di Graham. Uso della tecnica backtracking al problema del string matching: algoritmo di Knuth, Morris & Pratt.

Tecnica branch & bound
Introduzione. Schema generale. Aspetti cruciali.
Scelta ordine di visita dei figli: strategia hill climbing. Tecnica come nuova tecnica ricerca in un albero: strategia best-first. Applicazione della tecnica al problema dell'assegnamento e al problema dello zaino. Applicazione della tecnica al problema del commesso viaggiatore come esempio di funzione lower bound non banale.

Paradigma programmazione dinamica
Introduzione. Schema generale. Aspetti cruciali. Applicazione della tecnica al problema della massima sottosequenza crescente. Applicazione della tecnica al problema del string matching approssimato e al problema dello zaino. Analisi di esempi di applicazione. Pattern ricorrenti per la determinazione di sottoproblemi. Tecnica memoization (annotazione).

Tecnica ricerca locale
Introduzione e studio caso applicazione al problema dell'albero minimo di ricoprimento. Risoluzione del problema dell'ordinamento mediante tecnica di ricerca locale: ordinamento per inserimento e ShellSort.
Tecniche avanzate di ricerca locale: Simulated annealing e Tabù search.

Algoritmi probabilistici
Definizione. Algoritmi probabilistici numerici, algoritmi di Monte Carlo e algoritmi di Las Vegas. Esempi di problemi risolti con tali algoritmi: Buffon's needle, Pattern Matching e Universal hashing.

Algoritmi di approssimazione
Classi NPO e PO. Errore relatio e indice di performance. Algorimo r-approssimante. Problema r-approssimabile.
Studio dell'approssimabilità del problema Min Vertex Cover: dall'algoritmo greedy all'algoritmo pseudo-casuale.

Modulo: COMPLESSITÀ
-------
Introduzione
Concetto di modello di calcolo, risorsa computazionale, algoritmo efficiente e problema trattabile.

Modelli di calcolo
Macchina di Turing (MdT). MdT a più nastri (k-MdT). Decidere o accettare un linguaggio.
"Macchina ad accesso casuale" (RAM = Random Access Machine). Tempo di computazione secondo il criterio di costo uniforme e costo logaritmico.

Complessità in tempo
Classe di complessità TIME(). Teorema di relazione polinomiale tra le computazioni delle macchine k-MdT e MdT.
Teorema sul costo di simulazione di una MdT mediante un programma RAM.
Teorema sul costo di simulazione di un programma RAM mediante una MdT (solo enunciato).
Tesi del calcolo sequenziale e sue conseguenze.
Teorema dell'accelerazione lineare (linear speed-up) e sue conseguenze.
La classe di complessità P.
Esempio di problemi della classe P: PATH, MAX FLOW, ACCOPPIAMENTO PERFETTO (PERFECT MATCHING).
Estensione della MdT: MdT non deterministica (NMdT).
La risorsa tempo nelle NMdT a k-nastri. Classe di complessità NTIME(). Relazione tra NMdT e MdT.
La classe di complessità NP.
Relazione tra NP e P.
Caratterizzazione alternativa della classe NP: verificatori polinomiali.
La classe di complessità EXP.

Complessità in spazio
Concetto di complessità spaziale. Macchina di Turing con input e output. Classi di complessità SPACE() e NSPACE().
Teorema di compressione.
Classi di complessità L e NL.
Esempi di problemi: PALINDROME ∈ L e PATH ∈ NL.
Teoremi di relazione tra spazio e tempo di computazione per una MdT con I/O. Relazioni tra classi di complessità
Concetto di funzione propria ed esempi di funzioni.
Il teorema del gap di Borodin.
Il metodo di raggiungibilità.
Teorema di inclusione tra classi in tempo e in spazio: NTIME(f(n)) ⊆ SPACE(f(n)), NSPACE(f(n)) ⊆ TIME(k(log n+f(n))).
Concetto di Macchina di Turing Universale. L'insieme Hf. Lemma 1 e 2 per il teorema di gerarchia temporale.
Teorema di gerarchia in tempo: versione lasca e versione stretta. Corollario P ⊂ EXP.
Teorema di gerarchia spaziale (solo enunciato). Corollario L ⊂ PSPACE. Teorema di Savitch. Corollario SPACE(f(n))=SPACE(f(n)^2). Corollario PSPACE=NPSPACE.

Riduzioni e completezza
Concetto di riduzione e di riduzione logaritmica in spazio.
Esempio di riduzione: HAMILTON PATH ≤log SAT, PATH ≤log CIRCUIT VALUE, CIRCUIT SAT ≤log SAT.
Proprietà delle riduzioni.
Concetto di completezza di un linguaggio.
Concetto di chiusura rispetto alla riduzione. Chiusura delle classi L, NL, P, NP, PSPACE e EXP.
Concetto di tabella di computazione.
Dimostrazione che CIRCUIT VALUE è P-completo.
Dimostrazione alternativa del teorema di Cook: CIRCUIT SAT è NP-completo.
Esempi di problemi NP-completo e loro riduzioni: SAT e sue varianti (3SAT, 3SAT con vincoli). Il caso 2SAT.
Cenni sulla completezza della PROGRAMMAZIONE LINEARE INTERA, ZAINO e RIEMPIMENTO DEI CESTINI (BIN PACKING).
Concetto di algoritmo pseudo polinomiale. Problemi fortemente NP-completi.


Modulo: INTELLIGENZA ARTIFICIALE
-------
Risoluzione di problemi come ricerca in uno spazio di stati; procedure di ricerca non informate; procedure di ricerca informate e ricerca euristica. Problemi di soddisfazione di vincoli. Rappresentazione della conoscenza con logica proposizionale e al primo ordine; forme normali; uguaglianza.
Algoritmi per la soddisfacibilità (SAT). Dimostrazione di teoremi per risoluzione e riscrittura.

Bibliografia

Testi di riferimento
Autore Titolo Casa editrice Anno ISBN Note
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani Algorithms (Edizione 1) McGraw-Hill Higher Education 2007 978-0-07-352340-8 Testo secondario
Alan Bertossi Algoritmi e strutture dati (Edizione 1) UTET 2000 88-7750-611-3 Testo secondario
T. Cormen, C. Leiserson, R. Rivest, C. Stein Introduzione agli Algoritmi e Strutture Dati (Edizione 2) McGraw-Hill 2005 88-386-6251-7 Testo consigliato per la prima parte del corso
Steven S. Skiena The Algorithm Design Manual (Edizione 2) Springer 2008 9781848000698 Testo secondario per il corso ma ottimo come manuale di riferimento per un'ampia classe di problemi.
Christos H. Papadimitriou Computational complexity Addison Wesley 1994 0201530821 testo principale
Stuart Russell, Peter Norvig Artificial Intelligence: A Modern Approach (Edizione 2) Prentice Hall 2003 0137903952 Testo adottato
Judea Pearl Heuristics: Intelligent search strategies for computer problem solving (Edizione 1) Addison Wesley 1985 0-201-0559 Testo complementare
Stuart Russell, Peter Norvig Intelligenza artificiale: Un approccio moderno (Edizione 2) Pearson Education Italia 2005 88-7192-22 Traduzione italiana del testo adottato
Chin-Liang Chang, Richard Char-Tung Lee Symbolic Logic and Mechanical Theorem Proving (Edizione 1) Academic Press 1973 0121703509 Testo complementare

Modalità d'esame

Modulo: ALGORITMI AVANZATI
-------
L'esame consiste in una prova scritta (da sostenere insieme alle prove scritte degli altri due moduli) della durata di 1 ora (3 ore complessive). Il voto di questo modulo vale 1/3 del voto finale.


Modulo: COMPLESSITÀ
-------
L'esame consiste in una prova scritta (da tenersi insieme alle prove scritte degli altri due moduli) della durata di 1 ora (3 ore complessive). Il voto di questo modulo vale 1/3 del voto finale.


Modulo: INTELLIGENZA ARTIFICIALE
-------
Il voto nel modulo Intelligenza artificiale vale 1/3 del voto nell'esame di Algoritmi. La prova consiste in un compito scritto.

Le/gli studentesse/studenti con disabilità o disturbi specifici di apprendimento (DSA), che intendano richiedere l'adattamento della prova d'esame, devono seguire le indicazioni riportate QUI