Exiting due to GUEST_PROVISION: Failed to start host: config

Publié le 31 janvier 2021 par Jean-Paul

❌ Exiting due to GUEST_PROVISION: Failed to start host: config: please provide an IP address : Error with kubernetes and minikube minikube

Introduction – Exiting due to GUEST_PROVISION

So, if you are trying to start the kubernetes tutorial from https://kubernetes.io/fr/docs/setup/learning-environment/minikube and you want to start minikube by the command :

minikube start

Then, you are getting this error :

minikube v1.17.1 sur Darwin 10.15.7
✨  Utilisation du pilote ssh basé sur le profil existant
👍  Démarrage du noeud de plan de contrôle minikube dans le cluster minikube
🤦  StartHost failed, but will try again: config: please provide an IP address
😿  Failed to start ssh bare metal machine. Running "minikube delete" may fix it: config: please provide an IP address

❌  Exiting due to GUEST_PROVISION: Failed to start host: config: please provide an IP address

😿  If the above advice does not help, please let us know: 
👉  https://github.com/kubernetes/minikube/issues/new/choose

Solution

And, the best way to solve this problem is to run the following command. Also you can find information on Website minikube.sigs.k8s.io

If you are running with docker you will find on https://minikube.sigs.k8s.io/docs/drivers/docker/ what i have done is to delete the last minkube cluster and rerun with the command specify the docker :

minikube delete

You will get :

🔄  Désinstallation de Kubernetes v1.20.2 à l'aide de kubeadm…
🔥  Trying to delete invalid profile minikube

And then :

minikube start --driver=docker

This is working :

😄  minikube v1.17.1 sur Darwin 10.15.7
✨  Utilisation du pilote docker basé sur la configuration de l'utilisateur
👍  Démarrage du noeud de plan de contrôle minikube dans le cluster minikube
🚜  Pulling base image ...

Internal links :

https://128mots.com/index.php/en/2021/01/31/unable-to-pick-a-default-driver/

runtimeerror: attempting to deserialize object on a cuda device

https://128mots.com/index.php/en/2021/01/31/runtimeerror-attempting-to-deserialize-object/

Installer kubernetes mac os x – Tutorial kubernetes débutant

https://128mots.com/index.php/2021/01/31/installer-kubernetes-mac/

exiting due to drv_not_detected – Kubernetes error resolution

Publié le 31 janvier 2021 par Jean-Paul

exiting due to drv_not_detected: no possible driver

😄 minikube v1.17.1 sur Darwin 10.15.7
👎 Unable to pick a default driver. Here is what was considered, in preference order:
▪ parallels : Not installed: exec: « prlctl »: executable file not found in $PATH
▪ podman : Not installed: exec: « podman »: executable file not found in $PATH
▪ virtualbox : Not installed: unable to find VBoxManage in $PATH
▪ vmware : Not installed: exec: « docker-machine-driver-vmware »: executable file not found in $PATH
▪ vmwarefusion : Not installed: the ‘vmwarefusion’ driver is no longer available
▪ docker : Not installed: exec: « docker »: executable file not found in $PATH
▪ hyperkit : Not installed: exec: « hyperkit »: executable file not found in $PATH

❌ Exiting due to DRV_NOT_DETECTED: No possible driver was detected. Try specifying –driver, or see https://minikube.sigs.k8s.io/docs/start/

When you try to launch :

minikube start

You get this error :

😄  minikube v1.17.1 sur Darwin 10.15.7
👎  Unable to pick a default driver. Here is what was considered, in preference order:
    ▪ parallels : Not installed: exec: "prlctl": executable file not found in $PATH
    ▪ podman : Not installed: exec: "podman": executable file not found in $PATH
    ▪ virtualbox : Not installed: unable to find VBoxManage in $PATH
    ▪ vmware : Not installed: exec: "docker-machine-driver-vmware": executable file not found in $PATH
    ▪ vmwarefusion : Not installed: the 'vmwarefusion' driver is no longer available
    ▪ docker : Not installed: exec: "docker": executable file not found in $PATH
    ▪ hyperkit : Not installed: exec: "hyperkit": executable file not found in $PATH

❌  Exiting due to DRV_NOT_DETECTED: No possible driver was detected. Try specifying --driver, or see https://minikube.sigs.k8s.io/docs/start/

Solution setup Docker with homebrew- Unable to pick a default driver :

You can setup Docker with Homebrew Cask : Homebrew Cask is a Homebrew extension for installing GUI software on Mac os like docker.

brew cask install docker

if you get :

Error: Calling `brew cask install` is disabled! Use brew install [--cask] instead.

Then use instead this command and it will works :

brew install docker --cask

Check docker version :

docker --version

If the command doesn’t works :

docker --version
zsh: command not found: docker

So you can run docker app in finder or in command line it will start docker desktop :

open /Applications/Docker.app

Then you can try again minikube :

minikube start

External links – exiting due to drv_not_detected: no possible driver:

Docker on Mac with Homebrew: A Step-by-Step Tutorial

Website www.cprime.com

Website github.com

Website kubernetes.io

Internal links :

Installer kubernetes mac os x – Tutorial kubernetes débutant

https://128mots.com/index.php/2021/01/31/installer-kubernetes-mac/

Installer kubernetes mac os x – Tutorial kubernetes débutant

Publié le 31 janvier 2021 par Jean-Paul

Kubernetes mac os x, voici des explications pour installer facilement kubernetes sur son mac.

Kubernetes, ou k8s, est une plate-forme open source, lancée par Google, qui a commencé comme un simple outil d’orchestration de conteneurs mais est devenue une plate-forme native pour le cloud.

Introduction – installer kubernetes mac

Sur mac os x une des méthodes les plus rapide pour installer Kubernetes est d’utiliser HoweBrew (voir le lien : Homebrew). Homebrew est un système de gestion de progiciels gratuit et open source qui simplifie l’installation de logiciels sur le système d’exploitation mac OS x Apple.

J’ai démarrer une console et executé la commande :

brew install kubectl

Vous devriez obtenir une sortie du type :

==> Pouring kubernetes-cli-1.20.2.catalina.bottle.tar.gz
==> Caveats
zsh completions have been installed to:
  /usr/local/share/zsh/site-functions
==> Summary
🍺  /usr/local/Cellar/kubernetes-cli/1.20.2: 246 files, 46.1MB

A la fin de l’installation vous pouvez vérifier que kubernetees est bien installer :

kubectl version --client

kubectl version --client
Client Version: version.Info{Major:"1", Minor:"20", GitVersion:"v1.20.2", GitCommit:"faecb196815e248d3ecfb03c680a4507229c2a56", GitTreeState:"clean", BuildDate:"2021-01-14T05:14:17Z", GoVersion:"go1.15.6", Compiler:"gc", Platform:"darwin/amd64"}

Vous pouvez également installer autocomplétion de shell : kubectl fournit un support d’auto-complétion pour Bash et Zsh :

brew install bash-completion@2

Ensuite :

export BASH_COMPLETION_COMPAT_DIR="/usr/local/etc/bash_completion.d"
[[ -r "/usr/local/etc/profile.d/bash_completion.sh" ]] && . "/usr/local/etc/profile.d/bash_completion.sh"

Activation de l’autocomplétion :

Lancez les commandes suivantes :

echo 'source <(kubectl completion bash)' >>~/.bashrc
kubectl completion bash >/usr/local/etc/bash_completion.d/kubectl
echo 'alias k=kubectl' >>~/.bashrc
echo 'complete -F __start_kubectl k' >>~/.bashrc

Installer Minikube :

minikube est un Kubernetes local qui vise à faciliter l’apprentissage et le développement pour Kubernetes.

J’ai lancé les commandes :

brew install minikube

Liens externes :

Website minikube.sigs.k8s.io

Website kubernetes.io

Liens internes installer kubernetes mac :

Qiskit textbook : tutorial d’algorithme quantique en Python

