Mar 17

Algorithmes récursifs

By Fabien Aubret | Informatique, Intermédiaire Raspberry Pi | No Comments

I- Introduction à la récursivité

Récursif ou itératif… Voilà un sujet de discussion encore non élucidé entre les développeurs du monde entier. Pourtant, avant de chercher à argumenter dans un sens ou dans l’autre autour de cette question, il faut déjà comprendre ce que l’on appelle algorithme récursif (et donc algorithme itératif). Si l’on remonte ainsi aux débuts de l’informatique, un programme en langage machine s’exécutait « verticalement » en lisant tour à tour les instructions écrites, autorisant néanmoins l’instruction « jump » qui permettait de sauter vers une étape particulière du programme. L’informatique évoluant, la puissance des ordinateurs aussi, on a pu arriver petit à petit à des algorithmes plus ou moins efficaces que ces derniers. Parmi les voie d’optimisation, on a développé les algorithmes récursifs, c’est-à-dire des algorithmes qui s’appellent eux-mêmes lors de l’exécution et qui sont donc plus « compactes » mais aussi et surtout plus compréhensibles selon les cas. Des avantages de la programmation récursive, on pourra souligner :

La facilité d’explication de certains algorithmes beaucoup plus complexes
L’optimisation du code par les compilateurs qui est rendue plus facile par l’abstraction
L’existence de structures qui se prêtent facilement à l’utilisation de tels algorithmes

Encore aujourd’hui, la programmation récursive constitue un outil à part entière et on peut souvent « simplifier » nos codes en faisant appel à des fonctions récursives. De plus, la plupart des langages auxquels nous accédons aujourd’hui ont un environnement qui permet l’utilisation de fonctions récursives. Cela se résume bien souvent à la gestion astucieuse d’une pile de stockage mémoire…

Dans cet article, j’aborderai un exemple commun d’algorithme récursif en implémentant le calcul de la fonction mathématiques factorielle.

II- Programmation

a) La fonction factorielle

Avant de se lancer dans la programmation, j’ai souhaité écrire quelques lignes sur la fonction factorielle afin que l’on parle tous de la même chose et que l’on s’accorde sur les termes et notations.
En mathématiques, la fonction factorielle est définie de la manière suivante :

Dès lors, on note l’image de x par la fonction factorielle. A titre indicatif, on notera les valeurs suivantes :

On remarque ainsi que l’on peut écrire la fonction factorielle de la manière suivante :

Et nous voilà ainsi arrivés à l’écriture dont nous aurons besoin dans la suite de notre article. En effet, la formule ci-dessus nous permet de calculer la factorielle de « rang » n en calculant auparavant la factorielle de « rang » n-1. On peut alors répéter l’opération jusqu’à arriver à la factorielle de « rang » 0 dont la valeur est définie à 1

b) Du code, enfin…

Dans un premier temps, je vous propose une implémentation « à l’ancienne » de la fonction factorielle. En fait, cela correspond à un algorithme itératif, littéralement qui va itérer sur notre produit jusqu’à arriver à la fin :

import time
def factorielle(n):
    resultat = 1
    for k in range(1, n+1):
        resultat *= k
    return resultat
 
clock1 = time.perf_counter_ns()
print(factorielle(1000))
clock2 = time.perf_counter_ns()
print("Temps d'exécution: " + str(clock2 - clock1) + "ns")

Dans ce script, j’ai inclus le calcul du temps d’exécution qui pourrait bien nous être utile pour la suite…

Quant à l’algorithme récursif, il est en fait beaucoup plus clair car on applique directement les formules établies dans la première partie. Cet algorithme est dit récursif car il s’appelle lui-même dans sa fonction. Cela devrait être bien plus explicite à la lecture du code suivant :

import time
 
def factorielle(n):
    if n == 0:
        return 1
    else:
        return n * factorielle(n-1)
 
clock1 = time.perf_counter_ns()
print(factorielle(100))
clock2 = time.perf_counter_ns()
 
print("Temps d'exécution: " + str(clock2 - clock1) + "ns")

