Vai al contenuto principale
Oggetto:
Oggetto:

Algoritmi e Complessità

Oggetto:

Algorithms and Complexity

Oggetto:

Anno accademico 2022/2023

Codice dell'attività didattica
INF0097
Docente
Luca Roversi (Titolare)
Corso di studi
[008515] Laurea magistrale in informatica
Anno
1° anno 2° anno
Periodo didattico
Secondo semestre
Tipologia
Caratterizzante
Crediti/Valenza
6 CFU - Numero di ore - Number of hours: 48 (in aula)
SSD dell'attività didattica
INF/01 - informatica
Modalità di erogazione
Tradizionale
Lingua di insegnamento
Italiano
Modalità di frequenza
Facoltativa
Tipologia d'esame
Orale
Prerequisiti

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.


Being able to design iterative and recursive algorithms using common strategies, leveraging data structures such as trees, stacks, and graphs. Possessing rudiments of the theory of computational complexity: the existence of deterministic and nondeterministic computational complexity classes in time. Being able to program in some structured programming language.
Propedeutico a

È opportuno aver superato insegnamenti di base offerti da una tipica Laurea in Informatica e che vertono su programmazione e studio di algoritmi di base su pile, alberi o grafi.

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.


It is advisable to have passed basic courses offered by a typical Bachelor's Degree in Computer Science, which focus on programming and the study of basic algorithms on stacks, trees, or graphs.

It is suggested, but not mandatory, to take this course during the first of the two years provided for the master's degree. The methodological approach given to the curriculum can provide an overall view useful for better framing other more specialized courses.

Oggetto:

Sommario insegnamento

Oggetto:

Obiettivi formativi

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

The course aims to illustrate the relevance of concepts such as "intractable computational problems", "reductions between problems", "heuristics", and "models of computation, including unconventional ones". The objectives are transversal to the three areas of interest ("realtà virtuale", "reti e sistemi informatici", "sistemi per il trattamento dell'informazione") listed in the document "Obiettivi formativi specifici del CdS in Informatica (LM18)". The reason for this transversality is that the teaching objectives are methodological in nature, aiming to convey the relevance of established concepts and tools that identify a fundamental watershed: on one side, it is known that the digital transformation of a process can certainly be effective, on the other side, the effectiveness of the digital transformation of a process can be ineffective, resulting in a waste of resources.

More specifically, intractable problems, which have a combinatorial nature and recognized practical utility, are characterized by the following two features:

  • there are no known algorithms that solve any instance of the problem, using acceptable amounts of resources;
  • it is impossible to prove that such algorithms do not exist.

Starting from objective historical motivations on the need to introduce new formal tools to solve intractable problems, the course aims to illustrate or implement:

  • exhaustive state space generation strategies, hinting at the use of tools to certify that the implementation is correct with respect to given specifications (brute-force and certification);
  • strategies to prune the state space, potentially improving algorithmic performance (backtracking and branch&bound);
  • techniques to estimate how much the algorithmic answer approximates the best one, not known (approximation);
  • a recursive algorithmic technique, an alternative to the previous ones, to provide answers to combinatorial problems (dynamic programming);
  • the concept of reduction and its application to incontrovertibly demonstrate the intrinsic difficulty of classic intractable problems (theory of polynomial reduction);
  • the potential relevance of non-conventional models of computation, which promise to efficiently solve intractable problems (computation (quantum)-as-Hamiltonian).

 

Oggetto:

Risultati dell'apprendimento attesi

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.

 

Knowledge and understanding.

The knowledge will focus on methodologies related to the theory of computational complexity, the theory of algorithms, with brief incursions into the theory of computational models, and formal software certification mechanisms.

The understanding skills will be related both to the characteristics and properties of reference algorithmic techniques, and to the principles underlying the definition of reductions between computational problems.

Ability to apply knowledge and understanding.

By programming or using specific formal tools, algorithms will be implemented in accordance with the studied algorithmic techniques, eventually discussing their properties, including correctness with respect to formal specifications.

Autonomy of judgment.

It will stem from the knowledge of essential techniques to independently evaluate the potential intractability of computational problems, typically of applicative interest.

Communicative skills.

They will allow for arguments on concepts such as, for example: "Algorithmic intractability", "NP-completeness", "Reductions between computational problems", "Algorithmic techniques (BruteForce, Backtracking, Branch&Bound, Approximation, Dynamic Programming)", "Computational models, classical and unconventional".

