- Oggetto:
- Oggetto:
Fisica della computazione
- Oggetto:
Physics of computation
- Oggetto:
Anno accademico 2024/2025
- Codice attività didattica
- FIS0188
- Docente
- Piero Fariselli (Titolare del corso)
- Corso di studio
- 008703 Laurea in Fisica
- Anno
- 3° anno
- Periodo
- Primo semestre
- Tipologia
- D=A scelta dello studente
- Crediti/Valenza
- 3
- SSD attività didattica
- FIS/07 - fisica applicata (a beni culturali, ambientali, biologia e medicina)
- Erogazione
- Tradizionale
- Lingua
- Italiano
- Frequenza
- Facoltativa
- Tipologia esame
- Orale
- Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
L'obiettivo dell'insegnamanto è quello di fornire le conoscenze di base dei concetti di computabilità a livello teorico matematico, sia includendo i concetti fisici della computazione, thermodinamica stocastica, paradigmi computazionali inspirati dalla biologia, reti neurali e concetti di computazione quantistica.
The goal of teaching is to provide basic knowledge of the concepts of computability, both at a mathematical theoretical level and by including physical concepts of computation, stochastic thermodynamics, computational paradigms inspired by biology, neural networks and basic of quantum computing.
- Oggetto:
Risultati dell'apprendimento attesi
Conoscenza e capacità di comprensione: lo studente al termine del corso avrà contezza delle problematiche relative alla computabilità, la complessità computazionale di algoritmi, aspetti della termodinamica della computazione e informazione, una visione generale di cosa possa vedersi come computazione.
Capacità di applicare conoscenza e comprensione: lo studente al termine del corso avrà la capacità di applicare le conoscenze acquisite al calcolo ed ad altri settori delle fisica.
At the end of the course, the student will have an understanding of computational issues, the computational complexity of algorithms, aspects of the thermodynamics of computation and information, and a general overview of what computation can be.
- Oggetto:
Programma
1. Che cosa può essere calcolato? ("What can be computed?" MacCormick, chap 2-5,10-11, "Feynman Lectures on Computation" Chap. 3, "Biological sequence analysis" Durbin et al., Chap. 9,) [ 6 ore]
- Problemi trattabili, intrattabili e non computabili.
- Computazione universale, macchina di Turing, tesi di Church-Turing.
- Concetti di complessità computazionale asintotica e media, esempi di algoritmi
- Problemi Polinomiani, Nondeterministici Polinomiali, Esponenziali
2. Termodinamica della computazione. (Peliti Pigolotti Stochastic Thermodynamics Chap1-5, Feynman Lectures on Computation Chap. 5, D. Wolpert 2019, Van den Broeck ed Esposito 2015, Parrondo, 2015) [ 12 ore]
- Elementi di teoria dell'informazione
- Breve introduzione alla Stochastic Thermodynamics
- La fisica dell’informazione, Maxwell Deamon, Szilard engine e soluzione dei paradossi.
- Termodinamica della computazione, costo energetico vs velocità.
- Elementi di computazione quantistica:
- Qbits, Sfera di Bloch, quantum gates,
- esempi di circuiti quantisitici con Qiskit
- Teletrasporto quantistico
- Algorithmo di Deutsch-Jozsa
3. Computazione ispirata dalla Biologia (varie sorgenti) [ 6 ore]
- Algoritmi genetici
- Reti neurali e deep learning:
- Building block base
- Reti neurali convoluzionali
- Reti neurali ricorrenti
- Transformers e attention layer (se il tempo lo permette)
- Swarm intelligence, esempio con “ant colony optimization”.
1. What can be computed? ( "What can be computed?" MacCormick, chap 2-5,10-11, "Feynman Lectures on Computation" Chap. 3, "Biological sequence analysis" Durbin et al., Chap. 9,) [ 6 hours]
- Tractable problems, intractable problems, uncomputable problems.
- Universal computers and computation, Turing machine.
- Concepts of asymptotic and average computational complexity, examples of algorithms.
- Polynomial, Nondeterministc Polynomial, EXP problems.
2. Thermodynamics of computation (Peliti Pigolotti Stochastic Thermodynamics Chap1-5, Feynman Lectures on Computation Chap. 5, D. Wolpert 2019, Van den Broeck ed Esposito 2015, Parrondo, 2015) [ 12 hours]
- Information theory
- A brief introduction to Stochastic Thermodynamics.
- Physics of information, Maxwell Demon Szilard engine and relative paradox solution.
- Thermodynamics of computation, energy cost vs speed.
- Concept of quantum computation:
- Qbits, Bloch Sphere, quantum gates,
- quantum circuits with Qiskit
- Quantum teleportation
- Deutsch-Jozsa's and Grover's algorithms
3. Computation inspired by biology (various sources and lecture notes) [6 hours]
- Genetic algorithms
- Neural networks and deep learning:
- basic building block
- Convolutional NNs
- Recurrent NNs
- Transformers and attention layer (if time allows)
- Swarm intelligence, for example, with "ant colony optimization
- Oggetto:
Modalità di insegnamento
Lezioni con proiezioni di diapositive, uso di lavagna. Le lezioni saranno solo in presenza e il materiale sarà inserito posteriormente alla lezione su moodle. Slides delle lezioni e suggerimenti di lettura verranno forniti durante le lezioni. Le ore di lezione frontali ammontano a 24.
Lectures on the blackboard and on slide projections. The lectures are in a classroom. Lecture slides and further reading will be provided during the course. The hours of teaching in class are 24.
- Oggetto:
Modalità di verifica dell'apprendimento
Esame: la studentessa/ lo studente dovrà scegliere un argomento trattato, oppure estendere uno di quelli trattati e spiegarne la parte teorica e pratica attraverso un progetto e una presentazione. Verrà anche chiesto un secondo argomento tratto da quanto svolto a lezione.
Exam: the student will have to choose a topic covered or extend one of those covered and explain its theoretical and practical aspects through a project and a presentation. After the presentation, there will be questions about another subject treated in the class.
- Oggetto:
Attività di supporto
Ricevimento student*: non ci sono date fissate, ma gli student* possono contattare il titolare dell'insegnamento via email, oppure durante e dopo le lezioni per prendere un appuntamento.
Student reception: There are no fixed dates, but students can contact the course instructor via email, or during and after classes to make an appointment.Student reception: There are no fixed dates, but students can contact the course instructor via email, or during and after classes to make an appointment.
Testi consigliati e bibliografia
- Oggetto:
- Libro
- Titolo:
- Feynman Lectures On Computation
- Anno pubblicazione:
- 2000
- Editore:
- Westview Press
- Autore:
- Richard P. Feynman
- ISBN
- Capitoli:
- 3,4,5,6
- Obbligatorio:
- No
- Oggetto:
- Libro
- Titolo:
- WHAT CAN BE COMPUTED?
- Anno pubblicazione:
- 2018
- Editore:
- Princeton University Press
- Autore:
- JOHN MACCORMICK
- ISBN
- Capitoli:
- 2-6,8-11
- Obbligatorio:
- No
- Oggetto:
- Libro
- Titolo:
- Stochastic Thermodynamics: an introduction
- Anno pubblicazione:
- 2021
- Editore:
- Princeton Univ Press
- Autore:
- i Luca Peliti, Simone Pigolotti
- ISBN
- Capitoli:
- 1,2,3,4,5
- Obbligatorio:
- No
- Oggetto:
Further reading
- Parrondo, J., Horowitz, J. & Sagawa, T. Thermodynamics of information. Nature Phys 11, 131-;139 (2015). https://doi-org.bibliopass.unito.it/10.1038/nphys3230
- Van den Broeck and Esposito 2015 "Ensemble and trajectory thermodynamics: A brief introduction" Physica A 418 (2015) 6-;16
- David H. Wolpert 2019 "Stochastic thermodynamics of computation" https://arxiv.org/abs/1905.05669
- Sergio Ciliberto and Eric Lutz 2018 "The Physics of Information: From Maxwell to Landauer" http://lptms.u-psud.fr/nicolas_pavloff/files/2019/11/CilibertoLutz2018.pdf
- Thomas G. Wong "Introduction to Classical and Quantum Computing" https://www.thomaswong.net/introduction-to-classical-and-quantum-computing-1e3p.pdf
- D. Simon. EVOLUTIONARY OPTIMIZATION ALGORITHMS. John Wiley & Sons, 2013
- Burkov A. "The Hundred-Page Machine Learning Book" , 2019.
- Goodfellow et al. 2016 "Deep Learning" MIT Press 2016, https://www.deeplearningbook.org/
- Marco Dorigo, Christian Blumb 2005 "Ant colony optimization theory: A survey" doi:10.1016/j.tcs.2005.05.020
- Oggetto:
Note
Gli/le studenti/esse con DSA o disabilità, sono pregati di prendere visione delle modalità di supporto (https://www.unito.
it/servizi/lo-studio/studenti- e-studentesse-con-disabilita) e di accoglienza (https://www.unito.it/ accoglienza-studenti-con- disabilita-e-dsa) di Ateneo, ed in particolare delle procedure necessarie per il supporto in sede d’esame (https://www.unito.it/servizi/ lo-studio/studenti-e- studentesse-con-disturbi- specifici-di-apprendimento- dsa/supporto) Students with Specific Learning Disorders (SLD) or disabilities are requested to review the university's support (https://www.unito.it/servizi/lo-studio/studenti-e-studentesse-con-disabilita) and reception (https://www.unito.it/accoglienza-studenti-con-disabilita-e-dsa) procedures, and in particular the necessary procedures for support during exams (https://www.unito.it/servizi/lo-studio/studenti-e-studentesse-con-disturbi-specifici-di-apprendimento-dsa/supporto)."
- Registrazione
- Aperta
- Oggetto:
