DEV Community: Jacques Supcik

A Fresh Approach to Local MQTT Development

Jacques Supcik — Wed, 30 Apr 2025 14:30:19 +0000

Need a local MQTT instance on your machine? Want to integrate Node-Red too? Docker makes this incredibly simple. I'll show you exactly how to get everything up and running with minimal effort.

Before we begin, verify that Docker is properly installed on your system. You can download Docker Desktop from the official website where you'll also find comprehensive installation instructions.

I also suggest installing just, a useful tool that simplifies running commands from your terminal with minimal typing.

Create a new directory and add the following compose.yml file :

services:
  mosquitto:
    image: eclipse-mosquitto
    ports:
      - "1883:1883/tcp"
      - "8090:8090"
    volumes:
      - ./mosquitto/mosquitto.conf:/mosquitto/config/mosquitto.conf
    environment:
      - TZ=Europe/Zurich

  node-red:
    image: nodered/node-red
    ports:
      - "1880:1880"
    volumes:
      - ./node-red/data:/data
    environment:
      - TZ=Europe/Zurich
    links:
      - "mosquitto:mqtt-broker"
      - "mosquitto:mqtt"
      - "mosquitto:broker"

Adapt the timezone to your location.

Create a directory mosquitto and add the following mosquitto.conf file :

# Config file for mosquitto
listener 1883
protocol mqtt
listener 8090
protocol websockets
allow_anonymous true

Create another directory named node-red and add the following Dockerfile :

FROM nodered/node-red

RUN npm install @flowfuse/node-red-dashboard
RUN npm install @flowfuse/node-red-dashboard-2-ui-led

Within your node-red directory, create a new empty folder named data which will serve as the storage location for all your project data.

Finally, add a justfile with the following content :

up target="":
    docker compose up {{ target }}

up-rebuild target="":
    docker compose up --build --force-recreate {{ target }}

The content of your directory should look like this :

.
├── compose.yml
├── justfile
├── mosquitto
│   └── mosquitto.conf
└── node-red
    ├── data
    └── Dockefile

To start your server, just type the following command :

just up

You should see something like this :

docker compose up 
[+] Running 3/3
 ✔ Network mosquitto-nodered_default        Created
 ✔ Container mosquitto-nodered-mosquitto-1  Created
 ✔ Container mosquitto-nodered-node-red-1   Created
Attaching to mosquitto-1, node-red-1
mosquitto-1  | mosquitto version 2.0.21 starting
mosquitto-1  | Config loaded from /mosquitto/config/mosquitto.conf.
mosquitto-1  | Opening ipv4 listen socket on port 1883.
mosquitto-1  | Opening ipv6 listen socket on port 1883.
mosquitto-1  | Opening websockets listen socket on port 8090.
mosquitto-1  | mosquitto version 2.0.21 running
node-red-1   | 
node-red-1   | Welcome to Node-RED
node-red-1   | ===================
node-red-1   | 
node-red-1   | [info] Node-RED version: v4.0.9
node-red-1   | [info] Node.js  version: v20.19.0
node-red-1   | [info] Linux 6.10.14-linuxkit arm64 LE
node-red-1   | [info] Loading palette nodes
node-red-1   | [info] Settings file  : /data/settings.js
node-red-1   | [info] Context store  : 'default' [module=memory]
node-red-1   | [info] User directory : /data
node-red-1   | [warn] Projects disabled : editorTheme.projects.enabled=false
node-red-1   | [info] Flows file     : /data/flows.json
node-red-1   | [info] Creating new flow file
node-red-1   | 
node-red-1   | ---------------------------------------------------------------------
node-red-1   | Your flow credentials file is encrypted using a system-generated key.
node-red-1   | 
node-red-1   | If the system-generated key is lost for any reason, your credentials
node-red-1   | file will not be recoverable, you will have to delete it and re-enter
node-red-1   | your credentials.
node-red-1   | 
node-red-1   | You should set your own key using the 'credentialSecret' option in
node-red-1   | your settings file. Node-RED will then re-encrypt your credentials
node-red-1   | file using your chosen key the next time you deploy a change.
node-red-1   | ---------------------------------------------------------------------
node-red-1   | 
node-red-1   | [info] Server now running at http://127.0.0.1:1880/
node-red-1   | [warn] Encrypted credentials not found
node-red-1   | [info] Starting flows
node-red-1   | [info] Started flows

The MQTT broker is available at :

mqtt://<YOUR IP ADDRESS>:1883
ws://<YOUR IP ADDRESS>:8090

The node-RED is available at http://127.0.0.1:1880/

Press Ctrl+C to stop the server

If you just want to start the MQTT broker, type the following command :

just up mosquitto

If you need to rebuild the container, type the following command :

just up-rebuild

When configuring Node-RED, simply reference your MQTT broker using the hostname mosquitto and the port 1883.

Note : If you prefer, you can also use mqtt-broker, mqtt or broker as a hostname instead of mosquitto.

Enjoy your MQTT Broker and Node-RED instance.

Création de sites web pour l'enseignement

Jacques Supcik — Sat, 23 Jul 2022 20:01:54 +0000

Comme professeur, j'ai constaté que les enseignant(e)s en haute école spécialisée ou à l'université utilisent souvent des transparents (slides) pour illustrer leurs cours magistraux. Ces transparents sont habituellement faits avec un outil comme "PowerPoint" et projetés sur un écran pendant le cours. De plus, les enseignant(e)s distribuent tout un tas de documents en relation avec le cours :

des exercices ;
des documents décrivant les travaux pratiques ;
des vidéos ;
des livres ;
...

Pour distribuer ces documents, certains utilisent des services en lignes tels que Moodle, mais pour ma part, j'avais besoin d'un outil qui me convenait mieux. C'est alors que j'ai découvert MkDocs avec le thème Material et
ce système correspond beaucoup mieux à ma manière de travailler. De plus, ces systèmes étant des logiciels « libres », je pouvais les modifier à ma guise.

La découpe traditionnelle des « slides » en pages était nécessaire quand on travaillait avec des rétroprojecteurs :

Rétroprojecteur [source : wikimedia]

mais aujourd'hui, les étudiant(e)s sont habitué(e)s au défilement infini et
cette découpe en page du contenu peut être remise en question.

Pour mon enseignement actuel, j'ai remplacé les « slides » par un site fait avec MkDocs, et ce site me permet également de distribuer les supports relatifs au cours. J'ai eu de très bons retours de la part des étudiant(e)s qui semblent apprécier cette manière de faire.

En commençant cet article, je souhaitais partager mon expérience et expliquer en détail comment réaliser un tel site Internet. J'ai cependant constaté que ça serait beaucoup trop long et que le blog n'était pas la plate-forme idéale pour cette tâche. J'ai donc publié un site Internet qui explique... comment faire un site Internet :

https://heia-fr.github.io/mkdocs-edu-howto/

Ce site est fait avec les mêmes techniques expliquées dans le site lui-même.

Les deux innovations principales que j'apporte sont les suivantes :

La possibilité de publier des chapitres et les solutions des exercices au fur et à mesure de l'avancée du cours.
La possibilité de distribuer une version "offline" complète du site et la réalisation d'un logiciel permettant de visualiser cette version "offline".

J'ai pour ma part beaucoup de plaisir à rédiger du contenu pour mes cours avec ces sites Internet j'espère que les informations contenues dans ce blog et sur le site Création de sites web pour l'enseignement vous seront utiles.

Crédit: Photo de couverture par Ash @ModernAfflatus

Solving the Hash Code 2022 Practice Challenge with 70 lines of code

Jacques Supcik — Wed, 26 Jan 2022 20:39:55 +0000

Introduction

The Google Hash Code is a team coding competition organized by Google. The qualification round usually takes place in February and the organizers usually publish a practice challenge to warm you up. In this post, I explain how I solved this challenge with just 70 lines of Python code.

Description of the challenge

As usual, the practice challenge for the Hash Code 2022 is about Pizzas. This time, the goal is to find the only pizza that appeals to as many people as possible.

The input of the challenge is a list of potential customers with the list of ingredients they like and the list of ingredients they dislike. For example:

3
2 cheese peppers
0
1 basil
1 pineapple
2 mushrooms tomatoes
1 basil

means that we have 3 customers :

The first potential customers likes 2 ingredients, namely "cheese" and "peppers" and dislikes nothing (0 ingredient).
The second potential customers likes 1 ingredient, namely "basil" and also dislikes 1 ingredient, namely "pineapple".
The third potential customers likes 2 ingredients, namely "mushrooms" and "tomatoes" and dislikes 1 ingredient, namely "basil".

A customer would buy the pizza if it has all the ingredients he likes and none of the ingredient he dislikes.

So using the set theory notation, given a pizza with the set of ingredients $p$ , the customer with the set of ingredients he likes $l$ and the set of ongredients he dislikes $d$ would buy it if and only if $\cap l = l$ and $\cap d = \emptyset$ .

To submit the solution, we just write a single line with the number of ingredients followed by the list of the ingredients on the pizza. For example:

4 cheese mushrooms tomatoes peppers

means that the only pizza we serve has 4 ingredients, namely "cheese", "mushrooms", "tomatoes" and "peppers".

Analysis

One possible solution for this problem would be to try all possible combination of ingredients. This would work if the number of ingredients is rather small, but the most difficult input has 10000 ingredients and there are $210000≈2⋅1030102^{10000} \approx 2 \cdot 10^{3010}$ possible combinations (this is a 2 followed by 3010 zeros)!

As usually with such challenges, we need another approach. The most basic one consists of computing many pizzas with a random set of ingredients and keeping the one with the best score. This would work and would be very fast, but it will not converge toward the best solution. But we can keep the idea and use a genetic algorithm to improve the convergence. This is what we are going to do!

Coding

The Hash Code can be solved with any programming language, but for this example, I will use Python 3. Python 3 is a rather simple language and there is a good library for genetic algorithm. So let's begin.

I start by implementing two classes :

The customer (with the ingredients he likes and dislikes)
The challenge itself (with the list of customers, the set of all ingredients, the solution, and the score)

from dataclasses import dataclass, field

@dataclass
class Customer:
    likes: set[str]
    dislikes: set[str]

@dataclass
class Challenge:
    customers: list[Customer] = field(default_factory=list)
    all_ingredients: set = field(default_factory=set)
    solution: set = field(default_factory=set)
    score: int = 0

Then in the Challenge class, I implement a method to reset the challenge (if I want to keep the instance of this class for several inputs):

class Challenge:
    def reset(self):
        self.customers = []
        self.all_ingredients = set()
        self.solution = set()
        self.score = 0

I also implement a method add_customer that appends the customer to the list and update the set of all ingredients with the one that this customer likes. Note that there is no need to add the ingredients that he dislikes because there is no benefit in having them on our pizza.

class Challenge:
    def add_customer(self, customer):
        self.customers.append(customer)
        self.all_ingredients |= customer.likes

Now I need a method that computes the score of a given pizza. The score is the number of customers who would buy this pizza. To do that, we iterate over all customers and test if they would buy it with the formula that we found earlier ( $\cap l = l$ and $\cap d = \emptyset$ ):

class Challenge:
    def evaluate(self, pizza: set[str]) -> int:
        result = 0
        for c in self.customers:
            if c.likes & pizza == c.likes and c.dislikes & pizza == set():
                result += 1
        return result

Now this is where the magic occurs! In the method solve, we implement a fitness function that takes a solution candidate as argument and returns the score. The candidate is a NumPy binary vector of the size of the set of all ingredients and where a 1 means that this ingredient is chosen and a 0 means that the ingredient is not chosen.

We let then the PyGAD package do the job of selecting the best candidate:

class Challenge:
    def solve(self, generations=100):
        ingr_list = sorted(list(self.all_ingredients))

        def fitness_func(solution, solution_idx):
            pizza = set([ingr_list[k] for (k,v) in enumerate(solution) if v == 1])
            return self.evaluate(pizza)

        ga_instance = pygad.GA(
            num_generations=generations,
            num_parents_mating=2,
            sol_per_pop=3,
            num_genes=len(ingr_list),
            fitness_func=fitness_func,
            init_range_low=0,
            init_range_high=2,
            random_mutation_min_val=0,
            random_mutation_max_val=2,
            mutation_by_replacement=True,
            gene_type=int)

        ga_instance.run()

        solution, solution_fitness, solution_idx = ga_instance.best_solution()
        self.solution = set([ingr_list[k] for (k,v) in enumerate(solution) if v == 1])
        self.score = solution_fitness

If we plot the fitness function for the difficult challenge (600 ingredients), we see that we almost reach a score of 1550 points in 2000 generations:

We then add a process method that deal with file reading and writing and this is the final code:

from dataclasses import dataclass, field
import pygad

@dataclass
class Customer:
    likes: set[str]
    dislikes: set[str]

@dataclass
class Challenge:
    customers: list[Customer] = field(default_factory=list)
    all_ingredients: set = field(default_factory=set)
    solution: set = field(default_factory=set)
    score: int = 0

    def reset(self):
        self.customers = []
        self.all_ingredients = set()
        self.solution = set()
        self.score = 0

    def add_customer(self, customer):
        self.customers.append(customer)
        self.all_ingredients |= customer.likes

    def evaluate(self, pizza: set[str]) -> int:
        result = 0
        for c in self.customers:
            if (c.likes & pizza == c.likes and 
                c.dislikes & pizza == set()):
                result += 1
        return result

    def solve(self, generations=100):
        ingr_list = sorted(list(self.all_ingredients))

        def fitness_func(solution, solution_idx):
            pizza = set([ingr_list[k] for (k,v) in enumerate(solution) if v == 1])
            return self.evaluate(pizza)

        ga_instance = pygad.GA(
            num_generations=generations,
            num_parents_mating=2,
            sol_per_pop=3,
            num_genes=len(ingr_list),
            fitness_func=fitness_func,
            init_range_low=0,
            init_range_high=2,
            random_mutation_min_val=0,
            random_mutation_max_val=2,
            mutation_by_replacement=True,
            gene_type=int)

        ga_instance.run()

        solution, solution_fitness, solution_idx = ga_instance.best_solution()
        self.solution = set([ingr_list[k] for (k,v) in enumerate(solution) if v == 1])
        self.score = solution_fitness

    def process(self, filename, generations=100):
        self.reset()
        with open(f"in/{filename}.in.txt") as f:
            n = int(f.readline())
            for i in range(n):
                customer = Customer(
                    set(f.readline().strip().split()[1:]),
                    set(f.readline().strip().split()[1:])
                )
                self.add_customer(customer)

            print(len(self.all_ingredients))
            self.solve(generations)

        with open(f"out/{filename}.out-{self.score}.txt", "w") as f:
            f.write(f"{len(self.solution)} ")
            f.write(" ".join(self.solution))

c = Challenge()
c.process("a_an_example", 1000)
c.process("b_basic", 1000)
c.process("c_coarse", 1000)
c.process("d_difficult", 1000)
c.process("e_elaborate", 1000)

The input files are expected in the ./in directory and you need a ./out directory where the program can write the results.

Conclusion

We were able to solve the Hash Code 2022 Practice Challenge with just 70 lines of Python 3 code and the magic of the PyGAD. The code is not yet optimized and I am sure that we can improve the operations on sets and also tune the settings of PyGAD to get better and faster results, but this goes beyond the scope of this post.

Credit : Cover photo by Vitalii Chernopyskyi on Unsplash

References and Bibliography

Jacques Supcik — Mon, 15 Nov 2021 09:03:55 +0000

Note : The content of this article was written in 2010 by Laurenz Altwegg. This is just a new layout for the web.

Why are references needed

Timothy T. Allen nicely describes why and when references should be cited in scientific papers[1]:

"It is important to properly and appropriately cite references in scientific research papers in order to acknowledge your sources and give credit where credit is due. Science moves forward only by building upon the work of others. There are, however, other reasons for citing references in scientific research papers. Citations to appropriate sources show that you've done your homework and are aware of the background and context into which your work fits, and they help lend validity to your arguments. Reference citations also provide avenues for interested readers to follow up on aspects of your work — they help weave the web of science. You may wish to include citations for sources that add relevant information to your own work, or that present alternate views.

You should acknowledge a source any time (and every time) you use a fact or an idea that you obtained from that source. Thus, clearly, you need to cite sources for all direct quotations. But you also need to cite sources from which you paraphrase or summarize facts or ideas — whether you've put the fact or idea into your own words or not, you got the fact or idea from somebody else and you need to give them proper acknowledgement (even if an idea might be considered "common knowledge," but you didn't know it until you found it in a particular source).

Sources that need to be acknowledged are not limited to books and journal articles, but include internet sites, computer software, written and e-mail correspondence, even verbal conversations with other people (in person or by telephone). All different kinds of sources must be acknowledged. Furthermore, if you use figures, illustrations, or graphical material, either directly or in modified form, that you did not yourself create or design, you need to acknowledge the sources of those figures."

Which format should references and citations have?

Citations should be indicated by superscript numerals (e.g. ¹, ²) or numerals in square brackets (e.g [2], [3]) in consecutive numerical order. The references themselves should be arranged in the same order at the end of the text. In the case of numerous references, as an alternative the first three letters of the author’s last name and year in square brackets (e.g. [MIL02], [BRO99]) can be used. The references themselves should then be arranged alphabetically at the end of the text. The format of the references depends somewhat on the style adopted by the periodical or organization. The following format is good practice and is proposed by IEEE[2]. For convenience, the text by IEEE has been slightly reordered and shortened:

Articles in periodicals

Articles listed shall include the following information in the order shown:

Last name of author or authors and first name or initials, or name of organization
Title of article in quotation marks
Title of periodical in full and set in italics
Volume, number, and, if available, part
First and last pages of article
Date of issue

Example:

[1] Boggs, S. A. and Fujimoto, N., "Techniques and instrumentation for measurement of transients in gas-insulated switchgear", IEEE Transactions on Electrical Installation, vol. ET-19, no. 2, pp. 87–92, Apr. 1984.

Books

Books listed shall include the following information in the order shown:

Last name of author or authors and first name or initials, or name of organization
Title of book (in italics)
Edition number (if applicable)
Place of publication (city)
Name of publisher
Year of publication

Example:

[26] Peck, R. B., Hanson, W. E., and Thornburn, T. H., Foundation Engineering, 2nd ed. New York: McGraw-Hill, 1972, pp. 230-292.

Theses, dissertations, and other unpublished works

[5] Diessner, A., "Studies on Compressed Gas Insulation." Master’s thesis, Stanford University, 1969.

Articles presented at conferences

[3] Cookson, A. H., and Pedersen, B. O., "Thermal measurements in a 1200 kV compressed gas insulated transmission line," Seventh IEEE Power Engineering Society Transmission and Distribution Conference and Exposition, Atlanta, GA, pp. 163-167, Apr. 1979.

Standards

Standards listed shall include designation and title.

Example:

[3] ISO/IEC 7498-4, Information processing systems — Open Systems Interconnection — Basic Reference Model — Part 4: Management framework.

Articles in corporate reports

[6] Dale, S. J., "Performance of a technical and economic feasibility study of an HVDC compressed gas-insulated transmission line", Westinghouse Electric Corporation, Trafford, PA, Final Report, Dec. 1983.

Government publications

[2] Cookson, A. H., "Particle Trap for Compressed Gas Insulated Transmission Systems", U.S. Patent no. 4554399, Nov. 1985.

Web-pages

The format of web pages has not been described in Ref. [1]. Web-pages listed shall include the following information in the order shown:

Last name of author or authors and first name or initials, or name of organization
Title of article in quotation marks (in italics)
Year of publication, or, if and only if not available, ``retrieved'' with month and year of when page was last accessed (e.g. retrieved Nov. 07)
URL

Example:

[6] Timothy T. Allen, "Citing References in Scientific Research Papers", 2000, http://tim.thorpeallen.net/Courses/Reference/Citations.html

References

[1] : Timothy T. Allen, Citing References in Scientific Research Papers, 2000, http://tim.thorpeallen.net/Courses/Reference/Citations.html

[2] : IEEE Standards Style Manual, § 19 Bibliography, The Institute of Electrical and Electronics Engineers, New York, revised 2007, http://standards.ieee.org/guides/style/section7.html#992

Credits

Thanks to Laurenz Altwegg for the original version to this article.

Cover photo by Susan Q Yin on Unsplash.

10 Règles pour le développement de code en systèmes embarqués critiques

Jacques Supcik — Mon, 02 Aug 2021 11:07:12 +0000

En informatique, certains systèmes doivent vraiment être très robustes. C'est principalement le cas dans le domaine du spatial où des systèmes sont envoyés sur la lune ou sur d'autres planètes. Ce n'est pas si facile de demander à quelqu'un sur la planète Mars de presser sur le bouton "reset" en cas de problème !

La fiabilité et la robustesse du code ne profitent pas uniquement aux systèmes envoyés dans l'espace et nous avons tous à y gagner en appliquant les bonnes pratiques.

En 2006, Gerard J. Holzmann, chercheur au Jet Propulsion Laboratory de la NASA, publiait "The Power of 10: Rules for Developing Safety-Critical Code". Cet article décrit 10 bonnes pratiques pour écrire du code en C le plus fiable possible. Certains diront que choisir du C pour écrire du code fiable est une hérésie et qu'il vaudrait mieux utiliser un langage plus moderne, mais dans le monde des systèmes embarqués, le C reste beaucoup utilisé. De plus, certaines règles sont universelles et s'appliquent aussi aux langages plus modernes.

Ces 10 règles ont été traduites en français sur Wikipedia, mais il manque les explications autour de ces règles. Cet article reprend ces 10 règles et y ajoute une explication qui justifie la règle. J'y ajoute également parfois une note personnelle.

1. Éviter les constructions de flux complexes, telles que "goto" et la récursivité directe ou indirecte.

De nos jours, nous savons que le goto est toxique et qu'il ne faut pas l'utiliser. Cette instruction n'est d'ailleurs plus présente dans les langages modernes. On peut cependant encore produire du code "spaghetti" en abusant des instructions break et continue. Cette règle reste donc valable.

Éviter la récursivité est plus surprenant, mais il est très facile, pour une fonction récursive, de s'emballer et de consommer très rapidement toute la mémoire disponible. De plus, un tel comportement n'est pas facile à détecter avec une analyse statique de code. Pour des performances et une lisibilité équivalente, préférez les fonctions itératives aux fonctions récursives.

Notez que cette règle n'exige pas que toutes les fonctions aient un seul point de retour — bien que cela simplifie souvent le flux de contrôle. Dans bien des cas, un retour d'erreur précoce est une bonne pratique.

2. Toutes les boucles doivent avoir un nombre d'itérations maximum limité.

De plus, un outil d'analyse statique de code doit pouvoir prouver que cette limite supérieure ne peut pas être dépassée.

