L’algorithme pour miner le bitcoin en Python

Cet article décrit une implémentation en python du minage du bitcoin qui s’appuie sur un algorithme basé sur un double hash SHA-256.

bitcoin python algorithme miner minage

Introduction – Principe de l’agorithme de minage du bitcoin

Les mineurs du réseau bitcoin doivent rechercher le nonce qui est un un nombre de 32 bits. Le mineur va tester successivement plusieurs NONCE (1,2,3 ….10^32-1), pour chacun des nonce il crée l’entête suivante et le hasher 2 fois avec une fonction de hachage SHA-256 bits.

FieldDescriptionSize
versionVersion 4
Hash du bloc précédent256-bit hash du block précédent32
Merkle rootIl s’agit d’un hash sur les données du bloc. Il est fournit au mineur et il contient un résumé des transactions qui sont contenues dans le bloc. 32
timeUn timestamp numérique qui représente le nombre de seconde depuis 1970-01-01T00:00 UTC4
bitsLa cible actuelle (Current target) en format compacté4
nonce32-bit number (starts at 0)4

Une fois le hash obtenu le mineur doit ensuite vérifier que le hash obtenu est inférieur au facteur de difficulté cible du bloc. Si le hash obtenu est supérieur alors le nonce n’est pas le bon il faut en tester un autre.

Exemple sur le bloc 671712

Si vous utilisez un explotateur de blochain bitoin (par exemple blocstream info), si on prends par exemple le bloc 671712 :

https://blockstream.info/block/000000000000000000062a949bc297739a12e639ba9e2107638b469afe11d0f8?expand

bitcoin python algorithme miner minage

Dans ce cas voici un algorithme en python qui permet de miner ce bloc :

Dans cette simulation j’affiche le header et le hash calculé ainsi que le hash rate.

Le nonce a trouver pour le bloc 671712 était 4107802144

Soit en hexa : 0xf4d81620

Cette algorithme démarre avec un nonce = 4107802144 – 400 nous allons faire comme si on était à très proche de trouver le bloc (il manque 400 double hash à effectuer pour trouver le bloc) :

import hashlib
from hashlib import sha256
import time
import struct
import binascii
import datetime
from binascii import unhexlify, hexlify
from dateutil import parser
from datetime import datetime
from datetime import timedelta 

nontrouve = True
dtprec = datetime.now()
inonc = 4107802134 - 400 #Starting 400 before the good nonce
resultat = []

while(nontrouve):
    inonc +=1
    if(inonc%50==0):
        print(str(round(timedelta(seconds=1)/(datetime.now() - dtprec))) + ' H/s')
    dtprec = datetime.now()
    header_hex = (binascii.hexlify(struct.Struct('<L').pack(int('0x2fffe000',16))).decode()  + 
     binascii.hexlify(binascii.unhexlify('000000000000000000078908d256fa7a9f97b2e1ea532fb1ce45ee4bf050d221')[::-1]).decode()+
     binascii.hexlify(binascii.unhexlify('c504fc3a406f11c7c5b598da7f50916f4e298041e6f9b91535a80db113af109a')[::-1]).decode() +
     binascii.hexlify(struct.Struct('<L').pack(int(hex(int(parser.parse('2021-02-22 15:14:22 GMT +1').timestamp())-3600),16))).decode() +
     binascii.hexlify(struct.Struct('<L').pack(int("0x170cf4e3",16))).decode() + 
     binascii.hexlify(struct.Struct('<L').pack(int(hex(inonc),16))).decode()) 
    header_bin = unhexlify(header_hex)
    dt1 = datetime.now().strftime("%H:%M:%S.%f")
    hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()
    hexlify(hash).decode("utf-8")
    hexlify(hash[::-1]).decode("utf-8")
    hash=hexlify(hash[::-1]).decode("utf-8") 
    resultat.append([round(int(hash,16)/10**65)])
    
    MAX_TARGET = int("00000000FFFF0000000000000000000000000000000000000000000000000000", 16)           
    Difficulty = 21724134900047.27                     
    target = int(MAX_TARGET / Difficulty)
    target32 = '{:0>64x}'.format(target)    
    if(int(hash,16) < int(target32,16)):
        print('###########BLOC MINED###################')
        print('HEADER=' + header_hex)
        print('HASH=' + hash)
        print('NONCE=' + str(inonc))
        print('NONCE (hex)=' + hex(inonc))
        print('###########BLOC MINED###################')
        break

La sortie est la suivante :

1149 H/s
4405 H/s
4115 H/s
1534 H/s
3831 H/s
2392 H/s
4386 H/s
3165 H/s
###########BLOC MINED###################
HEADER=00e0ff2f21d250f04bee45ceb12f53eae1b2979f7afa56d20889070000000000000000009a10af13b10da83515b9f9e64180294e6f91507fda98b5c5c7116f403afc04c53ebc3360e3f40c172016d8f4
HASH=000000000000000000062a949bc297739a12e639ba9e2107638b469afe11d0f8
NONCE=4107802144
NONCE (hex)=0xf4d81620
###########BLOC MINED###################

Lien externe – minage de bitcoin en python

https://en.bitcoin.it/wiki/Block_hashing_algorithm

Lien interne

http://128mots.com/index.php/2020/03/30/construire-une-application-decentralisee-full-stack-pas-a-pas-ethereum-blockchain-dapp-en-plus-de-128-mots-partie-1/

Levenshtein Python Implémentation algo Wagner & Fischer

Voici l’implémentation en python de l’algorithme de Wagner & Fischer (Wagner-Fischer). Il permet de calculer la distance de Levenshtein (distance entre deux chaines de caractères).

Wagner python Levenshtein python Voici l'implémentation en python de l'algorithme de Wagner & Fischer (Wagner-Fischer) qui permet de calculer la distance de Levenshtein.

Premièrement le but de l’algorithme est de trouver le coût minimal. Coût minimal pour transformer une chaîne en une autre. Alors une fonction récursive permet de retourner le nombre minimal de transformation. Et pour transformer une sous-chaine de A avec n caractères en une sous-chaine de B avec le même nombre de caractères. La solution est donnée. Il faut calculer la distance entre les 2 lettres à la même position dans la chaine A et B. Alors Soit les lettres et la lettre précédentes sont identiques. Soit il y a une différence et dans ce cas on calcule 3 côuts. Alors le premier est de supprimer une lettre le la chaine A. Et d’insérer une lettre dans la chaine A pour substituer une lettre de la chaine A. Alors On peut alors trouver le cout minimal.

import numpy as np

def levenshtein(chaine1, chaine2):
    taille_chaine1 = len(chaine1) + 1
    taille_chaine2 = len(chaine2) + 1
    levenshtein_matrix = np.zeros ((taille_chaine1, taille_chaine2))
    for x in range(taille_chaine1):
        levenshtein_matrix [x, 0] = x
    for y in range(taille_chaine2):
        levenshtein_matrix [0, y] = y

    for x in range(1, taille_chaine1):
        for y in range(1, taille_chaine2):
            if chaine1[x-1] == chaine2[y-1]:
                levenshtein_matrix [x,y] = min(
                    levenshtein_matrix[x-1, y] + 1,
                    levenshtein_matrix[x-1, y-1],
                    levenshtein_matrix[x, y-1] + 1
                )
            else:
                levenshtein_matrix [x,y] = min(
                    levenshtein_matrix[x-1,y] + 1,
                    levenshtein_matrix[x-1,y-1] + 1,
                    levenshtein_matrix[x,y-1] + 1
                )
    return (levenshtein_matrix[taille_chaine1 - 1, taille_chaine2 - 1])

print("distance de levenshtein = " + str(levenshtein("Lorem ipsum dolor sit amet", "Laram zpsam dilir siy amot")))

Pour calculer la distance de Levenshtein avec un algorithme non récursif. On utilise une matrice qui contient les distances de Levenshtein. Alors Ce sont les distances entre tous les préfixes de la première chaîne et tous les préfixes de la seconde chaîne de caractères.

Aussi on peut calculer dynamiquement les valeurs dans cette matrice. La dernière valeur calculée sera la distance de Levenshtein entre les deux chaînes entières.