https://128mots.com/index.php/2021/01/28/qiskit-textbook-qiskit-tutorial-algorithme-quantique-programmation/

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

runtimeerror: attempting to deserialize object on a cuda device

Publié le 31 janvier 2021 par Jean-Paul

runtimeerror: attempting to deserialize object on a cuda device but torch.cuda.is_available() is false. if you are running on a cpu-only machine, please use torch.load with map_location=torch.device(‘cpu’) to map your storages to the cpu, How to solve the error presented here with Pytorch in python in the context of deeplearning?

Introduction

First of all, usually this error is encountered when trying to run your model code on the machine’s CPU instead of the GPU.

lib/python3.6/site-packages/torch/serialization.py", ... in validate_cuda_device
    raise RuntimeError('Attempting to deserialize object on a CUDA '
RuntimeError: Attempting to deserialize object on a CUDA device but 
  torch.cuda.is_available() is False. If you are running on a CPU-only machine, 
  please use torch.load with map_location='cpu' to map your storages to the CPU.

In this case you encounter an error which is a raised RuntimeError exception.

This means that you are looking to deserialize an object using code that runs with the GPU while the GPU is disabled.

Explanation – runtimeerror: attempting to deserialize object on a cuda device

Then, The error then occurs when you try to load the pytorch model using the torch.load instruction (see Website pytorch.org)

Example :

torch.load('mymodel.pt')

So when the reloading is done with the wrong configuration you get the error:

lib/python3.6/site-packages/torch/serialization.py", ... in validate_cuda_device
    raise RuntimeError('Attempting to deserialize object on a CUDA '
RuntimeError: Attempting to deserialize object on a CUDA device but 
  torch.cuda.is_available() is False. If you are running on a CPU-only machine, 
  please use torch.load with map_location='cpu' to map your storages to the CPU.

Solution

Also, As you can see in the Pytorch documentation (see Website pytorch.org) there is a map_location parameter – (a function, torch.device, string or a dict specifying how to remap storage locations).

This is where we must force the parameter to specify the location to use.

Note that if your model is registered and saved as using the GPU you will have to specify GPU otherwise you will have to put CPU. The objective here is to put a consistent parameter between what has been saved and what is reloaded.

And If you want to force CPU usage :

torch.load('mymodel.pt',map_location='cpu')

For CPU usage you can also use :

torch.load('mymodel.pt', map_location=torch.device('cpu'))

# Load on first GPU
torch.load('mymodel.pt', map_location=lambda storage, loc: storage.cuda(1))
# Lord on GPU 0 and 1
torch.load('mymodel.pt', map_location={'cuda:1':'cuda:0'})

External links :

Website pytorch.org

Website discuss.pytorch.org

Internal links – runtimeerror: attempting to deserialize object on a cuda device but torch.cuda.is_available() is false :

Pytorch tutorial Deep Learning with Python

https://128mots.com/index.php/en/2020/11/20/deep-learning-pytorch-from-0-to-1-2/

https://128mots.com/index.php/en/category/non-classe-en/

Qiskit textbook : tutorial d’algorithme quantique en Python

Publié le 28 janvier 2021 par Jean-Paul

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 sur le qiskit textbook https://qiskit.org.

Circuits dans Qiskit :

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 : Website 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 :

[latexpage]
$$ |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 : Website www.maths-cours.fr)

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

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

Ainsi si on mesure un qubit q on a :

[latexpage]
$$ |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.

Qiskit tutorial et Qiskit textbook – Liens internes :

Ordinateur quantique prix – Combien coûte un ordinateur quantique ?

https://128mots.com/index.php/2021/01/26/ordinateur-quantique-prix/

Algorithme Quantique – algorithme de tri quantique

https://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/

COBOL UPON ET DISPLAY UPON – Apprendre le COBOL

Publié le 28 janvier 2021 par Jean-Paul

COBOL UPON ET COBOL DISPLAY UPON, DISPLAY provoque l’affichage et l’instruction UPON entraîne l’affichage des données sur le périphérique demandé.

Fonctionnement de DISPLAY … UPON

La présence de la phrase UPON peut affecter le périphérique de sortie utilisé.

DISPLAY "HELLO WORLD" UPON SYSTEM-OUTPUT 
DISPLAY "ERROR" UPON SYSTEM-OUTPUT

DISPLAY . . . UPON SYSOUT est traité comme si SYSOUT IS SYSOUT était précisé dans un paragraphe SPECIAL-NAMES sauf si SYSOUT a été déclaré autrement.

Sur le système COBOL 16 bits, la taille maximale COBOL d’un programme est de 256 Mo pour les données et de 4096 Mo pour le code.

Aussi, lorsque DISPLAY contient plus de un opérande, la taille totale de l’élément qui va être affiché corresponds à la somme de toutes les tailles des opérandes, et les valeurs sont alors concaténées.

Si le STATEMENT : WITH NO ADVANCING n’est pas utilisé. Alors le positionnement du périphérique de sortie standard est réinitialisé à la position la plus à gauche sur une nouvelle ligne.

Liens Externes :

Website fr.wikipedia.org

Website www.developpez.net

Website ibmmainframes.com

COBOL UPON Liens Internes :

Apprendre COBOL – Tutorial pour apprendre le COBOL

https://128mots.com/index.php/2020/10/08/apprendre-cobol/

Apprendre le COBOL – Tutorial pour apprendre COBOL

https://128mots.com/index.php/2020/10/07/apprendre-le-cobol/

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

importerror: iprogress not found. please update jupyter and ipywidgets

Publié le 27 janvier 2021 par Jean-Paul

importerror: iprogress not found. And this is the solution if you get this error .

When trying to install Jupyter Widgets : Please update jupyter and ipywidgets. See https://ipywidgets.readthedocs.io/en/stable/user_install.html

Error

You can check on the Website ipywidgets.readthedocs.io to get the complete user install guide for Jupyter Widgets.

ImportError: IProgress not found. Please update jupyter and ipywidgets. See https://ipywidgets.readthedocs.io/en/stable/user_install.html

To solve this problem you need to setup Iprogress on jupyter lab :

pip install ipywidgets
jupyter nbextension enable --py widgetsnbextension

importerror: iprogress not found – Internal Links :

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

https://128mots.com/index.php/category/les-reseaux-sociaux/

Greedy algorithm python – Coin change problem

https://128mots.com/index.php/en/2021/01/21/greedy-algorithm-python/

Note for old version of jupyter

Installing ipywidgets automatically configures Jupyter Notebook to use widgets.

This package does this by depending on the widgetsnbextension package. This package configures Jupyter Notebook to display and use widgets.

If you have an old version of Jupyter Notebook installed, you may need to manually enable the ipywidgets notebook extension with.

jupyter nbextension enable --py widgetsnbextension

Note for separate environnements between JupyterLab and IPython

If JupyterLab and the IPython kernel are installed in different environments.

You need to do it in 2 steps :

Install jupyterlab_widgets

conda install -n base -c conda-forge jupyterlab_widgets

Install ipywidgets on each kernels

conda install -n py36 -c conda-forge ipywidgets

importerror: iprogress not found – External Links :

Website ipywidgets.readthedocs.io

Example using Python Jupyter Lab :

Now, to give change to an x value of using these coins and banknotes, then we will check the first element in the array. And if it’s greater than x, we move on to the next element. Otherwise let’s keep it. Now, after taking a valuable coin or bill from the array of coinAndBill [i], the total value x we need to do will become x – coinAndBill [i].

Here is the associated greedy python algorithm:

  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0
  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];