Cette règle évite de créer involontairement des boucles infinies. Elle ne s'applique cependant pas aux itérations qui sont censées ne pas se terminer — par exemple, dans un ordonnanceur (scheduler) ou un processus (thread) coopératif. Dans ces cas particuliers, la règle inverse s'applique : il doit être possible de prouver statiquement que la boucle ne peut pas se terminer.

Une façon d'implémenter cette règle est d'ajouter une limite supérieure explicite à toutes les boucles qui ont un nombre variable d'itérations. Lorsque la limite supérieure est dépassée, la fonction termine et retourne une erreur.

3. Éviter d'allouer de la mémoire dynamiquement, sauf lors de l'initialisation

Selon l'article "A proactive approach to more secure code", Microsoft écrivait en 2019 que 70% des vulnérabilités sont dues à des problèmes de sécurité de la mémoire. Ce type d'erreur provient plus spécifiquement d'une mauvaise gestion des routines d'allocation (mallocet calloc) et de libération (free) de la mémoire :

oublier de libérer la mémoire
libérer la mémoire deux fois
continuer à utiliser la mémoire après l'avoir libérée
tenter d'allouer plus de mémoire que disponible
dépasser les limites de la mémoire allouée
etc.

Le fait d'obliger toutes les applications à vivre dans une zone de mémoire fixe, préallouée, peut éliminer beaucoup de ces problèmes.

On pourrait penser que les "garbage collectors" résolvent ce problème, mais ils ne le font que partiellement et ils ont souvent un comportement imprévisible qui peut avoir un impact significatif sur les performances.

Un autre problème lié à la mémoire est le dépassement de la capacité de la pile (stack). En l'absence de récursion (règle 1), on peut calculer statiquement la limite supérieure de l'utilisation de la pile, et ainsi garantir qu'il n'y aura pas de dépassement de la capacité.

4. Limiter la taille des fonctions à ce qui peut être imprimé sur une page de papier

En général, cette règle signifie qu'une fonction ne devrait pas avoir plus de 60 lignes de code. Cette règle est reprise par Google dans son "C++ Style Guide" qui dit même qu'une fonction ne devrait pas dépasser 40 lignes.

Chaque fonction doit constituer une unité qui soit compréhensible et vérifiable. Une fonction longue est forcément plus compliquée à comprendre et peut donc cacher plus d'erreurs. Les fonctions trop longues sont souvent le signe d'un code mal structuré.

5. Utiliser un minimum de deux "assertions" par fonction

Les assertions permettent de vérifier qu'une condition donnée soit toujours vraie. Si, par exemple, à un endroit du code, vous êtes sûr que la variable x est comprise entre 0 et 10, vous pouvez écrire assert (x >= 0 && x <= 10). Le système vérifie les assertions à l'exécution, et si une assertion est fausse, le système peut prendre des mesures (envoyer une alerte, faire clignoter une LED, redémarrer le système ...)

Assurez-vous que vos assertions sont sans effet de bord. Une assertion qui modifie une variable globale fera plus de mal de que bien !

Certains langages proposent un mécanisme d'assertion, mais même si ce n'est pas le cas, vous pouvez implémenter des assertions avec des procédures. Les assertions servent à valider les préconditions à l'entrée des procédures, les invariants au milieu et les postconditions à la sortie.

Cette règle préconise de mettre au moins deux assertions par fonction, procédure ou méthode.

6. Limiter la portée des variables au maximum.

Il est facile de comprendre le rôle d'une variable dont la portée n'est que de quelques lignes. Les langages de programmation modernes permettent de déclarer des variables locales n'importe où dans une méthode et nous pouvons en profiter pour appliquer cette règle. Si vous devez faire une boucle qui compte jusqu'à 10, déclarez la variable à l'intérieur de la boucle :

for (int i = 0; i < 10; i++) { ... }

Ainsi, la portée de la variable i est minimum.

Cette règle nous indique également que les variables globales sont à proscrire. En effet, par définition, une variable globale a une très grande portée.

7. Vérifier la valeur de retour de toutes les fonctions non-void

Certaines fonctions utilisent la valeur de retour spéciale pour indiquer une erreur. En C, c'est le cas, par exemple, des fonctions printf ou malloc. La fonction printf retourne une valeur négative si elle n'a pas réussi à faire son travail et malloc retourne null en cas d'échec.

Votre programme doit systématiquement valider et vérifier les valeurs retournées par les fonctions. Notez que c'est une bonne occasion d'utiliser les assertions dont nous avons parlé précédemment.

Si le résultat ne fait aucune différence pour la suite du programme, vous pouvez transformer le résultat en void pour montrer que vous ignorez intentionnellement ce résultat. Vous pouvez aussi ajouter un commentaire pour expliquer votre choix.

8. Limiter l'utilisation du préprocesseur C

Le préprocesseur C est un outil simple, mais qui peut facilement introduire des erreurs difficiles à trouver dans un programme. Considérez, par exemple, les quelques lignes suivantes :

#define MY_CONST 4 + 2
int myVar = MY_CONST * 2;

Un lecteur non averti pourrait penser que MY_CONST vaut 6 et que myVar vaut 12, mais comme le préprocesseur fait une substitution textuelle, c'est comme si on avait écrit int myVar = 4 + 2 * 2 et comme la multiplication précède l'addition, myVar vaut dont 8.

De plus, une constante définie par #define n'a pas de type et le compilateur ne peut donc pas détecter certaines erreurs liées à une incompatibilité de type.

Quand on programme en C ou en C++, on n'a pas d'autre choix que d'utiliser des #include pour avoir accès aux bibliothèques et cette règle ne l'interdit pas. On peut aussi faire appel au préprocesseur pour de la compilation conditionnelle, mais à part ça, il faudrait éviter de l'utiliser. Utilisez des constantes typées à la place des #define et des procédures inline à la place des macros.

9. Limiter l'utilisation du pointeur à un seul déréférencement et ne pas utiliser de pointeur de fonction

Les pointeurs sont difficiles à maîtriser, même par un programmeur confirmé et un code avec beaucoup d'opérations sur les pointeurs devient vite incompréhensible. C'est particulièrement le cas avec les doubles indirections (des pointeurs sur des pointeurs), mais dans de très rares cas, comme dans la gestion des listes chaînes, certains considèrent qu'il est de "bon goût" de remplacer une condition par une double indirection. Dans tous les cas, ce genre de construction demande de bons commentaires.

Les pointeurs de fonctions sont aussi problématiques, car une analyse statique de code ne permet pas toujours savoir ce qui va se passer. Il ne faut les utiliser qu'en dernier recours si d'autres constructions ne sont pas possibles ou si la lisibilité du code en est améliorée.

10. Compiler avec tous les "warnings" possibles actifs

Les "warnings" ne sont pas là pour embêter le programmeur, mais pour le rendre attentif à une potentielle erreur. Un programme robuste compile sans "warning", même avec la configuration la plus stricte qui soit.

Cette règle nous dit de configurer tous les "warnings" possibles et les traiter comme des erreurs. Prenez pour habitude d'appliquer cette règle dès le début de chaque projet.

