Image de une - Algorithmes récursifs

Algorithmes récursifs

By | 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éfinition de la fonction factorielle
Dès lors, on note  l’image de x par la fonction factorielle. A titre indicatif, on notera les valeurs suivantes :

Valeurs de la fonction factorielle

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

Forme réduite factorielle
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 :

1
2
3
4
5
6
7
8
9
10
11
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 :

1
2
3
4
5
6
7
8
9
10
11
12
13
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.

Se connecter au WiFi avec le raspberry Pi 3

Premiers pas avec un Raspberry

By | Non classé | No Comments

Bonjour à toutes et à tous.

Félicitation ! Vous avez enfin franchi le cap et êtes entrés dans la secte de la framboise ! Mais maintenant vous vous demandez sans doute quoi faire avec. Pas de stress ! Je vais vous accompagner dans vos premiers pas. A travers ce tutoriel, je vais vous expliquer comment installer la distribution Raspbian sur votre raspberry (je l’appelerai RPi dans la suite du tutoriel).

Je tiens tout d’abord a vous informer d’une chose. Ce tutoriel sera large et s’adressera à tous les modèles de RPi (ceux avec WiFi intégrés et ceux qui ne l’ont pas).

Voici les différentes parties que je vais détailler :

  • Préparation de la carte SD
  • Paramétrage de la connexion SSH
  • Paramétrage de la connexion WiFi (Rpi 0w et RPi 3)
  • Première connexion et paramétrage
  • Activation du profil « root »

 

Préparation de la carte SD

Il va falloir un peu de matériel :

  • Un raspberry Pi 0w (dans mon cas)
  • Une carte SD (32 GB pour moi)
  • Un adaptateur secteur/micro-USB
  • Une alimentation 5v pour le raspberry

Dans un premier temps il va falloir préparer la carte SD afin de graver Raspbian dessus.

Afin de préparer cette carte SD il nous faut télécharger la dernière version de Raspbian http://downloads.raspberrypi.org/raspbian_latest. Il s’agit de cette version que nous allons installer sur notre carte.

Il va aussi nous falloir télécharger le logiciel Win32DiskManager que nous pouvons retrouver ici https://sourceforge.net/projects/win32diskimager/files/latest/download. Je vous laisse l’installer sur votre ordinateur.

Bien entendu il nous faut un port SD sur notre ordinateur pour pouvoir écrire dessus.

  • Décompressez l’archive de Raspbian afin d’obtenir un « .img ».
  • Cliquez ensuite sur l’icône représentant un dossier bleu à droite de « Image File ».
  • Sélectionnez l’image de Raspbian que vous venez de décompresser.
  • Dans l’onglet « Device » sélectionnez bien l’emplacement de votre carte SD. Faites bien attention à ne pas vous tromper !
Logiciel Win32DiskImager

Logiciel Win32DiskImager

  • Appuyez sur « Write » pour lancer l’écriture.
Ecriture de Raspian sur une carte SD

Ecriture de Raspbian sur une carte SD

Une fois terminé, la fenêtre affiche « Write Successful ». Ejectez la carte. La voilà prête pour le raspberry !

 

Paramétrage connexion SSH

Depuis la version « Stretch » de Raspbian, la sécurité au niveau des connexions a été renforcée (Je ne rentrerai pas dans les détails des nouveautés de cette version). En effet, par défaut il est impossible de se connecter en ssh ou wifi au raspberry. Mais n’ayez crainte, tout est prévu pour !

La première chose à faire est d’autoriser la connexion ssh. Comment ? rien de bien compliqué.

  • Commencez par créer un fichier sans extension (fichier texte par exemple auquel vous supprimerez l’extension .txt) donc le nom sera ssh.
  • Copiez ce fichier dans la partition boot de la carte SD précédemment configurée.

 

Paramétrage connexion WiFi (RPi 0w, RPi 3)