A la lecture du temps d’exécution des deux programmes, on remarque que l’algorithme itératif est bien plus rapide (environ deux fois) mais l’algorithme récursif est bien plus simple à comprendre. Du moins, il est plus proche de la vision mathématique que l’on a de la fonction. On peut cependant lui trouver une limite si l’on demande à calculer factorielle(1000), Python refusera alors le calcul. En effet, lorsque le nombre d’appel de l’algorithme (« profondeur » de récursivité) est trop élevé, l’occupation mémoire de l’algorithme devient trop importante et Python met alors en place une limite pour éviter les erreurs.

III- Conclusion

Au cours de cet article, nous avons abordé les fondamentaux de la programmation récursive. Si l’intérêt ne semble à première vue pas gigantesque, comprenez que ce type de programme nous permet de calculer des formes fractales ou autres étranges beautés mathématiques d’une manière souvent bien plus élégante que la méthode récursive.

L’objectif n’est pas ici de maitriser un algorithme en particulier mais bien de comprendre l’intérêt d’une telle méthode pour un développeur confronté à un problème bien particulier. Nous aurons sans doute par la suite l’occasion d’aborder de nouveau ce type de programmation.

Mar 07

Electronique, approche théorique

By Fabien Aubret | Intermédiaire Arduino, Intermédiaire Raspberry Pi | No Comments

I- Introduction

Ne vous êtes-vous jamais posé la question de savoir comment ou pourquoi le circuit électronique que vous avez devant les yeux exécute réellement ce que vous lui demandez ? Non ? Parce que nous oui !
En fait, pour comprendre cette science de la théorie, il faut s’intéresser aux phénomènes physiques en jeu et, malheureusement (ou avec joie pour d’autre), il faudra s’intéresser aux outils mathématiques afin de comprendre pleinement ce à quoi nous sommes confrontés.
Si ce tutoriel présentera certaines lois classiques d’électronique comme les lois de Kirchhoff, nous nous intéresserons aussi en détail à l’analyse de l’évolution d’une tension dans un circuit RC (Résistance / Condensateur).
Bien sûr, dans ce tutoriel, finies les contraintes de la vraie vie, nous vivrons dans un monde sans pertes, sans dissipation, bref un monde idéal. En mathématiques ou en physique, on appelle ça un modèle et croyez nous, il vaut mieux pour que nous restions dans ce cadre…
Certaines notions abordées sont étudiées en classes préparatoires scientifiques (maths sup/ maths spé). Nous essaierons de vulgariser au maximum. C’est l’objet de ce tutoriel et nous ferons en sorte que le plus grand nombre puisse comprendre ce que nous expliquons. N’hésitez pas à poser des questions complémentaires en commentaire, ou à nous corriger si des coquilles se glissent dans nos présentations !

II- Lois de Kirchhoff

Avant d’aller plus loin, il nous sera nécessaire de nous baser sur deux principes « fondamentaux » en électronique et sur un principe qui, pour le coup, est considéré comme fondamental pour la physique toute entière. Le premier, c’est celui de la conservation de la charge, il caractérise le fait que dans un système fermé (sans transfert de matière avec l’extérieur), la charge se conserve dans l’ensemble du circuit.
Partant de cette constatation, Kirchhoff, physicien allemand, a établi deux lois majeures en électronique, la loi des nœuds et la loi des mailles.

Loi des noeuds

Loi des mailles

III- Quelques formules

Il nous faudra admettre quelques formules pour étudier un système électronique. Je vous propose d’étudier ici les caractéristiques d’un condensateur et d’une résistance (circuit RC). Voyons ensemble quelques formules qui pourraient bien nous être utiles:

Pour le condensateur:

$q=\frac{di(t)}{dt}$
q est la charge du condensateur, i(t) est l’intensité du courant qui le traverse à l’instant t

$q=C.u(t)$
q est encore la charge du condensateur, C est sa capacité en farad, u(t) la tension à ses bornes à l’instant t

Pour la résistance:

$u(t)=R.i(t)$
u(t) est la tension aux bornes de la résistance à l’instant t, R sa résistance en ohm et i le courant qui la traverse à l’instant t

Notion de dérivation mathématiques:

Un outil important qui nous servira tout au long de notre étude est l’utilisation des dérivées en mathématiques. Pour faire simple, c’est un outil qui nous permet d’étudier les variations d’une fonction. En fait, c’est un outil extrêmement puissant dont nous aurions du mal à nous passer en physique comme en mathématiques. Dans nos exemples, nous étudierons l’évolution de la tension aux bornes d’un dipôle et nous devrons donc faire appel aux dérivées. Si nous ne verrons pas vraiment ensemble comment dériver telle ou telle fonction, nous vous donnerons les dérivées dont nous aurons besoin. En réalité, il est nécessaire de connaitre un certain nombre de dérivées de fonctions usuelles et de fonctions composées lorsqu’on travaille dans le monde mathématico-physique. D’un point de vu des notations uniquement, vous devez savoir que les trois notations suivantes sont équivalentes:
$\frac{dx}{dt} = \dot{x} = (x)'$

Attention cependant, la dernière notation n’est absolument pas rigoureuse dans ce cadre, on symbolise plus régulièrement la dérivation d’une fonction de la manière suivante:
$f'(x)$

Nous utiliserons très régulièrement à première et la seconde notation, bien moins la dernière, plus utilisées en mathématiques cependant.
Posons donc les bases de notre étude, un petit schéma électronique…

IV- Présentation de l’étude

Schéma du circuit RC étudié par l’approche mathématiques de l’électronique

Le condensateur, est initialement chargé d’une tension $u_0$

V- Début de l’étude

On a placé nos dipôles en convention générateur. On est face à un circuit RC-Série, le courant dans le circuit est donc constant et on peut écrire, grâce à la loi des mailles:
$u_r(t) + u_c(t) = 0$
Or, la loi d’Ohm nous donne:
$u_r(t) = R.i(t)$
Et les formules précédentes sur le condensateur donnent :
$u_c(t) = \frac{q(t)}{C}$
Alors, finalement il vient:
$R.i(t) + \frac{q(t)}{C} = 0$
$\leftrightarrow \frac{dq}{dt} + \frac{1}{RC}.q(t) = 0$

On pose arbitrairement
$\tau = R.C$
On obtient alors:
$\frac{dq}{dt} + \frac{1}{\tau}.q = 0$
Autrement dit:
$\dot{q}+\frac{1}{\tau}.q = 0 (E)$

Cette équation est qualifiée d’équation différentielle du premier ordre, linéaire, sans second membre (donc homogène) et à coefficients constants.
Ouhlaaaa, une grande et vaste notion vient d’être abordée, celle des équations différentielles. Lançons-nous dans la résolution de celle que nous avons ci-dessus. Pour simplifier, une équation différentielle est une équation qui, à la différence d’une équation « algébrique », admettra une solution sous la forme d’une fonction. Si vous n’avez jamais eu de formation scientifique sur ce point, la résolution que nous allons détailler ci-dessous pourra vous sembler un peu complexe. Nous allons essayer d’expliquer chaque point et de détailler chacune des décisions que nous prendrons pour arriver à la résolution. Heureusement pour nous, cette équation est dite homogène, c’est-à-dire que son second membre est nul, et vous ne le savez peut-être pas encore mais cela va largement nous simplifier le travail puisque la solution est simplement une formule, là encore à connaitre par cœur lorsque l’on est en étude scientifique…
En fait, les équations différentielles ne sont pas toutes aussi simples, on a parfois des membres doublements dérivés (équations différentielles du second ordre), avec second membres, ou mêmes les deux à la fois.

VI- Résolution de l’équation différentielle

Rappelons (E):
$\dot{q}+\frac{1}{\tau}.q = 0 (E)$
Comme nous l’avons vu, cette équation différentielle est plus simple à résoudre. C’est une équation dite « homogène » qui se résout par la simple application d’une formule à connaître si l’on souhaite pouvoir en résoudre soi-même plus tard. Cette formule implique l’utilisation de la fonction exponentielle, nul doute que vous ayez déjà entendu ce mot puisqu’il est largement utilisé pour caractériser une évolution rapide d’un paramètre quelconque. En effet, la courbe caractéristique de la fonction exponentielle est la suivante:

Représentation de la fonction exponentielle

Représentation graphique de la fonction exponentielle tracée à l’aide du logiciel GeoGebra

On comprend alors cette augmentation rapide. Je n’entrerai pas en détail dans l’étude de cette fonction, c’est une fonction très utile, qui est caractérisée par deux points:
$\frac{d}{dx}(e^x) = e^x$
$e^0 = 1$
Bien, il est temps de revenir à notre équation différentielle. Cette dernière admet donc comme solutions les fonctions de la forme:
$q(t) = A.e^{\frac{-t}{\tau}} , A \in \mathbb{R}$