Complétez la validation de votre code avec des analyseurs statiques de code tels que cpplint ou (clang-tidy)[https://clang.llvm.org/extra/clang-tidy/] pour encore plus de sûreté et faites en sorte de tester systématiquement votre code (CI/CD).

Conclusion

Ces dix règles sont utilisées par la NASA pour la programmation de logiciels critiques et permettent l'envoi de robots dans l'espace. J'espère qu'elles vous permettront à vous aussi d'écrire du code plus robuste et plus fiable.

Credit : L'image en tête d'article est une photo de NASA/JPL-Caltech

Guide de rédaction de rapports pour les étudiants

Jacques Supcik — Tue, 20 Jul 2021 21:07:56 +0000

Dans mon rôle de professeur à la Haute école d'ingénierie et d'architecture de Fribourg, j'ai eu à maintes reprises l'occasion de corriger des rapports d'étudiants. Je constatais souvent les mêmes erreurs et j'ai alors décidé d'écrire cet article pour vous éviter de refaire ces mêmes erreurs.

Structure du rapport

Évitez de structurer votre rapport sur un axe temporel. Un rapport final n'est pas un journal de travail et vous décrivez votre travail à la fin du projet. L'ordre des chapitres ne représente pas l'évolution de votre projet dans le temps.

Les sections suivantes décrivent la structure traditionnelle d'un rapport final.

Page de garde

Vous pouvez concevoir la page de garde comme vous voulez, mais assurez-vous de mettre les éléments suivants :

Le nom de l'école et logo officiel (utilisez le logo "large" avec le nom complet de l'école)
Le nom de la filière d'étude
Le titre du rapport
La nature du projet (projet de semestre 5, projet de bachelor, ...)
L'année académique
Le ou les auteurs
Le lieu (Fribourg) et la date de publication
Le nom, l'entreprise et le logo du mandant (s’il y a en un)
Le nom des superviseurs
Le numéro de version (par exemple v0.4.2)

Pour un travail de bachelor, ajoutez encore :

Le nom des experts

Tableau de versions

Indiquez dans un tableau ce qui a changé entre les versions. Cette information doit permettre à une personne qui vous suit régulièrement de ne lire que ce qui a changé entre deux versions.

Sommaire exécutif

Les lecteurs commencent très souvent par lire le sommaire exécutif de votre rapport. Ce sommaire permet au lecteur de savoir s’il va lire la suite de votre rapport ou non, et ça vaut la peine d'en soigner la rédaction.

Ne dépassez pas une demi-page pour le sommaire. Expliquez brièvement le contexte, l'approche que vous avez eu pour résoudre les problèmes et mentionnez vos résultats.

Le sommaire exécutif est souvent la dernière chose que vous écrirez, mais il doit figurer au début de votre rapport. C'est également une bonne idée de traduire ce sommaire dans une deuxième langue (par exemple, en français si le rapport est en anglais).

Table des matières

Numérotez les chapitres, car vous pourrez plus facilement y faire référence.

Assurez-vous de ne pas laisser de chapitres seuls. Si vous avez par exemple, un chapitre 1.4.1, mais que vous n'avez pas de chapitre 1.4.2, alors ça ne vaut pas la peine de diviser le chapitre 1.4. Renommez le chapitre 1.4 si nécessaire ou ajoutez-y un chapitre 1.4.2

Liste des abréviations, glossaire

Il est important de mettre une liste des abréviations et un glossaire au début de votre rapport. Ça permet au lecteur de se préparer et il ne sera pas surpris quand il verra ces abréviations dans le document.

Introduction

L'introduction présente le contexte ou l'historique des travaux déjà faits sur le sujet. Vous décrivez dans ce chapitre la nature du problème ainsi que son importance.

