Liste de projets, expérimentation numérique.

• Remarque: les "vidéos" ci-dessous sont des gifs animés. Si vous utilisez le navigateur Firefox, on conseille d'installer le plugin "Toggle animated GIFs" et d'utiliser les touches:
  
  • "Shift+M": pour recommencer la vidéo
  • "Ctrl+M": pour stopper/continuer la vidéo.

Objectif de cet enseignement:

Apprendre l'expérimentation numérique pour divers problèmes de science (physique, ..), et connaitre les différentes méthodes et algorithmes standards.

Déroulement de l'enseignement:

Dans une première partie, chaque étudiant s'initie à un langage de programmation bien adapté au calcul scientifique. On propose python ou le C++. Voici un didacticiel pour C++ et voici un didacticiel pour python. On a choisit ces deux langages, car de nombreuses bibliothèques scientifiques sont disponibles. (pour python il y a scipy, matplotlib,..., pour C++ il y a gsl,  root, armadillo... ).

Dans une deuxième partie, en travaillant par binomes (ou seuls), les étudiants choisissent un projet d'expérimentation numérique qu'ils développent. Une liste de projets possibles est donnée ci-dessous. On peut distinguer trois parties dans ce travail:

1. Phase de modélisation: partant du problème posé, il faut réfléchir à la façon de modéliser le problème, c'est à dire le mettre en équation, quel algorithme mettre en oeuvre, définir les objectifs que l'on peut obtenir de façon réaliste,...
   Très souvent on connait les résultats au problème posé pour des cas particuliers. Il faut bien étudier au préalable ces cas particuliers, car ils permettront de tester le programme.
   
2. Phase de programmation: on écrit le programme dans le langage choisit. (On teste le programme au fur et à mesure en utilisant les cas particuliers)
3. Phase d'exploitation: on étudie et discute les résultats de la simulation. On rédige un “document scientifique” (en utilisant Lyx).

Outre la programmation, il pourra être utile de faire du calcul formel au cours du projet. Pour cela on suggère l'utilisation du logiciel libre xcas.

• A la dernière séance, chaque étudiant (ou binome) présente son projet sur vidéo projecteur, pendant 15 à 20 mn, à l'ensemble de la classe. Cette présentation devra être préparée avec Lyx (qui permet de créer des documents scientifiques) et exportée en html (avec LyxHtml) ou en pdf. Pour apprendre Lyx, voici un document en pdf qui sert d'exemple et d'exercice. Voici le même document en html, qui vous servira éventuellement pour copier/coller.
• Une documentation supplémentaire est disponible pour beaucoup de projets ci-dessous. Pour plus d'informations, contacter l'enseignant: Frédéric Faure. Le signe (*) signifie que il y a énoncé précis. On indique aussi la difficulté du projet: 1,2,3,4,5.

1 Systèmes dynamiques avec peu de degrés de liberté

1.1 L'équation du télégraphe en dimension 1.

1.2 Modèles de dynamiques prédateurs, proix et généralisation.

1.3 Application logistique, fractale de Julia et de Mandelbrot.

• Voir Cours.
• Zoomdans la fractale de Mandelbrot.

1.4 Le problème à trois corps restreint.

1.5 Dynamique sur une surface hyperbolique

1.6 Billard polygonal

1.7 Application de Gauss et fractions continues en théorie des nombres.

1.8 Moulin de Lorenz et flot de Lorenz