Enfin il y a de nombreux cas d’utilisation de la distance de Levenshtein. La distance de Levenshtein est utilisée dans des domaines. La linguistique informatique, la biologie moléculaire. Et encore la bioinformatique, le machine learning. Également le deep learning, l’analyse de l’ADN. De plus, un programme qui fait de la vérification orthographique utilise par exemple la distance de Levenshtein.

Liens sur l’algorithme de Wagner & Fischer (Wagner-Fischer) et la distance de Levenshtein en Python ou d’autre langage :

https://graal.hypotheses.org/tag/algorithme-de-wagner-fischer

https://fr.wikipedia.org/wiki/Algorithme_de_Wagner-Fischer

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein

https://medium.com/@sddkal/wagner-fischer-algorithm-be0d96893f6d

https://www.python-course.eu/levenshtein_distance.php

Liens internes sur les algorithmes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/graphes/

Algorithme Quantique – algorithme de tri quantique

Dans cet article je vous propose un algorithme de tri quantique qui permet de trier une liste d’entier codés sur deux qubits. Cet algorithme peut être utilisé et peut servir de base pour résoudre des problèmes de tri sur une liste non triée d’entiers.

Introduction

Nous considérons le problème suivant : Étant donné une liste de quatre entiers compris entre 0 et 3 strictement différents, trier la liste :

Figure 1 : Problem to solve with Quantum sorting algorithm

Un algorithme de tri classique comme par exemple le tri fusion permet de résoudre le problème, voir plus en détail mon article sur le sujet :

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites.

Quelques concepts d’algorithme quantique

Je rappelle ici quelques concepts que nous allons utiliser dans notre algorithme de tri quantique, aussi je vous conseille de consulter le site IBM Qiskit pour en savoir plus https://qiskit.org/textbook/what-is-quantum.html et le très bon livre « Programming Quantum Computers: Essential Algorithms and Code Samples »de Eric R. Johnston , Nic Harrigan , Mercedes Gimeno-Segovia :

Circuits

Le principe en algorithme quantique est de manipuler des qubits, le processus peut être représenté sous forme de circuit (entrées à gauche, sortie à droite). Nous pouvons effectuer différentes opérations au moyen de portes quantiques (qui agissent sur les qubits de manière similaire en algorithme classique aux portes logiques comme ET, OU, OU Exclusif …).

Dans cet article je vais m’appuyer sur Qiskit qui est le framework IBM pour l’informatique quantique.

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_qubit = QuantumRegister(2, 'qubit')
creg_classic = ClassicalRegister(2, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)

circuit.reset(qreg_qubit[0])
circuit.reset(qreg_qubit[1])
circuit.x(qreg_qubit[0])
circuit.measure(qreg_qubit[0], creg_classic[0])
circuit.measure(qreg_qubit[1], creg_classic[1])

Dans ce premier algorithme on initialise un registre quantique à l’état |01> . On mesure dans un registre classique à 2 bits l’état quantique d’un registre quantique de 2 qubits. Le circuit peut être dessiné au moyen de l’instruction circuit.draw() ou via Circuit Composer de IBM Quantum Experience : https://quantum-computing.ibm.com/

Etat quantique d’un qubit seul :

L’état d’un qubit peut s’exprimer sous la forme d’un vecteur d’état si on passe en forme trigonométrique et exponentielle on a avec θ and ϕ qui sont des nombres réels :

    \[|q\rangle = \cos{(\tfrac{\theta}{2})}|0\rangle + e^{i\phi}\sin{\tfrac{\theta}{2}}|1\rangle\]

Avec alpha et beta qui sont des nombres complexes (c’est à dire une partie réelle et imaginaire) dans ce cas il existe la relation (rappel mathématique sur les nombres complexes : https://www.maths-cours.fr/cours/nombres-complexes-geometrie/) :

    \[|\psi\rangle = \alpha|0\rangle + \beta|1\rangle\]

    \[\sqrt{|\alpha|^2 + |\beta|^2} = 1\]

Ainsi si on mesure un qubit q on a :

    \[|q\rangle = \alpha|0\rangle + \beta|1\rangle\]

C’est à dire qu’il existe une probabilité de mesurer le qubit dans l’état |0> et une probabilité de mesurer le qubit dans l’état |1>. La mesure d’un qubit révèle si celui-ci est dans l’état 1 ou dans l’état 0, en général la mesure est placée en fin de circuit car elle affecte l’état du qubit en conséquence.

Portes quantiques

Voici quelques portes quantiques à connaitre et que nous allons utiliser dans l’algorithme de tri quantique :

Porte X (Pauli-X) :

La porte X permet de retourner l’état du qubit sans modifier la phase :

    \[X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = |0\rangle\langle1| + |1\rangle\langle0|\]

<

Voir l’exemple ci-dessus avec l’utilisation de qiskit.

Porte Y (Pauli-Y) :

La porte de pauli Y permet de retourner la phase et l’état du qubit en même temps :

Exemple si on considère ici l’état initialisé |0> du qubit et sa phase de 0, il y a alors 100% de chance de mesurer l’état |0>.

L’application de la porte quantique Y a l’effet suivant sur l’état et la phase du qubit (voir la sphère de bloch) :

Il y a alors 100% de chance de mesurer l’état 1 et la phase se retrouve inversée (voir la sphère de bloch ci-dessus)

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_qubit = QuantumRegister(1, 'qubit')
creg_classic = ClassicalRegister(1, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)

circuit.reset(qreg_qubit[0])
circuit.y(qreg_qubit[0])
circuit.measure(qreg_qubit[0], creg_classic[0])

Porte Z (Pauli-Z) :

La porte Z est utilisée pour retourner uniquement la phase et non l’état du qubit.

A noter que les portes Y et Z peuvent être représentées par les matrices suivantes :

    \[Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} \quad\quad\quad\quad Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\]

    \[Y = -i|0\rangle\langle1| + i|1\rangle\langle0| \quad\quad Z = |0\rangle\langle0| - |1\rangle\langle1|\]

Voir : https://qiskit.org/textbook/ch-states/single-qubit-gates.html

Porte de Hadamard

La porte Hadamard (porte H) est une porte quantique importante qui permet de créer une superposition de | 0⟩ et | 1⟩.

La matrice de cette porte est :

    \[H = \tfrac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\]

Porte de SWAP

Une porte SWAP permet d’échange l’état de deux qubits :

Exemple SWAP de l’état | 1⟩ du qubit 0 vers le qbit 2

Et SWAP de l’état | 0⟩ du qubit 1 vers le qbit 2

En Python avec le framework Qiskit on a :

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_qubit = QuantumRegister(3, 'qubit')
creg_classic = ClassicalRegister(1, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)

circuit.reset(qreg_qubit[0])
circuit.reset(qreg_qubit[1])
circuit.reset(qreg_qubit[2])
circuit.x(qreg_qubit[0])
circuit.swap(qreg_qubit[1], qreg_qubit[2])
circuit.measure(qreg_qubit[2], creg_classic[0])

Porte de Toffoli

La porte quantique Toffoli est à trois qubits (deux commandes et une cible).
Il effectue un retournement de phase (porte quantique X sur la cible) uniquement si les deux contrôles sont dans l’état | 1⟩.
Un Toffoli est équivalent à une porte NON contrôlée (on l’appelle aussi la porte CCX).

Exemple ci-dessous avec 2 qubits de commande en état | 1⟩ on a alors 100% de chance de mesurer l’état | 1⟩ sur le qubit cible de la porte de Toffoli qui était au départ initialisé à l’état | 0⟩ (soit un retournement de l’état).

Exemple ci-dessous dans le cas inverse (on a alors 0% de chance de mesurer l’état | 1⟩ soit 100% de chance de mesurer l’état | 0⟩):

Porte classique porte ET, porte OU équivalence en porte quantique

On voit ici comment combiner des porte pour créer un comportement équivalent à ce qu’on a l’habitude d’utiliser en circuit classique.

Porte ET :

A partir de Qbit a et b et d’un qubit avec une initialisation forcée à l’état | 0⟩ on peut obtenir l’opération a ET b en utilisant une porte quantique de Toffoli et une pote SWAP.

Le circuit suivant effectue un classique ET sur un algorithme quantique