Il est intéressant d'également mentionner les objectifs dans l'introduction. Faites bien attention de ne pas confondre objectif avec activité. Un objectif est un délivrable que vous fournissez à la fin du projet (par exemple "un prototype" ou "une application). Vous décrirez l'objectif par un substantif (un nom). Une activité est une action qui vous permet d'atteindre l'objectif (par exemple "faire l'état de l'art", "développer" ou "tester"). L'activité est décrite par un verbe.

Contexte

Vous aurez présenté le contexte dans l'introduction et vous pouvez développer dans ce chapitre. Expliquez pourquoi vous faites ce projet et précisez les besoins que vous couvrez ou les problèmes que vous résolvez.

Analyse

Dans l'analyse, vous faites l'état de l'art dans le domaine de votre projet. Vous étudiez les outils et les "frameworks" disponibles et vous étudiez ce qui a déjà été fait. Vous prenez en compte les contraintes du projet et vous comparez les options. À la fin de l'analyse, le lecteur doit être convaincu que vous connaissez votre sujet et que vous avez su faire les bons choix.

Conception

Avec la conception, vous montrez les travaux et les réflexions que vous avez faites avant de réaliser votre projet. Pour du logiciel, ça peut être de faire des diagrammes de classes, des algorithmes en pseudo-code ou des esquisses d'interface utilisateur. Vous démontrez au lecteur que vous avez pris le temps de bien réfléchir avant de commencer la réalisation.

Réalisation / Implémentation

Dans ce chapitre, vous décrivez la réalisation pratique de votre projet. Vous pouvez donner des précisions sur les structures de données que vous utilisez, la manière dont vous avez réalisé les algorithmes ou les détails de bibliothèques que vous avez utilisées.

Pour un projet informatique, les commentaires dans votre code sont une bonne source d'inspiration pour rédiger ce chapitre.

Tests et validations

Le chapitre des tests et validations est souvent négligé. On n'y pense qu'à la fin et on n'a plus le temps de bien l'écrire. Et souvent, on ne sait pas trop quoi écrire, car on a aussi oublié de faire les tests en premier lieu.

Un bon ingénieur sait l'importance de délivrer un produit de qualité et fiable. Il planifie les tests dès le début du projet et démontre dans ce chapitre que son système satisfait aux standards.

Pour un projet informatique, ce chapitre décrit les tests unitaires, les tests d'intégration et les tests système. Vous pouvez décrire les résultats des tests dans une table en indiquant :

Le nom du test
La fonctionnalité qui est vérifiée par le test
Le résultat attendu
Le résultat obtenu
Un commentaire

Décrivez aussi les mécanismes que vous avez mis en place pour vérifier votre programme (CI/CD, analyse statique de code...) et évaluez les performances de votre solution (en temps CPU et en mémoire).

Évolutions possibles et futurs travaux

Pendant votre projet, vous aurez de nouvelles idées, mais vous ne pourrez pas toutes les réaliser par manque de temps. Ce chapitre vous permet de mentionner ces idées et de donner des pistes pour faire évoluer ou pour améliorer votre projet.

Conclusion

La conclusion se concentre sur les résultats de votre projet. Vous écrivez comment vous avez répondu aux attentes du mandant et vous revenez sur les objectifs initiaux. Si vous n'avez pas atteint les objectifs, expliquez pourquoi et décrivez ce que vous avez fait à la place.

Pensez à bien soigner la conclusion. Certains lecteurs avertis commencent par lire le sommaire exécutif, puis ils lisent la conclusion, et s’ils aiment ce qu'ils lisent, alors ils lisent l'ensemble de votre rapport.

Complétez ce chapitre avec une conclusion personnelle. Faites preuve d'imagination et évitez de commencer par "j'ai bien aimé ce projet..." Vous pouvez aussi parler de comment vous avez géré le projet et dire ce que vous feriez différemment. N'hésitez pas à écrire cette partie à la première personne et à écrire "Je ..."

Remerciements

N'oubliez pas de remercier les personnes qui vous ont aidé pour ce projet, ça fait toujours plaisir. Remerciez les superviseurs, les mandants, les experts ainsi que la famille ou vos amis qui ont corrigé vos fautes d'orthographe.

Références et bibliographie

Mentionnez ici toutes les sources que vous avez utilisées dans votre rapport. Assurez-vous que tous les éléments de cette liste sont cités dans votre rapport. Ça ne sert à rien de mettre une référence juste parce que ça fait joli.

Citez les articles, les livres, et aussi les sites Internet que vous utilisez. Pour les sites Internet, précisez la date à laquelle vous avez lu l'information. Pour éviter que du contenu disparaisse, vous pouvez citer des URLs en passant par la "WayBack Machine" de l'Internet Archive

Vous trouverez plus de détails à ce sujet dans l'article de Laurenz Altwegg "References and Bibliography" :

References and Bibliography

Jacques Supcik ・ Nov 15 '21

#writing

Annexes

Les éléments suivants se retrouvent souvent dans les annexes :

La version définitive du cahier des charges
La planification (diagramme de Gant ou liste de "Sprints")
Les codes informatiques (ou des extraits)

Technique d'écriture rapide et efficace

Si vous écrivez votre rapport paragraphe par paragraphe en vous efforçant de choisir les bons mots et corrigeant toutes les fautes d'orthographe, vous risquez alors de déprécier la cohérence et le flux de vos idées. Et comme vous aurez déjà passé beaucoup de temps sur votre texte, votre relecture sera superficielle et vous laisserez passer des fautes d'orthographe.

Une technique éprouvée pour écrire un document technique est de faire une première passe en écrivant le document dans un flux continu, sans faire attention à l'orthographe ou à la grammaire. L'idée est de mettre les idées dans le rapport dans un enchaînement logique. Ne cherchez pas les tournures de phrases parfaites, mais écrivez simplement vos pensées le plus vite possible.

Refaites ensuite une deuxième passe dans votre rapport et soignez maintenant la forme. Relisez chaque paragraphe et corrigez toutes les fautes. N'hésitez pas à vous faire aider par des logiciels de correction tels que LanguageTool ou Antidote et ne passez pas au paragraphe suivant tant que vous n'êtes pas satisfait.

Règles de style

On n'écrit pas un rapport scientifique comme un blog ou comme un roman policier. Le but du rapport, c’est de documenter votre travail et ça ne sert à rien de faire des phrases compliquées. Privilégiez la simplicité, mais ne négligez pas la forme. Un rapport qui ne suit pas certaines règles n'est souvent pas agréable à lire.

Utilisez la voie active

Souvent, pour éviter d'écrire "je" ou "nous", nous choisissons de tourner la phrase au passif. Cette pratique rend le texte ennuyeux et lourd. Privilégiez donc autant que possible la voie active.

Considérer, par exemple, la phrase suivante" :

"Nous avons choisi un langage de programmation adapté au problème"

Pour éviter le "nous", on pourrait écrire :

"Un langage de programmation adapté au problème a été choisi"

On a alors une phrase au passif qui n'est pas franchement intéressante. Nous pouvons retourner la phrase à l'actif en évitant le "nous" avec :

"Une comparaison sur différents critères a permis de choisir un langage de programmation adapté au problème"

... et le tour est joué, la phrase est maintenant à l'actif.

Écrivez au présent

Le rapport présente la situation telle qu'elle est à la fin du projet et le plus simple, c’est d'écrire toutes les phrases au présent. Vous pouvez utiliser le passé dans l'introduction et le futur dans la conclusion si le contexte s'y prête, mais de manière générale, écrivez au présent.

Expliquez le "pourquoi" des choses

Vous avez passé de nombreuses heures à travailler dur votre projet et certaines choses semblent aller de soi. Mettez-vous à la place du lecteur et demandez-vous si ce que vous avez écrit est compréhensible par quelqu'un qui découvre votre travail.

Si vous écrivez "Il est clair que", ou "il va de soi que", est-ce vraiment si clair que ça pour le lecteur ? Votre rapport doit répondre aux questions, et ne pas en soulever d'autres.

Il en va de même avec les expressions "il faut", ou "on doit"; si vous écrivez "il faut", vous devez expliquer pourquoi c'est comme ça. Notez qze vous prendrez moins de risque en écrivant "on peut" au lieu de "on doit".

Si en lisant votre rapport, le lecteur se dit "mais pourquoi il écrit ça!" vous faites alors quelque chose de faux.

Utilisez des formes positives pour les phrases

Évitez le plus possible le mot "pas". Au lieu d'écrire "le système ne résout pas le problème dans le temps imparti", écrivez "le système prend plus de temps que toléré pour résoudre le problème".

Ne mettez pas l'accent sur les points négatifs de votre projet, mais parlez plutôt de tout ce qui s'est bien passé.

Évitez aussi d'écrire "nous avons dû faire...". Une telle phrase donne l'impression que c'était une corvée et sonne de manière négative. Préférez une tournure positive ou alors neutre : "nous avons fait...".

Éviter "malheureusement"

Le dictionnaire "Le Robert" définit le malheur comme "Évènement qui affecte péniblement, cruellement (qqn)." C'est souvent trop fort dans un rapport scientifique et ça donne une image négative à votre travail.

Évitez "s'occupe de"

Le verbe pronominal "s'occuper de" est souvent mal utilisé et alourdit inutilement la phrase. Au lieu d'écrire "Le compilateur s'occupe de traduire le programme", écrivez simplement "Le compilateur traduit le programme". Dès que vous pensez à écrire "s'occupe de", réfléchissez si vous pouvez vous en passer.

Typographie

Vous disposez aujourd'hui d'outils modernes pour produire des documents de haute qualité. Comme futur ingénieur et étudiant dans une haute école, je ne peux que vous recommander LaTeX pour produire vos documents. LaTeX vous permet de séparer votre document en plusieurs fichiers et vous avez accès à de nombreuses bibliothèques pour mettre en forme pratiquement n'importe quel document. Si vous ne voulez pas installer la suite LaTeX sur votre machine, vous pouvez utiliser les services de Overleaf. Pour apprendre LaTeX, je vous recommande l'excellent The Not So Short Introduction to LaTeX 2ε de Tobias Oetiker. Vous trouverez également beaucoup de documentation sur le site de Overleaf ou sur Wikibooks

Voici encore quelques modèles de documents LaTeX publiés par de très bons anciens étudiants de l'école :

Pas de souligné

En typographie moderne, on ne souligne plus le texte que l'on veut mettre en évidence. Cette pratique se faisait avec les machines à écrire mécaniques, mais avec les traitements de texte modernes, on préfère utiliser différentes polices et différents poids (semi-gras, gras…) pour remplacer le souligné.

Indentation des paragraphes

Un nouveau paragraphe commence soit par un espace horizontal au début de la première ligne, soit par espacement vertical. Mais attention, cette règle n'est valable pour les paragraphes qui en suivent un autre. Elle ne s'applique en général pas pour le premier paragraphe d'un chapitre, ni si le paragraphe est déjà précédé par un espace blanc vertical (par exemple, à la suite d'un tableau ou d'une illustration).

À mon avis, le plus simple est d'opter pour l'espace vertical entre les paragraphes. Avec LaTeX, vous pouvez utiliser le "package" parskip.

Commencez chaque chapitre ou sous-chapitre par une courte introduction

Évitez d'enchaîner un chapitre et un sous-chapitre sans mettre de texte pour introduire le chapitre.

De même, ne commencez pas un chapitre par un tableau, une illustration ou une liste à puce. Commencez toujours par du texte.

Illustrations

Les illustrations et les figures sont indispensables dans un rapport scientifique. N'hésitez pas à en abuser, mais faites attention à utiliser la même police d'écriture et la même grandeur de lettres que dans le texte principal.

Si votre illustration est trop grande, organisez les éléments de manière différente, mais n'utilisez pas de police plus petite que dans votre rapport.

Si vous faites des "screenshots" ou que vous mettez des "listings", évitez le "Dark Mode". Le "Dark Mode" s'est très bien à l'écran, mais dans un rapport imprimé sur du papier blanc, ça fait un trop grand contraste et ce n'est pas élégant.

Numérotez toutes les figures, les tables, les listings et référencez-les dans le texte

Les images ne sont pas que pour faire joli; elles permettent d'illustrer ce que vous avez écrit dans le texte. Toutes vos images auront donc un numéro et une légende, et on doit retrouver dans le texte une référence à l'image. Par exemple : "Comme illustré par la figure 12, ...". Cette règle vaut également pour les tables et les listings.

Ethique

Avec Internet et Wikipedia, c'est facile de copier des informations que vous trouvez en ligne. Ce n'est pas interdit de le faire, mais vous devez absolument citer toutes les sources que vous utilisez. Ça vaut pour tous les éléments de votre rapport : les textes, les illustrations, le code, ...

Mentionnez aussi toute utilisation d'intelligence artificielle (ChatGPT) pour produire du contenu.

L'article 29 du règlement sur la formation de base (bachelor et master) en HES-SO stipule que :

Toute fraude y compris le plagiat ou la tentative de fraude dans les travaux d’évaluation, les examens et le travail de bachelor ou le travail de master, entraîne la non-acquisition des crédits ECTS correspondants voire l’invalidation du titre et peut faire l’objet d’une des sanctions prévues à l’article 30.

Ne prenez pas de risque, citez toutes vos sources.

Conclusion

Je n'avais pas prévu d'écrire un article aussi long, mais j'espère que les conseils et les règles que je décris vous permettront de bien rédiger vos rapports d'étude et également les rapports professionnels que vous écrirez plus tard.

Remerciements

Merci à Rudolf Scheurer pour ses commentaires et suggestions constructifs.

Crédit

L'image en tête d'article est une photo de Markus Spiske sur Unsplash

Comment bien rater un travail écrit en 8 points faciles

Jacques Supcik — Mon, 19 Jul 2021 19:52:20 +0000

Voici comment bien rater un travail écrit.

Apprendre par cœur la veille du travail écrit (ou pendant les TPs des autres cours)
Apprendre par cœur les réponses (parfois fausses) des examens des années passées.
Répondre sans lire les questions
Répondre sans comprendre les questions
Répondre sans réfléchir ni vérifier la plausibilité des réponses
Ne pas répondre aux questions posées
Mettre des chiffres (mais sans unité) et des formules un peu partout
Écrire de manière illisible… on ne sait jamais, ça peut rapporter des points

Crédit

L'image en tête d'article est une photo de Polina Zimmerman sur Pexels

10 techniques efficaces pour bien rater ses études à la HEIA-FR!

Jacques Supcik — Mon, 19 Jul 2021 19:51:02 +0000

Voici 10 techniques efficaces et éprouvées pour bien rater ses études à la HEIA-FR.

Ne pas écouter pendant le cours
Ne pas prendre de notes
Ne jamais poser de question, même si on ne comprend pas
Surtout ne pas faire les exercices
Laisser les collèges faire les TPs
Garder son PC ouvert ou garder son smartphone à la main pour ne pas rater les notifications
Regarder des vidéos drôles ou jouer pendant le cours et les TPs
“Chater” et rigoler avec collègues pendant le cours
Apprendre par coeur sans comprendre
Ne pas lire les livres conseillés, mais chercher les solutions des exercices et des TPs sur Internet

Crédit

L'image en tête d'article est une photo de Kind and Curious sur Unsplash

L'algorithme de recherche binaire

Jacques Supcik — Mon, 19 Jul 2021 19:45:00 +0000

La recherche binaire (binary search) fait partie des algorithmes fondamentaux de l'informatique que tout bon informaticien se doit de connaître. Dans leur célèbre livre A Method Of Programming, Edsger W. Dijkstra et W.H.J. Feijen qualifient même cet algorithme de «quasi canonique»:

The binary search [...] is an important, almost canonical, algorithm. It should be familiar in all its details to any educated computer scientist.

Je constate cependant que rares sont les programmeurs qui aujourd'hui, sont capables de comprendre et d'implémenter correctement cet algorithme. Ils l'ont peut-être oublié, ou peut-être ne l'ont-ils jamais vraiment appris.

Le but de cet article est d'expliquer cet algorithme à l'aide de prédicats logiques et de vous permettre de l'implémenter de manière efficiente et correcte.

L'algorithme de recherche binaire permet de trouver efficacement un élément dans un tableau trié. Commençons par définir formellement ce qu'est la recherche d'un élément dans un tableau:

Si $a$ un tableau de taille $N$ , avec des index $\leq i < N$ et si $x$ est un élément de ce tableau, trouver $x$ dans $a$ revient à trouver l'index $i_x$ tel que $a[i_x]$ soit égal à $x$ .

i_x : 0 \leq x_i < N : x \in a \wedge a[i_x] = x

Nous avons aussi dit que le tableau est trié (du plus petit au plus grand). Ca signifie que pour tout $i$ et $j$ , si $i$ est plus petit ou égal à $j$ alors $a [i]$ est aussi plus petit ou égal à $a [j]$ .

\forall i,j : 0 \leq i \leq j < N : a[i] \leq a[j]

Nous pouvons généraliser l'objectif de la recherche dans le cas où l'élément recherché $x$ est présent plusieurs fois. Dans ce cas, nous aimerions avoir l'index du premier $x$ . Autrement dit, l'élément qui précède $x$ doit être strictement plus petit que $x$ :

i_x : 0 \leq x_i < N : x \in a \wedge a[i_x] = x \wedge a[i_x-1] < x

Cette nouvelle condition peut s'avérer problématique si $x$ est le tout premier élément du tableau $a$ . Dans ce cas, $i_x-1$ est égal à $- 1$ et $a [- 1]$ n'est pas défini. Nous pouvons résoudre ce problème en définissant un élément virtuel à la position $- 1$ qui soit plus petit que tous les autres éléments du tableau:

\infty

Nous sommes partis du principe que $x$ soit présent dans $a$ , mais nous pouvons lever cette contrainte en spécifiant que si $x$ n'est pas dans $a$ , alors on aimerait avoir l'index où il devrait être. Si $x$ est strictement plus petit que $a [0]$ , alors le prédicat est satisfait en mettant $i_x$ égal à $0$ . Si $x$ est strictement plus grand que $a [N - 1]$ , l'index où il devrait être c'est $N$ , mais $a [N]$ n'est pas défini.Nous contournons le problème de la même manière que pour $a [- 1]$ en définissant un nouvel élément virtuel à la position $N$ qui soit plus grand que tous les autres éléments du tableau:

\infty

On peut récrire le prédicat de la recherche ainsi:

i_x : 0 \leq x_i \leq N : a[i_x] \geq x \wedge a[i_x-1] < x

Au début, l'intervalle de recherche est $[0.. N]$ , l'idée de l'algorithme de recherche binaire consiste à réduire cet intervalle à chaque itération afin de trouver $i_x$ . Nous définissons l'intervalle de recherche à l'aide de deux nouvelles variables : $L$ (pour left ou lower) et $R$ (pour right). Ces nouvelles variables devront en tout temps satisfaire l'invariant suivant:

\leq L < R \leq N : a[L] < x \wedge a[R] \geq x

Pour commencer, nous pouvons initialiser $L$ à $- 1$ et $R$ à $N$ . Grâce à nos deux éléments virtuels, l'invariant est satisfait, car $\infty < x$ et $\infty \geq x$ . Il nous suffit maintenant de réduire l'intervalle $] L, R]$ et quand $L$ sera juste à côté de $R$ , nous aurons $L = R - 1$ et si l'invariant est toujours vrai, alors on aura $\leq x_i \leq N : a[R] \geq x \wedge a[R-1] < x$ et $R$ sera le $i_x$ que nous cherchons.

Avant de coder la recherche binaire, il nous faut encore juste trouver comment réduire l'intervalle $] L, R]$ tout en conservant l'invariant. La solution consiste à prendre un $h$ n'importe où entre $L$ et $R$ ( $L < h < R$ ) et si $a [h]$ est strictement plus petit que $x$ , alors nous pouvons donner à $L$ la valeur de $h$ , car $a [L]$ serait strictement plus petit que $x$ comme nous ne modifions pas $R$ , l'invariant tiendrait toujours. Au contraire, si $a [h]$ est plus grand ou égal à $x$ , alors nous pouvons donner à $R$ la valeur de $h$ , car $a [R]$ serait plus grand ou égal à $x$ comme nous ne modifions pas $L$ , l'invariant tiendrait encore.

Tant que $L < R - 1$ , on peut toujours trouver un $h$ entre $L$ et $R$ . On peut par exemple prendre $h = L + 1$ ou $h = R - 1$ , mais notre algorithme ne ferait que des tout petits pas vers la solution. Une manière plus efficace consiste à prendre $h$ au milieu de l'intervalle $] L, R]$ , autrement dit $\frac{L+R}{2}$ . $h$ est un index et doit être un nombre entier; nous devons alors arrondir $h$ vers un entier. On peut sans autre arrondir $h$ vers le haut ou vers le bas et nous décidons ici de l'arrondir vers le bas : $\lfloor\frac{L+R}{2}\rfloor$ . Si $L < R - 1$ , alors $\lfloor\frac{L+R}{2}\rfloor < R$ . Si $L = R - 1$ , la recherche est terminée et nous n'avons plus besoin de réduire l'intervalle.

Nous avons maintenant assez de logique et de math pour pouvoir écrire un algorithme de recherche binaire correct. Pour cet article, nous décidons de coder cet algorithme en Python:

def binary_search(a: list, x) -> int:
    L:int = -1
    R:int = len(a)
    while (L < R-1):
        h: int = (L+R) // 2
        if a[h] < x:
            L = h
        else:
            R = h
    return R

Python n'a pas de problème de dépassement de capacité (overflow) avec les entiers, mais la plupart des autres langages n'ont pas ce confort et l'opération L+R pourrait provoquer un dépassement de capacité. On pourrait alors sans autre remplacer h = (L+R) // 2 par h = L + (R-L) // 2 et ainsi supprimer le risque de dépassement de capacité.

Si on souhaite savoir si $x$ est présent dans $a$ et retourner un boolean, on peut alors écrire

def present(a: list, x) -> bool:
    R = binary_search(a, x)
    return R < len(a) and a[R] == x

Pour compléter, voici l'algorithme codé en C:

#include <stdbool.h>

int binary_search(int* a, int n, int x) {
    int L = -1;
    int R = n;
    while (L < R-1) {
        int h = L + (R-L) / 2;
        if (a[h] < x) {
            L = h;
        } else {
            R = h;
        }
    }
    return R;
}

bool present(int* a, int n, int x) {
    int R = binary_search(a, n, x);
    return (R < n && a[R] == x);
}

De nos jours, on écrit souvent des programmes ou des «apps» en utilisant des «frameworks» et en copiant des bouts de code trouvés sur Internet. Les programmeurs amateurs diront qu'il est inutile de comprendre les détails des algorithmes fondamentaux, car ils ont déjà été implémentés par des personnes très compétentes et qu'il suffit d'utiliser la bonne bibliothèque. L'informaticien qui se respecte ne peut se satisfaire d'une telle démarche et sa saine curiosité ne sera satisfaite que lorsqu'il aura compris et implémenté lui-même l'algorithme.

J'espère que cet article aura ravivé la mémoire de certains et éveillé chez d'autres l'envie d'étudier plus en détail la science et l'art de l'informatique. Voici pour conclure quelques livres qui vous permettront d'en savoir plus:

Crédit : L'image en tête d'article est une photo de UX Indonesia sur Unsplash

Les 10 commandements du programmeur à la Haute école d'ingénierie et d'architecture de Fribourg

Jacques Supcik — Mon, 19 Jul 2021 15:13:51 +0000

Tu peux déroger à ces commandements si tu les comprends bien et si le code résultant est plus lisible et plus élégant… mais réfléchis bien!

1. Tu éviteras les variables globales

Tu n'utiliseras pas de variable globale et les méthodes ne modifieront pas d'état global.

2. Tu mettras un entête dans chaque fichier source

Tu commenceras tous les fichiers sources par un commentaire avec un copyright, un titre, le ou les auteurs, la date de création et la date de dernière modification.

3. Tu choisiras les identificateurs avec grand soin

Tu nommeras les identificateurs avec soin. Tu utiliseras un verbe d'action pour une procédure, et tu utiliseras un nom qui décrit le résultat pour une fonction. Pour les variables, tu utiliseras des noms descriptifs sans abuser des abréviations. Si une variable à une très courte portée (par exemple, une boucle sur quelques lignes), tu pourras utiliser des identificateurs d'une seule lettre comme i, j, k. Les identificateurs seront en anglais sans caractères spéciaux (uniquement des lettres, des chiffres et des "underscores"). Cette règle s'applique aussi aux noms des classes, des modules et des "namespaces".

Sache que cette règle est difficile à appliquer, mais elle contribue grandement à faire la différence en un bon et un excellent programmeur.

4. Tu soigneras le style

Tu utiliseras un style consistant dans tous tes codes sources. Tu respecteras les pratiques usuelles, la façon d'écrire du code et les conventions du langage utilisé. Tu indenteras avec des espaces (et non des tabulateurs). Tu n'écriras aucune ligne de plus de 120 caractères. Tu veilleras aussi à limiter la taille des méthodes (~50 lignes) et des modules.

N'hésite pas à utiliser les outils de mise en page (formater) pour garder un style consistant. Les outils d'analyse statique de code (linter) peuvent aussi t'aider à corriger des fautes de style.

5. Tu écriras des commentaires

Tu écriras un court commentaire devant chaque méthode publique. Ce commentaire expliquera ce que fait la méthode. Tu pourras aussi documenter les arguments, le résultat, les "pre-" et "post-conditions", le contrat … Tu peux aussi appliquer cette pratique aux méthodes privées.

Documente aussi les parties plus complexes d'un programme, mais ne documente pas ce qui est trivial. Un commentaire ne doit pas remplacer un mauvais choix de nom pour un identificateur.

6. Tu n'utiliseras aucun "nombre magique" dans ton code.

Toutes les constantes auront un nom descriptif. Une exception est admise ou les cas évidents tels que count=0 ou i+=1.

7. Tu utiliseras un outil de gestion de codes sources

Tu utiliseras toujours un outil de gestion de codes sources tel que "git" pour toutes tes sources. Tu feras des "commits" régulier, avec des commentaires utiles, et tu synchroniseras souvent ton dépôt avec un dépôt distant. Rien ne pourra excuser la perte ou la suppression accidentelle d'un fichier source.

8. Tu ne feras pas de "Copier-Coller"

Tu ne dupliqueras pas de code. Si tu es tenté de faire un "copier-coller", réfléchis à une procédure ou une fonction supplémentaire qui te permettra d'éviter cette pratique. Ce commandement est aussi connu sous le terme DRY : "Don't repeat yourself". Mais attention à ne pas tomber dans l'extrême; privilégiez toujours la simplicité et la lisibilité.

9. Tu feras des tests unitaires

Tu vérifieras les méthodes de ton programme avec des tests unitaires. Ça ne sera pas possible pour toutes les méthodes, mais tu feras au mieux. Tu utiliseras les outils et les bonnes pratiques du moment pour le langage choisi.

10. KISS "Keep It Small and Simple"

Tu ne rendras donc pas ton programme inutilement complexe. Au contraire, tu rechercheras la perfection en le simplifieras au maximum et en implémentant des algorithmes efficaces.

Crédit

L'image en tête d'article est une photo de Darren Halos sur Pexels