Corso di laurea magistrale in Informatica

Saper progettare algoritmi iterativi e ricorsivi secondo strategie comuni, sfruttando strutture dati come alberi, pile, grafi. Possedere rudimenti della teoria della complessità computazionale: esistenza di classi di complessità computazionale deterministica e non deterministica in tempo. Saper programmare in un qualche linguaggio di programmazione strutturato.

Si suggerisce, ma non è obbligatorio, seguire l'insegnamento durante il primo dei due anni previsti per la magistrale.

L'impostazione metodologica data al programma didattico può dare una visione d'insieme utile per meglio inquadrare altri insegnamenti più specialistici.

L'insegnamento ha l'obiettivo di illustrare la rilevanza di concetti quali: "problema compuazionale intrattabile", "riduzione tra problemi", "euristica", "modelli di calcolo anche non convenzionali". Gli obiettivi sono trasversali alle tre aree di interesse ("realtà virtuale", "reti e sistemi informatici", "sistemi per il trattamento dell'informazione") elencate nel documento che individua gli "Obiettivi formativi specifici del CdS in Informatica (LM18)". Il motivo della trasversalità è che gli obiettivi dell'insegnamento sono di natura metodologica, mirando a trasmettere la rilevanza di concetti e strumenti consolidati che individuano uno spartiacque fondamentale: al di qua è noto che l'informatizzazione di un processo potrà certamente essere efficace, al di là l'efficacia dell'informatizzazione di un processo può, invece, essere inefficace con conseguente spreco di risorse.

Più nel dettaglio, i problemi intrattabili, che hanno natura combinatoria e riconosciuta utilità applicativa, sono accomunati dalle due seguenti caratteristiche:

• non sono noti algoritmi che risolvono qualsiasi istanza, impiegando quantità di risorse accettabili;
• non è possibile dimostrare che tali algoritmi proprio non esistono.

Partendo da motivazioni storiche oggettive sulla necessità di introdurre nuovi strumenti formali per risolvere problemi intrattabili, l'insegnamento si propone di illustrare o implementare:

• strategie di generazione esaustiva di spazi degli stati, accennando all'uso di strumenti per certificare che l'implementazione sia corretta rispetto a specifiche date (brute-force e certificazione);
• strategie per sfrondare lo spazio degli stati, con potenziale miglioramento delle prestazioni algoritmiche (backtracking e branch&bound);
• tecniche per stimare quanto la risposta fornita algorimticamente approssimi quella migliore, non nota (approssimazzione);
• una tecnica algoritmica ricorsiva, alternativa alle precedenti, per fornire risposte a problemi combinatori (programmazione dinamica);
• il concetto di riduzione e la sua applicazione per dimostrare incontrovertibilmente la difficoltà intrinseca di problemi intrattabili classici (toria della riduzione polinomiale);
• la potenziale rilevanza di modelli non convenzionali di computazione, che promettono di risolvere efficientemente problemi intrattabili (computazione (quantistica)-come-Hamiltoniano).

Conoscenza e capacità di comprensione.

Le conoscenze verteranno su metodologie relative alla teoria della complessità computazionale, alla teoria degli algoritmi, con brevi incursioni nella teoria dei modelli di computazione, e dei meccanismi di certificazione formale del software.

Le capacità di comprensione saranno relative a sia caratteristiche e proprietà di tecniche algoritmiche di riferimento, sia a principi alla base della definizione di riduzioni tra problemi computazionali.

Capacità di applicare conoscenza e comprensione.

Programmando, o usando strumenti formali specifici, si sapranno realizzare algoritmi in accordo con le tecniche algoritmiche studiate, eventualmente discutendone proprietà, inclusa la correttezza rispetto a specifiche formali.

Autonomia di giudizio.

Scaturirà dalla conoscenze di tecniche essenziali per esercitare autonomamente la valutazione della potenziale intrattabilità di problemi computazionali, tipicamente di interesse applicativo.

Abilità comunicative.

Permetteranno argomentazioni su concetti come, ad esempio: "Intrattabilità algoritmica", "NP-completeness", "Riduzione tra problemi computazionali", "Tecniche algoritmiche (BruteForce, Backtracking, Branch&Bound, Approssimazione, Programmazione Dinamica", "Modelli di computazione, classici e non convenzionali".

Capacità di Apprendimento.

Permetteranno un accesso più agevole alla letteratura di frontiera, costituita, ad esempio, da articoli scientifici appena pubblicati, relativi a tecniche algoritmiche di avanguardia che forniscono soluzioni interessanti a problemi intrattabili.

 

Motivazioni

• Problemi di ottimizzazione reali
• Inadeguatezza del Calcolo classico

Tecniche algoritmiche classiche

• BruteForce
• Backtracking
• Rilassamento lineare
• Approssimazione
• Branch&Bound
• Programmazione Dinamica

Riduzione tra problemi

• Riallineamento: relazioni tra modelli di calcolo astratti e concreti, problemi decisionali, classi (N)PTIME, riducibilità polinomiale, NP-completezza, etc.
• Catene di riduzioni rilevanti

Riduzione e modelli di calcolo non convenzionali

• Accenni alla computazione adiabatica quantistica e Simulated Annealing
• Modelli QUBO/Ising
• Riduzioni a modelli QUBO

L'insegnamento si sviluppa in 48 ore di lezione con frequenza facoltativa. Il corso si svolgerà in presenza con materiale distribuito attraverso opportune infrastrutture di supporto alla didattica on-line. Lo scopo delle lezioni è porre attenzione alla sintesi di concetti ed alle tecniche necessarie al loro apprendimento. Quindi, le lezioni potranno essere costituite dallo studio collettivo di parti di un capitolo di uno dei testi di riferimento, da brevi video che illustrano elementi specifici di una tecnica algoritmica, da esercizi che si possono svolgere individualmente o collettivamente, dalla sintesi di schemi di algoritmi. Può essere utile avere con sé un personal computer in aula, ma assolutamente non necessario.

 

L'esame è orale e sarà organizzato come segue. Tra gli argomenti del programma didattico svolto, individueremo un insieme di argomenti significativi. Prepararsi all'esame significherà organizzare materiale da esporre oralmente per ciascuno degli argomenti significativi. L'esame consisterà nel presentare il materiale preparato relativo a due argomenti scelti a caso. Globalmente, le due presentazioni non dovrebbero durare più di 40 minuti. Delle presentazioni saranno valutate: ampiezza degli aspetti rilevanti per l'argomento esposto, sintesi, chiarezza, correttezza.