Il faut noter qu’à la fin de ce circuit on retrouve l’état A ET B sur le qubit B l’état du qubit B se trouve au final sur le qubit C.

Le code en python équivalent est le suivant :

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_a = QuantumRegister(1, 'a')
qreg_b = QuantumRegister(1, 'b')
qreg_c = QuantumRegister(1, 'c')
creg_aANDb = ClassicalRegister(1, 'aANDb')
creg_aState = ClassicalRegister(1, 'aState')
creg_bState = ClassicalRegister(1, 'bState')
circuit = QuantumCircuit(qreg_a, qreg_b, qreg_c, creg_aANDb, creg_aState, creg_bState)

circuit.reset(qreg_c[0])
circuit.ccx(qreg_a[0], qreg_b[0], qreg_c[0])
circuit.swap(qreg_b[0], qreg_c[0])
circuit.measure(qreg_b[0], creg_aANDb[0])
circuit.measure(qreg_a[0], creg_aState[0])
circuit.measure(qreg_c[0], creg_bState[0])

L’équivalent de ce code en assembleur OpenQASM est :

OPENQASM 2.0;
include "qelib1.inc";

qreg a[1];
qreg b[1];
qreg c[1];
creg aANDb[1];
creg aState[1];
creg bState[1];

reset c[0];
ccx a[0],b[0],c[0];
swap b[0],c[0];
measure b[0] -> aANDb[0];
measure a[0] -> aState[0];
measure c[0] -> bState[0];

Nous utiliserons cette porte pour effectuer notre tri quantique de liste, voici quelques tests :

Pour | 0⟩ ET | 0⟩ vous avez | 0⟩ sur le qubit B :

Pour | 0⟩ ET | 1⟩ vous avez | 0⟩ sur le qubit B :

Pour | 1⟩ ET | 0⟩ vous avez | 0⟩ sur le qubit B :

Enfin pour | 1⟩ ET | 1⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :

Porte OU :

Pour réaliser une porte OU on combine 4 portes quantiques X, une porte de Toffoli et une porte quantique SWAP, également l’état de C doit être initialisé à l’état | 1> :

Le code pour cette porte en Qiskit :

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_a = QuantumRegister(1, 'a')
qreg_b = QuantumRegister(1, 'b')
qreg_c = QuantumRegister(1, 'c')
creg_aORb = ClassicalRegister(1, 'aORb')
creg_aState = ClassicalRegister(1, 'aState')
creg_bState = ClassicalRegister(1, 'bState')
circuit = QuantumCircuit(qreg_a, qreg_b, qreg_c, creg_aORb, creg_aState, creg_bState)

circuit.reset(qreg_a[0])
circuit.reset(qreg_b[0])
circuit.x(qreg_b[0])
circuit.x(qreg_c[0])
circuit.x(qreg_a[0])
circuit.ccx(qreg_a[0], qreg_b[0], qreg_c[0])
circuit.x(qreg_a[0])
circuit.x(qreg_b[0])
circuit.swap(qreg_b[0], qreg_c[0])
circuit.measure(qreg_b[0], creg_aORb[0])
circuit.measure(qreg_a[0], creg_aState[0])
circuit.measure(qreg_c[0], creg_bState[0])

en OpenQASM :

OPENQASM 2.0;
include "qelib1.inc";

qreg a[1];
qreg b[1];
qreg c[1];
creg aORb[1];
creg aState[1];
creg bState[1];

reset a[0];
reset b[0];
x b[0];
x c[0];
x a[0];
ccx a[0],b[0],c[0];
x a[0];
x b[0];
swap b[0],c[0];
measure b[0] -> aORb[0];
measure a[0] -> aState[0];
measure c[0] -> bState[0];

Si on teste on obtient bien une porte OU :

Ici pour | 0⟩ OU | 0⟩ vous avez bien | 0⟩ sur le qubit B avec une probabilité de 100% :

Ici pour | 0⟩ OU | 1⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :

Pour | 1⟩ OU | 0⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :

Finalement pour | 1⟩ OU | 1⟩ vous avez bien | 1⟩ sur le qubit B avec une probabilité de 100% :

Algorithme de tri quantique

Pour résoudre ce problème nous allons créer tout d’abord un circuit quantique qui permet de mesurer si un chiffre est inférieur à un autre, pour cela l’intuition est de se baser sur un circuit similaire à un circuit classique de comparaison de magnitude à 2 bits.

Comparateur de magnitude quantique :

On considère un chiffre A stocké dans un registre à 2 qubits (A0, A1) et un chiffre B stocké dans un autre registre (B0,B1) :

Voir le lien : https://www.electronics-tutorials.ws/combination/comb_8.html

Pour savoir si A > B avec 2 registre de 2 Qubits il faut appliquer l’équation :

A> B  =  (A_{1}\overline{B_{1}})+((A_{1}A_{0}+A_{0}\overline{B_{1}})\overline{B_{0}})

Le circuit équivalent pour créer cela est :

Ici dans l’exemple les 2 bits comparés par ce circuit sont dans le registre a et le registre B

Quantum qubit magnitude comparator

Le code équivalent pour ce comparateur en OpenQASM est :

J’ai créé une GATE comparator4 qui a le code équivalent OPENQASM suivant :

gate comparator4 a, b, c, d, f, g, i, j, k, l {
  x d;
  x j;
  x l;
  andG1 b, d, f;
  andG2 a, b, g;
  andG3 a, f, i;
  orG1 b, f, j;
  x c;
  andG4 c, f, k;
  x c;
  orG2 d, f, l;
  swap d, i;
  x d;
  swap b, g;
}

Ainsi on voit que cette custom quantum gate est consitué de porte quantum AND et porte quantum OR custom que j’ai créé de la façon suivante. Si on déplie les portes andG1, andG2, andG3, orG1, orG2 on a :

Le code équivalent OpenQASM pour écrire les différentes porte andG1, andG2, andG3, orG1, orG2 pour créer le comparator 4 est :

gate andG1 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate andG2 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate andG3 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate orG1 a, b, c {
  x a;
  x b;
  ccx a, b, c;
  x a;
  x b;
  swap b, c;
}

gate andG4 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate orG2 a, b, c {
  x a;
  x b;
  ccx a, b, c;
  x a;
  x b;
  swap b, c;
}
Circuit de vérification d’une liste triée

Si on considère ici une liste de 4 chiffres stockés dans les 4 registres de 2 qubits : a, b, m, n. Le circuit ci-dessur permet de tester si la liste en entrée est triée ou non. Pour cela j’ai mis en cascade 3 comparateurs de magnitude quantique (vu en détails dans le paragraphe précédent). Ainsi le circuit obtenu va tester si a > b et mettre le résulta sur le qbit c puis vérifier si b>m et stocker le résultat sur le qbit o et enfin il teste si m > n et stocke le résultat sur le qubit q.

La dernière porte quantique andOnCompare permet d’appliquer une parte ET mutliple :si c ET o ET q sont à l’état quantique |1> alors le qubit q est mis à l’état quantique |1> sinon il est à l’état quantique |0> :

Ci-dessous le code de la porte andOnCompare en openQASM :

gate andOnCompare a, b, c, d, f {
  ccx a, b, d;
  swap b, d;
  ccx b, c, f;
  swap c, f;
}

Nous avons créé un circuit qui vérifie qu’une liste de 4 chiffres stocké dans les registres a,b,m,n est triée de façon décroissante ou non. Le résultat est stocké dans le qubit q qui a 100% de chance d’être mesuré à l’état | 1> si la liste est triée sinon 100% d’être à | 0> si la liste a,b,m,n n’est pas en ordre décroissante.

Dans le schéma général ci-dessus on remarque que dans l’exemple :

a=0,b=2,m=3,n=1

dans ce cas ce circuit retournera l’état quantique |0 > sur le qubit q

Création d’un circuit de permutations

L’idée de notre algorithme est de permuter ces 4 chiffres en utilisant des qubits de commande qui seront en état de superposition.

Le circuit de permutation est le suivant :

Un registre de 6 Qubit « control » permet de piloter la permutation de la liste sachant qu’il y a pour 4 éléments : 4*3*2*1 permutations possibles soit 24 possibilités les 6 qubits permettent de générer ces différents états.

