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

4

Offerto anche nei corsi:

Lingua di erogazione

Italiano

Settore Scientifico Disciplinare (SSD)

ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI

Periodo

I semestre dal 1 ott 2009 al 31 gen 2010.

Per visualizzare la struttura dell’insegnamento a cui questo modulo appartiene, consultare:  organizzazione dell'insegnamento

Obiettivi formativi

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.

Programma

Richiamo dei principali concetti inerenti ai problemi computazionali: descrizione, istanze, codifica, modelli precisi e modelli approssimati. Problemi computazioni di ottimizzazione. Esempi di 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.
Valutazione due soluzioni all'esercizio di ricerca elemento in una matrice ordinata.
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)
Introduzione e analisi vantaggi svantaggi.

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.

Algoritmi per problemi temporali vincolati
-------------------------------------------
Introduzione ai concetti di problemi con vincoli e vincoli temporali.
Algoritmi per la risoluzione di problemi con vincoli temporali semplici (algoritmi polinomiali) o composti (tecnica di backtracking con ottimizzazioni locali).

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.

Modalità d'esame

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.

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