Learning ability.

It will allow for easier access to frontier literature, consisting, for example, of scientific articles just published, related to cutting-edge algorithmic techniques that provide interesting solutions to intractable problems.

Oggetto:

Modalità di insegnamento

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.

 

The course consists of 48 hours of lessons with optional attendance. The course will be held in person with materials distributed through appropriate online teaching support infrastructure. The purpose of the lessons is to focus on the synthesis of concepts and the techniques necessary for their learning. Therefore, the lessons may consist of the collective study of parts of a chapter from one of the reference texts, short videos illustrating specific elements of an algorithmic technique, exercises that can be done individually or collectively, and the synthesis of algorithmic diagrams. It may be useful to have a personal computer in the classroom, but it is not absolutely necessary

Oggetto:

Modalità di verifica dell'apprendimento

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.

 

The exam is oral and will be organized as follows. Among the topics covered in the course program, we will identify a set of significant ones. Preparing for the exam will involve organizing material to be presented orally for each of the significant topics. The exam will consist of presenting the prepared material related to two randomly chosen topics. Overall, the two presentations should not last more than 40 minutes. The presentations will be evaluated based on the breadth of relevant aspects covered, synthesis, clarity, and correctness.

Oggetto:

Programma

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

Motivations

  • Real optimization problems
  • Inadequacy of Classical

Classical algorithmic techniques

  • BruteForce
  • Backtracking
  • Linear relaxation
  • Aprroximation
  • Branch&Bound
  • Dynamic Programming

Reductions among problems

  • Refreshing: relationship among abstract and concrete computational models, decision problems, classes (N)PTIME, polynomial reducibility, NP-completeness, etc.
  • Relevant reduction chains

Reduction and unconventional computational models

  • Hints to adiabatic quantum computation and Simulated Annealing
  • QUBO/Ising models
  • Reductions to QUBO models

Testi consigliati e bibliografia



Oggetto:
Libro
Titolo:  
Computer Algorithms (2nd Edition)
Anno pubblicazione:  
2007
Editore:  
Silicon Press
Autore:  
E. Horowitz, S. Sahni e S. Rajasekaran
ISBN  
Permalink:  
Obbligatorio:  
No


Oggetto:
Libro
Titolo:  
Knapsack Problems
Anno pubblicazione:  
2004
Editore:  
Springer, Berlin
Autore:  
H. Kellerer, U. Pferschy e D. Pisinger
ISBN  
Obbligatorio:  
No


Oggetto:
Libro
Titolo:  
Computers and Intractability: A Guide to the Theory of NP-Completeness
Anno pubblicazione:  
1979
Editore:  
W. H. Freeman & Co.
Autore:  
M. R. Garey e D. S. Johnson
Obbligatorio:  
No


Oggetto:
Articolo
Titolo:  
Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models
Titolo rivista:  
arXiv
Anno pubblicazione:  
2019
Autore:  
F. Glover, G. Kochenberger e Y. Du
URL:  
Obbligatorio:  
No
Oggetto:

Possibili ulteriori fonti bibliografiche

  • T. Albash e D. Lidar. “Adiabatic quantum computation”. In: Reviews of Modern Physics 90 (2018), p.015002.
  • R. M. Karp. “Reducibility Among Combinatorial Problems.” In: Complexity of Computer Computations. A cura di R. E. Miller e J. W. Thatcher. The IBM Research Symposia Series. Plenum Press, New York, 1972, pp. 85-;103.
  • R. M. Karp. “Reducibility Among Combinatorial Problems”. In: 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. A cura di M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi e L. A. Wolsey. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 219-;241.
  • D. Kozen. The Design and Analisys of Algorithms. url: https://www.cs.cornell.edu/~kozen/Papers/daa.pdf.
  • A. Lucas. “Ising formulations of many NP problems”. In: Frontiers in Physics 2 (2014), p. 5.
  • C. McGeoch. “Theory versus practice in annealing-based quantum computing”. In: Theor. Comput. Sci. 816 (2020), pp. 169-;183.
  • N. N. Taleb. Il cigno nero. Come l’improbabile governa la nostra vita. Saggi. Tascabili. Il Saggiatore, 2009.

 



Oggetto:
Ultimo aggiornamento: 04/05/2023 18:14
Location: https://magistrale.informatica.unito.it/robots.html
Non cliccare qui!