4 portes quantique de Hadamard sont utilisées pour mettre en oeuvre ces permutations et tirer parti de la superposition du registre de Qubit ‘control’

En d’autre terme dans le circuit ci-dessus on voit que l’on démarre le circuit en initialisant les registres a,b,m,n avec sa liste de chiffre non triée, ici (a=0,b=2,m=3,n=1).

Le circuit de permutation qui est contrôlé par un registre de qubit en superposition permet de permuter la liste en superposition quantique.

Ainsi on obtient sur le qubit q0 l’état quantique | 1> si la liste permutée est triée de façon décroissante sinon l’état quantique | 0>.

Le code OpenQASM de l’algorithme quantique permettant d’effectuer des permutation est le suivant :

gate permuter a, b, c, d, f, g, i, j, k, l, m, n, o, p {
  cswap k, a, c;
  cswap l, a, f;
  cswap m, a, i;
  cswap k, b, d;
  cswap l, b, g;
  cswap m, b, j;
  cswap n, c, f;
  cswap o, c, i;
  cswap n, d, g;
  cswap o, d, j;
  cswap p, f, i;
  cswap p, g, j;
}
Amplification du résultat

Je vais appeler cette partie de mon algorithme l’amplification : l’idée est de mettre les qubit a,b,m,n à |00>,|00>,|00>,|00> si la liste est non triée. Si la liste est triée alors l’état quantique de a,b,m,n ne doit pas être modifié.

Ainsi on devrait mesurer le résultat suivant : |00>,|00>,|00>,|00> lorsque la liste est non trié et a,b,m,n avec les chiffre d’entrée en ordre trié (dans le cas de notre exemple cela signifie qu’il y a une probabilité de mesurer l’état |11>,|10>,|01>,|00> soit 3,2,1,0 soit la liste triée).

Le circuit de l’amplificateur quantique est le suivant :

Le circuit se base sur une série de porte quantique AND appliqué à l’état de sortie q0 ET le chiffre de la liste. Lorsque le qubit q0 indique que la liste est triée il est à |1> et laisse l’état des qubit a,b,m,n à leur état d’entrée (ou permuté par superposition) . Lorsque le qubit q0 indique que la liste est non triée il est à l’état | 0> l’application de la porte AND va ainsi mettre les qubit a,b,m,n à | 0>.

Le code de l’amplificateur est le suivant selon un algorithme quantique codé en OpenQASM :

gate amplifier2 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
  ccx a, k, l;
  swap a, l;
  ccx b, k, m;
  swap b, m;
  ccx c, k, n;
  swap c, n;
  ccx d, k, o;
  swap d, o;
  ccx f, k, p;
  swap f, p;
  ccx g, k, q;
  swap g, q;
  ccx i, k, r;
  swap i, r;
  ccx j, k, v;
  swap j, v;
}
Algorithme quantique complet pour le tri décroissant d’une liste de quatre chiffres :

Voici le circuit utilisé pour trié la liste suivante : a=0,b=2,m=3,n=1.

Il est possible facilement d’initialiser le circuit avec une autre liste en modifiant l’initialisation des registre a,b,m,n. Aussi l’algorithme actuel permet de trier des chiffres codés sur 2 qubits il reste possible de modifier l’algorithme selon le même principe pour trier des nombres stockés sur 3 qubits et considérer une liste de plus de 4 éléments (il faut alors multiplier le nombre de registres de qubits pour stocker la liste d’entrée).

Le code complet est le suivant en openQASM :

OPENQASM 2.0;
include "qelib1.inc";
gate andG1 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate andG2 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate andG3 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate orG1 a, b, c {
  x a;
  x b;
  ccx a, b, c;
  x a;
  x b;
  swap b, c;
}

gate andG4 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate orG2 a, b, c {
  x a;
  x b;
  ccx a, b, c;
  x a;
  x b;
  swap b, c;
}

gate comparator a, b, c, d, f, g, i, j, k, l {
  x d;
  x j;
  x l;
  andG1 b, d, f;
  andG2 a, b, g;
  andG3 a, f, i;
  orG1 b, f, j;
  x c;
  andG4 c, f, k;
  orG2 d, f, l;
}

gate comparator2 a, b, c, d, f, g, i, j, k, l {
  x d;
  x j;
  x l;
  andG1 b, d, f;
  andG2 a, b, g;
  andG3 a, f, i;
  orG1 b, f, j;
  x c;
  andG4 c, f, k;
  orG2 d, f, l;
  x d;
  swap b, g;
}

gate comparator3 a, b, c, d, f, g, i, j, k, l {
  x d;
  x j;
  x l;
  andG1 b, d, f;
  andG2 a, b, g;
  andG3 a, f, i;
  orG1 b, f, j;
  x c;
  andG4 c, f, k;
  orG2 d, f, l;
  swap d, i;
  x d;
  swap b, g;
}

gate comparator4 a, b, c, d, f, g, i, j, k, l {
  x d;
  x j;
  x l;
  andG1 b, d, f;
  andG2 a, b, g;
  andG3 a, f, i;
  orG1 b, f, j;
  x c;
  andG4 c, f, k;
  x c;
  orG2 d, f, l;
  swap d, i;
  x d;
  swap b, g;
}

gate permutation a, b, c, d, f, g, i, j, k, l, m, n, o, p {
  ccx a, c, k;
  ccx a, f, l;
  ccx a, i, m;
  ccx b, d, k;
  ccx b, g, l;
  ccx b, j, m;
  ccx c, f, n;
  ccx c, i, o;
  ccx d, g, n;
  ccx d, j, o;
  ccx f, i, p;
  ccx g, j, p;
}

gate andOnCompare a, b, c, d, f {
  ccx a, b, d;
  swap b, d;
  ccx b, c, f;
  swap c, f;
}

gate permuter a, b, c, d, f, g, i, j, k, l, m, n, o, p {
  cswap k, a, c;
  cswap l, a, f;
  cswap m, a, i;
  cswap k, b, d;
  cswap l, b, g;
  cswap m, b, j;
  cswap n, c, f;
  cswap o, c, i;
  cswap n, d, g;
  cswap o, d, j;
  cswap p, f, i;
  cswap p, g, j;
}

gate amplifier a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
  ccx l, a, m;
  swap a, m;
  ccx l, b, n;
  swap b, n;
  ccx l, c, o;
  swap c, o;
  ccx l, d, p;
  swap d, p;
  ccx l, f, q;
  swap f, q;
  ccx l, f, q;
  swap f, q;
  ccx l, g, r;
  swap g, r;
  ccx l, i, v;
  swap i, v;
  ccx l, j, k;
  swap j, k;
}

gate amplifier1 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
  ccx a, l, m;
  swap a, m;
  ccx b, l, n;
  swap b, n;
  ccx c, l, o;
  swap c, o;
  ccx d, l, p;
  swap d, p;
  ccx f, l, q;
  swap f, q;
  ccx f, l, q;
  swap f, q;
  ccx g, l, r;
  swap g, r;
  ccx i, l, v;
  swap i, v;
  ccx j, k, l;
  swap j, k;
}

gate amplifier2 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
  ccx a, k, l;
  swap a, l;
  ccx b, k, m;
  swap b, m;
  ccx c, k, n;
  swap c, n;
  ccx d, k, o;
  swap d, o;
  ccx f, k, p;
  swap f, p;
  ccx g, k, q;
  swap g, q;
  ccx i, k, r;
  swap i, r;
  ccx j, k, v;
  swap j, v;
}

qreg a[2];
qreg b[2];
qreg m[2];
qreg n[2];
qreg c[1];
qreg o[1];
qreg q[1];
qreg d[1];
qreg g[1];
qreg j[1];
qreg k[1];
qreg l[1];
qreg r[1];
qreg uu[1];
qreg zz[1];
qreg control[6];
creg sorted[8];