Maintenant que la connexion SSH est active, il est possible d’utiliser votre RPi via une connexion ethernet. Cependant, pour avoir une interaction vraiment sans contact physique, de nombreux utilisateurs préféreront utiliser le réseau Wi-Fi.

  • Commencez par créer un fichier nommé wpa_supplicant.conf
  • Vous pouvez paramétrer l’accès au réseau dès maintenant en utilisant un éditeur de texte (NotePad++, SublimText, etc…) et en écrivant les lignes suivantes :
1
2
3
4
5
6
7
8
ctrl_interface=DIR=/var/run/wpa_supplicant GROUP=netdev
update_config=1
country=FR
network={
        ssid="NomReseau"
        psk="MotDePasse"
        key_mgmt=WPA-PSK
}

(Pensez à remplacer « NomReseau » et « MotDePasse » par vos paramètres personnels.

  • Placez ce fichier dans la partition boot de la carte SD précédemment configurée.

 

Première connexion et paramétrage

Dans un premier temps insérez la carte SD dans le Raspberry puis connectez le à la box internet via un câble RJ45. Branchez ensuite l’alimentation du Raspberry.

Rendez-vous sur l’interface de la box internet http://192.168.1.254 (selon votre box).

Information connexion sur la box du raspberry

Information connexion sur la box du raspberry

L’adresse IP de mon Raspberry est 192.168.1.21.

A présent, lancez le logiciel Putty téléchargeable ici.

Entrez l’adresse IP de votre Raspberry et faites « Open ». Une console va s’ouvrir.

Console de connexion de Putty

Console de connexion de Putty

Le login par défaut est « pi »et le mot de passe par défaut est « raspberry ». Utilisons-les pour nous connecter dessus. Voici notre première connexion SSH sur notre Raspberry !

Première connexion en SSH sur le raspberry en profil Pi

Première connexion en SSH sur le raspberry en profil Pi

Ecrivez la ligne de commande

1
sudo raspi–config

Voici l’écran que vous devriez voir.

Fenêtre de configuration de Raspian

Fenêtre de configuration de Raspian

Faites « entrée » sur « Expand Filesystem » pour étendre la capacité de l’OS à toute la carte SD.

Vous pouvez améliorer la sécurité du profil « pi » du Raspberry en modifiant son mot de passe. Pour cela, il vous suffit d’aller dans « Change User Password ». Une nouvelle fenêtre va s’ouvrir vous indiquant que vous allez modifier le mot de passe pour « pi ». Appuyez sur « entrée » puis entrez votre nouveau mot de passe. (Aucun caractère ne s’affichera ! Attention de ne pas vous tromper !). Faites « entrée ». Le menu se rouvrira vous indiquant que la modification s’est parfaitement déroulée.

 

Activation du profil « root » (super-admin)

Nous allons à présent activer le profil « root » qui correspond au super-utilisateur du Raspberry.

Commençons tout d’abord par nous connecter avec le profil « pi ».

Tapez :

1
cat /etc/ssh/sshd_config

Vous devriez avoir à l’écran ceci :

Modification à apporter pour autoriser le profil root

Modification à apporter pour autoriser le profil root

Nous pouvons voir la ligne

« PermitRootLogin prohibit-password ». Nous devons la modifier en « PermitRootLogin yes ».
Afin de modifier le fichier nous devons taper

1
sudo nano /etc/ssh/sshd_config

Retrouvez la ligne à modifier puis effectuez le changement. Ensuite faites « ctrl+x » puis « y » puis « enter ».

1
sudo /etc/init.d/ssh restart

Maintenant reconnectez-vous avec le profil « pi ». Entrez cette commande :

1
sudo passwd root

et inscrivez le mot de passe du super utilisateur deux fois.

Faites un reboot, (sudo reboot) puis connectez-vous cette fois-ci avec le profil « root » et le mot de passe inscrit. A présent vous voilà super administrateur.

 

Vous savez à présent installer Raspian, créer une connexion ssh et wifi et paramétrer le profil root. Libre à vous d’apprendre le Python (je vous le conseille) pour jouer avec les ports GPIO, ou d’utiliser votre appareil pour d’autres utilisations.

A bientôt

Thomas A.

Image de Une

Participation à la MakerFaire 2018

By | Non classé | No Comments

Chers Maker,
Voici venu le temps de la rentrée, annonciateur souvent du retour de projets, d’articles mais aussi de conventions.
A propos de convention, vous pouvez dès à présent réserver les dates du 23, 24 et 25 novembre 2018 pour passer nous voir lors de l’édition 2018 de la MakerFaire Paris. En effet, pour une année supplémentaire, notre équipe sera présente pour vous accueillir et vous présenter nos divers projets. En supplément, vous aurez l’occasion cette année de découvrir plus en détail le projet SimpleDomo qui s’est largement précisé lors de ces deux derniers mois que nous avons pu passer à travailler dessus.

Ainsi, vous aurez l’occasion de découvrir les premiers prototypes de prises domotique ainsi que ceux de la centrale SimpleDomo. Vous pourrez en comprendre le fonctionnement et mieux cerner les finalités de notre projet. En complément, nous continuerons bien sûr à présenter notre volonté de transmettre nos connaissances sur la plateforme SimpleDuino en réalisant des projets concrets sur un vaste champ de sujets (Tracker solaire notamment) ou encore des projets futurs, portés sur le long terme, dont nous développons des « proof of concept », sortes de preuves de faisabilité, notamment avec l’idée d’un miroir connecté…

En conclusion, nous ne pouvons qu’insister sur la nécessité de passer nous voir, ne serait-ce que pour mettre un visage sur notre équipe qui s’efforce depuis près de trois années à vous proposer des articles d’une clarté, précision et rigueur à la hauteur de vos attentes.

A bientôt !

Manipulation de fichiers Excel en Python

Manipulation de documents Excel en Python

By | Débutant Raspberry Pi, Informatique | 10 Comments

Il y a peu, j’abordai la manipulation de fichiers basiques en Python au sein d’un article. Aujourd’hui, j’ai souhaité vous présenter les fondamentaux de l’utilisation de fichiers Excel sous Python. En effet, Excel permet l’organisation et le traitement d’un grand nombre de données mais, on peut aussi supposer avoir préparer un document sous Excel afin qu’il soit lisible par n’importe quel individu, et d’avoir besoin pour un quelconque traitement informatique d’importer ce document sous Python.
Bien sûr, il m’est compliqué de m’adapter à toutes les situations. La diversité des documents Excel ne permet pas de réaliser un article « universel » qui traiterait de tous les cas possibles de document sur Excel. Je me limiterai à un document relativement simpliste que je présenterai dans quelques lignes… Etant donné que le logiciel Excel permet de gérer des documents multipages, j’aborderai aussi cette notion.

Dès lors, et avant d’aller plus loin dans cet article, il nous sera nécessaire d’utiliser (et donc d’avoir installé) la librairie « xlrd » sous Python. Je vous renvoie pour cela au cours sur l’installation de librairie sous Python grâce à l’utilitaire pip. Vous aurez simplement besoin de connaitre le nom de la librairie telle que pip la connait, à savoir « xlrd ». Pour ceux d’entre-vous qui ont parcouru rapidement l’article traitant de cet utilitaire, je vous donne tout de même directement la ligne de commande permettant l’installation de la librairie :

1
pip install xlrd

Si vous rencontrez des problèmes à l’installation, pensez à lire notre article sur l’utilitaire pip, j’insiste sur ce point car on y traite certains problèmes qui peuvent être récurrents avec cet utilitaire…

Si l’installation s’est correctement déroulée, alors vous êtes fin prêt et nous allons pouvoir commencer ensemble en important notre premier fichier Excel dans Python.

1- Première importation et manipulations

Afin d’uniformiser le tutoriel, je vous propose d’utiliser une feuille de calcul dont la structure est semblable à celle-ci :

Capture d'écran feuille de calcul Excel 1

Capture d’écran de la première feuille de calcul de notre document Excel

Capture d'écran feuille de calcul Excel 2

Capture d’écran de la seconde feuille de calcul de notre document Excel

C’est un document Excel en deux feuilles de calcul dont la première (image de gauche) représente les images de la fonction f(x) = x^2 + 4 pour les x donnés et la seconde (image de droite) représente les images de f(x) = x^3 + 4
Notre objectif sera de récupérer sous Python ces données et d’en afficher les courbes représentatives. J’utiliserai d’ailleurs pour cela la bibliothèque matplotlib que vous pouvez installer depuis pip si vous le souhaitez. Si vous n’installez pas cette librairie, vous pourrez tout de même suivre ce tutoriel, le tracé sera la seule partie que vous ne pourrez pas exécuter. A ce propos, je ne détaillerai pas les fonctions utilisées pour le tracé (mais les codes seront fournis). L’utilisation de la bibliothèque matplotlib fera l’objet d’un article à part entière étant donné le fait que ce soit une librairie très complète.

La première étape consiste bien sûr à importer la librairie dans Python et à ouvrir notre fichier. Pour l’import de la librairie, on utilisera le classique

1
import xlrd

Et l’importation du document dans Python se fait au moyen de la fonction « open_workbook » de la librairie xlrd :

1
document = xlrd.open_workbook("document_excel.xlsx")

On veillera alors à bien placer notre fichier Excel dans le même répertoire que le fichier Python. Dans le cas contraire, on devra indiquer un chemin relatif vers le fichier (exemple « ../document_excel.xlsx » si le document se situe dans le dossier parent du fichier Python)

On peut alors accéder à quelques propriétés intéressantes, notamment le nombre de feuilles que contient notre document Excel (dans notre cas, 2) et le nom de chacune de ces feuilles sous la forme d’une liste. Cela s’obtient de la manière suivante :

1
2
print("Nombre de feuilles: "+str(document.nsheets))
print("Noms des feuilles: "+str(document.sheet_names()))

Vous noterez que je décide d’afficher ces données au moyen de « print ».
Mais l’objectif finalement, c’est de pouvoir récupérer les données que l’on a précédemment enregistré dans nos feuilles de calcul. Pour cela, on doit donc logiquement sélectionner notre première feuille de calcul, récupérer nos données, sélectionner la seconde, et ainsi de suite. On doit donc utiliser la fonction « sheet_by_index ». Au passage, il existe une fonction « sheet_by_name » qui fonctionne de la même manière en spécifiant simplement le nom de la feuille de calcul en paramètre. Je préfère utiliser la première fonction car je n’ai pas à faire attention à des caractères particuliers, espaces ou autres « altérations » possibles de ma chaine de caractère. Pour l’intérêt pédagogique, j’inclue cependant dans le script suivant les deux structures.

1
2
feuille_1 = document.sheet_by_index(0)
feuille_1 = document.sheet_by_name("Fonction 1")

Maintenant, j’ai dans l’objet « feuille_1 » la possibilité de retrouver toutes mes données. Mais avant de les obtenir, je vais avoir besoin d’accéder aux dimensions de ma feuille (nombre de lignes et de colonnes). J’ai pour cela la possibilité d’accéder à certaines informations de ma feuille, notamment son nom, son nombre de lignes et son nombre de colonnes au moyen des fonctions suivantes :

1
2
3
4
print("Format de la feuille 1:")
print("Nom: "+str(feuille_1.name))
print("Nombre de lignes: "+str(feuille_1.nrows))
print("Nombre de colonnes: "+str(feuille_1.ncols))

Vous remarquerez que je décide encore une fois d’afficher ces informations mais je vais dès à présent les stocker dans des variables que j’aurai sans doute l’occasion d’utiliser plus tard :

1
2
cols = feuille_1.ncols
rows = feuille_1.nrows

Vient alors le moment tant attendu, celui d’accéder à mes données. Pour cela, j’ai deux manières de procéder. La première, que je qualifierai de méthode bourrine, serait de parcourir toutes les lignes et colonnes de mon document et de tout stocker dans un tableau. Cette méthode a l’avantage de ne pas nécessiter la connaissance préalable du format du document Excel. Cependant, ce n’est pas la méthode que je souhaite utiliser ici. Je vais privilégier une méthode plus élégante étant donné que je sais déjà que ma première colonne contient mes valeurs de x  et la seconde de f(x) . Au passage, je n’oublie pas que ma première ligne me sert à nommer les colonnes afin de pouvoir comprendre le document Excel si un jour me viens l’envie de le relire. Alors ma « sélection » de données sous Python devra commencer à la seconde ligne.
Pour sélectionner la valeur d’une cellule dont je connais la ligne et la colonne, j’utilise la fonction suivante :

1
2
cellule = feuille_1.cell_value(rowx=1, colx=0)
print(cellule)

Attention, les cellules sont numérotées en partant de 0 pour leur ligne et leur colonne. Cela signifie que la cellule tout en haut à gauche est en position (0, 0)  et non (1, 1) . Si cela vous semble être une mauvaise idée de la part des concepteurs de Python, sachez qu’en fait, cela va nous permettre de parcourir très facilement nos lignes et colonnes. Par ailleurs, sachez que dans la plupart des langages de programmation, les tableaux démarrent à l’index 0 et que donc Python essaye, au moins sur ce coup, d’être en accord avec les autres…
En parcourant donc ma feuille de calcul à l’aide d’une boucle for pour former mes listes X et Y qui contiennent respectivement les valeurs de x  et de f(x) , j’en viens à adopter la structure suivante :

1
2
3
4
5
X = []
Y= []
for r in range(1, rows):
    X += [feuille_1.cell_value(rowx=r, colx=0)]
    Y += [feuille_1.cell_value(rowx=r, colx=1)]

Et je peux alors former très rapidement le graphe représentatif de ma fonction :

1
2
plt.plot(X, Y)
plt.show()

Et voici finalement mon script au complet :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import xlrd
import matplotlib.pyplot as plt
 
document = xlrd.open_workbook("document_excel.xlsx")
 
print("Nombre de feuilles: "+str(document.nsheets))
print("Noms des feuilles: "+str(document.sheet_names()))
 
feuille_1 = document.sheet_by_index(0)
feuille_1 = document.sheet_by_name("Fonction 1")
 
print("Format de la feuille 1:")
print("Nom: "+str(feuille_1.name))
print("Nombre de lignes: "+str(feuille_1.nrows))
print("Nombre de colonnes: "+str(feuille_1.ncols))
 
cols = feuille_1.ncols
rows = feuille_1.nrows
 
X = []
Y= []
 
for r in range(1, rows):
    X += [feuille_1.cell_value(rowx=r, colx=0)]
    Y += [feuille_1.cell_value(rowx=r, colx=1)]
 
plt.plot(X, Y)
plt.show()

Ce script fonctionne parfaitement pour la feuille 1 et je vous laisse libre soin de l’adapter pour la feuille 2 (les modifications sont infimes…)

2- Conclusion

En conclusion, j’ai souhaité vous démontrer ici toute la simplicité de l’utilisation d’Excel en collaboration avec Python. Si l’exemple que nous avons abordé ici n’est pas d’une pertinence absolue étant donné que l’on aurait pu directement tracer la courbe sur Excel ou obtenir la fonction sous Python, il a au moins le mérite d’être simple et d’expliquer clairement les fondamentaux de la manipulation de documents Excel.
Nul doute que nous serons amenés plus tard à manipuler des fichiers d’une manières plus avancés, notamment parce qu’un document Excel permet le stockage ordonné d’un grand nombre de données et semble donc parfaitement adapté à une utilisation pour le Machine Learning…

D’ici là, vous pouvez vous entrainer sur des classeurs Excel de votre composition afin de manipuler correctement les fondamentaux de la librairie xlrd. Si vous êtes curieux, sachez que le projet xlrd et disponible sur Github à l’adresse suivante : https://github.com/python-excel/xlrd et que vous y aurez tout loisir de découvrir comment fonctionne cette bibliothèque (attention, si vous débutez, vous risquez de vous perdre au milieu de toutes ces lignes de code…)

Fabien A.