Fondamenti di Fisica Computazionale

Fondamenti di Fisica Computazionale

1

Fondamenti di Fisica Computazionale: A.A. 2019-20, Docente: Claudio Melis

Corso di laurea Fisica

2

Numero crediti 5: 40 ore

Orario di ricevimento(2 ore alla settimana)Venerdiʼ: 15:00-17:00email: [email protected]: 070 675 4829Ufficio: M C3

INFORMAZIONI GENERALI



3

http://people.unica.it/claudiomelis/




4


https://www.dsf.unica.it/~fiore/fcstuff.html



https://www.dsf.unica.it/~fiore/fcstuff.html

5

Obiettivi del corso

Conoscenza e capacità di comprensione applicate-elementi del linguaggio di programmazione python e del sistema operativo unix-elementi di matematica numerica discreta per la soluzione di equazioni differenziali -analisi di segnale -elementi di nuova fisica rispetto a quella curricolare, sperimentata direttamente tramite simulazione.

Capacità applicative-la formulazione corretta, precisa, e pratica del problema fisico-la scelta di un algoritmo adatto al problema, sulla base della sua accuratezza e adeguatezza, anche in termini di costo computazionale e sforzo di programmazione-la scelta e realizzazione di soluzioni mirate ai problemi specifici, solo apparentemente elementari, che insorgono nella scrittura di programmi e nella scelta degli algoritmi (ad esempio: l’uso di strumenti non convenzionali come la manipolazione di liste o l’aritmetica vettoriale; la scelta di criteri di convergenza di un metodo iterativo o di individuazione ripetuta di quantità ottimali in un algoritmo).



6

Obiettivi del corso

Autonomia di giudizio-la scelta e il controllo e verifica delle approssimazioni da fare o non fare nel formulare il problema;-la formulazione numerica del problema in base all’accuratezza e alla prestazione dell’algoritmo, e l’esplorazione, test, e eventuale impiego di algoritmi alternativi-la continua analisi e valutazione dei risultati e della loro qualità, anche in vista dell’identificazione di possibili errori sia concettuali di formulazione, o di programmazione.

Abilita' nella comunicazione-necessità di scrivere codici comprensibili e riutilizzabili-presentare i propri risultati, inclusi gli antefatti fisici e numerici, in modo organico, comprensibile, e ragionevolmente completo



7

Prerequisiti



-elementi di matematica superiore (derivate, integrali, sviluppo in serie, cioè almeno il corso di Analisi Matematica I)

-fisica di base (Fisica Generale I e II)

-elementi di sistemi operativi e linguaggi (come in Introduzione all’Informatica).

I prerequisiti strettamente necessari sono richiamati nelle lezioni e nel testo, anche se questo non può sostituire uno studio dettagliato precedente. Per la parte informatica, vengono forniti materiali didattici e lezioni video su web con congruo anticipo sul corso

8

Contenuti



A-Elementi di base-Revisione del sistema operativo unix-Elementi di python (lungo tutto il corso). -Rappresentazione finita dei numeri, discretizzazione, errore algoritmico e di arrotondamento e loro generazione e propagazione. -Esempi: derivate discretizzate e integrali numerici semplici (trapezi, Simpson).

B.1-Equazioni differenziali

-Equazione ordinaria di ordine n come sistema di n equazioni del I ordine. -Origine, applicazioni, e fallimenti degli algoritmi di Euler e Euler-Cromer per l’integrazione numerica di sistemi del primo ordine. -Algoritmo di Verlet e sua derivazione dal principio di azione stazionaria di Hamilton. -Applicazioni a problemi di meccanica (eq. di ordine 2): gravi, oscillatori, moto planetario. Elementi e classificazione di equazioni a derivate parziali per due variabili indipendenti.

9

Contenuti



