Course Syllabus
Obiettivi
Conoscenza e capacità di comprensione
Gli studenti comprenderanno i principi alla base del funzionamento di alcuni modelli di calcolo non convenzionali, modelli bio-ispirati e modelli quantistici.
Conoscenza e capacità di comprensione applicate
Gli studenti saranno in grado di scegliere il modello di calcolo più idoneo per risolvere un problema assegnato.
Autonomia di giudizio
Gli studenti acquisiranno la capacità di valutare se il modello di calcolo sia in grado di affrontare in modo efficiente problemi computazionalmente complessi.
Abilità comunicative
La grande attenzione dedicata agli aspetti formali permetterà agli studenti di comprendere l'importanza di una comunicazione univoca, utilizzando la terminologia corretta per esprimere le nozioni e i concetti appresi.
Capacità di apprendimento
la definizione di un ambito teorico formale aiuterà gli studenti a sviluppare l'uso di strategie di apprendimento deduttivo.
Contenuti sintetici
Nozioni e concetti alla base della Teoria della Computazione, e della Teoria della Complessità Computazionale, applicate a modelli di calcolo non convenzionali e quantistici. Il corso fornisce inoltre gli strumenti concettuali e teorici che consentono di comprendere le basi matematiche su cui si basa la definizione dei modelli di calcolo esaminati.
Programma esteso
Per la parte di Unconventional Computing:
• Introduzione: architetture di calcolo classiche, sequenziali e parallele
• Problemi di calcolo non-convenzionali
• DNA Computing: esperimento di Adleman, algoritmo di Lipton
• Computazione Cellulare
• Membrane systems: modello standard, membrane systems per problemi computazionalmente complessi
• Spiking neural P systems
• Algoritmi genetici e reti neurali
• Social algorithms
Per la parte di Quantum Computing:
• Fenomeni fisici quantistici, parallelismo quantistico, entanglement, misurazioni
• Notazione matematica: qubit, bra, ket, operatori unitari
• Gate quantistici, loro rappresentazione, e operatori corrispondenti
• Circuiti quantistici
• Algoritmi quantistici fondamentali: trasformata di Fourier quantistica, algoritmi di Shor (fattorizzazione e logaritmi discreti), algoritmo di Grover
• Cenni ad altri modelli: Macchine di Turing quantistiche, adiabatiche, …
• Linguaggi di programmazione, librerie, simulatori, piattaforme (in particolare: QCEngine , Qiskit)
• Reti neurali ibride, e quantum machine learning
Prerequisiti
Argomenti trattati nei corsi di matematica della laurea triennale in Informatica. È utile - ma non indispensabile - la conoscenza di alcune nozioni di base di informatica teorica (in particolare, macchine di Turing).
Modalità didattica
La lingua di erogazione prevista è l'Inglese. Tuttavia, le lezioni potranno essere erogate in Italiano se tutti gli studenti presenti in aula parlano Italiano, e nessuno studente fa richiesta di seguire le lezioni in lingua Inglese.
Le lezioni verranno registrate e rese disponibili sulla piattaforma e-learning. il corso e' organizzato in 24 lezioni da 2 ore ciascuna, svolte in modalità erogativa in presenza.
Materiale didattico
Libri:
• Andrew Adamatzky: Unconventional Computing - A Volume in the Encyclopedia of Complexity and Systems Science, Second Edition. Springer, 2018
• Wolfgang Polak, Eleanor Rieffel: Quantum Computing : A Gentle Introduction. MIT Press, 2011
• Michael A. Nielsen, Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2010
• Eric R. Johnston, Nic Harrigan, Mercedes Gimeno-Segovia: Programming Quantum Computers: Essential Algorithms and Code Samples. O'Reilly Media, 2019
Appunti forniti dai docenti.
Periodo di erogazione dell'insegnamento
Secondo semestre
Modalità di verifica del profitto e valutazione
La verifica dell'apprendimento è basata su un colloquio orale avente per oggetto gli argomenti svolti a lezione. Durante il colloquio verrà valutata la capacità dello studente di esporre gli argomenti del corso, e di effettuare brevi ragionamenti su di essi.
Non sono presenti prove in itinere.
Orario di ricevimento
Su appuntamento
Sustainable Development Goals
Aims
Knowledge and understanding
Students will understand the principles underlying the functioning of some unconventional, bio-inspired and quantum computational models.
Applied knowledge and understanding
Students will be able to choose to choose the most suitable computational model to solve an assigned problem.
Independent judgment
Students will acquire the ability to evaluate whether the computational model can efficiently tackle computationally difficult problems.
Communication skills
The great attention paid to formal aspects will allow students to understand the importance of unambiguous communication, using the correct terminology to express the notions and concepts learned.
Learning skills
Establishing a formal theoretical framework will help students developing a the use of deductive learning strategies.
Contents
Notions and concepts at the base of the Theory of Computation, and of the Theory of Computational Complexity, applied to unconventional and quantum computational models. The course also provides the conceptual and theoretical tools that allow to understand the mathematical bases on which the definition of the computational models examined is based.
Detailed program
For the Unconventional Computing part:
• Introduction: classical, sequential and parallel computing architectures
• Unconventional Computing Problems
• DNA Computing: Adleman experiment, Lipton algorithm
• Cellular Computing
• Membrane systems: standard model, membrane systems for computationally complex problems
• Spiking neural P systems
• Genetic Algorithms, Neural Networks
• Social Algorithms
For the Quantum Computing part:
• Quantum physical phenomena, quantum parallelism, entanglement, measurements
• Mathematical notation: qubit, bra, ket, unit operators
• Quantum gates, their representation, and corresponding operators
• Quantum circuits
• Fundamental quantum algorithms: quantum Fourier transform, Shor's algorithms (factorization and discrete logarithms), Grover's algorithm
• Notes on other models: Quantum Turing machines, adiabatic Turing machines, ...
• Programming languages, libraries, simulators, platforms (in particular: QCEngine, Qiskit)
• Hybrid neural networks, and quantum machine learning
Prerequisites
Topics explained in mathematics courses held in the laurea degree in Informatics. It is useful - but not necessary - to have basic notions of theoretical computer science (in particular, Turing machines).
Teaching form
The expected language of instruction is English. However, classes may be conducted in Italian if all students present in the classroom speak Italian and no student requests to attend the lessons in English.
Lectures will be recorded and made available through the e-learning website. The course consists of 24 in-person lectures, each lasting 2 hours, delivered in a traditional (transmissive) teaching format.
Textbook and teaching resource
Textbooks:
• Andrew Adamatzky: Unconventional Computing - A Volume in the Encyclopedia of Complexity and Systems Science, Second Edition. Springer, 2018
• Wolfgang Polak, Eleanor Rieffel: Quantum Computing : A Gentle Introduction. MIT Press, 2011
• Michael A. Nielsen, Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2010
• Eric R. Johnston, Nic Harrigan, Mercedes Gimeno-Segovia: Programming Quantum Computers: Essential Algorithms and Code Samples. O'Reilly Media, 2019
Lecture notes provided by the teachers.
Semester
Second semester
Assessment method
The learning assessment is based on an oral interview, on the subjects exposed in class during the course. During the interview, the student's ability to explain the topics of the course, and to make brief thoughts on them, will be assessed.
No mid-term assessments are scheduled.
Office hours
On appointment
Sustainable Development Goals
Staff
-
Alberto Ottavio Leporati
-
Claudio Zandron
