La machine à algorithmes : 13 étapes (avec photos)

2024 Auteur: John Day | [email protected]. Dernière modifié: 2024-01-30 09:06

J'enseigne l'informatique au niveau collégial depuis 15 ans, et bien que mon expertise soit davantage du côté de la programmation, je passe encore pas mal de temps à couvrir les algorithmes standards de recherche et de tri. D'un point de vue pédagogique, la question centrale est la complexité de calcul: combien de temps chaque algorithme nécessite-t-il, compte tenu d'une entrée d'une taille particulière ? Mais il y a de nombreuses nuances. Par exemple, les algorithmes ont-ils des temps d'exécution différents en fonction des valeurs d'entrée spécifiques (par opposition à la taille) ? Dans quels cas choisiriez-vous un algorithme de tri plutôt qu'un autre ? Bien que nous discutions de ces problèmes dans l'abstrait, cela m'a toujours ennuyé qu'il n'y ait pas de moyen facile de voir comment différents algorithmes fonctionnent dans diverses conditions.

Buts

Mon objectif principal pour ce projet était de créer un affichage interactif permettant aux étudiants de visualiser et d'explorer des algorithmes. Je me suis limité aux algorithmes qui fonctionnent sur des tableaux de valeurs (entiers), donc je peux utiliser une bande LED RVB adressable pour visualiser le contenu du tableau. Le tableau comporte 100 éléments et chaque entier est associé à une couleur dans l'ordre de l'arc-en-ciel, de sorte qu'il est immédiatement évident lorsque le tableau est trié, partiellement trié ou randomisé. En plus des valeurs, cependant, je voulais un moyen de visualiser les aspects de contrôle de l'algorithme - par exemple, quels éléments du tableau sont actuellement comparés ou échangés.

Les objectifs spécifiques sont:

- Fournir une variété d'algorithmes de recherche et de tri

- Visualisez les valeurs dans le tableau d'une manière qui met en évidence la progression de l'algorithme

- Visualiser le contrôle de l'algorithme; en particulier, les éléments considérés.

- Permettre aux utilisateurs de choisir les modèles de données d'entrée plutôt que de toujours générer des valeurs aléatoires

- Permettre aux utilisateurs de contrôler la vitesse et de mettre en pause l'algorithme

- Autoriser les utilisateurs à forcer le comportement dans le meilleur des cas, dans le pire des cas, dans les cas moyens (spécifique à l'algorithme)

- Afficher le nombre d'étapes au fur et à mesure que l'algorithme avance

Visualisation

Du point de vue de la conception physique, la partie la plus intéressante de ce projet est la visualisation du réseau. J'ai eu du mal à montrer les données et le contrôle, et à construire le périphérique d'affichage lui-même. Mon objectif était d'afficher les valeurs de données sous forme de cercles colorés et les points de contrôle sous forme de flèches colorées pointant vers les valeurs de données. Après quelques expérimentations, j'ai opté pour une conception avec deux bandes parallèles de 100 LED RVB (WS2812) avec un masque circulaire sur chaque LED de données et un masque triangulaire sur chaque LED de contrôle. J'ai fait un modèle 3D du masque avec 10 paires de cercles et de triangles, puis j'ai imprimé en 3D 10 de ces modules pour un total de 100 cercles et 100 triangles. La taille et l'espacement de mon masque sont conçus pour des bandes de 100 LED par mètre. Les fichiers de modèle 3D sont fournis plus loin dans cette description.

Electronique et boitier

Le reste de l'appareil est simple, d'un point de vue électronique. En plus des deux bandes LED, il y a un tas de boutons momentanés, un encodeur rotatif (pour le contrôle de la vitesse) et un affichage à 7 segments (pour afficher les étapes). Avec autant de boutons et de commandes, j'ai choisi d'utiliser un microcontrôleur ESP32 car il expose beaucoup de broches et parce qu'il est assez puissant. Je vais passer en revue la stratégie de câblage, mais c'est assez basique. Vous pourriez probablement faire quelque chose d'intelligent avec les registres à décalage si vous souhaitez utiliser moins de broches.

Vous pouvez construire le boîtier de cet appareil sous de nombreuses formes différentes. Je l'ai d'abord imaginé comme un grand tableau rectangulaire avec la bande LED en haut et une grille de boutons au milieu. La forme avec laquelle j'ai fini est inspirée d'une sorte de vision des années 60 de la technologie de l'ère spatiale. Vous pouvez également le construire avec les bandes LED dans une orientation verticale. Ou agrandissez la partie LED - remplissez un mur entier - avec un panneau de commande séparé.

Logiciel

Le code de cet appareil est disponible gratuitement sur GitHub, et j'ai fait de mon mieux pour documenter son fonctionnement et sa configuration. La seule bibliothèque externe dont vous avez besoin est FastLED pour piloter les bandes WS2812.

Fournitures

Électronique

1 carte de développement ESP32 (par exemple, 2 bandes LED WS2812 ou similaires, densité 100 LED par mètre (par exemple, 1 bouton « démarrer » triangulaire (par exemple, 12 boutons momentanés (par exemple, https://amzn.com/B01N4D4750) -- différentes formes si vous le souhaitez

1 paquet (20) connecteurs de bouton précâblés (par exemple, 1 pack de connecteurs JST (par exemple, 1 encodeur rotatif (par exemple, 1 bouton pour encodeur rotatif (par exemple, 1 Pack de connecteurs Dupont (par exemple, https://amzn.com/B014YTPFT8) - cela vaut également la peine d'obtenir l'outil de sertissage.

1 prise Barrel (pour l'alimentation) (par exemple, 1 affichage numérique à 7 segments TM1637 (par exemple, Matériel de soudure et de câblage

Fichiers de modèle 3D

Vous pouvez trouver le modèle 3D d'une paire de modules à 10 lumières sur Thingiverse:

www.thingverse.com/thing:4178181

Vous devrez imprimer ce modèle cinq fois pour un total de 10 modules.

Logiciel

github.com/samguyer/AlgorithmMachine

Enceinte

Bois, plexiglas, boulons et vis en acier inoxydable

Matériel de diffusion. Mon préféré est Lee Filters #216 à diffusion entièrement blanche, mais il existe d'autres options. Même le papier blanc ordinaire fait du bon travail.

Étape 1: Algorithmes 101

Beaucoup de gens pensent que l'informatique est essentiellement l'étude de la programmation. Mais le véritable cœur et l'âme de ce domaine sont les algorithmes: l'étude des procédures systématiques pour résoudre les problèmes et leur coût (typiquement, combien de temps elles prennent). Des personnalités du domaine, comme Alan Turing, Alonzo Church et Edsger Dijkstra, pensaient à ces idées avant même que les ordinateurs tels que nous les connaissons n'existent.

La caractéristique clé d'un algorithme pour résoudre un problème particulier est qu'il est détaillé et précis, de sorte que quelqu'un pourrait l'utiliser pour obtenir une solution sans comprendre du tout comment il fonctionne; suivez simplement les étapes de manière mécanique et vous obtiendrez la bonne réponse. Vous pouvez voir comment cela aide à programmer des ordinateurs, car ils ont besoin de ce niveau de détail. Un ordinateur ne peut pas remplir les détails manquants ou porter des jugements, comme une personne peut le faire.

Combien de temps cela prendra-t-il?

Une fois que nous avons une procédure détaillée, une question naturelle est de savoir combien de temps faudra-t-il pour obtenir la réponse ? Nous ne pouvons pas utiliser d'unités de temps ordinaires, car cela dépend de qui fait le travail (comparez la vitesse à laquelle une personne peut calculer quelque chose par rapport à un superordinateur). De plus, cela dépend de la quantité de données dont nous disposons. De toute évidence, il faut plus de temps pour rechercher une liste d'un million de numéros de téléphone qu'une liste d'une centaine.

Pour décrire le coût d'un algorithme, nous choisissons d'abord une opération dans la procédure qui représente une "étape" - généralement quelque chose de simple, comme comparer ou ajouter deux nombres, qui prend un temps fixe à faire. Ensuite, nous proposons une formule qui décrit le nombre d'étapes que l'algorithme effectuera en fonction d'un certain nombre d'éléments de données. Pour des raisons historiques, nous désignons presque toujours le nombre de données avec un N majuscule.

Par exemple, parcourir une liste de N numéros de téléphone nécessite N étapes. Parcourir la liste deux fois prend 2N étapes. Ces deux algorithmes sont appelés algorithmes de temps linéaire - le nombre total d'étapes est un multiple de la taille de l'entrée. D'autres algorithmes sont quadratiques (N temps au carré) ou cubiques (N au cube) ou logarithmiques (log N) ou une combinaison de ceux-ci. Certains des problèmes de calcul les plus difficiles nécessitent des algorithmes à temps exponentiel (2^N).

Okay, alors quoi?

Lorsque le nombre d'éléments de données N est petit, cela n'a pas beaucoup d'importance. Par exemple, pour N=10, 10N est ce nom comme N au carré. Mais qu'en est-il de N=1000 ? ou N=1000000 ? Un million au carré est un assez gros nombre. Même sur un ordinateur très rapide, un algorithme quadratique peut prendre beaucoup de temps si l'entrée est suffisamment grande. Les algorithmes exponentiels sont beaucoup plus gênants: pour N=50, un algorithme exponentiel mettrait deux semaines à se terminer même sur un ordinateur où chaque étape ne dure qu'une nanoseconde (1 milliardième de seconde). Aie!

À l'autre extrémité de l'échelle, nous avons des algorithmes de temps logarithmique, qui sont très rapides. Le temps de journal est l'opposé du temps exponentiel: étant donné la taille d'entrée N, le nombre d'étapes est l'exposant T dans la formule 2^T = N. Par exemple, si notre taille d'entrée est d'un milliard, un algorithme de temps de journal ne nécessite que 30 étapes, puisque 2^30 = 1, 000, 000, 000. Comme c'est doux ?!??!

Vous vous demandez peut-être qui se soucie de la taille des entrées de millions ou de milliards ? Pensez-y: combien y a-t-il d'utilisateurs sur Facebook ? Combien de pages Web sont indexées par Google ? Combien y a-t-il de paires de bases dans le génome humain ? Combien de mesures entrent-elles dans une simulation météorologique ?

Étape 2: Les algorithmes

La machine à algorithmes implémente actuellement les algorithmes suivants. Deux d'entre eux sont des algorithmes de recherche (trouver une valeur particulière dans la liste), les autres sont des algorithmes de tri (mettre les valeurs dans l'ordre).

Recherche linéaire

Recherchez dans la liste des valeurs une par une en commençant par le début. Nécessite un temps linéaire.

Recherche binaire

Recherchez une liste en la divisant en deux à plusieurs reprises. Nécessite du temps de journal, mais la liste doit être triée pour que cela fonctionne.

Tri à bulles

Triez une liste en échangeant à plusieurs reprises des éléments voisins qui ne sont pas en ordre. Nécessite un temps quadratique.

Tri par insertion

Triez une liste en plaçant chaque élément à sa place dans la liste des valeurs déjà triées. Nécessite un temps quadratique.

Tri rapide

Triez une liste en divisant à plusieurs reprises la liste en deux et en déplaçant toutes les valeurs inférieures à la médiane vers la première moitié et toutes les valeurs supérieures à la médiane vers la seconde moitié. En pratique, nous ne pouvons pas trouver efficacement la médiane, nous choisissons donc une valeur au hasard. En conséquence, cet algorithme peut être quadratique dans le pire des cas, mais nécessite généralement N * logN temps.

Tri par fusion

Triez une liste en la divisant en deux, en triant les deux moitiés séparément (en utilisant le tri par fusion), puis en les fusionnant en entrelacant les valeurs. Nécessite toujours N * temps logN.

Tri par tas

Triez une liste en créant une structure de données appelée tas, qui vous permet de trouver la plus petite valeur en temps de journal. Nécessite toujours N * temps logN.

Tri bitonique

Semblable au tri par fusion et au tri rapide, divisez une liste en deux, triez les moitiés et recombinez-les. Cet algorithme nécessite N * logN * logN temps, mais a l'avantage d'être facile à paralléliser.

Étape 3: Barre LED: Imprimez le masque en 3D

La première étape de la construction de la barre LED consiste à imprimer en 3D le masque qui donne aux lumières leur forme. Chaque module couvre dix éléments du tableau, 10 valeurs (cercles) et 10 indicateurs (triangles), vous aurez donc besoin de 10 modules au total. Le fichier STL que je fournis ici contient deux instances du module, vous devrez donc effectuer cinq cycles d'impression. Je n'ai pas la meilleure imprimante 3D, j'ai donc dû les nettoyer manuellement à l'aide d'une lime et de papier de verre. Le plus important est que les trous circulaires et triangulaires soient propres.

Sur les photos, vous verrez ma configuration de test: j'ai scotché les deux bandes de LED et les ai connectées à une planche à pain avec un microcontrôleur. Cette étape n'est pas nécessaire, mais je voulais voir à quoi cela ressemblerait avant de commencer à assembler le boîtier. J'ai aligné les modules de masque sur les deux bandes LED et j'ai exécuté un croquis simple avec des couleurs aléatoires. Avec une bande de matériau de diffusion, les formes et les couleurs ressortent vraiment.

Étape 4: Alternatives à la barre LED

Lorsque j'ai commencé ce projet, j'ai expérimenté d'autres façons de fabriquer le masque à LED. Si vous n'avez pas d'imprimante 3D, vous pouvez envisager l'une de ces options. Je vais être honnête: c'est une énorme douleur de faire ces pièces.

Pour les cercles, j'ai acheté un tube en laiton 13/32, qui fait presque exactement 1cm de diamètre. Je l'ai coupé en cent segments de 1 cm, puis je les ai peints en blanc.

Pour les triangles, j'ai utilisé du papier d'aluminium épais découpé dans un moule jetable. J'ai fait une forme triangulaire en bois, puis j'ai enveloppé de courtes bandes de papier d'aluminium autour de la forme et je les ai scotchées. Encore une fois, vous aurez besoin d'une centaine de ces choses, donc cela prend du temps et de la patience.

Étape 5: Boîtier de barre LED

Mon boîtier est assez simple: deux lames de bois pour les côtés et deux lames de plexiglas pour le haut et le bas. Toutes les pièces font environ 102cm de long (1 mètre pour les LED, plus un petit plus pour loger le câblage). Les côtés doivent être un peu plus hauts que 1 cm pour faire de la place pour les bandes LED. Après avoir coupé les bandes, j'ai pris en sandwich les morceaux de masque imprimés en 3D entre eux pour mesurer la largeur du plexiglas. Coupez deux morceaux de plexiglas de la largeur et de la longueur de la barre. Enfin, découpez une bande de matériau de diffusion pour qu'elle s'adapte sur le masque.

Pour la diffusion, j'aime beaucoup les filtres Lee #216 (diffusion entièrement blanche). C'est une fine feuille de plastique qui donne une diffusion uniforme sans perdre beaucoup de lumière. Mais c'est des trucs chers. Parfois, vous pouvez trouver des feuilles plus petites à vendre en ligne, mais un rouleau entier vous coûtera environ 125 $. Certaines autres options sont le papier blanc ou tout autre type de plastique satiné ou dépoli. Un choix populaire est les tapis de coupe en plastique mince.

Avant d'assembler la barre LED, assurez-vous que les connecteurs appropriés sont soudés aux bandes LED. Beaucoup de bandes sont livrées avec des fils pré-soudés, vous pouvez donc simplement les utiliser.

J'ai commencé le montage en vissant la pièce supérieure en plexiglas sur les côtés en bois (voir photo). Ensuite, je l'ai retourné et j'ai placé la bande de diffusion, suivie des 10 morceaux de masque. Une fois satisfait de l'espacement, je les ai épinglés avec quelques points de colle chaude.

Ensuite, posez les deux bandes LED côte à côte sur le dessus des masques. Assurez-vous que les LED sont orientées vers le bas et assurez-vous que chaque LED s'aligne avec le trou correspondant dans le masque. Ajoutez de la colle chaude ou du ruban adhésif pour maintenir les bandes LED en place. Enfin, vissez la pièce arrière en plexiglas.

Exécutez un modèle de test. Bon travail! Vous avez fait le plus dur !

Étape 6: Panneau de configuration

Le panneau de contrôle est la partie qui offre la plus grande liberté de création. Il a juste besoin de contenir toutes les commandes et l'électronique, ainsi que la barre LED. La conception la plus simple est une planche rectangulaire: percez des trous pour les boutons et les commandes, et fixez la barre LED. J'aime combiner le bois, le plexiglas et d'autres matériaux pour donner une sorte de look steampunk/rétro-moderne. Dans ce cas, j'ai découpé un morceau de plexiglas robuste pour contenir les principaux boutons de choix de l'algorithme et une barre en bois pour contenir le reste de l'électronique. J'ai percé des trous pour correspondre à la taille des boutons d'arcade. Le câblage est visible à l'arrière, mais j'aime ça !

J'ai également percé de l'espace pour l'affichage à 7 segments, l'encodeur rotatif et une partie du câblage à l'arrière. J'ai coupé un dado en haut pour tenir la barre LED.

Étape 7: Harnais de boutons

Câblage de nombreux boutons peut être une vraie douleur. Heureusement, les fabricants de machines d'arcade ont mis au point des connecteurs standard que vous pouvez utiliser. Chaque câble de connecteur de bouton a deux fils, un pour VCC et un pour la terre. Une extrémité a des connecteurs à fourche qui s'adaptent aux fils à l'arrière du bouton - fixez la terre au fil "normalement ouvert" et VCC au fil "commun". Dans cette configuration, lorsque l'utilisateur appuie sur le bouton, le circuit est terminé et le microcontrôleur lira HIGH sur la broche d'entrée correspondante.

L'autre extrémité du câble a un connecteur JST (le petit truc blanc). Ce qui est bien avec ces connecteurs, c'est qu'ils n'entrent dans la prise que d'une seule manière, il n'y a donc aucun moyen d'inverser accidentellement le VCC et la masse.

Ce que j'ai fait, c'est construire un petit harnais pour ces connecteurs. Je soude une série de réceptacles JST sur un morceau de protoboard, puis je ramène les fils aux connecteurs Dupont que je vais brancher sur le microcontrôleur. Le fil rouge est la ligne VCC, et il se connecte à toutes les prises JST. Les fils bleus sont ceux qui sont séparés pour chaque bouton.

Étape 8: Encodeur rotatif

L'encodeur rotatif permet à l'utilisateur de contrôler la vitesse de l'algorithme. J'utilise un module qui se présente sous la forme d'une carte de dérivation qui comprend des résistances de rappel pour les deux lignes de données (fils jaunes). Celui-ci se trouve également être un bouton, mais je n'utilise pas cette fonctionnalité. Les deux autres fils sont VCC et terre. J'ai aussi un beau gros bouton.

Ce que j'aime dans un encodeur rotatif, par opposition à un potentiomètre, c'est qu'il signale simplement la rotation (dans le sens des aiguilles d'une montre ou dans le sens inverse des aiguilles d'une montre) au microcontrôleur, il est donc facile de changer la façon dont la valeur est interprétée. Par exemple, vous pouvez lui donner une impression d'accélération (comme une souris) lorsque l'utilisateur la fait tourner rapidement.

Étape 9: affichage à 7 segments

Pas grand chose à dire ici. Ces choses sont partout. Les LED sont contrôlées par une puce appelée TM1637, qui communique avec le microcontrôleur via un simple protocole série. J'utilise une bibliothèque existante qui me permet de lui dire quel numéro je veux afficher, et elle fait le reste.

Le dos a quatre broches: VCC, terre et deux fils pour le protocole série. J'ai soudé un morceau d'en-tête à 4 broches, qui se connecte à un connecteur Dupont correspondant câblé au microcontrôleur.

Étape 10: Carte contrôleur principale

La carte contrôleur principale abrite le microcontrôleur lui-même et tous les connecteurs des commandes (boutons, affichage, LED). Le microcontrôleur est un ESP32, qui fournit beaucoup de puissance de calcul et de mémoire, et expose beaucoup de broches. Le câblage est assez standard, mais je vais souligner quelques éléments intéressants.

REMARQUE: vous voudrez peut-être consulter le code (https://github.com/samguyer/AlgorithmMachine) avant de commencer à câbler la carte principale, afin que votre configuration de broches corresponde à la mienne.

J'ai soudé une prise cylindrique sur la carte pour l'alimentation et connecté deux gros fils de cuivre aux rails d'alimentation et de terre de la carte. La raison en est que la barre LED peut consommer beaucoup d'énergie si la luminosité est élevée, et je ne veux pas tirer toute cette puissance via le connecteur USB du microcontrôleur.

Pour simplifier le câblage des boutons, j'ai soudé une bande d'en-tête à angle droit mâle-femelle sur tout le côté du microcontrôleur (côté supérieur de la carte, comme indiqué). Les connecteurs Dupont du faisceau de boutons se branchent directement sur cet en-tête.

IMPORTANT: l'alimentation des boutons (le fil rouge) doit être connectée à la ligne d'alimentation 3,3 V du microcontrôleur. L'ESP32 est une puce de 3,3 V, donc seules des sources de 3,3 V doivent être connectées aux broches de données.

Le microcontrôleur tire l'alimentation (ou pousse l'alimentation) vers les rails (côté inférieur de la carte, comme illustré) via la broche USB 5V et la terre. Tous les autres fils rouges/noirs sont VCC et terre.

Les deux fils bleus sont les lignes de données pour les bandes LED (les WS2812). La paire jaune/verte correspond aux lignes de données de l'encodeur rotatif et la paire jaune correspond à la connexion série à l'affichage à 7 segments.

Étape 11: Assemblage

Cette série de photographies montre l'assemblage final et le câblage. J'ai également attaché la carte contrôleur principale à l'arrière en haut.

Avant de le mettre sous tension, j'ai fait quelques vérifications pour éviter les mauvaises surprises. En particulier, pour m'assurer que je n'avais pas de connecteurs d'alimentation/masse à l'envers, et pas de courts-circuits. Réglez votre multimètre pour tester la continuité - il émet un bip lorsqu'il y a un chemin électrique entre les deux fils. Attachez un fil à la ligne VCC commune aux boutons. Attachez ensuite l'autre laisse à chaque broche du harnais une par une. Le multimètre ne doit émettre un bip que lorsque vous appuyez sur le bouton. Si vous obtenez d'autres bips, cela signifie que vous avez un renversement ou un court-circuit. Trouvez-le et réparez-le avant de mettre l'appareil sous tension !

Étape 12: Coder

Tout d'abord, ouvrez votre IDE Arduino et assurez-vous que la bibliothèque FastLED est installée.

Téléchargez le code Algorithm Machine depuis GitHub:

github.com/samguyer/AlgorithmMachine.git

Vous pouvez soit le cloner directement dans votre dossier Arduino, soit le copier à la main.

Avant de le télécharger, assurez-vous que les paramètres de broche correspondent à votre configuration matérielle. J'ai placé tous les paramètres de broche en haut du fichier.

Téléchargez et profitez-en!

Étape 13: Comment utiliser

L'Algorithm Machine est simple à utiliser et presque toutes les combinaisons de boutons sont acceptables !

Tout d'abord, utilisez les boutons de données pour initialiser les valeurs du tableau. Il y a trois choix: (1) randomiser, (2) ajouter une valeur aléatoire et (3) inverser le tableau. Notez que les valeurs sont persistantes, vous pouvez donc commencer par les trier, puis ajouter du bruit, puis exécuter un algorithme de tri ou de recherche différent.

Choisissez un algorithme de recherche ou de tri parmi les autres choix de boutons. Actuellement, il n'y a pas de retour lorsque vous faites ce choix (quelque chose pour un travail futur). Appuyez ensuite sur le bouton « jouer ».

Le bouton contrôle la vitesse. Vous pouvez également appuyer sur "play" pour mettre en pause et reprendre l'algorithme.

Il s'arrêtera automatiquement une fois terminé. Vous pouvez également appuyer sur un autre bouton d'algorithme à tout moment. La machine arrêtera l'algorithme actuel et initialisera le nouveau, mais conservera les données exactement telles que l'algorithme précédent les a laissées.

Grand prix du concours STEM