B.2-Equazioni differenziali-Equazioni a derivate parziali in due variabili. Classificazione e analisi di stabilità (matriciale e di Neumann).-Equazioni paraboliche: equazione di diffusione con metodo FTCS (applicazioni: trasporto di calore in diverse configurazioni e c.a.c., diffusione neutronica in un modello di reattore), equazione di Schroedinger time-dependent (metodo Crank-Nicolson; animazione).-Equazioni ellittiche: Laplace-Poisson e metodi iterativi; applicazioni a vari casi di elettrostatica.-Equazioni iperboliche: cenni all’equazione delle onde e di Burgers (onde d’urto).

C-Trasformata di Fourier-Introduzione ai principi della tecnica di analisi di Fourier e alle peculiarità della versione discreta (leakage, aliasing, etc.). —-Semplici applicazioni di analisi di segnale (armoniche nelle note musicali, frequenze armoniche superiori nell’oscillatore anarmonico, filtro di trend lineari sovrapposti a oscillazioni, ripulitura di immagini per deconvoluzione, rumore colorato e sue caratteristiche, etc).

10

Contenuti



D-Metodo Montecarlo-Numeri pseudocasuali e loro test. -Integrazione Montecarlo e importance sampling. Applicazioni al random walk e al decadimento. -Metodo di Metropolis per la generazione di distribuzioni “arbitrarie”.- Applicazioni: meccanica statistica di oscillatori; annealing simulato; problema del commesso viaggiatore.

11

Consigli non richiesti

Questo corso come tutti i vostri corsi DEVE essere seguito:

la frequenza e’ fondamentale

la selezione del materiale non è banale, l’unico modo per saperlo è seguire le lezioni

le trasparenze delle lezioni non saranno esaustive ma un buon punto di partenza



12

Testi consigliati

-Il corso segue un testo del docente fornito in pdf sul sito del corso.

-Per il linguaggio di programmazione, esistono testi convenzionali resi disponibili, ma il grosso dell’informazione è comodamente accessibile su web (python.org e scipy.org, per esempio), anche in forum specialistici (stackoverflow.com, ad esempio).

Particolarmente utili sono -R. Landau, M. Paez, C. Bordeianu, Survey on computational physics (con codici in python); -N. Giordano, Computational Physics; W. Press et al., -Numerical recipes, con dettagliate informazioni di analisi numerica e algoritmica. -Learning Scientific Programming with Python, di Christian Hill; il sito associato (http://scipython.com) è pieno di utili suggerimenti e applicazioni.



13

Testi consigliati

[1] A. L. Garcia: Numerical methods for physics (presso il docente)[2] R. Landau, M. Paez: Computational physics (PUV0356140)[3] S. Koonin, D. Meredith: Computational physics (MIL0045727)[4] W. Brainerd: Guide to Fortran 2003 Programming (pdf)[5] W. Press et al.: Numerical recipes (NAP0388524)[6] H. P. Langtangen: A Primer on Scientific Programming with Python (pdf)[7] S. Blundell: Magnetism in condensed matter (RMS0137775)[8] J. Binney et al.: The theory of critical phenomena (MIL0179482)[9] C. Hill, Learning Scientific Programming with Python , CUP



14

Metodi didattici

Le lezioni sono frontali con dimostrazioni informatiche: -viene inquadrato il problema fisico- viene discusso l’algoritmo da sviluppare, e si procede allo sviluppo del codice,in aula. - Gli studenti sono incoraggiati a portare il proprio computer e a seguire passo passo il

materiale proposto. In aggiunta, circa 1/5 del tempo è dedicato a revisione periodica, con soluzione di problemi di programmazione e simili in aula insieme al tutore.

Un sito dedicato raccoglie i materiali forniti negli anni precedenti e in quello presente. Sono forniti dei web tutorial interattivi sulle diverse applicazioni sviluppate.



15

Verifica dell’apprendimento

-Durante il corso (orientativamente a 1/3,2/3 al termine delle lezioni) vengono assegnati tre esercizi individuali da svolgere a casa, con scadenza di consegna fissata a circa un mese dall’assegnazione (e incentivata da un bonus di 1 punto per ogni esercizio).

-Ogni esercizio consiste nella realizzazione e utilizzo di codici per la simulazione di un dato problema fisico, e nella stesura di una relazione.

-Tipici problemi proposti sono ad esempio il moto planetario e precessione del perielio, calcolo del potenziale elettrostatico in configurazioni varie, diffusione del calore in un sistema a conduttività termica variabile, analisi di segnali, generazione di distribuzioni di numeri random, annealing simulato.

Il voto viene assegnato in base a una valutazione complessiva (e comparativa tra tutti gli studenti) delle relazioni relative ai tre esercizi.



16

Altre informazioni

-Un sito dedicato del corso (http://www.dsf.unica.it/~fiore/fcstuff.html) raccoglie tutti i materiali forniti negli anni precedenti e in quello in corso.



17

A-Elementi di base

CHE COSA E’ LA FISICA COMPUTAZIONALE?

Studio, sviluppo ed implementazione di algoritmi numerici per risolvere problemi di fisica con i computer.


• Fisica della materia (simulazioni atomistiche)• Fluido dinamica • Fisica delle alte energie/fisica delle particelle• Astrofisica• Biofisica• ….


18

A-Elementi di base

La descrizione di un sistema o fenomeno fisico tramite simulazione numerica richiede:1) costruzione di un modello2) traduzione in un algoritmo di calcolo

