À la découverte des Arbres Binaires à Commande Équilibrée

Magazine
Marque
GNU/Linux Magazine
Numéro
215
Mois de parution
mai 2018
Domaines


Résumé
Dans cet article un peu théorique, nous allons jouer avec la métaphore des aiguillages. Vous pensiez peut-être que concevoir une gare de triage est un jeu d'enfant, mais quand des contraintes (fictives ? réelles ?) s'en mêlent, il faut se gratter un peu la tête et faire appel à des permutations astucieuses... C'est ainsi qu'apparaissent les ABCE, ou Arbres Binaires à Commande Équilibrée, une technique inhabituelle qui trouve sa place, entre autres, dans des circuits électroniques numériques.

Je vous propose ici une amélioration d'une structure incontournable en informatique et en électronique : l'arbre binaire équilibré, tel qu'on le voit sur la figure 6a. Bien qu'elle soit idéale du point de vue du cheminement des données (tous les chemins de la racine vers les feuilles sont de la même longueur minimale), elle pose quelques soucis dans certains cas. Heureusement, nous allons voir que la structure de la figure 6a n'est qu'une des manières de contrôler un arbre binaire équilibré : nous allons découvrir et apprendre à construire d’autres versions, où les signaux de commande sont aussi équilibrés.

Pour garder l'explication abordable, je ne désire pas employer des mots effrayants comme topologie, parcours infixe et théorie des graphes alors nous allons nous mettre dans la peau d'un jeune ingénieur de la Compagnie de Chemins de Fers. Évidemment, rien de ce qui suit ne prétend à une quelconque exactitude ferroviaire, mais cette métaphore s'impose...

Cet article est réservé aux abonnés. Il vous reste 96% à découvrir.
à partir de 21,65€ HT/mois/lecteur pour un accès 5 lecteurs à toute la plateforme
J'en profite


Articles qui pourraient vous intéresser...

L’édition des liens démystifiée

Magazine
Marque
GNU/Linux Magazine
Numéro
244
Mois de parution
janvier 2021
Domaines
Résumé

Parmi les étapes concourant à la fabrication d’un exécutable, l’édition des liens est certainement la plus méconnue. Elle est pourtant cruciale à plus d’un titre. Le choix entre édition statique et dynamique des liens a notamment des implications sur la facilité de développement, la sécurité et la performance.

Scikit-image, une alternative à OpenCV pour la reconnaissance d'images

Magazine
Marque
GNU/Linux Magazine
Numéro
244
Mois de parution
janvier 2021
Domaines
Résumé

Une fois n'est pas coutume, nous allons découvrir et utiliser une alternative à OpenCV, scikit-image communément appelé skimage. Nous implémenterons la reconnaissance d'images avec la méthode des histogrammes de gradients orientés (HOG : Histogram of Oriented Gradients) associée à une machine à vecteurs de support (SVM : Support Vector Machine). Cette méthode est employée dans bien des applications telles que l'automobile, pour la détection de piétons [1].