q(t)=Ae^((-t)/τ) ,A∈R
Nous avons bien dit les fonctions car il y en a une infinité en théorie grâce à la constante « A ». Bien sûr, nous allons devoir définir cette constante afin qu’elle caractérise exactement le circuit que nous avons choisi au départ. Pour cela, je vous propose de réinjecter notre solution dans $u_c(t)$ . Souvenons-nous d’abord de l’expression de &latex u_c(t)&s=1&bg=f8f8f8$:
$q = C.u(t)$
$\leftrightarrow u_c(t) = \frac{q}{C}$
On remplace alors « q » par la solution déterminée ci-dessus, on a alors:
$u_c(t) = \frac{A.e^{\frac{-t}{\tau}}}{C}$
Maintenant, il faut déterminer « A », pour cela on va utiliser les conditions initiales, en effet, on avait spécifié qu’à t = 0, $u_c(t) = u_0$ , on a alors:
$u_c(t=0)=\frac{A}{C}$
$\leftrightarrow A = C.u_0$
Voilà notre constante exprimée, remplaçons « A » dans la solution par cette valeur:
$q(t) = C.u_0.e^{-\frac{t}{\tau}}$
Voilà, on a désormais l’équation qui régit la variation de la charge dans notre circuit. Mais pour nous, le plus intéressant serait de connaître l’évolution de la tension aux bornes du condensateur. Pour cela, on reprend notre formule de la tension du condensateur:
$u_c(t) = \frac{q}{C}$
Et on injecte cette fois-ci notre solution finale de l’équation différentielle, on a alors:
$u_c(t) = \frac{C.u_0.e^{-\frac{t}{\tau}}}{C}$
En simplifiant, il vient:
$u_c(t) = u_0.e^{-\frac{t}{\tau}}$ avec $\tau = R.C$

Ensuite, on peut rentrer cette formule dans un logiciel qui permet de tracer des courbes, comme Geogebra ou Excel et observer l’effet d’une résistance ou d’une capacité différente.
Pour notre part, avec une résistance de 850 ohms, une capacité de 0,04 Farads et une tension $u_0 = 4V$ , on obtient la courbe suivante:

Evolution de la tension dans un circuit RC

Représentation graphique de l’évolution de la tension aux bornes d’un condensateur dans un circuit RC obtenue à l’aide du logiciel GeoGebra

Le temps, en secondes, est en abscisse et la tension aux bornes du condensateur, en volts, est en ordonnée.

VII- Conclusion

Si vous avez eu le courage de lire en intégralité ce tutoriel, félicitation !
Vous devriez maintenant être en mesure d’étudier d’une manière plus mathématique un circuit électronique relativement simple. Relisez le tutoriel, comprenez chaque étape, posez vos questions et entraînez-vous avec des circuits un poil plus complexe avec deux résistances ou deux condensateurs. Evidemment, dans ce cas, il faudra utiliser les formules pour retrouver la résistance équivalente de deux résistances en série ou de deux condensateurs en série.

Ce tutoriel a été écrit par Fabien Aubret, relu et vulgarisé par Thomas Aubret et Grégoire Aubret.
Une relecture a été effectuée par un professeur de physique diplômé de l’Ecole Normale Supérieure (ENS), un grand merci à lui.

Oct 01

Illustration tutoriel utilisation des entrées avec Raspberry Pi

[Tutoriel] Les entrées Raspberry Pi

By Fabien Aubret | Intermédiaire Raspberry Pi | 4 Comments

Bonjour et bienvenu(e),

Ce tutoriel sera consacré à l’utilisation basique des entrées grâce au langage Python. Si vous êtes un parfait débutant, sachez que nous allons tout vous expliquer de A à Z afin que vous puissiez être en mesure de gérer vous-mêmes les entrées de votre Raspberry Pi à la fin de ce tutoriel.
Pour commencer, il faut savoir qu’en comparaison avec l’Arduino, le Raspberry Pi ne possède pas d’entrées analogiques par défaut. Concrètement, cela signifie que notre contrôleur ne sera pas en mesure d’interpréter le signal émis par un potentiomètre. En effet, il existe deux types de signaux : analogiques et digitaux. Le premier délivre une tension variable interprétée par un contrôleur équipé d’entrées analogiques qui convertit cette tension en une variable comprise entre 0 et 1024. Le second type de signal, le signal digital est plus simple. Il est de type « tout ou rien » ce qui signifie qu’il ne peut prendre que deux valeur : 1= HAUT ou 0= BAS