renduMonnaieGlouton(33)#Exemple sur 33 euros

>>> Ordinateur quantique prix – Combien coûte un ordinateur quantique ?

Publié le 26 janvier 2021 par Jean-Paul

Le prix d’un ordinateur quantique évolue entre 10 millions de dollars $ et 25 millions de dollars $. Voici quelques repère pour comprendre le prix d’un ordinateur quantique. L’article vous permettra de comprendre comment la course au quantique s’articule entre les différentes technologies et acteurs.

Introduction

Récemment Google a annoncé que sa puce Sycamore était la première à démontrer la «suprématie quantique» (article ici). Cela consiste à prouver que la résolution d’un problème à l’aide d’un algorithme quantique est plus efficace qu’à l’aide d’un algorithme classique. Aussi IBM construit actuellement un ordinateur quantique de 1 121 qubits, Condor (lien). Aussi il sera stocké à l’intérieur d’un « réfrigérateur » à dilution (voir ici). Et le but est de créer un ordinateur quantique et de le rendre disponible en ligne d’ici 2023.

Pour expliquer le prix d’un ordinateur quantique il faut dans un premier temps situer les différents acteurs de cette course au quantique et situer les dates importantes.

Les acteurs et l’écosystème de l’informatique quantique

PRINCIPAUX Acteurs dans le Hardware (CONSTRUCTEURS d’ordinateur quantique ET DE CIRCUITS) :