reset a[0];
reset a[1];
reset b[0];
reset b[1];
reset m[0];
reset m[1];
reset n[0];
reset n[1];
reset c[0];
reset o[0];
reset q[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
reset r[0];
reset uu[0];
h control[0];
h control[1];
h control[2];
h control[3];
h control[4];
h control[5];
reset a[0];
reset a[1];
reset b[0];
x b[1];
x m[0];
x m[1];
reset n[1];
reset c[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
x n[0];
permuter a[0],a[1],b[0],b[1],m[0],m[1],n[0],n[1],control[0],control[1],control[2],control[3],control[4],control[5];
comparator4 a[0],a[1],b[0],b[1],c[0],d[0],g[0],j[0],k[0],l[0];
reset zz[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
comparator4 b[0],b[1],m[0],m[1],o[0],d[0],g[0],j[0],k[0],l[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
comparator4 m[0],m[1],n[0],n[1],q[0],d[0],g[0],j[0],k[0],l[0];
andOnCompare c[0],o[0],q[0],r[0],uu[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
reset r[0];
reset uu[0];
amplifier2 a[0],a[1],b[0],b[1],m[0],m[1],n[0],n[1],q[0],d[0],g[0],j[0],k[0],l[0],r[0],uu[0],zz[0];
measure a[0] -> sorted[0];
measure a[1] -> sorted[1];
measure b[0] -> sorted[2];
measure b[1] -> sorted[3];
measure m[0] -> sorted[4];
measure m[1] -> sorted[5];
measure n[0] -> sorted[6];
measure n[1] -> sorted[7];

Voici le code Python Qiskit pour mon algorithme de tri quantique :

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_a = QuantumRegister(2, 'a')
qreg_b = QuantumRegister(2, 'b')
qreg_m = QuantumRegister(2, 'm')
qreg_n = QuantumRegister(2, 'n')
qreg_c = QuantumRegister(1, 'c')
qreg_o = QuantumRegister(1, 'o')
qreg_q = QuantumRegister(1, 'q')
qreg_d = QuantumRegister(1, 'd')
qreg_g = QuantumRegister(1, 'g')
qreg_j = QuantumRegister(1, 'j')
qreg_k = QuantumRegister(1, 'k')
qreg_l = QuantumRegister(1, 'l')
qreg_r = QuantumRegister(1, 'r')
qreg_uu = QuantumRegister(1, 'uu')
qreg_zz = QuantumRegister(1, 'zz')
qreg_control = QuantumRegister(6, 'control')
creg_sorted = ClassicalRegister(8, 'sorted')
circuit = QuantumCircuit(qreg_a, qreg_b, qreg_m, qreg_n, qreg_c, qreg_o, qreg_q, qreg_d, qreg_g, qreg_j, qreg_k, qreg_l, qreg_r, qreg_uu, qreg_zz, qreg_control, creg_sorted)

circuit.x(qreg_b[1])
circuit.x(qreg_m[0])
circuit.x(qreg_m[1])
circuit.x(qreg_n[0])
circuit.x(qreg_j[0])
circuit.x(qreg_l[0])
circuit.h(qreg_control[0])
circuit.cswap(qreg_control[0], qreg_a[0], qreg_b[0])
circuit.cswap(qreg_control[0], qreg_a[1], qreg_b[1])
circuit.h(qreg_control[1])
circuit.cswap(qreg_control[1], qreg_a[0], qreg_m[0])
circuit.cswap(qreg_control[1], qreg_a[1], qreg_m[1])
circuit.h(qreg_control[2])
circuit.cswap(qreg_control[2], qreg_a[0], qreg_n[0])
circuit.cswap(qreg_control[2], qreg_a[1], qreg_n[1])
circuit.h(qreg_control[3])
circuit.cswap(qreg_control[3], qreg_b[0], qreg_m[0])
circuit.cswap(qreg_control[3], qreg_b[1], qreg_m[1])
circuit.h(qreg_control[4])
circuit.cswap(qreg_control[4], qreg_b[0], qreg_n[0])
circuit.x(qreg_b[0])
circuit.cswap(qreg_control[4], qreg_b[1], qreg_n[1])
circuit.x(qreg_b[1])
circuit.ccx(qreg_a[1], qreg_b[1], qreg_c[0])
circuit.ccx(qreg_a[0], qreg_a[1], qreg_d[0])
circuit.swap(qreg_a[1], qreg_d[0])
circuit.x(qreg_a[1])
circuit.swap(qreg_b[1], qreg_c[0])
circuit.ccx(qreg_a[0], qreg_c[0], qreg_g[0])
circuit.swap(qreg_c[0], qreg_g[0])
circuit.x(qreg_c[0])
circuit.ccx(qreg_a[1], qreg_c[0], qreg_j[0])
circuit.x(qreg_c[0])
circuit.swap(qreg_c[0], qreg_j[0])
circuit.reset(qreg_j[0])
circuit.x(qreg_j[0])
circuit.x(qreg_a[1])
circuit.swap(qreg_a[1], qreg_d[0])
circuit.reset(qreg_d[0])
circuit.ccx(qreg_b[0], qreg_c[0], qreg_k[0])
circuit.swap(qreg_c[0], qreg_k[0])
circuit.x(qreg_c[0])
circuit.reset(qreg_k[0])
circuit.x(qreg_b[0])
circuit.x(qreg_b[1])
circuit.ccx(qreg_b[1], qreg_c[0], qreg_l[0])
circuit.x(qreg_c[0])
circuit.swap(qreg_c[0], qreg_l[0])
circuit.reset(qreg_l[0])
circuit.x(qreg_l[0])
circuit.x(qreg_b[1])
circuit.swap(qreg_b[1], qreg_g[0])
circuit.reset(qreg_g[0])
circuit.x(qreg_b[1])
circuit.h(qreg_control[5])
circuit.cswap(qreg_control[5], qreg_m[0], qreg_n[0])
circuit.x(qreg_m[0])
circuit.x(qreg_n[0])
circuit.cswap(qreg_control[5], qreg_m[1], qreg_n[1])
circuit.x(qreg_m[1])
circuit.ccx(qreg_b[1], qreg_m[1], qreg_o[0])
circuit.ccx(qreg_b[0], qreg_b[1], qreg_d[0])
circuit.swap(qreg_b[1], qreg_d[0])
circuit.x(qreg_b[1])
circuit.swap(qreg_m[1], qreg_o[0])
circuit.ccx(qreg_b[0], qreg_o[0], qreg_g[0])
circuit.swap(qreg_o[0], qreg_g[0])
circuit.x(qreg_o[0])
circuit.ccx(qreg_b[1], qreg_o[0], qreg_j[0])
circuit.x(qreg_o[0])
circuit.swap(qreg_o[0], qreg_j[0])
circuit.reset(qreg_j[0])
circuit.x(qreg_j[0])
circuit.x(qreg_b[1])
circuit.swap(qreg_b[1], qreg_d[0])
circuit.reset(qreg_d[0])
circuit.ccx(qreg_m[0], qreg_o[0], qreg_k[0])
circuit.swap(qreg_o[0], qreg_k[0])
circuit.reset(qreg_k[0])
circuit.x(qreg_o[0])
circuit.x(qreg_m[0])
circuit.x(qreg_m[1])
circuit.ccx(qreg_m[1], qreg_o[0], qreg_l[0])
circuit.x(qreg_o[0])
circuit.swap(qreg_o[0], qreg_l[0])
circuit.ccx(qreg_c[0], qreg_o[0], qreg_r[0])
circuit.reset(qreg_l[0])
circuit.x(qreg_l[0])
circuit.swap(qreg_o[0], qreg_r[0])
circuit.reset(qreg_r[0])
circuit.x(qreg_m[1])
circuit.swap(qreg_m[1], qreg_g[0])
circuit.reset(qreg_g[0])
circuit.x(qreg_m[1])
circuit.x(qreg_n[1])
circuit.ccx(qreg_m[1], qreg_n[1], qreg_q[0])
circuit.ccx(qreg_m[0], qreg_m[1], qreg_d[0])
circuit.swap(qreg_m[1], qreg_d[0])
circuit.x(qreg_m[1])
circuit.swap(qreg_n[1], qreg_q[0])
circuit.ccx(qreg_m[0], qreg_q[0], qreg_g[0])
circuit.swap(qreg_q[0], qreg_g[0])
circuit.x(qreg_q[0])
circuit.ccx(qreg_m[1], qreg_q[0], qreg_j[0])
circuit.x(qreg_q[0])
circuit.swap(qreg_q[0], qreg_j[0])
circuit.reset(qreg_j[0])
circuit.x(qreg_m[1])
circuit.swap(qreg_m[1], qreg_d[0])
circuit.reset(qreg_d[0])
circuit.ccx(qreg_n[0], qreg_q[0], qreg_k[0])
circuit.swap(qreg_q[0], qreg_k[0])
circuit.reset(qreg_k[0])
circuit.x(qreg_q[0])
circuit.x(qreg_n[0])
circuit.x(qreg_n[1])
circuit.ccx(qreg_n[1], qreg_q[0], qreg_l[0])
circuit.x(qreg_q[0])
circuit.swap(qreg_q[0], qreg_l[0])
circuit.reset(qreg_l[0])
circuit.ccx(qreg_o[0], qreg_q[0], qreg_uu[0])
circuit.swap(qreg_q[0], qreg_uu[0])
circuit.reset(qreg_uu[0])
circuit.ccx(qreg_a[0], qreg_q[0], qreg_d[0])
circuit.swap(qreg_a[0], qreg_d[0])
circuit.x(qreg_n[1])
circuit.swap(qreg_n[1], qreg_g[0])
circuit.reset(qreg_g[0])
circuit.ccx(qreg_a[1], qreg_q[0], qreg_g[0])
circuit.swap(qreg_a[1], qreg_g[0])
circuit.ccx(qreg_b[0], qreg_q[0], qreg_j[0])
circuit.swap(qreg_b[0], qreg_j[0])
circuit.ccx(qreg_b[1], qreg_q[0], qreg_k[0])
circuit.swap(qreg_b[1], qreg_k[0])
circuit.ccx(qreg_m[0], qreg_q[0], qreg_l[0])
circuit.swap(qreg_m[0], qreg_l[0])
circuit.ccx(qreg_m[1], qreg_q[0], qreg_r[0])
circuit.swap(qreg_m[1], qreg_r[0])
circuit.ccx(qreg_n[0], qreg_q[0], qreg_uu[0])
circuit.swap(qreg_n[0], qreg_uu[0])
circuit.x(qreg_n[1])
circuit.ccx(qreg_n[1], qreg_q[0], qreg_zz[0])
circuit.swap(qreg_n[1], qreg_zz[0])
circuit.measure(qreg_a[0], creg_sorted[0])
circuit.measure(qreg_a[1], creg_sorted[1])
circuit.measure(qreg_b[0], creg_sorted[2])
circuit.measure(qreg_b[1], creg_sorted[3])
circuit.measure(qreg_m[0], creg_sorted[4])
circuit.measure(qreg_m[1], creg_sorted[5])
circuit.measure(qreg_n[0], creg_sorted[6])
circuit.measure(qreg_n[1], creg_sorted[7])

Test du circuit algorithme de tri quantique

Les test s’effectuent en démarrant l’algorithme sur le simulateur quantique :

Pour démarrer l’algorithme quantique il faut au préalable initialiser :

%matplotlib inline
# Importing standard Qiskit libraries
from qiskit import QuantumCircuit, execute, Aer, IBMQ
from qiskit.compiler import transpile, assemble
from qiskit.tools.jupyter import *
from qiskit.visualization import *
from iqx import *

# Loading your IBM Q account(s)
provider = IBMQ.load_account()

Et pour effectuer le test par exemple en exécutant 100 fois le circuit quantique et afficher la probabilité de mesure sous forme d’histogramme :

backend = Aer.get_backend('qasm_simulator')
results = execute(circuit, backend=backend, shots=100).result()
answer = results.get_counts()
plot_histogram(answer)

On obtient le résultat qui confirme qu’on a plus de change de mesurer l’état quantique de la liste trié que les autres combinaison (dans mon test 5%) :

Et après 200 shots :

Problème du sac à dos – Algorithme en Python (knapsack problem)

Le problème du sac à dos en algorithmique (et son implémentation python) est intéressant et fait parti du programme de Sciences numériques et informatique de première.

Ce problème illustre les algorithmes gloutons qui énumèrent toutes les possibilités de résolution d’un problème pour trouver la meilleure solution.

Le problème du sac à dos algorithme python est un problème d’optimisation, c’est à dire une fonction que l’on doit maximiser ou minimiser et des contraintes qu’il faut satisfaire.

Le problème du sac à dos – algorithme Python

Pour un sac à dos de capacité maximale de P et N articles chacun avec son propre poids et une valeur définie, jetez les articles à l’intérieur du sac à dos de telle sorte que le contenu final ait la valeur maximale.

Le problème du sac à dos - algorithme Python

Exemple d’énoncé :

  • Capacité maximum du sac à dos : 11 unités
  • Nombre d’objet : 5
  • Valeurs des objets : {10,50,20,30,60}
  • Poids des objets : {1,5,3,2,4}

Quelles est la valeur maximum qu’il est possible de mettre dans le sac à dos en considérant la contrainte de capacité maximum du sac qui est de 11 ?

Algorithme glouton python

Une solution efficace consiste à utiliser un algorithme glouton. L’idée est de calculer le rapport valeur / poids pour chaque objet et de trier l’objet sur la base de ce rapport calculé .

On prends l’objet avec le ratio le plus élevé et on ajoute jusqu’à ce qu’on ne puisse plus en ajouter.

En version fractionnaire il est possible d’ajouter des fractions d’article au sac à dos.

Implémentation du problème du sac à dos Python – version non fractionnaire

Voici une implémentation du problème du sac à dos python en version non fractionnaire, c’est à dire qu’on ne peut pas ajouter de fraction d’un objet dans le sac. Seul des objets entiers peuvent être ajoutés.

class ObjetSac: 
    def __init__(self, poids, valeur, indice): 
        self.indice = indice         
        self.poids = poids 
        self.valeur = valeur
        self.rapport = valeur // poids 
  #Fonction pour la comparaison entre deux ObjetSac
  #On compare le rapport calculé pour les trier
    def __lt__(self, other): 
        return self.rapport < other.rapport 
  

def getValeurMax(poids, valeurs, capacite): 
        tableauTrie = [] 
        for i in range(len(poids)): 
            tableauTrie.append(ObjetSac(poids[i], valeurs[i], i)) 
  
        #Trier les éléments du sac par leur rapport
        tableauTrie.sort(reverse = True) 
  
        compteurValeur = 0
        for objet in tableauTrie: 
            poidsCourant = int(objet.poids) 
            valeurCourante = int(objet.valeur) 
            if capacite - poidsCourant >= 0: 
                #on ajoute l'objet dans le sac
                #On soustrait la capacité
                capacite -= poidsCourant 
                compteurValeur += valeurCourante
                #On ajoute la valeur dans le sac 
        return compteurValeur 


poids = [1,5,3,2,4] 
valeurs = [10,50,20,30,60] 
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite) 
print("Valeur maxi dans le sac à dos =", valeurMax) 

Le résultat obtenu est le suivant :

py sacados.py 
Valeur maxi dans le sac à dos = 120

Implémentation du problème du sac à dos python – version fractionnaire

En version fractionnaire de l’agorithme du sac à dos python on peut ajouter des fractions d’objet au sac à dos.

class ObjetSac: 
    def __init__(self, poids, valeur, indice): 
        self.indice = indice         
        self.poids = poids 
        self.valeur = valeur
        self.rapport = valeur // poids 
  #Fonction pour la comparaison entre deux ObjetSac
  #On compare le rapport calculé pour les trier
    def __lt__(self, other): 
        return self.rapport < other.rapport 
  

def getValeurMax(poids, valeurs, capacite): 
        tableauTrie = [] 
        for i in range(len(poids)): 
            tableauTrie.append(ObjetSac(poids[i], valeurs[i], i)) 
  
        #Trier les éléments du sac par leur rapport
        tableauTrie.sort(reverse = True) 
  
        compteurValeur = 0
        for objet in tableauTrie: 
            poidsCourant = int(objet.poids) 
            valeurCourante = int(objet.valeur) 
            if capacite - poidsCourant >= 0: 
                #on ajoute l'objet dans le sac
                #On soustrait la capacité
                capacite -= poidsCourant 
                compteurValeur += valeurCourante
                #On ajoute la valeur dans le sac 
            else: 
                fraction = capacite / poidsCourant 
                compteurValeur += valeurCourante * fraction 
                capacite = int(capacite - (poidsCourant * fraction)) 
                break
        return compteurValeur 


poids = [1,5,3,2,4] 
valeurs = [10,50,20,30,60] 
capacite = 11
valeurMax = getValeurMax(poids, valeurs, capacite) 
print("Valeur maxi dans le sac à dos =", valeurMax) 

Le résultat obtenu est le suivant :

py sacados.py 
Valeur maxi dans le sac à dos = 140.0

Liens internes algorithme python :

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/2021/01/21/algorithme-glouton-python/
http://128mots.com/index.php/2021/01/19/levenshtein-python/
http://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/

Liens externes algorithme python :

http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie.pdf

http://www.dil.univ-mrs.fr/~gcolas/algo-licence/slides/gloutons.pdf

Algorithme KNN Python : k plus proches voisins

L’algorithme knn python d’apprentissage des k plus proches voisins (KNN) est utilisé pour effectuer de la classification de données.

algorithme knn python

Introduction

Pour prédire la classification d’une nouvelle donnée, l’algorithme se base sur les k enregistrements issus de l’ensemble de données d’apprentissage sont alors localisés les plus similaires à ce nouvel enregistrement.

La similitude entre les enregistrements peut être mesurée de différentes manières. Et généralement un bon point de départ est la distance euclidienne.

L’algorithme knn python :

Pour une entrée x quelle est sa classe y si je me base sur les k voisins les plus proches de x ?

  1. Trouver les k entrée partie les données d’entrainement qui sont les plus « proches » de mon entrée x (ici on utilisera par exemple la distance euclidienne)
  2. Faire voter chacune de ces données d’entrainement pour sa classe y.
  3. Retourner la classe majoritaire

Ainsi, Le succès de l’algorithme va reposer sur la quantité de donnée d’entrainement et sur la qualité de la mesure de la distance entre 2 vecteurs x.

Implémentation python de l’algorithme knn des k plus proches voisins.

Finalement, Voici un exemple d’utilisation et d’implémentation Python sur la base de données qui concerne l’accord d’un crédit en fonction de l’age et du montant demandé. La classe correspond à la réponse OUI ou NON.

from math import sqrt
 
# Faire une predicition de la classification
def predire_classification(donnee_test, entrainement, nombre_voisins_vote):
	voisins = recherche_voisins(entrainement, donnee_test, nombre_voisins_vote)
	sortie = [vecteur[-1] for vecteur in voisins]
	prediction = max(set(sortie), key=sortie.count)
	return prediction


 #Distance euclidienne de 2 vecteurs
def distance_euclidienne(vecteur1, vecteur2):
	distance = 0.0
	for i in range(len(vecteur1)-1):
		distance += (vecteur1[i] - vecteur2[i])**2
	return sqrt(distance)
 

# Recherche les voisins
def recherche_voisins(entrainement, donnee_test, nbVoisins):
	distances = list()
	for ligneEntrainement in entrainement:
		dist = distance_euclidienne(donnee_test, ligneEntrainement)
		distances.append((ligneEntrainement, dist))
	distances.sort(key=lambda tup: tup[1])
	kVoisins = list()
	for i in range(nbVoisins):
		kVoisins.append(distances[i][0])
	return kVoisins
 
 
# Données d'entrainement
donneesApprentissage = [[25,40000,'NON'],
		   [30,60000,'OUI'],
		   [35,80000,'NON'],
		   [45,50000,'NON'],
		   [20,60000,'NON'],
		   [60,15000,'NON'],
		   [70,5000,'OUI'],
		   [80,1000,'NON'],
		   [33,80000,'OUI'],
		   [32,10000,'NON']]

prediction = predire_classification(donneesApprentissage[1], donneesApprentissage, 3)
print('On devrait trouver %s, la prediction est : %s.' % (donneesApprentissage[1][-1], prediction))

Liens externes :

https://fr.wikipedia.org/wiki/M%C3%A9thode_des_k_plus_proches_voisins

https://www.python.org/

Liens internes :

http://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/
http://128mots.com/index.php/2020/10/09/pytorch-comment-charger-un-modele-pre-entraine/

http://128mots.com/index.php/category/python/

Implémentation Python de l’algorithme de Dijkstra

Cet article fait suite à l’article suivant sur l’algorithme de Dijkstra : http://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Voici l’implémentation Python de l’algorithme

from collections import deque

def dijkstra(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    while queue:
        t = queue.popleft()
        print("On visite le sommet " + str(t))
        for voisin in graph[t]:
                queue.append(voisin)
                nouvelle_distance = distance[t] + graph[t][voisin]
                if(voisin not in distance or nouvelle_distance < distance[voisin]):
                    distance[voisin] = nouvelle_distance
                    print("Met à jour le sommet " + str(voisin) + " avec la distance : " + str(nouvelle_distance))
                    
    return distance



#Liste d'ajacence du graphe
graph = {'A':{'B':15,'C':4},'B':{'E':5},'C':{'E':11,'D':2},'D':{'E':3},'E':{}}
distance = dijkstra(graph,'A')
print("Distances" + str(distance))

Implémentation Python du parcours en largeur dans les graphes (BFS)

Cet article fait suite à celui qui porte sur l’algorithme BFS ici : http://128mots.com/index.php/2020/02/11/parcours-en-largeur-dans-les-graphes-bfs/

L’implémentation Python de cet algorithme est la suivante :

from collections import deque

def bfs(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    pere = {vertex: None}
    while queue:
    	t = queue.popleft()
    	for voisin in graph[t]:
    		if voisin not in distance:
    			queue.append(voisin)
    			distance[voisin] = distance[t] + 1
    			pere[voisin] = t
    return distance, pere


#Liste d'ajacence du graphe
graph = {
	'A': ['B','C'],
	'B': ['A','C', 'D'],
	'C': ['D'],
	'D': ['C','A']
}

distance,pere = bfs(graph,'A')
print("Distances" + str(distance))
print("Pere = " + str(pere))

Parcours en largeur Python – Algorithme sur les Graphes

Le parcours en largeur python d’un graphe (BFS) est un algorithme utilisé pour parcourir les structures de donnée de graphe. BFS met en œuvre une stratégie spécifique pour visiter tous les sommets d’un graphe.

Introduction – Parcours en largeur python

BFS commence par un sommet, puis il vérifie les voisins du sommet initial, puis les voisins des voisins, etc.

En entrée de l’algorithme il y a le graphe G et un sommet de départ D pour lequel on considère que la distance est 0.

En sortie de l’algorithme sont calculées toutes les distances entre le sommet D et chaque sommet du graphe G ainsi que l’arbre couvrant si le graphe G est connexe (c’est à dire que pour toute paire de sommet il existe un chemin entre eux dans le graphe).

Description de l’algorithme

On utilise les tableaux suivants :

  • Distance[.] : Stocke la distance entre D (sommet de départ) et un autre sommet du graphe.
  • Father[.] : Stocke le sommet père d’un sommet du graphe parcouru.
  • Visite[.] : Stocke l’état de visite du sommet, liste des valeurs possible 0:pas encore visité,1:Visite en cours,2:Visité

On utilise les fonctions suivantes pour une file F :

  • First(F) : Retourne l’élément en tête de la file F sans le supprimer.
  • Dequeue(F) : Retourne l’élément en tête de la file F en le supprimant.
  • Append(F, A) : Mettre l’élément A dans la file F en queue de la file.

Les étapes de l’algorithme :

  • Phase d’initialisation
    • 1. Pour tous les sommets faire
      • Visite = 0 (Pas encore visité)
      • Pere = null (Initialise le tableau)
      • Distance = -1
    • 2. Append(F,D) (ajoute l’élément de départ)
    • 3. Distance[R] = 0 (postulat de départ)
  • Phase d’action (parcours du graphe G)
    • Tant que la file F n’est pas vide
      • t = First(F)
      • Pour tous les voisins v de t faire
        • Si Visite[v] = 0 (sommet non visité) alors
          • Visite[v] = 1 (Visite en cours)
          • Distance[v] = Distance[t] + 1
          • Father[v] = t
          • Append(F,v)
      • Dequeue(F)
      • Visite[t] = 2

Si on détaille les étapes avec le cas du graphe exemple ci-dessous.

Phase d’initialisation :

Parcours en largeur Python - Algorithme sur les Graphes

Initialisation l’élément A est l’élément de départ à distance 0, il est coloré en orange pour indiquer que la visite est en cours.

Visite des voisins du sommet A (Visite du sommet B)

Parcours en largeur Python - Algorithme sur les Graphes
Le sommet B passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.

Visite des voisins du sommet A (Visite du sommet C)

Parcours en largeur Python - Algorithme sur les Graphes
Le sommet C passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.

Marquage de A comme visité et suppression de la file

Parcours en largeur Python - Algorithme sur les Graphes
A est marqué comme visité (couleur bleue) et retiré de la tête de la file

Visite des voisins du sommet B (Visite du sommet D)

Parcours en largeur Python - Algorithme sur les Graphes
Le sommet C etant marqué comme en cours de visite il ne sera pas visité, on visite le sommet D on calcule sa distance = 2 et on note le sommet B comme père du sommet B.

Marquage de B et C comme visité et suppression de la file

B est marqué comme visité (couleur bleue) et retiré de la tête de la file
C est marqué comme visité (couleur bleue) et retiré de la tête de la file (son voisin D est marqué en cours de visite)

Marquage de D comme visité et fin de l’algorithme

Parcours en largeur Python - Algorithme sur les Graphes
D est marqué comme visité (couleur bleue) et retiré de la tête de la file.
Fin de l’algorithme

Construction de l’arbre couvrant si le graphe est connexe

Parcours en largeur Python - Algorithme sur les Graphes
Si le graphe est connexe on déplie le résultat du parcours et on obtient l’arbre couvrant du graphe qui contient tous les sommets.

Application : Le parcours en largeur d’un graphe (BFS) est utile pour :

  • Vérifier si un graphe est connexe (tous les sommets sont alors marqués comme visités à la fin de l’algorithme).
  • Calculer les distances à partir d’un sommet donné
  • Construire un arbre couvrant du graphe

Parcours en largeur python – Liens externes

https://fr.wikipedia.org/wiki/Python_(langage)

https://www.python.org/

https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur

Parcours en largeur python – Liens internes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/2021/01/21/algorithme-glouton-python/

Python les bases en plus de 128 mots [Partie 1]

Voici mes notes pour apprendre très rapidement le langage python. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.

Opérateurs logiques :

  • and : retourne True si les deux déclarations sont vraies
  • or : Renvoie True si l’une des déclarations est true
  • not : Inverser le résultat, renvoie False si le résultat est vrai

Opérateurs de comparaison :

  • == Égalité
  • != Non égal
  • > < Supérieur / Inférieur
  • <= >= Inférieur égal / Supérieur égal
  • != Différent

Mot clé pass :

Lorsque l’instruction pass est exécutée, rien ne se produit, mais vous évitez une erreur lorsque du code vide n’est pas autorisé.

x = 22
y = 150

if x > y:
  pass

Entrée utilisateur :

Utilisation de l’instruction input :

nom = input("Nom utilisateur :")
print("Username is: " + nom)

Boucle While :

La boucle while exécute un ensemble d’instructions tant qu’une condition est vraie. L’instruction break, permet d’arrêter la boucle même si la condition while est vraie.

x = 1
while x < 11:
  if x == 5:
    break
  x += 1 

Boucle For :

Une boucle for effectue une itération sur une séquence (une liste, un tuple, un dictionnaire, un ensemble ou une chaîne de caractère).

Une liste :

for x in [1, 2, 3]:
  print(x)

Une chaine de caractère :

for x in "hello":
  print(x)

Un tuple :

tupleObjet = ('Citroen', 2019, 'C4', 23000)
 
for elements in tupleObj:
    print(elements)

Un dictionnaire :

dico = {'couleur': 'vert', 'animal': 'chien', 'legume': 'epinard'}
for cle in dico:
    print(cle)

Fonction Range :

Pour boucler un nombre de fois spécifique, utilisez la fonction range ().

for x in range(10):
  print(x)

Les Listes :

Une liste est une collection qui est ordonnée et modifiable et qui permet les doublons.

liste = ["pomme", "banane", "poire"]
print(liste[1])
print(liste[-1]) #Affiche le dernier élément de la liste
print(liste[2:3])#Lorsque vous spécifiez une plage, la valeur de retour sera une nouvelle liste avec les éléments spécifiés.
print(liste[2:3])#Lorsque vous spécifiez une plage, la valeur de retour sera une nouvelle liste avec les éléments spécifiés.
print(liste[:3])#En omettant la valeur initiale, la plage commencera au premier élément:
print(liste[1:])#En omettant la valeur de fin, la plage ira à la fin de la liste:
print(liste[-2:-1])#des index négatifs pour lancer la recherche à partir de la fin de la liste: Cet exemple renvoie les éléments de l'index -2 (inclus) à l'index -1 (exclu).

Tri fusion Python – implémentation de l’algorithme

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présente une implémentation du tri fusion python.

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présent une implémentation du tri fusion python.

Introduction

L’algorithme est le suivant :
Diviser en deux moitiés la liste à trier.
On trie chacune d’entre elles.
Fusionner les deux moitiés obtenues pour reconstituer la liste triée.

On applique récursivement cet algorithme c’est à dire jusqu’à ce que la liste à trier soit constituée d’un seul élément.

tri fusion python
Tri fusion (source : wikipedia)
#Tri fusion fonction de division du tableau
def tri_fusion(tableau):
    if  len(tableau) <= 1: 
        return tableau
    pivot = len(tableau)//2
    tableau1 = tableau[:pivot]
    tableau2 = tableau[pivot:]
    gauche = tri_fusion(tableau1)
    droite = tri_fusion(tableau2)
    fusionne = fusion(gauche,droite)
    return fusionne


#Tri fusion fonction de fusion de 2 listes
def fusion(tableau1,tableau2):
    indice_tableau1 = 0
    indice_tableau2 = 0    
    taille_tableau1 = len(tableau1)
    taille_tableau2 = len(tableau2)
    tableau_fusionne = []
    while indice_tableau1<taille_tableau1 and indice_tableau2<taille_tableau2:
        if tableau1[indice_tableau1] < tableau2[indice_tableau2]:
            tableau_fusionne.append(tableau1[indice_tableau1])
            indice_tableau1 += 1
        else:
            tableau_fusionne.append(tableau2[indice_tableau2])
            indice_tableau2 += 1
    while indice_tableau1<taille_tableau1:
        tableau_fusionne.append(tableau1[indice_tableau1])
        indice_tableau1+=1
    while indice_tableau2<taille_tableau2:
        tableau_fusionne.append(tableau2[indice_tableau2])
        indice_tableau2+=1
    return tableau_fusionne

tableau = [11, 222, 3, 899, 24, 5, 46, 67]
print(tableau)
tableau_trie = tri_fusion(tableau)
print(tableau_trie)

A propos de tri fusion

Enfin, Le tri fusion fonctionne par comparaison. La complexité de l’algorithme pour n entrée est n log n, donc asymptotiquement optimal.

La technique est de diviser pour régner. Et l’algorithme fait principalement une opération de fusion (deux listes triées peuvent être fusionnées en temps linéaire).

Tri fusion python : liens externes

https://www.geeksforgeeks.org/merge-sort/

http://lwh.free.fr/pages/algo/tri/tri_fusion.html

https://pixees.fr/informatiquelycee/n_site/isn_algo_diviser_pour_regner.html

https://fr.wikipedia.org/wiki/Tri_fusion

https://graal.hypotheses.org/tag/algorithme-de-wagner-fischer

https://fr.wikipedia.org/wiki/Algorithme_de_Wagner-Fischer

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein

https://medium.com/@sddkal/wagner-fischer-algorithm-be0d96893f6d

https://www.python-course.eu/levenshtein_distance.php

Liens internes sur les algorithmes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/graphes/

http://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Pour calculer la distance de Levenshtein avec un algorithme non récursif. On utilise une matrice qui contient les distances de Levenshtein. Alors Ce sont les distances entre tous les préfixes de la première chaîne et tous les préfixes de la seconde chaîne de caractères.