{ "cells": [ { "cell_type": "markdown", "id": "819325fc-1906-453f-a3a7-81ee4b56ef81", "metadata": {}, "source": [ "$\\newcommand\\N{\\mathbb N}\n", "\\newcommand\\Z{\\mathbb Z}\n", "\\newcommand\\Q{\\mathbb Q}\n", "\\newcommand\\R{\\mathbb R}\n", "\\newcommand\\C{\\mathbb C}\n", "\\newcommand\\too\\longrightarrow\n", "\\renewcommand\\phi\\varphi\n", "\\renewcommand\\epsilon\\varepsilon\n", "\\newcommand\\fl[1]{\\left\\lfloor #1\\right\\rfloor}\n", "\\newcommand\\llbracket{[\\![}\n", "\\newcommand\\rrbracket{]\\!]}\n", "\\newcommand\\bbr[2]{\\llbracket #1,#2\\rrbracket}\n", "\\newcommand\\todo{{\\bf TODO }}\n", "\\newcommand\\prob{\\mathbb P}\n", "\\newcommand\\esp{\\mathbb E}\n", "\\newcommand\\var{\\mathbb V}\n", "\\newcommand\\tribu{\\mathfrak T}$" ] }, { "cell_type": "markdown", "id": "0321df4e-1193-4a75-a05b-fbbe574b3fdb", "metadata": {}, "source": [ "# L'électricien sournois\n", "\n", "Marc Lorenzi\n", "\n", "27 août 2024" ] }, { "cell_type": "code", "execution_count": null, "id": "caee8190-7f56-4435-bae7-08b718a1b570", "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "import random\n", "import time" ] }, { "cell_type": "markdown", "id": "27abbbd3", "metadata": {}, "source": [ "## 1. Introduction" ] }, { "cell_type": "markdown", "id": "23a0976e", "metadata": {}, "source": [ "### 1.1 Description du jeu" ] }, { "cell_type": "markdown", "id": "115ef3a2", "metadata": {}, "source": [ "Une installation électrique comporte $n$ lampes et $n$ boutons. Chaque bouton *est censé* changer l'état de la lampe correspondante (allumée ou éteinte). Le problème est que l'installation a été faite par un électricien sournois. Quand on appuie sur un bouton, il change l'état de la lampe correspondante, *mais aussi l'état de certaines autres lampes*. Au départ, toutes les lampes sont éteintes. Le but du jeu est de les allumer toutes." ] }, { "cell_type": "markdown", "id": "998ef4e3-64ff-4e59-849a-548061f193ef", "metadata": {}, "source": [ "Nous prendrons dans la suite l'exemple suivant (où $n=8$). On numérote les lampes et les boutons de 0 à 7.\n", "\n", "- L'appui sur le bouton 0 bascule l'état des lampes 0, 1, 2, 6, 7\n", "- L'appui sur le bouton 1 bascule l'état des lampes 1, 3, 7\n", "- L'appui sur le bouton 2 bascule l'état des lampes 1, 2, 3\n", "- L'appui sur le bouton 3 bascule l'état des lampes 1, 3, 5\n", "- L'appui sur le bouton 4 bascule l'état des lampes 2, 3, 4, 5, 6\n", "- L'appui sur le bouton 5 bascule l'état des lampes 3, 5, 7\n", "- L'appui sur le bouton 6 bascule l'état des lampes 5, 6, 7\n", "- L'appui sur le bouton 7 bascule l'état des lampes 1, 5, 7" ] }, { "cell_type": "markdown", "id": "03525a6e", "metadata": {}, "source": [ "Nous allons voir que derrière ce jeu apparemment sans aucun intérêt se cachent des espaces vectoriels sur le corps à deux éléments et l'algorithme du pivot de Gauss." ] }, { "cell_type": "markdown", "id": "f8a994fb", "metadata": {}, "source": [ "### 1.2 L'approche « c'est évident »" ] }, { "cell_type": "markdown", "id": "98894b4b", "metadata": {}, "source": [ "Dans la règle du jeu, nous voyons que chaque entier entre 0 et 7 apparaît un nombre impair de fois. Or, si une lampe est éteinte et que nous appuyons sur l'interrupteur un nombre impair de fois, la lampe est allumée. Donc, si nous appuyons sur tous les boutons l'un après l'autre, toutes les lampes seront allumées.\n", "\n", "Le problème est que cet argument ne fonctionne que sur l'exemple choisi. Pour une autre installation électrique, cet argument ne fonctionnera plus. Nous allons voir dans ce notebook qu'il est possible de trouver une solution au jeu de façon générale, avec $n$ lampes et $n$ boutons qui changent l'état de certaines des $n$ lampes. Notre algorithme effectuera $O(n^2)$ opérations sur des entiers." ] }, { "cell_type": "markdown", "id": "7ead2df3", "metadata": {}, "source": [ "### 1.3 L'approche enfantine" ] }, { "cell_type": "markdown", "id": "04bc0397", "metadata": {}, "source": [ "On représente un état du jeu par un entier $x\\in\\bbr 0{255}$. Précisément, écrivons\n", "\n", "$$x=\\sum_{k=0}^7 b_{k}2^{k}$$\n", "\n", "Si $b_k=0$ (resp : $b_k=1$) alors la lampe $k$ est éteinte (resp : allumée). Par exemple, prenons $x=114$. On a, en base 2,\n", "\n", "$$x=01110010$$\n", "\n", "Rappelons que les bits se lisent de droite à gauche ! Les bits 1, 4, 5 et 6 de $x$ sont à 1, donc les lampes 1, 4, 5 et 6 sont allumées et les autres lampes sont éteintes.\n", "\n", "L'état initial du jeu est 0 et l'état final est 255.\n", "\n", "La variable `exemple` est une liste dont le $k$ème élément est un entier de 8 bits qui décrit les lampes dont l'état change quand on appuie sur le bouton $k$. Pour $j\\in\\bbr 07$, si le bit $j$ est à 1, la lampe $j$ change d'état. Sinon, elle ne change pas d'état." ] }, { "cell_type": "code", "execution_count": null, "id": "3b9303ee", "metadata": {}, "outputs": [], "source": [ "exemple = [0b11000111, 0b10001010, 0b00001110, 0b00101010, 0b01111100, 0b10101000, 0b11100000, 0b10100010]\n", "print(exemple)" ] }, { "cell_type": "markdown", "id": "ae26f943", "metadata": {}, "source": [ "L'appui sur un bouton est réalisé par la fonction `appuyer`. Pour appuyer sur l'interrupteur $k$, on réalise un ou exclusif entre les bits de l'état $x$ et ceux de l'entier `exemple[k]`. L'opérateur Python `^` effectue cette opération." ] }, { "cell_type": "code", "execution_count": null, "id": "712c60dd", "metadata": {}, "outputs": [], "source": [ "def appuyer(x, k): return x ^ exemple[k]" ] }, { "cell_type": "markdown", "id": "c85611e7", "metadata": {}, "source": [ "L'approche enfantine consiste à appuyer sur des boutons au hasard. On finira bien par allumer les lampes ... La fonction `jeu_enfantin` renvoie le nombre d'appuis sur des boutons nécessaires pour aller de l'état `debut` à l'état `fin`." ] }, { "cell_type": "code", "execution_count": null, "id": "838ae352", "metadata": {}, "outputs": [], "source": [ "def jeu_enfantin(debut, fin):\n", " x = debut\n", " c = 0\n", " while x != fin:\n", " k = random.randint(0, 7)\n", " x = appuyer(x, k)\n", " c += 1\n", " return c" ] }, { "cell_type": "code", "execution_count": null, "id": "d785a49a", "metadata": {}, "outputs": [], "source": [ "jeu_enfantin(0, 255)" ] }, { "cell_type": "markdown", "id": "76124d46", "metadata": {}, "source": [ "Cette approche est **très** naïve, vu que si on appuie deux fois sur le même bouton, les actions s'annulent. Il suffit donc d'appuyer uniquement sur des boutons différents. C'est l'objet du paragraphe suivant." ] }, { "cell_type": "markdown", "id": "69de35d8", "metadata": {}, "source": [ "### 1.4 L'approche naïve" ] }, { "cell_type": "markdown", "id": "d79b3f36", "metadata": {}, "source": [ "La fonction `jeu_naif` fonctionne comme suit. Pour chaque partie $A$ de $\\bbr 07$ elle appuie sur les boutons dont le numéro appartient à $A$. S'il existe une solution, elle ne peut que réussir ... mais au bout d'un certain temps.\n", "\n", "La fonction `parties` énumère les parties d'un ensemble $E$ donné par la liste de ses éléments." ] }, { "cell_type": "code", "execution_count": null, "id": "15db6ce1", "metadata": {}, "outputs": [], "source": [ "def parties(E):\n", " if len(E) == 0: yield []\n", " else:\n", " a = E[0]\n", " E1 = E[1:]\n", " for A in parties(E1):\n", " yield A\n", " yield [a] + A" ] }, { "cell_type": "code", "execution_count": null, "id": "228bc4dd", "metadata": {}, "outputs": [], "source": [ "for A in parties([0, 1, 2, 3]):\n", " print(A, end=' ')" ] }, { "cell_type": "markdown", "id": "1850ed92", "metadata": {}, "source": [ "La fonction `jeu_naif` opère comme la fonction `jeu_tres_naif`. Elle renvoie la solution trouvée et le nombre de parties de $\\bbr 0 7$ que l'on a testées." ] }, { "cell_type": "code", "execution_count": null, "id": "fe0ef148", "metadata": {}, "outputs": [], "source": [ "def jeu_naif(debut, fin):\n", " c = 0\n", " for A in parties(list(range(8))):\n", " x = debut\n", " c += 1\n", " for k in A:\n", " x = appuyer(x, k)\n", " if x == fin: return A, c" ] }, { "cell_type": "code", "execution_count": null, "id": "f0404a4c", "metadata": {}, "outputs": [], "source": [ "jeu_naif(0, 255)" ] }, { "cell_type": "markdown", "id": "6afa53ce", "metadata": {}, "source": [ "Dans le pire des cas, l'approche naïve sur un jeu de taille $n$ teste toutes les parties de l'ensemble $\\bbr 0{n-1}$. Il y en a $2^n$, ce qui nous donne une complexité exponentielle. C'est clairement inacceptable : il va nous falloir trouver mieux." ] }, { "cell_type": "markdown", "id": "58da32db", "metadata": {}, "source": [ "### 1.5 Quelques remarques" ] }, { "cell_type": "markdown", "id": "91cb6d44-4a2a-4e13-8726-72c14053f26a", "metadata": {}, "source": [ "Comme nous l'avons vu, si nous appuyons successivement sur les boutons 0, 1, ..., 7 nous allumons toutes les lampes." ] }, { "cell_type": "code", "execution_count": null, "id": "6da8e04b-a0e2-4584-89dd-486b7a3b95c2", "metadata": {}, "outputs": [], "source": [ "x = 0\n", "for k in range(8):\n", " x = appuyer(x, k)\n", " print(x, end=' ')" ] }, { "cell_type": "markdown", "id": "2aa2c07d-0f06-4765-b0c3-ed4c2742403b", "metadata": {}, "source": [ "Gagné. Et si on appuie sur les boutons de 0 à 7 dans un ordre aléatoire ?" ] }, { "cell_type": "code", "execution_count": null, "id": "40b770f2-5e4e-4435-a3f3-57d683d50af6", "metadata": {}, "outputs": [], "source": [ "x = 0\n", "s = list(range(8))\n", "random.shuffle(s)\n", "print(s)\n", "for k in s:\n", " x = appuyer(x, k)\n", " print(x, end=' ')" ] }, { "cell_type": "markdown", "id": "ac3c4823-65af-4ed0-be5b-367c50a93f34", "metadata": {}, "source": [ "Cela ne change rien. Bien que les états intermédiaires soient différents, on gagne à chaque fois. Et qu'arrive-t-il si on modifie l'effet de l'appui sur un bouton ? Si on change l'état de départ ? L'état d'arrivée ? Et quel est le nombre minimal d'appuis nécessaires pour gagner pour un jeu donné ? Etc.\n", "\n", "**Bref, mathématisons le jeu pour mieux le comprendre et pour obtenir une solution générale.**" ] }, { "cell_type": "markdown", "id": "2d04acca", "metadata": {}, "source": [ "## 2. Algèbre linéaire" ] }, { "cell_type": "markdown", "id": "99503499-41a8-4815-9155-0e555e0889da", "metadata": {}, "source": [ "### 2.1 Un espace vectoriel" ] }, { "cell_type": "markdown", "id": "626e971e-1f7d-4c31-beb2-fabaee0eeadb", "metadata": {}, "source": [ "Soit $\\mathbb K=\\{0,1\\}$ le corps à deux éléments. Soit $E=\\mathbb K^n$, qui est un $\\mathbb K$-espace vectoriel de dimension $n$.\n", "\n", "Modélisons un état du jeu par un vecteur $x=(x_0,\\ldots,x_{n-1})\\in E$. Si $x_k=0$, la lampe $k$ est éteinte. Sinon, elle est allumée.\n", "\n", "Les appuis sur des boutons peuvent eux aussi être représentés par des vecteurs de $E$. Pour $k\\in\\bbr 0{n-1}$, soit $e_k$ le vecteur « appui sur le bouton $k$ ». Si $x\\in E$ est un état du jeu, alors $x+e_k$ est l'état du jeu après avoir appuyé sur le bouton $k$ en partant de l'état $x$. " ] }, { "cell_type": "markdown", "id": "ddd48a35", "metadata": {}, "source": [ "La famille $\\mathcal B=(e_0,\\ldots,e_{n-1})$ est de cardinal $n=\\dim E$. En supposant que $\\mathcal B$ est une base de $E$, tout vecteur $x$ de $E$ s'écrit alors de façon unique\n", "\n", "$$x=\\sum_{k=0}^{n-1} x_ke_k$$\n", "\n", "où les $x_k$ appartiennent à $\\mathbb K$. Trouver « une » solution du jeu revient à trouver les coordonnées $x_k$ du vecteur $(1,\\ldots,1)$ dans la base $\\mathcal B$. Pour terminer le jeu il suffit d'appuyer sur les boutons $k$ tels que $x_k=1$. Et l'ordre dans lequel on appuie n'a aucune importance puisque l'addition des vecteurs est commutative. Mieux, il y a unicité de la solution modulo 2. Si $x_k=0$ (resp : 1) il faut appuyer un nombre pair (resp : impair) de fois sur le bouton $k$.\n", "\n", "Nous voici donc ramenés à un problème classique d'algèbre linéaire : trouver les coordonnées $x_0,\\ldots,x_{n-1}$ du vecteur $y=(1,\\ldots, 1)$ dans la base $\\mathcal B$.\n", "\n", "Notons $\\mathcal B_0$ la base canonique de $E$. Soit $P$ la matrice de passage de $\\mathcal B_0$ à $\\mathcal B$. On a par les formules de changement de bases\n", "\n", "$$(1 \\ldots 1)^T=P(x_0\\ldots x_{n-1})^T$$\n", "\n", "Notre problème se ramène donc à la résolution du système $PX=Y$." ] }, { "cell_type": "markdown", "id": "2d0fb278", "metadata": {}, "source": [ "### 2.2 Modélisation" ] }, { "cell_type": "markdown", "id": "73139ad3", "metadata": {}, "source": [ " En identifiant les éléments de $\\mathbb K$ avec les entiers 0 et 1, la fonction $\\phi: E\\too\\bbr 0{2^n-1}$ définie par\n", "\n", "$$\\phi(x_0,\\ldots,x_{n-1})=\\sum_{k=0}^{n-1} x_k2^k$$\n", "\n", "est une bijection. Les opérations dans $E$ sont faciles à décrire via la bijection $\\phi$. Le produit par un scalaire est trivial, vu qu'il n'y a que deux scalaires, 0 et 1. L'addition des vecteurs est également très simple. Si $x,y\\in E$, on a\n", "\n", "$$\\phi(x+y)=\\sum_{k=0}^{n-1} (x_k\\oplus y_k)2^k$$\n", "\n", "où $x_k\\oplus y_k$ est une addition dans le corps $\\mathbb K$. Cette somme vaut 1 si $x_k\\ne y_k$ et 0 sinon. En d'autres termes, $x_k\\oplus y_k$ est le « ou exclusif » de $x_k$ et $y_k$. Si nous identifions $E$ avec $\\bbr 0{2^n-1}$, additionner deux vecteurs revient donc à faire un ou exclusif entre les bits des entiers correspondants. C'est précisément ce que fait l'opérateur Python `^`.\n" ] }, { "cell_type": "markdown", "id": "620e23b1", "metadata": {}, "source": [ "### 2.3 Transposition" ] }, { "cell_type": "markdown", "id": "8685de14", "metadata": {}, "source": [ "Soit $A=(A_0,\\ldots,A_{n-1})$ une liste de $n$ entiers. Supposons que ces entiers peuvent s'écrire sur $n$ bits. Ces entiers peuvent être vus comme des vecteurs de l'espace vectoriel $E=\\mathbb K^n$ : pour tout $i\\in\\bbr 0{n-1}$,\n", "\n", "$$A_i=\\sum_{j=0}^{n-1}A_{ij}2^j$$\n", "\n", "où les $A_{ij}$ appartiennent à $\\mathbb K$. La liste $A$ peut donc aussi être vue comme la matrice $(A_{ij})_{0\\le i,j\\le n-1}\\in \\mathcal M_n(\\mathbb K)$.\n", "\n", "Prenons par exemple la liste $\\mathcal L$ des vecteurs « appui sur un bouton ». Cette liste, vue comme une matrice, est la matrice des vecteurs de $\\mathcal B$ *écrits en ligne*. La matrice de passage de la base $\\mathcal B_0$ à la base $\\mathcal B$ est, quant à elle, la matrice des vecteurs de $\\mathcal B$ *écrits en colonne*. Il convient donc d'écrire une fonction qui transpose une matrice.\n", "\n", "En reprenant les notations ci-dessus, soit $B=A^T$. En interprétant $B$ comme une liste $(B_0,\\ldots,B_{n-1})$ de $n$ entiers, on a pour tout $i\\in\\bbr 0{n-1}$,\n", "\n", "$$B_i=\\sum_{j=0}^{n-1}B_{ij}2^j=\\sum_{j=0}^{n-1}A_{ji}2^j$$" ] }, { "cell_type": "markdown", "id": "2acc19fe", "metadata": {}, "source": [ "La fonction `bit` prend en paramètres deux entiers $x$ et $i$. Elle renvoie le $i$ème bit de $x$. Il suffit pour cela de décaler $x$ de $i$ bits vers la droite et de renvoyer le bit de poids faible." ] }, { "cell_type": "code", "execution_count": null, "id": "10ef6602", "metadata": {}, "outputs": [], "source": [ "def bit(x, i): return (x >> i) & 1" ] }, { "cell_type": "markdown", "id": "298177bf", "metadata": {}, "source": [ "La fonction `transp` prend en paramètre une liste $A$ d'entiers interprétée comme une matrice. Elle renvoie $A^T$, sous forme d'une liste de $n$ entiers. Remarquons que la complexité de `transp` est, en nombre d'opérations sur des entiers, $O(n^2)$." ] }, { "cell_type": "code", "execution_count": null, "id": "970f8483", "metadata": {}, "outputs": [], "source": [ "def transp(A):\n", " n = len(A)\n", " B = []\n", " for i in range(n):\n", " x = 0\n", " for j in range(n):\n", " x = (x << 1) | bit(A[n - 1 - j], i)\n", " B.append(x)\n", " return B" ] }, { "cell_type": "markdown", "id": "afa536c0", "metadata": {}, "source": [ "Voici la matrice de passage de $\\mathcal B_0$ à $\\mathcal B$." ] }, { "cell_type": "code", "execution_count": null, "id": "3b23f8ce", "metadata": {}, "outputs": [], "source": [ "P = transp(exemple)\n", "print(P)" ] }, { "cell_type": "markdown", "id": "823695c2", "metadata": {}, "source": [ "À titre de vérification, une nouvelle transposée devrait redonner la liste `regle`." ] }, { "cell_type": "code", "execution_count": null, "id": "603771dc", "metadata": {}, "outputs": [], "source": [ "print(transp(P) == exemple)" ] }, { "cell_type": "markdown", "id": "7632b315", "metadata": {}, "source": [ "## 3. Le pivot de Gauss" ] }, { "cell_type": "markdown", "id": "a2c4a28f", "metadata": {}, "source": [ "Pour trouver la solution du jeu, il suffit de résoudre un système linéaire. La façon la plus élégante de le faire est d'utiliser le pivot de Gauss. *Je vais supposer que le lecteur sait comment fonctionne cet algorithme.*\n", "\n", "Commençons par écrire quelques fonctions utiles." ] }, { "cell_type": "markdown", "id": "f61c81ea", "metadata": {}, "source": [ "### 3.1 Fonctions utiles" ] }, { "cell_type": "markdown", "id": "8a77212d", "metadata": {}, "source": [ "La fonction `eye` renvoie la matrice identité d'ordre $n$. Interprétée comme une liste d'entiers, cette matrice est\n", "\n", "$$(2^0,2^1,\\ldots, 2^{n-1})$$" ] }, { "cell_type": "code", "execution_count": null, "id": "4c640d39-7ce1-4b82-829e-d8652177a66c", "metadata": {}, "outputs": [], "source": [ "def eye(n):\n", " return [2 ** k for k in range(n)]" ] }, { "cell_type": "code", "execution_count": null, "id": "a19226e8-37c1-4ed3-a6b7-7e4e51a33ed1", "metadata": {}, "outputs": [], "source": [ "print(eye(8))" ] }, { "cell_type": "markdown", "id": "144b295a", "metadata": {}, "source": [ "Pour tester les fonctions que nous allons écrire, il sera bon de pouvoir fabriquer des exemples « à la volée ». La fonction `rand_mat` renvoie une liste de $n$ entiers aléatoires ayant au plus $n$ bits." ] }, { "cell_type": "code", "execution_count": null, "id": "95a73789", "metadata": {}, "outputs": [], "source": [ "def rand_mat(n):\n", " return [random.randint(0, 2 ** n - 1) for k in range(n)]" ] }, { "cell_type": "code", "execution_count": null, "id": "8b23b33f", "metadata": {}, "outputs": [], "source": [ "A = rand_mat(8)\n", "print(A)" ] }, { "cell_type": "markdown", "id": "d60f9c9d", "metadata": {}, "source": [ "### 3.2 Opérations sur les lignes" ] }, { "cell_type": "markdown", "id": "3cca9b10", "metadata": {}, "source": [ "La fonction `ech` échange les lignes $i_1$ et $i_2$ de la matrice $A$. Sa complexité est $O(1)$." ] }, { "cell_type": "code", "execution_count": null, "id": "aa5c9e18-beef-4164-a521-2f2aa34f181a", "metadata": {}, "outputs": [], "source": [ "def ech(A, i1, i2): A[i1], A[i2] = A[i2], A[i1]" ] }, { "cell_type": "markdown", "id": "a6cc7858", "metadata": {}, "source": [ "La fonction `add` ajoute à la ligne $i_1$ de la matrice $A$ sa ligne $i_2$. Rappelons nous que nos matrices sont à coefficients dans le corps $\\mathbb K$. L'addition s'effectue donc en faisant un ou exclusif. Sa complexité est aussi $O(1)$ (à condition que la taille de $A$ soit inférieure à la taille des entiers « machine », qui est sans doute 64)." ] }, { "cell_type": "code", "execution_count": null, "id": "655ee9de-9e21-443d-bb76-e8e787fd64b5", "metadata": {}, "outputs": [], "source": [ "def add(A, i1, i2): A[i1] = A[i1] ^ A[i2]" ] }, { "cell_type": "markdown", "id": "d53a5259", "metadata": {}, "source": [ "### 3.3 Pivoter" ] }, { "cell_type": "markdown", "id": "af0e88ef", "metadata": {}, "source": [ "La fonction `rech_pivot` prend en paramètres une matrice $A$ et un entier $k$. Elle cherche dans la colonne $k$ de $A$, parmi $A_{kk}$, $A_{(k+1)k}$, etc. un coefficient égal à 1. Elle renvoie l'indice de ligne de ce coefficient. Si elle ne trouve pas un tel coefficient, elle renvoie la taille de $A$. La complexité de cette fonction est $O(n-k)=O(n)$ où $n$ est la taille de $A$." ] }, { "cell_type": "code", "execution_count": null, "id": "5336bf81-d973-4017-8b11-d05f2e7efa51", "metadata": {}, "outputs": [], "source": [ "def rech_pivot(A, k):\n", " n = len(A)\n", " for i in range(k, n):\n", " if bit(A[i], k) == 1:\n", " return i\n", " return n" ] }, { "cell_type": "markdown", "id": "6b9f9917", "metadata": {}, "source": [ "La fonction `pivoter` prend en paramètres deux matrices $A$ et $B$, ainsi qu'un entier $k$.\n", "\n", "- Elle commence par rechercher un entier $i\\ge k$ tel que $A_{ik}=1$. Si elle n'en trouve pas, la théorie de l'algorithme du pivot de Gauss nous dit que $A$ n'est pas inversible. La fonction lève alors une exception.\n", "- La fonction échange les lignes $i$ et $k$ des matrices $A$ et $B$.\n", "- Pour tout $i\\ne k$, si $A_{ik}=1$, la fonction ajoute à la ligne $i$ de $A$ la ligne $k$ de $A$, et de même pour $B$. Ceci a pour effet d'annuler $A_{ik}$. En effet, $A_{ik}=A_{kk}=1$ et donc $A_{ik}\\land A_{kk}=0$ (le $\\land$ est un ou exclusif).\n", "\n", "Remarquons que comme nos fonctions `ech` et `add` ont une complexité en $O(1)$, la complexité de `pivoter` est $O(n)$. Dans un pivot de Gauss « classique », cette complexité serait $O(n^2)$." ] }, { "cell_type": "code", "execution_count": null, "id": "93198d98-1947-4ee3-9460-e89063a6e519", "metadata": {}, "outputs": [], "source": [ "def pivoter(A, B, k):\n", " n = len(A)\n", " i = rech_pivot(A, k)\n", " if i == n:\n", " raise Exception('Non inversible')\n", " else:\n", " ech(A, i, k)\n", " ech(B, i, k)\n", " for i in range(n):\n", " if i != k and bit(A[i], k) == 1:\n", " add(A, i, k)\n", " add(B, i, k)" ] }, { "cell_type": "markdown", "id": "ac44c5a3", "metadata": {}, "source": [ "### 3.4 Résoudre" ] }, { "cell_type": "markdown", "id": "cb8bf30c", "metadata": {}, "source": [ "La fonction `gauss` prend en paramètres deux matrices $A$ et $B$ (c'est à dire, avec nos conventions, deux listes d'entiers) de même taille. Elle résout le système $AX=B$ d'inconnue $X$. Si la matrice $A$ n'est pas inversible, une exception est levée par l'appel à `pivoter`. La complexité de `gauss` est $O(n^2)$ (à comparer avec le $O(n^3)$ du pivot classique)." ] }, { "cell_type": "code", "execution_count": null, "id": "79e31417-f54d-46a6-9b11-3bdb35b77996", "metadata": {}, "outputs": [], "source": [ "def gauss(A, B):\n", " A, B = A[:], B[:]\n", " n = len(A)\n", " for k in range(n):\n", " pivoter(A, B, k)\n", " return A, B" ] }, { "cell_type": "markdown", "id": "42bc40f4", "metadata": {}, "source": [ "Cela ne coûte rien, le pivot de Gauss permet le calcul de l'inverse d'une matrice. Ici, en $O(n^2)$." ] }, { "cell_type": "code", "execution_count": null, "id": "c7fc999b-d513-41d8-a640-1c4651d25b28", "metadata": {}, "outputs": [], "source": [ "def inverse(A):\n", " n = len(A)\n", " A1, B1 = gauss(A, eye(n))\n", " return B1" ] }, { "cell_type": "markdown", "id": "3f0b82e2", "metadata": {}, "source": [ "Testons. Comme nous prenons une matrice aléatoire, il est possible qu'une exception soit levée. Il n'y a qu'à réévaluer la cellule." ] }, { "cell_type": "code", "execution_count": null, "id": "829c06d9-9860-454e-abaa-b8065c81bd59", "metadata": {}, "outputs": [], "source": [ "try:\n", " A = rand_mat(8)\n", " B = inverse(A)\n", " print(A)\n", " print(B)\n", "except Exception:\n", " print('C\\'est raté')" ] }, { "cell_type": "markdown", "id": "61d4d2da", "metadata": {}, "source": [ "On tombe assez souvent sur des matrices non inversibles. Comment cela se fait-il ? Le cardinal de $\\mathcal M_n(\\mathbb K)$ est\n", "\n", "$$|\\mathcal M_n(\\mathbb K)|=|\\mathbb K|^{n^2}=2^{n^2}$$\n", "\n", "Pour fabriquer une matrice inversible, on crée ses colonnes $C_0,C_1,\\ldots,C_{n-1}$ en faisant en sorte que pour tout $k\\in\\bbr0{n-1}$, la colonne $C_k$ ne soit pas combinaison linéaire des colonnes $C_0,\\ldots,C_{k-1}$. Remarquons que le nombre de telles combinaisons linéaires est $2^k$.\n", "\n", "- On choisit $C_0$ non nulle : $2^n-1$ possibilités.\n", "- On choisit $C_1$ non colinéaire à la colonne 0 : $2^n-2^1$ possibilités.\n", "- On choisit $C_2$ non combinaison linéaire de $C_0$ et $C_1$ : $2^n-2^2$ possibilités.\n", "- ...\n", "- On choisit $C_k$ non combinaison linéaire de $C_0,\\ldots,C_{k-1}$ : $2^n-2^k$ possibilités.\n", "- ...\n", "- On choisit $C_{n-1}$ non combinaison linéaire de $C_0,\\ldots,C_{n-1}$ : $2^n-2^{n-1}$ possibilités.\n", "\n", "Le cardinal de $GL_n(\\mathbb K)$ est donc\n", "\n", "$$|GL_n(\\mathbb K)|=\\prod_{k=0}^{n-1}(2^n-2^k)=\\prod_{k=1}^{n}(2^n-2^{n-k})=\\prod_{k=1}^{n}2^n(1-2^{-k})$$\n", "\n", "Munissons $\\mathcal M_n(\\mathbb K)$ de la probabilité uniforme $\\prob$. La probabilité de $GL_n(\\mathbb K)$ est alors\n", "\n", "$$\\prob(GL_n(\\mathbb K))=\\frac{|GL_n(\\mathbb K)|}{|\\mathcal M_n(\\mathbb K)|}=\\prod_{k=1}^{n}\\left(1-\\frac 1{2^{k}}\\right)$$" ] }, { "cell_type": "code", "execution_count": null, "id": "4c33d8b7", "metadata": {}, "outputs": [], "source": [ "def proba_inversible(p, n):\n", " x = 1\n", " for k in range(1, n + 1):\n", " x *= 1 - 1 / (p ** k)\n", " return x" ] }, { "cell_type": "code", "execution_count": null, "id": "70ffff2e", "metadata": {}, "outputs": [], "source": [ "print(proba_inversible(2, 8))" ] }, { "cell_type": "markdown", "id": "10750865", "metadata": {}, "source": [ "Il y a moins de 30% de chances qu'une matrice de taille 8 soit inversible, d'où le commentaire que j'ai fait un peu plus haut sur la réévaluation fort possible d'une certaine cellule.\n", "\n", "**Remarque.** Le produit infini\n", "\n", "$$\\prod_{k=1}^{\\infty}\\left(1-\\frac 1{2^{k}}\\right)$$\n", "\n", "est convergent. De même, pour tout réel $x>1$, le produit infini\n", "\n", "$$\\psi(x)=\\prod_{k=1}^{\\infty}\\left(1-\\frac 1{x^{k}}\\right)$$\n", "\n", "Il y a énormément de choses à dire sur la fonction $\\psi$ mais cela nous éloignerait de notre sujet ... Le lecteur intéressé pourra se documenter sur la notion de *$q$-symbole de Pochhammer*.\n", "\n", "\n", "L'errrur commise en approchant $\\psi(2)$ par le produit pour $k$ allant de 1 à $n$ est de l'ordre de $1/2^n$. La convergence est donc relativement rapide. Remarquons que pour Python," ] }, { "cell_type": "code", "execution_count": null, "id": "88d82a33", "metadata": {}, "outputs": [], "source": [ "1 - 1 / (2 ** 53)" ] }, { "cell_type": "code", "execution_count": null, "id": "5ccc2f6b", "metadata": {}, "outputs": [], "source": [ "1 - 1 / (2 ** 54)" ] }, { "cell_type": "markdown", "id": "e11fd722", "metadata": {}, "source": [ "Inutile, donc, de prendre $n\\ge 54$. Nous ne ferions que des multiplications par 1 dans la fonction `proba_inversible`. Une bonne valeur de $\\psi(2)$ est donc sans doute" ] }, { "cell_type": "code", "execution_count": null, "id": "080c0d83", "metadata": {}, "outputs": [], "source": [ "print(proba_inversible(2, 53))" ] }, { "cell_type": "markdown", "id": "a514ca76", "metadata": {}, "source": [ "### 3.5 Vérifications" ] }, { "cell_type": "markdown", "id": "943122a0", "metadata": {}, "source": [ "La fonction `mul` effectue le produit des matrices $A$ et $B$, supposées carrées. Rappelons nous que le corps de base est $\\mathbb K$. Les additions sont des « ou exclusifs », et les multiplications des « et »." ] }, { "cell_type": "code", "execution_count": null, "id": "7bfce56b-f8b6-4744-a6d9-f80e839a066f", "metadata": {}, "outputs": [], "source": [ "def mul(A, B):\n", " n = len(A)\n", " C = n * [0]\n", " for i in range(n):\n", " for j in range(n):\n", " s = 0\n", " for k in range(n):\n", " s = s ^ (bit(A[i], k) & bit(B[k], j))\n", " C[i] += s << j\n", " return C" ] }, { "cell_type": "markdown", "id": "bf93699a", "metadata": {}, "source": [ "La fonction `random_inversible` renvoie un triplet $(A,B,c)$ où $A\\in GL_n(\\mathbb K)$, $B=A^{-1}$ et $c$ est le nombre d'essais effectués pour obtenir le résultat. " ] }, { "cell_type": "code", "execution_count": null, "id": "3fb36ff9", "metadata": {}, "outputs": [], "source": [ "def random_inversible(n):\n", " c = 0\n", " while True:\n", " try:\n", " c += 1\n", " A = rand_mat(n)\n", " B = inverse(A)\n", " return A, B, c\n", " except Exception: continue" ] }, { "cell_type": "markdown", "id": "c636be19", "metadata": {}, "source": [ "Testons. Prenons une matrice inversible $A$, la matrice $B$ qui est censée être son inverse, et calculons le produit $AB$. Celui-ci devrait être égal à $I_n$." ] }, { "cell_type": "code", "execution_count": null, "id": "638fe1f3", "metadata": {}, "outputs": [], "source": [ "A, B, c = random_inversible(8)\n", "print(A)\n", "print(B)\n", "print(c)\n", "print(mul(A, B) == eye(8))" ] }, { "cell_type": "markdown", "id": "443d6a53", "metadata": {}, "source": [ "## 4. Retour au jeu de l'électricien fou" ] }, { "cell_type": "markdown", "id": "9966a33d", "metadata": {}, "source": [ "### 4.1 Notre jeu favori" ] }, { "cell_type": "markdown", "id": "6b4ee8d7", "metadata": {}, "source": [ "Revenons à notre jeu favori. Rappelons la matrice de passage de la base $\\mathcal B_0$ à la base $\\mathcal B$." ] }, { "cell_type": "code", "execution_count": null, "id": "f1b17d5a-28e8-43ab-96c8-66d5a08a254f", "metadata": {}, "outputs": [], "source": [ "P = transp(exemple)\n", "print(P)" ] }, { "cell_type": "markdown", "id": "f515018a", "metadata": {}, "source": [ "Au fait, $\\mathcal B$ est-elle une base de $E$ ? C'est le cas si et seulement si $P$ est inversible." ] }, { "cell_type": "code", "execution_count": null, "id": "f2900b84-2e2a-4b1d-92cc-c505bbaf2331", "metadata": {}, "outputs": [], "source": [ "Q = inverse(P)\n", "print(Q)" ] }, { "cell_type": "markdown", "id": "983b701a", "metadata": {}, "source": [ "Oui, $\\mathcal B$ est une base. Le vecteur $(1,\\ldots,1)$ s'écrit donc de façon unique comme combinaison des éléments de $\\mathcal B$. Voici la matrice de ce vecteur dans la base $\\mathcal B_0$." ] }, { "cell_type": "code", "execution_count": null, "id": "a909a0e6-0ff4-408b-8626-482029963334", "metadata": {}, "outputs": [], "source": [ "Y = 8 * [1]\n", "print(Y)" ] }, { "cell_type": "markdown", "id": "9f669a0a", "metadata": {}, "source": [ "Le produit $X=P^{-1}Y$ est la solution du jeu." ] }, { "cell_type": "code", "execution_count": null, "id": "d297a682-569a-4e58-9f26-e44de66f88ae", "metadata": {}, "outputs": [], "source": [ "print(mul(Q, Y))" ] }, { "cell_type": "markdown", "id": "ffc1077a", "metadata": {}, "source": [ "Nous obtenons ce que nous savions déjà depuis longtemps : pour terminer le jeu il suffit d'appuyer une fois sur chacun des boutons.\n", "\n", "Remarquons que nous pouvions utiliser le pivot de Gauss directement sans passer par $P^{-1}$ :" ] }, { "cell_type": "code", "execution_count": null, "id": "a17a72c0", "metadata": {}, "outputs": [], "source": [ "I, X = gauss(P, Y)\n", "print(I)\n", "print(X)" ] }, { "cell_type": "markdown", "id": "2fe0a48a", "metadata": {}, "source": [ "Ultime vérification, on doit avoir $PX=(1\\ldots 1)^T$." ] }, { "cell_type": "code", "execution_count": null, "id": "bf175e3f", "metadata": {}, "outputs": [], "source": [ "mul(P, X)" ] }, { "cell_type": "markdown", "id": "02e180e3", "metadata": {}, "source": [ "### 4.2 Jeux aléatoires" ] }, { "cell_type": "markdown", "id": "dbea4262", "metadata": {}, "source": [ "Nous avons maintenant tout ce qu'il nous faut pour créer et résoudre des jeux aléatoires. Le jeu auquel nous avons joué était caractérisé par la liste `exemple`. Pour créer un jeu aléatoire, il suffit de tirer la règle au hasard. La seule condition imposée est que la matrice correspondante soit inversible, ce qui assure l'existence et l'unicité de la solution (modulo 2).\n", "\n", "La fonction `random_jeu` renvoie un jeu aléatoire de taille $n$. Cette fonction est quasiment la même que `random_inversible`. La seule différence est qu'on impose à la matrice renvoyée d'avoir tous ses coefficients diagonaux égaux à 1 (pour que l'appui sur le bouton $k$ modifie l'état de la lampe $k$). Ceci est réalisé grâce à l'opérateur Python `|` qui effectue un ou *inclusif* sur les bits de ses arguments." ] }, { "cell_type": "code", "execution_count": null, "id": "1b650be0", "metadata": {}, "outputs": [], "source": [ "def random_jeu(n):\n", " while True:\n", " try:\n", " A = rand_mat(n)\n", " for i in range(n):\n", " A[i] = A[i] | (2 ** i)\n", " B = inverse(A)\n", " return transp(A)\n", " except Exception: continue" ] }, { "cell_type": "code", "execution_count": null, "id": "45dab4d9", "metadata": {}, "outputs": [], "source": [ "J = random_jeu(8)\n", "print(J)" ] }, { "cell_type": "markdown", "id": "f029befd", "metadata": {}, "source": [ "Ceci n'est pas très explicite. Écrivons une fonction qui affiche une description du jeu." ] }, { "cell_type": "code", "execution_count": null, "id": "95be8c4b", "metadata": {}, "outputs": [], "source": [ "def decrire(J):\n", " n = len(J)\n", " for k in range(n):\n", " s = str(k) + \" -> \"\n", " bs = [bit(J[k], i) for i in range(n)]\n", " for i in range(n):\n", " if bs[i] == 1:\n", " s += str(i) + ', '\n", " print(s[:-2])" ] }, { "cell_type": "markdown", "id": "672b35b0", "metadata": {}, "source": [ "Testons sur notre jeu favori." ] }, { "cell_type": "code", "execution_count": null, "id": "4617323c", "metadata": {}, "outputs": [], "source": [ "J = exemple\n", "decrire(J)" ] }, { "cell_type": "markdown", "id": "7dfcad2c", "metadata": {}, "source": [ "Résoudre un jeu est immédiat. On « transpose » le jeu et on appelle `gauss`." ] }, { "cell_type": "code", "execution_count": null, "id": "fb34e6c6", "metadata": {}, "outputs": [], "source": [ "def resoudre(J):\n", " n = len(J)\n", " P = transp(J)\n", " Y = n * [1]\n", " I, X = gauss(P, Y)\n", " return X" ] }, { "cell_type": "markdown", "id": "8cc61fd1", "metadata": {}, "source": [ "### 4.3 Quelques tests" ] }, { "cell_type": "markdown", "id": "82e8b3a6", "metadata": {}, "source": [ "Premier test, sur notre jeu favori." ] }, { "cell_type": "code", "execution_count": null, "id": "9f00a837", "metadata": {}, "outputs": [], "source": [ "J = exemple\n", "decrire(J)\n", "X = resoudre(J)\n", "print('\\nSolution :', X)" ] }, { "cell_type": "markdown", "id": "b922cd83", "metadata": {}, "source": [ "Essayons maintenant le « jeu trivial » : l'appui sur le bouton $k$ change l'état de la lampe $k$, et seulement elle. Ce serait le cas d'une installation électrique effectuée par un électricien normal. Sans être un génie, on peut trouver la solution du jeu sans calculs :-)." ] }, { "cell_type": "code", "execution_count": null, "id": "c5360e4a", "metadata": {}, "outputs": [], "source": [ "J = eye(8)\n", "decrire(J)\n", "X = resoudre(J)\n", "print('\\nSolution :', X)" ] }, { "cell_type": "markdown", "id": "d0f3b7d0", "metadata": {}, "source": [ "Prenons un jeu aléatoire de taille 20." ] }, { "cell_type": "code", "execution_count": null, "id": "7d549a0d", "metadata": {}, "outputs": [], "source": [ "J = random_jeu(20)\n", "decrire(J)\n", "X = resoudre(J)\n", "print('\\nSolution :', X)" ] }, { "cell_type": "markdown", "id": "dae3a31a", "metadata": {}, "source": [ "La création et la résolution d'un jeu de taille $n$ utilisent toutes les deux l'algorithme du pivot de Gauss dont la complexité est miraculeusement pour nous $O(n^2)$. On peut donc espérer pour voir créer et résoudre sans difficulté un jeu de taille 1000." ] }, { "cell_type": "markdown", "id": "fe88772c", "metadata": {}, "source": [ "Créons le jeu. Ici, tout dépend de la chance puisqu'il faut créer une matrice inversible de taille 1000. Quelques secondes suffisent pourvu qu'on ne soit pas malchanceux." ] }, { "cell_type": "code", "execution_count": null, "id": "7cd348f2", "metadata": {}, "outputs": [], "source": [ "J = random_jeu(1000)" ] }, { "cell_type": "markdown", "id": "28db84a9", "metadata": {}, "source": [ "Résolvons le jeu. J'ai mis `print(X)` en commentaire parce que le résultat n'est pas vraiment passionnant." ] }, { "cell_type": "code", "execution_count": null, "id": "1a2bbe84", "metadata": {}, "outputs": [], "source": [ "t1 = time.time()\n", "X = resoudre(J)\n", "t2 = time.time()\n", "print(t2 - t1)\n", "# print(X)" ] }, { "cell_type": "markdown", "id": "cb06f35f", "metadata": {}, "source": [ "Sur mon vieil ordinateur de bureau, il faut 1.3 seconde. Sur mon portable, il faut environ 0.3 seconde. Remarquons la confirmation éclatante du fait que notre pivot de Gauss a ici la complexité inespérée $O(n^2)$. Si cette complexité était $O(n^3)$ cela aurait signifié que Python peut effectuer sur mon portable $1000^3$, c'est à dire 1 milliard, d'opérations en 0.3 seconde. J'adorerais ..." ] }, { "cell_type": "markdown", "id": "57946564", "metadata": {}, "source": [ "### 4.4 Représentation graphique" ] }, { "cell_type": "markdown", "id": "8bfd93a7", "metadata": {}, "source": [ "Terminons ce notebook en affichant graphiquement la solution d'un jeu. La fonction `plot_solution` prend en paramètre un jeu $J$. Si la solution du jeu comporte $c$ appuis sur des boutons, on affiche un grapique de $c+1$ lignes d'ordonnées 0, 1, ..., $c$. La ligne 0 est entièrement noire (lampes éteintes). Pour $i\\in\\bbr 1c$, la ligne $i$ représente l'état des lampes après appui sur le $i$ème bouton de la solution. En noir, les lampes éteintes. En blanc, les lampes allumées. La ligne $c$ est entièrement blanche (lampes allumées)." ] }, { "cell_type": "code", "execution_count": null, "id": "4d09f139", "metadata": {}, "outputs": [], "source": [ "def plot_solution(J, lines=True):\n", " n = len(J)\n", " Sol = resoudre(J)\n", " A = [n * [0]]\n", " x = 0\n", " c = 0\n", " for i in range(n):\n", " if Sol[i] == 1:\n", " c += 1\n", " x = x ^ J[i]\n", " A.append([bit(x, k) for k in range(n)])\n", " print('Nombre de coups :', c)\n", " plt.imshow(A, cmap='gray', interpolation='none', extent=(-0.5, n - 0.5, -0.5, c + 0.5), origin='lower')\n", " if lines:\n", " for i in range(c + 1):\n", " plt.plot([-0.5, n - 0.5], [i - 0.5, i - 0.5], 'k', lw=0.25)\n", " for i in range(n + 1):\n", " plt.plot([i - 0.5, i - 0.5], [-0.5, c + 0.5], 'k', lw=0.25)" ] }, { "cell_type": "markdown", "id": "6990308a", "metadata": {}, "source": [ "Voici la solution de notre jeu favori" ] }, { "cell_type": "code", "execution_count": null, "id": "0a1b864f", "metadata": {}, "outputs": [], "source": [ "plot_solution(exemple, True)" ] }, { "cell_type": "markdown", "id": "b593b891", "metadata": {}, "source": [ "La solution du jeu trivial va de soi. On allume les lampes les unes après les autres." ] }, { "cell_type": "code", "execution_count": null, "id": "f4525ce1", "metadata": {}, "outputs": [], "source": [ "plot_solution(eye(8), True)" ] }, { "cell_type": "markdown", "id": "f1d7b1f0", "metadata": {}, "source": [ "Un jeu aléatoire de taille 50 ?" ] }, { "cell_type": "code", "execution_count": null, "id": "8455099e", "metadata": {}, "outputs": [], "source": [ "plot_solution(random_jeu(50), True)\n", "plt.savefig('fig01.png', bbox_inches='tight')" ] }, { "cell_type": "markdown", "id": "bfd5883b", "metadata": {}, "source": [ "Pour fêter la fondation de Rome, terminons par un jeu aléatoire de taille 753." ] }, { "cell_type": "code", "execution_count": null, "id": "718925ce", "metadata": {}, "outputs": [], "source": [ "plot_solution(random_jeu(753), False)\n", "plt.savefig('fig01.png', bbox_inches='tight')" ] }, { "cell_type": "markdown", "id": "868fc912", "metadata": {}, "source": [ "Quand on regarde l'aspect *apparemment* chaotique de ce graphique, on se dit qu'arriver à allumer les lampes manuellement en appuyant physiquement sur les boutons aurait été assez délicat ..." ] }, { "cell_type": "code", "execution_count": null, "id": "f065ece1", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.8" } }, "nbformat": 4, "nbformat_minor": 5 }