Lorsque cette partie du tutoriel aura été comprise, vous serez beaucoup plus à l’aise avec les termes que nous emploierons plus tard.

Commençons dès maintenant l’utilisation des entrées digitales.

Connectons un bouton comme le montre le schéma suivant sur notre Raspberry Pi :

Ce qu’il faut savoir :

La valeur de la résistance est égale à 10kohms

Voilà pour le branchement, nous utiliserons ce montage tout au long du tutoriel.

Avant de commencer la programmation, il faut signaler que chaque broche du Raspberry Pi a un « numéro » attitré. Là où cela devient plus complexe, c’est que dans notre script, nous avons deux « bases » disponibles. C’est-à-dire que chaque broche à deux nombres différents qui peuvent l’identifier. Ces deux « bases », on les appelle BCM pour BroadCom (le nom du processeur qui équipe le Raspberry Pi) ou BOARD (Board = Plaque en anglais). Pourquoi ces deux noms différents ? Parce que le premier prend en compte l’identifiant de la broche sur la puce BroadCom tandis que le second, BOARD, ne prend en compte que les broches qui sont disponibles sur le connecteur Raspberry Pi 26 broches.

Ainsi, la première chose à faire dans un programme est de définir la base de référence. Tout d’abord, il va falloir installer la bibliothèque Python qui contient un ensemble de fonction permettant le contrôle de notre Raspberry Pi. Théoriquement, cette librairie est présente par défaut. Vérifions en écrivant ceci dans la console de votre Raspberry Pi :

1	sudo python

1	import RPi.GPIO as GPIO

Vous avez une erreur ? C’est que la librairie n’est pas installée. Il va falloir faire ceci :

Commencez par écrire ceci dans la console du raspberry :

1	sudo wget https://pypi.python.org/packages/source/R/RPi.GPIO/RPi.GPIO-0.5.7.tar.gz

Ensuite, écrivez ceci :

1	sudo tar zxf RPi.GPIO-0.5.7.tar.gz

Puis :

1	cd RPi.GPIO-0.5.7

Et enfin :

1	sudo python setup.py install

Ensuite, vous pouvez retenter les deux commandes suivantes :

1	sudo Python

1	Import RPi.GPIO as GPIO

Qui devraient fonctionner cette fois-ci. Dans le cas inverse, laisser un post sur le forum ou en commentaire.

Bien, votre IDLE Python est prêt. Nous allons pouvoir commencer à coder. Voici votre premier script que nous avons commenté comme il se doit afin que vous le compreniez

#On importe la librairie RPi.GPIO qui va nous permettre de contrôler les GPIO du Raspberry Pi
 
#Attention : Notez qu’on importe cette librairie en la renommant GPIO
 
import RPi.GPIO as GPIO
 
#On importe la librairie time, inclue par défaut avec Python et qui va nous permettre
 
#de faire des pauses dans le programme
 
Import time
 
#On dit au programme qu’on utilisera les identifiants associés au mode « Board » GPIO.setmode(GPIO.BOARD)
 
#L’identifiant de notre GPIO est 25 en mode « BCM » et 22 en mode « BOARD »
 
#On déclare donc la broche 22 en entrée (GPIO.IN)
 
GPIO.setup(22, GPIO.IN)
 
#On lit l’état du GPIO 22 qu’on stocke dans A
 
A = GPIO.input(22)
 
#On affiche A
 
Print(A)
 
#On utilise la librairie Time pour faire une pause de 0,5 sec
 
Time.sleep(500)

Voilà votre premier programme. En fait, l’ensemble des programmes qui utiliseront les entrées d’une manière basique auront toujours cette même forme.

Pour exécuter ce programme, il suffit de l’enregistrer et d’appuyer sur F5. Ensuite, vous remarquerez que la valeur de la variable « A » change lorsque le bouton est appuyé ou relâché.

Merci d’avoir suivi ce tutoriel, n’hésitez pas à laisser vos commentaires et à partager sur les réseaux sociaux si vous avez aimé.

Ce tutoriel sera ajouté dans la catégorie « Tutoriels Raspberry Pi », n’hésitez pas à laisser vos avis !