IBM : IBM construit un ordinateur quantique avec 1121 qubits d’ici 2023. Vous pouvez déjà programmer sur des systèmes Quantiques IBM via le cloud IBM sur des simulateurs ou des ordinateurs quantique réel via IBM Quantum Experience (voir mon article sur la programmation quantique avec IBM qiskit)

GOOGLE : Sycamore est un processeur quantique de 53 qubits créé par Google (en savoir plus)

INTEL : Intel crée un processeur « Tangle Lake ». Comme ses concurrents IBM, Google, Rigetti, IMEC et BBN Technologies Intel se base sur une architecture de qubits supraconducteurs.

ALICE AND BOB : développe une solution qui permet de résoudre le problème des erreurs quantiques.

D-WAVE : La société D-WAVE crée et commercialise des ordinateurs quantiques.

IONQ : crée un ordinateur quantique à ions piégés.

RIGETTI : Rigetti crée un ordinateur full-stack pour l’informatique hybride classique et quantique.

BRANE CELL

PSIQuantum : L’objectif de PsiQuantum est de construire le premier ordinateur quantique à usage général utile au monde avec au moins 1 millions de Qubits. La société travaille par exemple sur des qubits photoniques.

TURING :XGR-1 est une mémoire quantique révolutionnaire de la première génération de Turing.

QILIMANJARO :Enfin, Qilimanjaro se concentre sur des architectures de qubit de haute qualité de recuit quantique cohérent.

PRINCIPAUX Acteurs dans le SOFTWARE (KIT DE développement, Logiciels, Solutions cryptographiques)

IBM Qiskit :IBM Qiskit permet aux développeurs de créer des algorithmes quantiques à l’aide d’une interface en Python.

MICROSOFT : Q# est un langage de microsoft de programmation qui permet la programmation quantique.

1QBIT : 1QUBIT est une société de service en informatique quantique.

QCWARE : Egalement QCWARE une entreprises qui se concentre sur la création d’algorithmes quantiques.

QUSOFT QuSoft est le centre de recherche néerlandais sur les logiciels quantiques. Sa mission est de développer de nouveaux protocoles, algorithmes et applications pouvant être exécutés sur des prototypes de petite et moyenne taille d’un ordinateur quantique.

STRANGE WORKS : Commercialise des logiciels d’informatique quantiques.

Ordinateur quantique prix – Indication du prix d’un ordinateur quantique

Le prix d’un ordinateur quantique D-WAVE 200Q est par exemple d’environ 15 millions de dollars (15 m$). De plus, cette même entreprise commercialisait un ordinateur quantique 1000Q quelques années auparavant. Et en 2011, D-Wave lance son premier modèle d’ordinateur quantique qui sera disponible dans le commerce. Aussi il coûte 10 millions de dollars. Cela donne une bonne estimation de combien coûte un ordinateur quantique.

Greedy algorithm python – Coin change problem

Publié le 21 janvier 2021 par Jean-Paul

A greedy python algorithm (greedy algorithm python) greedily selects the best choice at every step. He hopes that these choices lead to the optimal overall solution to the problem. So, a greedy algorithm does not always give the best solution. However in many problems this is the case.