Ci sono numerose fonti di errore possibili (la rappresentazione dei numeri, l’accuratezza dei parametri, lo specifico algoritmo scelto) che bisogna conoscere e controllare



19

A-Elementi di base


IL TERMINE ALGORITMO INDICA UN PROCEDIMENTO CHE RISOLVE UN DETERMINATO PROBLEMA ATTRAVERSO UN NUMERO FINITO DI PASSI (ISTRUZIONI) ELEMENTARI. (Il termine deriva dalla trascrizione latina del nome del matematico persiano al-Khwarizmi, vissuto nel IX secolo d.C., che è considerato uno dei primi autori ad aver fatto riferimento a questo concetto scrivendo il libro "Regole di ripristino e riduzione”.)

UN PROBLEMA RISOLVIBILE MEDIANTE UN ALGORITMO SI DICE COMPUTABILE.UN ALGORITMO È UN INSIEME BEN ORDINATO DI OPERAZIONI NON AMBIGUE ED EFFETTIVAMENTE CALCOLABILI CHE, ESEGUITO, PRODUCE UN RISULTATO E TERMINA IN UNA QUANTITÀ FINITA DI TEMPO.

•TERMINAINUNAQUANTITÀFINITADITEMPO

DEFINIZIONE DI UN ALGORITMO

Gli algoritmi sono ampiamente utilizzati in tutte le aree dell’IT (Information Technologies). Volendo fare un esempio di algoritmo in informatica, i motori di ricerca come Google sono basati proprio su questo concetto per poter rispondere quanto più coerentemente alla richiesta di un utente.


https://it.wikipedia.org/wiki/Lingua_latina

https://it.wikipedia.org/wiki/Matematico

https://it.wikipedia.org/wiki/Al-Khwarizmi

https://it.wikipedia.org/wiki/IX_secolo_d.C.

https://it.wikipedia.org/wiki/IX_secolo_d.C.

20

A-Elementi di base


•TERMINAINUNAQUANTITÀFINITADITEMPO

Proprietà fondamentali degli algoritmi

• i passi costituenti devono essere "elementari", ovvero non ulteriormente scomponibili (atomicità);

• i passi costituenti devono essere interpretabili in modo diretto e univoco dall'esecutore, sia esso umano o artificiale (non ambiguità);

• l'algoritmo deve essere composto da un numero finito di passi e richiedere una quantità finita di dati in ingresso (finitezza)

• l'esecuzione deve avere termine dopo un tempo finito (terminazione);• l'esecuzione deve portare a un risultato univoco (effettività).


21

A-Elementi di base


Esempio sempliceProblema da risolvere: dato un mazzo di chiavi, abbiamo la necessità di trovare, all’interno di questo, la chiave che apre un determinato lucchetto.

l’algoritmo a cui fare riferimento?

1. Si sceglie una chiave dal mazzo e la si marca con un pennarello2. Si tenta di aprire il lucchetto con la chiave appena marcata; se funziona, si va al passo 4;3. Se non funziona, si va avanti a controllare la chiave successiva e:

– Se non è marcata, la si marca e si torna al passo 2 – Se si verifica il contrario, si notifica che nel mazzo non è presente la chiave che apre il lucchetto

4. Fine della ricerca.


22

A-Elementi di base

Modelli di computazione: la tesi di Church–TuringSebbene le prime testimonianze storiche di algoritmi di calcolo siano molto antiche — siamo al corrente che già i babilonesi utilizzavano algoritmi di calcolo per l’abaco — per avere una definizione formale di algoritmo si e’ dovuto attendere sino agli anni ’30



23

A-Elementi di base

Modelli di computazione: la tesi di Church–TuringAlonzo Church e Alan Turing si impegnarono nella risoluzione di un problema posto da David Hilbert (Entscheidungsproblem) qualche anno prima: il problema si interrogava sull’esistenza di un algoritmo capace di risolvere ogni problema della matematica. Uno scoglio per i due scienziati fu quello di formulare in termini matematicamente rigorosi il concetto intuitivo di algoritmo.



24

A-Elementi di base

Modelli di computazione: la tesi di Church–Turing


Turing presentò al mondo una macchina calcolatrice ideale capace di riproporre il procedimento mentale dell'uomo scomponendolo nei suoi passi ultimi.

La risposta di Turing è la seguente: una funzione è computabile se e solo se esiste una macchina di Turing, vale a dire un elenco di istruzioni, che la computa. Le macchine di Turing sono in grado di calcolare qualsiasi funzione calcolabile utilizzando i più

recenti e potenti strumenti elettronici.


25

A-Elementi di base

Macchina di Turing

si tratta di una costruzione di pensiero, non soggetta ai vincoli imposti da una realizzazione fisica pratica — che ancor oggi appare incarnare ciò che intendiamo come “algoritmo”.

La tesi di Church–Turing afferma “che la classe di funzioni calcolabili da una macchina di Turing corrisponde esattamente alla classe di funzioni che riteniamo calcolabili da un algoritmo”



26

A-Elementi di base

Macchina di TuringQuella di Church–Turing è una congettura in quanto non si può escludere a priori la possibilità che venga trovato prima o poi un qualche processo che definiremmo algoritmico ma che non possa essere eseguito da una macchina di Turing. Tuttavia ad oggi non si ha alcuna evidenza contraria alla tesi.

A-Elementi di base



27

A-Elementi di baseA-Elementi di base

Macchina di Turing

La macchina di Turing è costituita da un programma, un controllo a stati finiti e un nastro sul quale la macchina abbia accesso in lettura e scrittura tramite una testina.



28


Macchina di TuringIl controllo a stati finiti è una sorta di processore che può assumere un insieme finito di stati q1, q2, . . ., qm; il nastro `e un oggetto unidimensionale che si estende infinitamente in una direzione: possiamo pensarlo diviso in caselle contenenti ciascuna un simbolo preso da un’insieme finito di simboli (detto alfabeto). La testina può scorrere il nastro e agire su una casella alla volta.

Capitolo 1. Introduzione alla teoria della computabilita

Figura 1.1: Schema della macchina di Turing.

Il controllo a stati finiti e una sorta di processore che puo assumere un insiemefinito di stati q1, q2, . . ., qm; il nastro e un oggetto unidimensionale che si esten-de infinitamente in una direzione: possiamo pensarlo diviso in caselle contenenticiascuna un simbolo preso da un’insieme finito � di simboli (detto alfabeto). Latestina puo scorrere il nastro e agire su una casella alla volta.

La configurazione iniziale della macchina prevede che il controllo sia nello statodi partenza qs e che la testina indichi il simbolo ., posto all’origine del nastro.L’evoluzione dell’algoritmo e regolata dal programma, costituito da un elenco distringhe contenenti cinque elementi ciascuna. In primis la macchina selezionaall’interno del programma la stringa avente come primo elemento lo stato in cui sitrova il controllo e come secondo elemento il simbolo indicato dalla testina. Se ilprogramma non contiene la stringa cercata la macchina assume lo stato di arrestoqh e l’esecuzione del programma termina. In caso contrario la configurazione dellamacchina si modifica in accordo con i successivi tre elementi della stringa: il terzoelemento rappresenta lo stato che il controllo dovra assumere; il quarto e un simbolodi � che la testina scrive sulla casella in cui punta; la quinta e ultima istruzionepermette di spostare la testina di una casella a sinistra o a destra sul nastro, o dimantenerla nella posizione corrente.Il ciclo prosegue a meno che il controllo non arrivi a trovarsi nello stato qh; quandoquesto avviene la casella su cui punta la testina contiene l’output del programma.

Abbiamo illustrato la piu semplice delle molte possibili varianti della macchinadi Turing. Esse possono di↵erire ad esempio nel numero di nastri o nella lorodimensionalita. Tutte le varianti conosciute sono pero tra loro equivalenti, nelsenso che ognuna e capace di simulare l’altra.

1.1.3 Modello circuitale di computazione

Un modello di calcolatore alternativo alla macchina di Turing e quello circuitale,che impiega dei circuiti composti da rami di collegamento e porte logiche permanipolare informazioni codificate in numeri binari.Nonostante all’apparenza questo modello non sembri avere molte caratteristiche

6

La configurazione iniziale della macchina prevede che il controllo sia nello stato di partenza qs e che la testina indichi il simbolo posto all’origine del nastro.








6

L’evoluzione del l ’a lgori tmo è regolata dal programma, costituito da un elenco di stringhe contenenti cinque elementi ciascuna



29


Macchina di TuringIn primis la macchina seleziona all’interno del programma la stringa avente come primo elemento lo stato in cui si trova il controllo e come secondo elemento il simbolo indicato dalla testina

Se il programma non contiene la stringa cercata la macchina assume lo stato di arrestoqh e l’esecuzione del programma termina



30


Macchina di TuringIn caso contrario la configurazione della macchina si modifica in accordo con i successivi tre elementi della stringa: il terzo elemento rappresenta lo stato che il controllo dovrà assumere; il quarto è un simbolo di che la testina scrive sulla casella in cui punta; la quinta e ultima istruzione permette di spostare la testina di una casella a sinistra o a destra sul nastro, o di mantenerla nella posizione corrente.








6

Il ciclo prosegue a meno che il controllo non arrivi a trovarsi nello stato qh; quando questo avviene la casella su cui punta la testina contiene l’output del programma.



31


Modello circuitale di computazioneUn modello di calcolatore alternativo alla macchina di Turing è quello circuitale, che impiega dei circuiti composti da rami di collegamento e porte logiche per manipolare informazioni codificate in numeri binari.

Nonostante all’apparenza questo modello non sembri avere molte caratteristiche in comune con la macchina di Turing, si può dimostrare che i due modelli sono di fatto equivalenti



32


Modello circuitale di computazione

Una porta logica è una funzione

1.1. Modelli di computazione

in comune con la macchina di Turing, si puo dimostrare che i due modelli sono difatto equivalenti.

Figura 1.2: Le piu comuni porte logiche classiche.

Una porta logica e una funzione

f : {0, 1}k ! {0, 1}l (1.1)

che associa a k cifre binarie (bit) in input l cifre binarie di output — i simboliconvenzionali di alcune comuni porte logiche sono riportati in figura 1.2. Sebbenetali funzioni siano infinite, ognuna di esse si puo comporre utilizzando un numerofinito di porte logiche chiamate, per questo motivo, universali (un risultato similevale nell’ambito del modello circuitale quantistico, come vedremo al §2.3).Dimostriamo rapidamente quanto a↵ermato costruendo una funzione f qualunquefacendo uso solamente delle porte logiche not, or, and e xor.Limitiamoci inizialmente a funzioni booleane f : {0, 1}k ! {0, 1} (si ottengonoponendo l = 1 nella 1.1); procediamo per induzione. Nel caso k = 1 esistonoquattro diverse possibili f : l’identita, il not e le funzioni costanti 0 e 1. Lefunzioni costanti si possono ottenere, rispettivante, facendo l’and dell’input conun ancilla bit1 posto uguale a 0 oppure facendone l’or con l’ancilla bit 1.Dimostriamo ora il passo induttivo mostrando che una funzione booleana di n+1bit puo essere calcolata utilizzando funzioni di n bit. Consideriamo le due funzioni

f0(x1, x2, . . . , xn) ⌘ f(0, x1, x2, . . . , xn)

f1(x1, x2, . . . , xn) ⌘ f(1, x1, x2, . . . , xn)(1.2)

esse sono funzioni booleane ad n bit che, per l’ipotesi induttiva, possono essererealizzate con le porte scelte precedentemente.Tramite queste due funzioni e possibile calcolare f utilizzando il circuito di figura

1Gli ancilla bit, o bit di lavoro, sono dei bit che non rappresentano un informazione in sensostretto ma hanno solo un ruolo tecnico nel funzionamento del circuito.

7

che associa a k cifre binarie (bit) in input l cifre binarie di output. Sebbene tali funzioni siano infinite, ognuna di esse si può comporre utilizzando un numero finito di porte logiche chiamate, per questo motivo, universali



33


Modello circuitale di computazione


Porte logiche classiche

Nome Effetto Note

AND 1 se entrambi gli input sono 1

OR 1 se almeno uno degli input è 1

NOT Cambia il valore del bit

NAND Equivale a NOT (A AND B)

Rilevante perchè è universale: tutte le porte logiche classiche si possono definire in termini di porte NAND


34


A differenza della sua controparte debole, la congettura forte di Church–Turing è stata più volte messa in discussione nel secolo scorso e tutt’oggi la sua validità è tutt’altro che accertata.

Subito dopo la pubblicazione della tesi di Turing, avvenuta nel 1936, furono assemblati i primi calcolatori elettronici. John von Neumann si occupò di delineare le caratteristiche che un computer reale avrebbe dovuto possedere per poter essere equiparato alla macchina di Turing, ma si dovette aspettare sino al 1947, anno dell’invenzione del transistor, per avere la possibilità di realizzare fisicamente un simile dispositivo



35


Zuse Z3



36Corso di laurea in igiene dentale


Da allora la tecnologia dei calcolatori elettronici si e’evoluta molto rapidamente, tanto che Gordon Moore, nel 1965, formulo’ l’omonima legge secondo la quale la potenza di calcolo dei computer sarebbe dovuta progredire raddoppiando di anno in anno






Di fatto si `e passati dall’Intel 4004 del 1971, costituito da 2250 transistor, al Pentium 4 che, nel 2000, ne conteneva 42 milioni. Tale evoluzione procede di pari passo con la miniaturizzazione dei componenti, la quale comporta da un lato una simile crescita esponenziale dei costi di produzione e dall’altro si scontra con dei limiti fisici. Se le dimensioni di un transitor raggiungeranno infatti l’ordine di grandezza della lunghezza di De Broglie dell’elettrone, gli effetti quantistici non saranno piu’ trascurabili e i circuiti elettronici non potranno più funzionare nel modo in cui oggi normalmente li utilizziamo.

Una delle possibili strade percorribili per non incorrere nel declino della crescitaesponenziale prevista da Moore è quella di passare ad un diverso e nuovo paradigma computazionale, quale è quello dei computer quantistici.





L’ideazione dei computer quantisticinel 1985 David Deutsch propose l’idea che un modello di computazione dovesse basarsi su una teoria fisica, e cercò di definire un modello di computazione capace di simulare qualsiasi sistema fisico.





L’ideazione dei computer quantisticiDato che le leggi della fisica sono, in ultima analisi, quanto–meccaniche, egli considerò un modello di computazione basato sulle leggi della meccanica quantistica. Non era questa un’idea del tutto nuova: Richard Feynman nel 1982 ipotizzò che un computer quantistico avrebbe potuto velocizzare considerevolmente la simulazione di sistemi quantistici.


Fondamenti di Fisica Computazionale

Documents

Transcript of Fondamenti di Fisica Computazionale