• Articlede Lorenz de 1963, "Deterministic nonperiodic flow". (il a utilisé l'article de Saltzman 1962).
• Articlede E. Ghys de 2010, "L'attracteur de Lorenz, paradigme du chaos".

1.9 Billard de sinai avec obstacles ronds ou obstacles rectangles

1.10 Le double pendule

1.11 « Dripping faucet » , « le robinet qui goutte »

1.12 Anosov linkage

1.13 (*4)Billard dispersif de Sinaï (1970)

1.14 Théorie Astronomique du climat

Informations:

1.15 (4) Relativité générale:

Objectif:

1.16 (3) Simulateur de Vol d'un planeur

1.17 Simulateur de Vol d'une montgolfiere

1.18 (2) Pendule chaotique

1.19 Dynamique du pendule pulsé

1.20 Boule du jeu Billard

1.21 Etude dynamique d'un billard parfait

1.22 Modèle des anneaux de Saturne

1.23 Optique géométrique

1.24 Oscillation de deux masses couplées

1.25 Bouteille magnétique

• Calcul trajectoire particule dans champ magnétique donné - champ uniforme, puis dipôle (incliné ou non)
• Effet "bouteille magnetique" (?), vitesse de dérive - éventuellement, calcul du champ electromagnétique rayonné par les particules.

1.26 Astronomie

• Voyage d'une sonde spatiale à travers le système solaire. Observer le phénomène de ”billard planétaire”
• Mouvement du soleil et des planètes dans le ciel, éphémérides.
• (*) Mouvement relatif de la Terre et du Soleil puis Construction d'un cadran solaire. Equation du temps. Documents
• Couplages entre les effets de marée et rotation d'une planète.
• Prévision des éclipses de Lune et de Soleil.

2 Systèmes dynamiques avec un grand nombre de degrés de liberté

2.1 Dynamique de N corps

• Approche libre, où le but est de voir les divers problèmes et amener les étudiants a proposer quelques solutions (application à un ensemble d'étoiles)
• Approche contrainte, 2 puis 3eme corps perturbatif, place a proximite des points de Lagrange, résonances.

2.2 Jeu de la vie, automates cellulaires

2.3 Circulation automobile et embouteillages

2.4 (*3)Dynamique spatio-temporelle

2.5 Modèle de Kuramoto-Sivashinsky de chaos -spatio_temporel.

• Equation de mouvement de Kuramoto-Sivashinski (p.4). On considère une fonction $u\left(x,t\right)\in C$ avec $x\in S^1=R/LZ$, $t\in R$, et déterminée par $$\begin{array}{cc}\frac{\partial u}{\partial t}=-u\frac{\partial u}{\partial x}-\frac{{\partial }^{2}u}{\partial x^2}-\frac{{\partial }^{4}u}{\partial x^4}& (1)\end{array}$$avec une condition initiale donnée $u\left(x,t\right)$ et une longueur $L>0$ donnée.
• Ecriture du modèle en Fourier: on décompose$$u\left(x,t\right)={\sum }_{k\in Z}{u}_k\left(t\right)e^{i2\pi kx/L}$$avec des composantes de Fourier $u_k\left(t\right)\in C$. Alors (1) s'écrit:$$\begin{array}{cc}{\sum }_{k\in Z}\frac{\partial u_k}{\partial t}{e}^{i2\pi kx/L}& =-{\sum }_{k_1,k_2\in Z}\left(\frac{i2\pi k_1}{L}\right)u_{k_1}{u}_{k_2}{e}^{i2\pi \left(k_1+k_2\right)x/L}\\ & -{\sum }_k{\left(\frac{i2\pi k}{L}\right)}^2{u}_k{e}^{i2\pi kx/L}-{\sum }_k{\left(\frac{i2\pi k}{L}\right)}^4{u}_k{e}^{i2\pi kx/L}\end{array}$$or le terme en double somme peut s'écrire ${\sum }_{k_1,k\in Z}\left(\frac{i2\pi k_1}{L}\right)u_{k_1}{u}_{k-k_1}{e}^{i2\pi kx/L}$ et l'unicité de la décomposition de Fourier donne:$$\begin{array}{cc}\forall k\in Z,\frac{\partial u_k}{\partial t}& =-{\sum }_{k_1}\left(\frac{i2\pi k_1}{L}\right)u_{k_1}{u}_{k-k_1}-{\left(\frac{i2\pi k}{L}\right)}^2{u}_k-{\left(\frac{i2\pi k}{L}\right)}^4{u}_k\\ \leftrightarrow \forall k\in Z,& \frac{\partial u_k}{\partial t}=-i{\sum }_{k_1\in Z}\left(\frac{2\pi k_1}{L}\right)u_{k_1}{u}_{k-k_1}+{\left(\frac{2\pi k}{L}\right)}^2{u}_k-{\left(\frac{2\pi k}{L}\right)}^4{u}_k\\ \leftrightarrow \forall k\in Z,& \frac{\partial u_k}{\partial t}=-i\left({\sum }_{k_1\in Z}{q}_{k_1}{u}_{k_1}{u}_{k-k_1}\right)+\left(q_k^2-q_k^4\right)u_k\end{array}$$ En posant $q_k=\left(\frac{2\pi k}{L}\right)$. On pose$$v_k=i{u}_k$$Ainsi$$\leftrightarrow \frac{\partial v_k}{\partial t}=-\left({\sum }_{k_1\in Z}{q}_{k_1}{v}_{k_1}{v}_{k-k_1}\right)+\left(q_k^2-q_k^4\right)v_k$$qui est une équation réelle.
• Approximation: Modèle tronqué en Fourier. On choisit $N\in N$ et on considère seulement les composantes $v_k\in C$ avec $k\in \left[-N,\dots N\right]$. Avec cette approximation on a le système dynamique$$\leftrightarrow \forall k\in \left[-N,N\right],\frac{\partial v_k}{\partial t}=-\left({\sum }_{k_1=-N}^N{q}_{k_1}{v}_{k_1}{v}_{k-k_1}\right)+\left(q_k^2-q_k^4\right)v_k$$Ce sont $2N+1$ équations couplées.
• Programme en python.

2.6 Accrochage de fréquences

2.7 Circulation automobile et embouteillages

2.8 Ondes solitaires à la surface de l'eau

2.9 Avalanche de neige ou de tas de sable

2.10 Modèles de morphogénèse

• Articlede Turing de 1952. "The Chemical basis of morphogenesis".
• Videosdu modèle de Gray-Scott sur la page de Karl Sims. Belles images. Videos étonantes: video,
• Logiciel Ready pour la simulation.
• Cet article 2005 de Rui Dilao

2.11 Des réseaux pour modéliser la diffusion des idées

2.12 Routage de voilier

1. Optimiser une courbe donnée.
2. construire une fonction sur l'espace à valeur temps d'arrivée.

3 EDP et problèmes d'ondes

3.1 (5) Chaos Quantique

Enoncé:

• partie 1
• partie 2, manuscrite.

3.2 (*2 puis 3) Formation de nuages sur une montagne par condensation de l'humidité

3.3 Son: réalisation d'un accordeur pour intrument musical

3.4 Son: détection d'une note musicale

1. détection d'une note musicale Enoncé.
2. détection du rythme
3. écriture automatique de la partition avec le logiciel lilypond.

3.5 Son: détection d'une polyphonie

3.6 Evolution d'une onde dans une cavité bidimensionelle (Billard).

3.7 (4) Etats stationnaires et effet tunnel en mécanique quantique

3.8 Solitons dans une chaine d'atomes

3.9 Ondes solitaires à la surface de l'eau

3.10 Transformée par ondelettes d'un signal sonore

3.11 Microscope en ondelettes d'une image (méthode de Daubuchie)

3.12 (*3) Vibration d'une membrane de tambour de forme quelconque

3.13 Evolution d'un paquet d'onde en milieu dispersif

3.14 Localisation des ondes dans un milieu désordonné

• On prend par l'exemple d'ondes quantiques d'électrons dans un milieu désordonné (métal contenant des impuretés) se traduisant par un potentiel V(x) aléatoire. On étudie la forme des ondes stationnaires, et la propagation des paquets d'ondes. On observe le résultatremarquable (et curieux) qu'à une dimension ces ondes sont toujours localisées dans une région de l'espace : ”localisation de Anderson”.

3.15 Equation de la chaleur

• jouer avec conditions initiales et aux limites, permettant d'introduire d'autres termes dans l'équation (écoulement)

3.16 Détection et reconnaissance d'une vibration

Etapes du projet

1. Partir de l'exemple donné sur l'utilisation du micro. Observer qu'il affiche un signal bruité en permanence et que si on tape sur la table, ce signal devient plus intense. Modifier le programme pour qu'il extrait un signal sur une durée $T$ si le signal observé dépasse un certain seuil.

4 Physique statistique et thermodynamique

4.1 (*4) Mouvement de particules dans une enceinte

4.2 (3) Mécanismes de l'aimantation et ferromagnétisme

Figure 1: Resultat de l'algorithme de Monte-Carlo pour le modèle d'aimantation de Ising, aux températures $\beta =1/\left(k_{b}T\right)=0.3$ (désordre), $0.4$ (transition de phase) et $0.5$ (ordre magnétique).

1. Combien y a t-il de sites? Quelles configurations donnent l'énergie minimale? et maximale?
2. L'algorithme d'évolution suivant est appelé algorithme de montecarlo . $\beta \ge 0$ est un paramètre fixé qui est l'inverse de la température: $\beta =1/\left(k_{b}T\right)$.
   
   1. A l'instant $n=0$, on part d'une configuration $f$ choisie au hasard.
   2. On choisit un site $X$ au hasard, et on note $f\text{'}$ la configuration identique à $f$ sauf au site $X$ où le spin est opposé: $f{\text{'}}_X=-f_X$ (spin opposé).
   3. A l'instant $n+1$,
      
      1. Si $E\left(f\text{'}\right)<E\left(f\right)$ on choisit la configuration $f\text{'}$.
      2. Si $E\left(f\text{'}\right)\ge E\left(f\right)$ on choisit la configuration $f\text{'}$ avec la probabilité $P_{f\to f\text{'}}=exp\left(-\beta \mathrm{.}\left(E\left(f\text{'}\right)-E\left(f\right)\right)\right)$ (et on reste donc avec $f$ avec la probabilité complémentaire).
   4. On revient en (b) pour poursuivre l'évolution du champ de spins.
   Cet algorithme correspond à une matrice stochastique réversible pour la mesure de Boltzmann:$$u\left(f\right)=\frac{1}{Z}exp\left(-\beta E\left(f\right)\right)$$
3. Ecrire un programme qui fait évoluer et représente la configuration du champ de spins $f_X$.
4. L'aimantation de la configuration $f$ est $M\left(f\right):={\sum }_X{f}_X$. Représenter l'aimantation au cours du temps. Quand l'équilibre statistique est atteind, calculer la moyenne $⟨M⟩$ et la variance $V=⟨{\left(M-⟨M⟩\right)}^2⟩$. Représenter $⟨M⟩\left(\beta \right)$ et $V\left(\beta \right)$ en fonction de $\beta$.

5 Jeux avec animation graphique

5.1 (*3) Le labyrinthe

• Il faut tout d'abord construire un labyrinthe à 2D au hasard, dans un grand carré NxN, ayant la propriété que pour tout point A,B du labyrinthe, il y a un unique chemin les connectant (structure en arbre).
• Une fois le labyrinthe construit, on peut en faire un jeu: on déplace un personnage, il doit trouver la sortie, et échapper aux montres qui le poursuivent à l'odeur...
• Indications. Article de 1981.

6 Jeux avec algorithme

6.1 Variante de Ines du Ti-Tac-Toe

• Le premier joueur rouge pose une croix dans la case de son choix. Ici en $\left(A2;B1\right)$. Le code $\left(2,1\right)$ de la micro case signifie que le deuxième joueur bleu doit jouer dans la macro-case correspondante qui est $\left(B,A\right)$. Il est libre de choisir la micro-case. Le joueur bleu joue en $\left(B3,A3\right)$ un rond bleu. Cela oblige le joueur rouge à jouer dans la macro-case $\left(C,C\right)$. Etc.

• Une macro-case est gagnée lorsque il y a troix croix (ou cercles) alignés. Par exemple dans cet exemple 2 la macro-case $\left(B,A\right)$ est gagnée par les bleus et $\left(C,B\right)$ est gagnée par les rouges. Si une macro-case est gagnée par exemple $\left(B,A\right)$, plus personne n'a le droit d'y jouer. On peut la colorier avec la couleur du gagnant.

• Le but du jeu est d'obtenir trois macro-cases alignées. Par exemple ici les bleus ont gagné:

6.2 (*3) La puissance 4

• Le jeu (bien connu) occupe deux joueurs (jaune et rouge). Il y a un tableau vertical de 10 cases par 10 cases. Chacun pose à son tour un pion (jaune ou rouge) dans une colonne. Le pion va s'empiler dans la colonne sur les pions déjà présents. Le gagnant est le premier qui a formé une ligne de 4 pions consécutifs de sa couleur. Cette ligne peut être horizontale, verticale ou diagonale.
• Dans un premier temps, le programme devra permettre à deux joueurs de jouer à l'écran (le programme arbitre). Dans un deuxième temps, on developpera une stratégie qui permette à l'ordinateur de jouer le mieux possible. (remarque: le plus simple est que l'ordinateur joue dans une colonne au hasard. Mais on peut faire mieux...)
• On peut ensuite faire un concours entre différents programmes...

6.3 (3) Le jeu oblique

• Voici le terrain de jeu: c'est un réseau de 11 lignes et 11 colonnes penché vers la droite de 30 degrés. On rajoute ensuite des lignes en diagonales (pente à -60 degrés) de façon à ce que chaque intersection ait 6 voisins. Il y a deux joueurs (blanc-noir). Chaque joueur pose à tour de rôle un pion (blanc ou noir selon sa couleur) sur une intersection de son choix. Le but du joueur blanc est de connecter le côté supérieur et le côté inférieur par une ligne de pions blancs voisins deux à deux. Le but du joueur noir est de relier les côtés gauche et droit. Clairement, il ne peut y avoir qu'un seul gagnant. La règle est très simple, mais il y a des astuces pour bien jouer...
• Le programme devra tout d'abord arbitrer, et détecter le premier gagnant. Dans un deuxième temps, on écrira un code qui permette au programme de jouer.

6.4 (4) Le jeu de Go

• Pour découvrir le jeu, voir jeudego.org.
• Indications de programmation: go_enonce.html

6.5 (*3) L'écureuil dans sa cage

• C'est un jeu en bois: des pièces peuvent se déplacer dans un cadre. Parmi elles, un ecureuil. Il y a une sortie en bas du cadre. On doit déplacer les pièces (par translations), pour faire sortir l'écureuil de sa cage.   Voici une photographie des pièces au départ du jeu:

• Voici une solution (page1, page2) en 95 coups (ainsi que l'adresse de l'artisan qui construit ce bel objet).

7 Idées en vrac

• Stabilité de l'axe de rotation terrestre (modèle de Lascar)
• Percolation, et groupe de renormalisation
• Dessin de fractales
• Ondes lumineuses dans un guide à indice variable
• Musique: son émit par une corde pincée.
• Evolution thermodynamique d'une étoile.
• Rayonnement synchrotron par résolution des équations de Maxwell.
• Fluide visqueux, équation de Navier Stokes, turbulence.
• Ecoulement visqueux d'un glacier.
• Remontée des grosses pierres dans un tas de sable
• Evolution de 3 corps en attraction gravitationnelle, puis N corps (amas d'étoiles, évolution vers l'effondrement gravitationnel).
• flux de molécules à travers l'ouverture d'un récipient.
• Effet de Serre: (effet d'Albedo,..)
• Perturbation de la position d'un satellite (developpt multipolaire du chaps de la Lune et Soleil)
• Coef de pénétration d'un profil (aile) dans un fluide parfait: résoudre Df = 0 , et calculer la force appliquée.
• Phénomène des marées dans un estuaire.
• Avalanche de neige ou de tas de sable: modèle de Monte-Carlo; avec coef de viscosité, et température. Voir ce site.
• Algoritmes de recuit
  
  • Empilement de sphères
  • Le problème du voyageur de commerce avec des contraintes
• Algoritmes de croissance
  
  • Croissance à partir d'un germe et mesure de porosité
  • Croissance par déposition d'atomes et croissance de défauts
    
    pyramidaux
  • Croissance d'amats ioniques par minimisation de l'énergie électrostatique
• Crytographie
  
  • On utilise un mot appelé “clef” ex. (EXCEPTIONNEL) pour coder un message ex: “MESSAGE SECRET”. Pour cela on convertit la clef en nombres ex: (5,24,3,...)$=\left(c_1,c_2\dots c_N\right)$ et aussi le message: $\left(m_1,m_2,\dots m_M\right)$ et on obtient un nouveau message codé en remplaçant $m_j$ par $m{\text{'}}_j=m_j+c_j$ modulo 27. Pour décoder il suffit de faire $m_j=m_j\text{'}-c_j$. Ensuite on peut chercher à craquer un message coder de cette façon: il faut trouver la clef et pour cela on utilise les statistiques usuelles des lettres en langue française.
  • Codage plus compliqué qui consiste à “partager une clef”: on considère un nombre premier $p$ (grand) et $g$ un générateur du groupe multiplicatif ${\left(Z/pZ\right)}^{*}$.
    
    • Deux personnes Alice et Bob connaissent secrètement ces nombres $p$ et $g$. Alice choisit secrètement un entier $a$ et Bob choisit secrètement un entier $b$.
    • Alice calcule $c_a:=g^a mod p$ et l'envoie publiquement à Bob. De même Bob calcule $c_b:=g^b mod p$ et l'envoie publiquement à Alice.
    • Alice calcule $c_b^a=g^{ab}$ et Bob calcule $c_a^b=g^{ab}$. Ainsi Alice et Bob connaissent tous les deux le même entier $g^{ab}$ appelé “clef” qui peut leur servir ensuite à coder un message.