Greedy Algorithm: Introduction

The problem of giving change is formulated as follows. How to return a given sum with a minimum of coins and banknotes?

Here is an example in python of the resolution of the problem:

If we consider the Euro monetary system without the cents we have the whole

EURO = (1, 2, 5, 10, 20, 50, 100, 200, 500)

Greedy algorithm python : Coin change problem

Here is the associated greedy python algorithm:

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(33)#Exemple sur 33 euros

The output for 33 euro is then:

Another example with 55 euro of greedy python algorithm:

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(55)#Exemple sur 55 euros

Output :

50
5

Conclusion

The problem of giving change is NP-difficult relative to the number of coins and notes of the monetary system considered (euro in this example). To go further, we can demonstrate that for certain so-called canonical money systems, the use of a greedy algorithm is optimal. A monetary system is said to be canonical if for any sum s the greedy algorithm leads to a minimal decomposition.

NP difficulty is the defining property of a class of problems informally « at least as difficult as the most difficult NP problems ».

A simple example of an NP-hard problem is the sum of subset problem. If P is different from NP then it is unlikely to find a polynomial time algorithm that exactly solves this problem.

External links :

Website math.univ-lyon1.fr

Website www.dil.univ-mrs.fr

Internal links python greedy algorithm :

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

Algorithme Quantique – algorithme de tri quantique

Levenshtein Python Implémentation algo Wagner & Fischer

https://128mots.com/index.php/category/non-classe/

Algorithme glouton python – Exemple rendu de monnaie

Publié le 21 janvier 2021 par Jean-Paul

Un algorithme glouton python sélectionne goulûment le meilleur choix à chaque étape. Il espère que ces choix mènent à la solution globale optimale du problème. Ainsi, un algorithme glouton ne donne pas toujours la meilleure solution. Cependant dans de nombreux problèmes c’est le cas.

Algorithme glouton : Introduction

Le problème du rendu de monnaie est formulé de la façon suivante. Comment rendre une somme donnée avec un minimum de pièces et billets ?

Voici un exemple en python de la résolution du problème :

Si on considère le système monétaire Euro sans les centimes on a l’ensemble

EURO = (1, 2, 5, 10, 20, 50, 100, 200, 500)

Algorithme glouton rendu de monnaie python

Maintenant, pour rendre la monnaie sur une valeur x de en utilisant ces pièces et billets, alors nous vérifierons le premier élément du tableau. Et si il est supérieur à x, nous passons à l’élément suivant. Sinon le gardons. Maintenant, après avoir pris une pièce ou un billet de valeur issu du tableau de pieceEtBillet [i], la valeur totale x que nous devons faire deviendra x – pieceEtBillet [i].

Voici l’algorithme glouton python associé :

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(33)#Exemple sur 33 euros

La sortie pour 33 euro est alors :

Autre exemple avec 55 euro d’algorithme glouton python :

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(55)#Exemple sur 55 euros

La sortie est alors :

50
5

Conclusion

Le problème du rendu de monnaie est NP-difficile relativement au nombre de pièce et billet du système monétaire considéré (euro dans cet exemple). Pour aller plus loin on pourra démontrer que pour certains systèmes de monnaie dits canoniques, l’utilisation d’un algorithme glouton est optimal. Un système monétaire est dit canonique si pour toute somme s l’algorithme glouton conduit à une décomposition minimale.

La difficulté NP est la propriété déterminante d’une classe de problèmes informellement « au moins aussi difficiles que les problèmes les plus difficiles de NP ».

Un exemple simple de problème NP-hard est le problème de somme de sous-ensembles. Si P est différent de NP alors il est peu probable de trouver un algorithme en temps polynomial qui résout de façon exact ce problème.

Liens externes

Website math.univ-lyon1.fr

Website www.dil.univ-mrs.fr

Liens internes

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

Algorithme Quantique – algorithme de tri quantique

Levenshtein Python Implémentation algo Wagner & Fischer

https://128mots.com/index.php/category/non-classe/