- Oggetto:
Fisica della computazione
- Oggetto:
Physics of computation
- Oggetto:
Anno accademico 2023/2024
- Codice attività didattica
- FIS0188
- Docente
- Piero Fariselli (Titolare del corso)
- Corso di studio
- 008703 Laurea in Fisica
- Anno
- 3° anno
- Periodo
- Secondo 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, 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, 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 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 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,)
- 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)
- Elementi di teoria dell'informazione
- Breve introduzione alla Stochastic Thermodynamics
- La fisica dell’informazione, Maxwell Deamon
- Termodinamica della computazione, costo energetico vs velocità.
- Elementi di computazione quantistica.
3. Computazione ispirata dalla Biologia (varie sorgenti)
- Algoritmi genetici
- Reti neurali e deep learning
- 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,)
- 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)
- Information theory
- A brief introduction to Stochastic Thermodynamics.
- Physics of information, Maxwell Demon
- Thermodynamics of computation, energy cost vs speed.
- Concept of quantum computation.
3. Computation inspired by biology (various sources and lecture notes)
- Genetic algorithms
- Neural networks and deep learning
- 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 e diverso da quello presentato.
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 argument treated in the class.
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:
- Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids
- Anno pubblicazione:
- 1998
- Editore:
- Cambridge University Press
- Autore:
- Durbin, Eddy, Krogh, Mitchison
- ISBN
- Capitoli:
- 9
- 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:
- Libro
- Titolo:
- WHAT CAN BE COMPUTED?
- Anno pubblicazione:
- 2018
- Editore:
- Princeton University Press
- Autore:
- JOHN MACCORMICK
- Capitoli:
- 2-6,8-11
- 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
- Registrazione
- Aperta
- Oggetto:
