- 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, nonché paradigmi computazionali inspirati dalla biologia.
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, as well as computational paradigms inspired by biology.
- 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. Introduzione alla teoria della computazione ( Feynman Lectures on Computation Chap. 3, Biological sequence analysis Durbin et al., Chap. 9, D. Wolpert 2019)
- Linguaggi formali, grammatiche regolari e automi. Automi a stati fininiti e gerarchie di Chomsky,
- Macchina di Turing, computabilità, tesi di Church-Turing.
- Concetti di complessità computazionale asintotica e media, esempi di algoritmi
2. Termodinamica della computazione. (Feynman Lectures on Computation Chap. 5, D. Wolpert 2019, Van den Broeck ed Esposito 2015, Parrondo, 2015)
- Breve introduzione alla Stochastic Thermodynamics
- La fisica dell’informazione, Maxwell Deamon
- Termodinamica della computazione, costo energetico vs velocità.
- Il computer reversibile.
- Concetto di computazione quantistica vs classica.
3. Computazione ispirata dalla Biologia (varie sorgenti)
- Algoritmi genetici
- Reti neurali e deep learning
- Swarm intelligence, esempio con “ant colony optimization”.
1. Introduction to the theory of computation (Feynman Lectures on Computation Chap. 3, Biological sequence analysis Durbin et al., Chap. 9, D. Wolpert 2019)
- Formal languages, regular grammar and automata. Chomsky hierarchies,
- Turing machine, computability, Church-Turing thesis.
- Concepts of asymptotic and average computational complexity, examples of algorithms.
2. Thermodynamics of computation (Feynman Lectures on Computation Chap. 5, D. Wolpert 2019, Van den Broeck ed Esposito 2015, Parrondo, 2015)
- A brief introduction to Stochastic Thermodynamics.
- Physics of information, Maxwell Demon
- Thermodynamics of computation, energy cost vs speed. Reversible computing.
- Concept of quantum vs classical 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:
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:
