La màquina de l'algoritme: 13 passos (amb imatges)

2024 Autora: John Day | [email protected]. Última modificació: 2024-01-30 08:12

Fa 15 anys que imparteixo classes d’informàtica a la universitat i, tot i que la meva experiència està més relacionada amb la programació, segueixo passant molt de temps cobrint algoritmes estàndard de cerca i classificació. Des del punt de vista de l’ensenyament, el tema central és la complexitat computacional: quant de temps requereix cada algorisme, donada l’entrada d’una mida determinada? Però hi ha nombrosos matisos. Per exemple, els algoritmes tenen temps d'execució diferents en funció dels valors d'entrada específics (a diferència de la mida)? En quins casos escolliríeu un algorisme d'ordenació per un altre? Tot i que discutim aquestes qüestions de manera abstracta, sempre em va molestar que no hi hagués cap manera fàcil de veure com funcionen diferents algoritmes en diverses condicions.

Metes

El meu objectiu general d’aquest projecte era crear una pantalla interactiva perquè els estudiants poguessin visualitzar i explorar algoritmes. Em vaig limitar a algorismes que funcionen en matrius de valors (enters), de manera que puc utilitzar una tira LED RGB adreçable per visualitzar el contingut de la matriu. La matriu té 100 elements i cada enter es mapea a un color en ordre arc de Sant Martí, de manera que és immediatament evident quan la matriu està ordenada, ordenada parcialment o aleatòriament. A més dels valors, però, volia una manera de visualitzar aspectes de control de l'algorisme, per exemple, quins elements de la matriu s'estan comparant o canviant actualment.

Els objectius específics són:

- Proporcionar una varietat d'algorismes de cerca i classificació

- Visualitzeu els valors de la matriu de manera que ressalteu el progrés de l'algorisme

- Visualitzar el control d'algoritmes; en particular, els elements que es consideren.

- Permetre als usuaris triar els patrons de dades d'entrada en lloc de generar sempre valors aleatoris

- Permetre als usuaris controlar la velocitat i posar en pausa l'algorisme

- Permetre als usuaris forçar el comportament en el cas millor, el pitjor dels casos i el cas mitjà (específic de l'algorisme)

- Mostra el nombre de passos a mesura que avança l'algoritme

Visualització

Des del punt de vista del disseny físic, la part més interessant d’aquest projecte és la visualització de la matriu. Vaig lluitar amb la manera de mostrar les dades i el control i com construir el dispositiu de visualització. El meu objectiu era mostrar els valors de les dades com a cercles de colors i els punts de control com a fletxes de colors que apunten als valors de les dades. Després d'alguna experimentació, em vaig fixar en un disseny amb dues tires paral·leles de 100 LED RGB (WS2812) amb una màscara circular sobre cada LED de dades i una màscara triangular sobre cada LED de control. Vaig fer un model 3D de la màscara amb 10 parells de cercles i triangles, i després vaig imprimir en 3D 10 d'aquests mòduls per a un total de 100 cercles i 100 triangles. La mida i l’espaiat de la meva màscara estan dissenyats per a tires amb 100 LED per metre. Els fitxers del model 3D es proporcionen més endavant en aquesta descripció.

Electrònica i armaris

La resta del dispositiu és senzill, des del punt de vista de l'electrònica. A més de les dues tires LED, hi ha un munt de botons momentanis, un codificador rotatiu (per al control de velocitat) i una pantalla de 7 segments (per mostrar els passos). Amb tants botons i controls, vaig optar per utilitzar un microcontrolador ESP32 perquè exposa molts pins i perquè és bastant potent. Repassaré l’estratègia de cablejat, però és bastant bàsica. Probablement podríeu fer alguna cosa intel·ligent amb els registres de desplaçament si voleu utilitzar menys pins.

Podeu construir el recinte d’aquest dispositiu de moltes formes diferents. Al principi l’imaginava com un tauler rectangular gran amb la tira LED a la part superior i una quadrícula de botons al mig. La forma amb què vaig acabar s’inspira en una mena de visió dels anys seixanta de la tecnologia de l’edat espacial. També podeu construir-lo amb les tires LED en orientació vertical. O bé, feu que la part LED sigui molt més gran (ompliu tota una paret) amb un tauler de control independent.

Programari

El codi d’aquest dispositiu està disponible gratuïtament a GitHub i he fet tot el possible per documentar com funciona i com configurar-lo. L'única biblioteca externa que necessiteu és FastLED per conduir les tires WS2812.

Subministraments

Electrònica

1 tauler de desenvolupament ESP32 (per exemple, 2 tires LED WS2812 o similars, densitat 100 LED per metre (per exemple, 1 botó "Inici" del triangle (per exemple, 12 botons momentanis (per exemple, https://amzn.com/B01N4D4750): formes diferents si voleu

1 paquet (20) de connectors de botó precablats (per exemple, 1 paquet de connectors JST (per exemple, 1 codificador rotatiu (per exemple, 1 comandament per al codificador rotatiu (per exemple, 1 paquet de connectors Dupont (per exemple, https://amzn.com/B014YTPFT8): també val la pena obtenir l'eina de crimpat.

1 presa de barril (per alimentar) (per exemple, 1 pantalla numèrica TM1637 de 7 segments (per exemple, Engranatges de soldadura i cablejat

Fitxers de models 3D

Podeu trobar el model 3D per a un parell de mòduls de 10 llums a Thingiverse:

www.thingiverse.com/thing:4178181

Haureu d’imprimir aquest model cinc vegades per a un total de 10 mòduls.

Programari

github.com/samguyer/AlgorithmMachine

Recinte

Fusta, plexiglàs, cargols i cargols d'acer inoxidable

Material de difusió. El meu favorit és Lee Filters # 216 de difusió en blanc complet, però hi ha altres opcions. Fins i tot el paper blanc normal fa una bona feina.

Pas 1: Algorismes 101

Molta gent pensa que la informàtica és bàsicament l’estudi de la programació. Però el veritable cor i ànima d’aquest camp són els algoritmes: l’estudi de procediments sistemàtics per resoldre problemes i el seu cost (normalment, quant triguen). Figures seminals del camp, com Alan Turing, Alonzo Church i Edsger Dijkstra, estaven pensant en aquestes idees abans que existissin les computadores tal com les coneixem.

La característica clau d’un algorisme per resoldre un problema concret és que és detallat i precís, de manera que algú el podria utilitzar per obtenir una solució sense entendre el seu funcionament; només cal que seguiu els passos de manera mecànica i obtindreu la resposta correcta. Podeu veure com això ajuda a programar ordinadors, ja que necessiten aquest nivell de detall. Un ordinador no pot omplir les dades que falten ni emetre judicis, tal com pot fer una persona.

Quant de temps trigarà?

Un cop tenim un procediment detallat, una pregunta natural és quant de temps trigarem a obtenir la resposta? No podem utilitzar unitats de temps normals, ja que depèn de qui fa la feina (compareu la velocitat amb què una persona pot calcular alguna cosa enfront d’un superordinador). A més, depèn de la quantitat de dades que tinguem. És evident que triga més a buscar una llista d’un milió de números de telèfon que una llista de cent.

Per descriure el cost d'un algorisme, primer escollim alguna operació en el procediment que representi un "pas", generalment quelcom senzill, com comparar o afegir dos nombres, que requereix un temps fix. A continuació, arribem a una fórmula que descriu quants passos prendrà l’algorisme donat un cert nombre d’elements de dades. Per motius històrics, gairebé sempre denotem el nombre d’elements de dades amb majúscules N.

Per exemple, mirar una llista de N números de telèfon fa N passos. Veure dues vegades la llista fa 2N passos. Tots dos s’anomenen algorismes de temps lineals: el nombre total de passos és un múltiple de la mida d’entrada. Altres algorismes són quadràtics (N temps quadrat) o cúbics (N cubats) o logarítmics (log N) o alguna combinació d'aquests. Alguns dels problemes computacionals més difícils requereixen algoritmes de temps exponencial (2 ^ N).

D'acord, i què?

Quan el nombre d’elements de dades N és petit, no importa gaire. Per exemple, per a N = 10, 10N és aquest nom com a N al quadrat. Però, què passa amb N = 1000? o N = 1000000? Un milió al quadrat és un nombre força gran. Fins i tot en un ordinador molt ràpid, un algorisme quadràtic pot trigar molt de temps si l’entrada és prou gran. Els algoritmes exponencials són molt més problemàtics: per a N = 50, un algorisme exponencial trigaria dues setmanes a acabar fins i tot en un ordinador on cada pas és només un nanosegon (1 bilionsèsima de segon). Ai!

A l’altre extrem de l’escala tenim algorismes de temps logarítmics, que són molt ràpids. El temps de registre és el contrari del temps exponencial: donada la mida d’entrada N, el nombre de passos és l’exponent T de la fórmula 2 ^ T = N. Per exemple, si la nostra mida d’entrada és de mil milions, un algorisme de temps de registre només requereix 30 passos, ja que 2 ^ 30 = 1, 000, 000, 000. Que dolç és això?! ??!

Potser us preguntareu a qui es preocupen les mides d’entrada de milions o milers de milions? Penseu-hi: quants usuaris hi ha a Facebook? Quantes pàgines web indexa Google? Quants parells de bases hi ha al genoma humà? Quantes mesures fan una simulació meteorològica?

Pas 2: els algorismes

Actualment, l'Algorithm Machine implementa els algoritmes següents. Dos d’ells són algorismes de cerca (trobeu un valor concret a la llista), la resta són algoritmes d’ordenació (ordeneu els valors).

Cerca lineal

Cerqueu un a un la llista de valors des del principi. Requereix temps lineal.

Cerca binària

Cerqueu una llista dividint-la repetidament per la meitat. Requereix temps de registre, però la llista s’ha d’ordenar perquè funcioni.

Tipus de bombolla

Ordeneu una llista per intercanviar repetidament elements veïns que no estiguin en ordre. Requereix temps quadràtic.

Classificació per inserció

Ordeneu una llista situant cada element al lloc adequat de la llista de valors ja ordenats. Requereix temps quadràtic.

Quicksort

Ordeneu una llista dividint la llista repetidament per la meitat i movent tots els valors inferiors a la mediana a la primera meitat i tots els valors superiors a la mediana a la segona meitat. A la pràctica, no podem trobar la mediana de manera eficient, de manera que escollim un valor a l’atzar. Com a resultat, aquest algorisme pot ser quadràtic en el pitjor dels casos, però normalment requereix temps N * logN.

Combina la classificació

Ordeneu una llista dividint-la per la meitat, ordenant les dues meitats per separat (mitjançant un ordre de combinació) i, després, fusionant-les intercalant els valors. Sempre requereix N * logN temps.

Tipus de pila

Ordeneu una llista creant una estructura de dades anomenada heap, que us permetrà trobar el valor més petit en el temps de registre. Sempre requereix N * logN temps.

Gènere bitònic

De manera similar a la combinació d’ordenació i quicksort, divideix una llista per la meitat, ordena les meitats i recombina-les. Aquest algorisme requereix N * logN * logN temps, però té l'avantatge que és fàcil de paral·lelitzar.

Pas 3: Barra LED: imprimeix 3D la màscara

El primer pas per construir la barra LED és imprimir en 3D la màscara que dóna forma a les llums. Cada mòdul cobreix deu elements de la matriu, 10 valors (cercles) i 10 indicadors (triangles), de manera que necessitareu 10 mòduls en total. El fitxer STL que proporciono aquí conté dues instàncies del mòdul, de manera que haureu de fer cinc cicles d'impressió. No tinc la millor impressora 3D, així que vaig haver de fer una neteja manual amb un fitxer i un paper de vidre. El més important és que els forats circulars i triangulars estiguin nets.

A les fotos veureu la configuració de la meva prova: vaig gravar les dues tires de LED cap avall i les vaig enganxar a una placa amb un microcontrolador. Aquest pas no és necessari, però volia veure com quedaria abans de començar a muntar el recinte. Vaig alinear els mòduls de màscares de les dues tires de LED i vaig fer un esbós senzill amb colors aleatoris. Amb una tira de material de difusió apareixen les formes i els colors.

Pas 4: alternatives de barres LED

Quan vaig començar aquest projecte, vaig experimentar amb altres maneres de fabricar la màscara LED. Si no teniu una impressora 3D, podeu considerar una d’aquestes opcions. Seré sincer: és un dolor enorme fer aquestes parts.

Per als cercles, vaig comprar un tub de llautó de 13/32, que fa gairebé exactament 1 cm de diàmetre. El vaig tallar en cent segments d'1cm i després els vaig pintar amb esprai de blanc.

Per als triangles, he utilitzat paper d'alumini de gran pes tallat en una paella d'un sol ús. Vaig fer una forma triangular de fusta, després vaig embolicar tires curtes de paper d'alumini al voltant de la forma i les vaig gravar. Una vegada més, necessitareu un centenar d’aquestes coses, de manera que necessiteu una mica de temps i paciència.

Pas 5: recinte de barres LED

El meu recinte és bastant senzill: dues tires de fusta per als laterals i dues tires de plexiglàs per la part superior i inferior. Totes les parts fan uns 102 cm de llargada (1 metre per als LED, més una mica més per adaptar-se al cablejat). Els laterals haurien de ser una mica més alts d’1 cm per deixar lloc a les tires LED. Després de tallar les tires, vaig intercalar les peces de la màscara impresa en 3D entre elles per mesurar l’amplada del plexiglàs. Talla dos trossos de plexiglass de l’amplada i la longitud de la barra. Finalment, talla una tira del material de difusió perquè s’adapti a la màscara.

Per a la difusió, m'agrada molt Lee Filters # 216 (difusió en blanc complet). És una làmina fina de plàstic que dóna fins i tot difusió sense perdre molta llum. Però són coses cares. De vegades, podeu trobar fulls més petits a la venda en línia, però tot un rotlle us recuperarà uns 125 dòlars. Algunes altres opcions són el paper blanc o qualsevol altre tipus de plàstic setinat o esmerilat. Una opció popular són les estores fines de plàstic.

Abans de muntar la barra LED, assegureu-vos que teniu els connectors adequats soldats a les tires de LED. Hi ha moltes tires amb cables pre-soldats, de manera que només podeu utilitzar-les.

Vaig començar el muntatge cargolant la peça superior de plexiglàs als costats de fusta (veure foto). Aleshores la vaig capgirar i hi vaig col·locar la tira de difusió, seguida de les 10 peces de màscara. Un cop em vaig alegrar amb l’espai, els vaig fixar al lloc amb uns quants punts de cola calenta.

A continuació, poseu les dues tires LED un al costat de l’altre de les màscares. Assegureu-vos que els LEDs estan cap avall i assegureu-vos que cada LED s’alineï amb el forat corresponent de la màscara. Afegiu una mica de cola o cinta calenta per mantenir les tires LED al seu lloc. Finalment, cargoleu la peça posterior de plexiglàs.

Executeu un patró de prova. Bona feina! Has fet el més difícil!

Pas 6: Tauler de control

El tauler de control és la part que proporciona més llibertat creativa. Només cal mantenir tots els controls i components electrònics, juntament amb la barra LED. El disseny més senzill és un taulers rectangulars: taladreu els botons i els controls i fixeu la barra LED. M’agrada combinar fusta, plexiglàs i altres materials per donar una mena d’aspecte steampunk / retro-modern. En aquest cas, vaig tallar un tros de plexiglàs resistent per aguantar els botons principals d’elecció de l’algoritme i una barra de fusta per contenir la resta d’electrònics. He foradat perquè coincideixi amb la mida dels botons arcade. El cablejat es mostra a la part posterior, però m’agrada!

També he aprofitat l'espai per a la pantalla de 7 segments, el codificador rotatiu i alguns dels cables de la part posterior. Vaig tallar un dau a la part superior per aguantar la barra LED.

Pas 7: Arnés de botons

Connectar molts botons pot ser un veritable dolor. Per sort, les persones que fabriquen màquines arcade han creat alguns connectors estàndard que podeu utilitzar. Cada cable de connector de botó té dos cables, un per a VCC i un per a terra. Un dels extrems té connectors de pala que s’adapten als cables de la part posterior del botó: fixeu la terra al cable “normalment obert” i VCC al cable “comú”. En aquesta configuració, quan l'usuari prem el botó, el circuit es completa i el microcontrolador llegirà HIGH al pin d'entrada corresponent.

L'altre extrem del cable té un connector JST (el petit blanc). El que és bo d’aquests connectors és que només entren al receptacle d’una manera, de manera que no hi ha manera d’invertir accidentalment VCC i terra.

El que vaig fer va ser construir un petit arnès per a aquests connectors. He soldat una sèrie de receptacles JST en un tros de proto-placa i després torno els cables als connectors Dupont que connectaré al microcontrolador. El cable vermell és la línia VCC i es connecta a tots els receptacles JST. Els cables blaus són els que estan separats per a cada botó.

Pas 8: codificador rotatiu

El codificador rotatiu permet a l'usuari controlar la velocitat de l'algorisme. Utilitzo un mòdul que es presenta com una placa de sortida que inclou resistències de tracció per a les dues línies de dades (cables grocs). Aquest també és un botó, però no estic fent servir aquesta funció. Els altres dos cables són VCC i terra. També tinc un bon pom greix.

El que m’agrada d’un codificador rotatiu, a diferència d’un potenciòmetre, és que només indica la rotació (en sentit horari vs antihorari) al microcontrolador, de manera que és fàcil canviar la manera com s’interpreta el valor. Per exemple, podeu donar-li una sensació d'acceleració (com un ratolí) quan l'usuari la fa girar ràpidament.

Pas 9: pantalla de 7 segments

No hi ha molt a dir aquí. Aquestes coses són a tot arreu. Els LED estan controlats per un xip anomenat TM1637, que es comunica amb el microcontrolador mitjançant un senzill protocol sèrie. Utilitzo una biblioteca existent que em permet dir-li quin número vull mostrar i fa la resta.

La part posterior té quatre pins: VCC, terra i dos cables per al protocol sèrie. He soldat un tros de capçalera de 4 pins, que es connecta a un connector Dupont corresponent connectat al microcontrolador.

Pas 10: placa principal del controlador

La placa principal del controlador allotja el propi microcontrolador i tots els connectors dels controls (botons, pantalla, LED). El microcontrolador és un ESP32, que proporciona molta memòria i potència informàtica, i exposa molts pins. El cablejat és bastant estàndard, però assenyalaré alguns bits interessants.

NOTA: és possible que vulgueu mirar el codi (https://github.com/samguyer/AlgorithmMachine) abans de començar a connectar la placa principal, de manera que la configuració del vostre pin coincideixi amb la meva.

Vaig soldar una presa de barril al tauler per obtenir energia, i vaig connectar dos cables de coure robustos a la xarxa elèctrica i de terra de la placa. El motiu és que la barra LED pot treure molta energia si la brillantor està ajustada i no vull treure tota aquesta energia a través del connector USB del microcontrolador.

Per simplificar el cablejat del botó, heu soldat una tira de capçalera d'angle recte home a dona per tot el costat del microcontrolador (costat superior de la placa, tal com es mostra). Els connectors Dupont de l'arnès de botons es connecten directament a aquesta capçalera.

IMPORTANT: l’alimentació dels botons (el cable vermell) s’ha de connectar a la línia elèctrica de 3,3 V del microcontrolador. L’ESP32 és un xip de 3,3 V, de manera que només s’han d’adjuntar fonts de 3,3 V als pins de dades.

El microcontrolador treu energia (o empeny l’alimentació) als rails (costat inferior de la placa, tal com es mostra) a través del pin USB de 5V i la terra. Tots els altres cables vermells / negres són VCC i estan a terra.

Els dos cables de color blau són les línies de dades de les tires LED (el WS2812). El parell groc / verd són les línies de dades del codificador rotatiu i el parell groc és la connexió en sèrie a la pantalla de 7 segments.

Pas 11: Muntatge

Aquesta sèrie de fotografies mostra el muntatge i el cablejat final. També he connectat la placa principal del controlador a la part posterior de la part superior.

Abans d’engegar-lo vaig fer uns quants controls per evitar desagradables sorpreses. En particular, per assegurar-me que no tingués cap connector d'alimentació / terra cap enrere i que no hi hagi cap curtcircuit. Configureu el multímetre per provar la continuïtat: emetrà un so quan hi hagi un recorregut elèctric entre els dos cables. Adjunteu un cable a la línia VCC comuna als botons. A continuació, fixeu l'altre cable a cada passador de l'arnès un per un. El multímetre només ha de sonar quan premeu el botó. Si reps altres sons, significa que tens una inversió o un curt. Seguiu-lo i corregiu-lo abans d’encendre l’alimentació.

Pas 12: Codi

Primer, obriu el vostre IDE Arduino i assegureu-vos que teniu instal·lada la biblioteca FastLED.

Descarregueu el codi Algorithm Machine de GitHub:

github.com/samguyer/AlgorithmMachine.git

Podeu clonar-lo directament a la carpeta Arduino o copiar-lo a mà.

Abans de penjar-lo, assegureu-vos que la configuració del PIN coincideixi amb la configuració del maquinari. He col·locat tots els paràmetres de fixació a la part superior del fitxer.

Carregueu i gaudiu!

Pas 13: com s'utilitza

Algorithm Machine és senzill d'utilitzar i gairebé qualsevol combinació de botons està bé.

En primer lloc, utilitzeu els botons de dades per inicialitzar els valors de la matriu. Hi ha tres opcions: (1) randomize, (2) afegir un valor aleatori i (3) invertir la matriu. Tingueu en compte que els valors són persistents, de manera que podeu fer coses com ordenar-les primer, després afegir una mica de soroll i, a continuació, executar un algorisme de classificació o cerca diferent.

Trieu un algorisme de cerca o d'ordenació entre les altres opcions de botó. Actualment, no hi ha cap comentari quan feu aquesta tria (alguna cosa per a futurs treballs). A continuació, premeu el botó "Reprodueix".

El comandament controla la velocitat. També podeu prémer "reproduir" per aturar i deixar en pausa l'algorisme.

S'aturarà automàticament quan s'acabi. També podeu prémer un altre botó d'algorisme en qualsevol moment. La màquina aturarà l'algorisme actual i inicialitzarà el nou, però conservarà les dades exactament tal com les va deixar l'algoritme anterior.

Gran Premi al Concurs STEM