Mașina algoritmului: 13 pași (cu imagini)

2024 Autor: John Day | [email protected]. Modificat ultima dată: 2024-01-30 11:43

Predau informatică la nivel de facultate de 15 ani și, deși expertiza mea este mai mult din partea programării, totuși petrec destul de mult timp acoperind algoritmi standard pentru căutare și sortare. Din punct de vedere didactic, problema centrală este complexitatea calculațională: cât timp necesită fiecare algoritm, având în vedere intrarea de o anumită dimensiune? Dar există numeroase nuanțe. De exemplu, algoritmii au runtime diferite în funcție de valorile specifice de intrare (spre deosebire de dimensiune)? În ce cazuri ați alege un algoritm de sortare față de altul? Deși discutăm aceste probleme în abstract, întotdeauna mi-a pus în eroare că nu exista o modalitate ușoară de a vedea cum funcționează diferiți algoritmi în diferite condiții.

Obiective

Scopul meu general pentru acest proiect a fost de a crea un afișaj interactiv pentru ca elevii să vizualizeze și să exploreze algoritmi. M-am limitat la algoritmi care funcționează pe tablouri de valori (numere întregi), așa că pot folosi o bandă LED RGB adresabilă pentru a vizualiza conținutul matricei. Matricea are 100 de elemente și fiecare număr întreg este mapat la o culoare în ordinea curcubeului, astfel încât este imediat evident când matricea este sortată, parțial sortată sau randomizată. În plus față de valori, totuși, am dorit o modalitate de a vizualiza aspectele de control ale algoritmului - de exemplu, care elemente ale matricei sunt în prezent comparate sau schimbate.

Obiectivele specifice sunt:

- Furnizați o varietate de algoritmi de căutare și sortare

- Vizualizați valorile din matrice într-un mod care evidențiază progresul algoritmului

- Vizualizați controlul algoritmului; în special, elementele fiind luate în considerare.

- Permiteți utilizatorilor să aleagă tiparele de date de intrare, mai degrabă decât să genereze întotdeauna valori aleatorii

- Permiteți utilizatorilor să controleze viteza și să întrerupă algoritmul

- Permiteți utilizatorilor să forțeze cel mai bun caz, cel mai rău caz, comportamentul în caz mediu (specific algoritmului)

- Afișați numărul de pași pe măsură ce algoritmul continuă

Vizualizare

Din punct de vedere al designului fizic, cea mai interesantă parte a acestui proiect este vizualizarea matricei. M-am luptat cu modul în care arăt datele și controlul și cum să construiesc dispozitivul de afișare în sine. Scopul meu a fost să arăt valorile datelor ca cercuri colorate și punctele de control ca săgeți colorate care indică valorile datelor. După câteva experimente, m-am stabilit pe un design cu două benzi paralele de 100 de LED-uri RGB (WS2812) cu o mască circulară peste fiecare LED de date și o mască triunghiulară peste fiecare LED de control. Am realizat un model 3D al măștii cu 10 perechi de cercuri și triunghiuri, apoi 3D a imprimat 10 dintre aceste module pentru un total de 100 de cercuri și 100 de triunghiuri. Dimensiunea și spațiul măștii mele sunt proiectate pentru benzi cu 100 de LED-uri pe metru. Fișierele model 3D sunt furnizate mai târziu în această descriere.

Electronice și carcase

Restul dispozitivului este simplu, din punct de vedere electronic. În plus față de cele două benzi LED, există o grămadă de butoane momentane, un codificator rotativ (pentru controlul vitezei) și un afișaj pe 7 segmente (pentru a arăta pașii). Cu atât de multe butoane și comenzi am ales să folosesc un microcontroler ESP32 deoarece expune o mulțime de pini și pentru că este destul de puternic. Voi trece peste strategia de cablare, dar este destul de simplă. Ați putea face ceva inteligent cu registrele de schimbare dacă doriți să utilizați mai puțini pini.

Puteți construi carcasa pentru acest dispozitiv în multe forme diferite. Mi-am imaginat-o inițial ca pe o placă dreptunghiulară mare, cu banda LED deasupra și o grilă de butoane în mijloc. Forma cu care am ajuns este inspirată dintr-un fel de viziune din anii 1960 a tehnologiei spațiului spațial. De asemenea, l-ați putea construi cu benzi LED într-o orientare verticală. Sau faceți partea LED mult mai mare - umpleți un întreg perete - cu un panou de control separat.

Software

Codul pentru acest dispozitiv este disponibil gratuit pe GitHub și am făcut tot posibilul să documentez cum funcționează și cum să îl configurez. Singura bibliotecă externă de care aveți nevoie este FastLED pentru a conduce benzile WS2812.

Provizii

Electronică

1 placă de dezvoltare ESP32 (de exemplu, 2 benzi LED WS2812 sau similare, densitate 100 LED-uri pe metru (de ex., 1 buton triunghi „pornire” (de exemplu, 12 butoane momentane (de exemplu, https://amzn.com/B01N4D4750) - forme diferite dacă doriți

1 pachet (20) conectori de butoane precablați (de exemplu, 1 pachet de conectori JST (de exemplu, 1 codificator rotativ (de exemplu, 1 buton pentru codificator rotativ (de exemplu, 1 pachet de conectori Dupont (de exemplu, https://amzn.com/B014YTPFT8) - merită să obțineți și instrumentul de sertizare.

1 mufa cu butoi (pentru putere) (de ex., 1 afișaj numeric TM1637 pe 7 segmente (de exemplu, Unelte de lipit și cablate

Fișiere model 3D

Puteți găsi modelul 3D pentru o pereche de module cu 10 lumini pe Thingiverse:

www.thingiverse.com/thing:4178181

Va trebui să imprimați acest model de cinci ori pentru un total de 10 module.

Software

github.com/samguyer/AlgorithmMachine

Incintă

Lemn, plexiglas, șuruburi și șuruburi din oțel inoxidabil

Material de difuzie. Preferatul meu este Lee Filters # 216 full diffusion alb, dar există și alte opțiuni. Chiar și hârtia albă simplă face o treabă bună.

Pasul 1: Algoritmi 101

Mulți oameni cred că informatica este în esență studiul programării. Dar adevărata inimă și suflet al acestui domeniu sunt algoritmii: studiul procedurilor sistematice pentru rezolvarea problemelor și costul acestora (de obicei, cât durează). Figurile seminale din domeniu, cum ar fi Alan Turing, Alonzo Church și Edsger Dijkstra, se gândeau la aceste idei înainte de calculatoare, așa cum știm că au existat.

Caracteristica cheie a unui algoritm pentru a rezolva o anumită problemă este că este detaliat și precis, astfel încât cineva să îl poată folosi pentru a obține o soluție fără a înțelege deloc cum funcționează; doar urmați pașii într-un mod mecanic și veți obține răspunsul corect. Puteți vedea cum ajută acest lucru la programarea computerelor, deoarece acestea au nevoie de acest nivel de detaliu. Un computer nu poate completa detaliile lipsă și nici nu poate judeca, așa cum poate o persoană.

Cât o să dureze?

Odată ce avem o procedură detaliată, o întrebare firească este cât timp va dura pentru a obține răspunsul? Nu putem folosi unități de timp obișnuite, deoarece depinde de cine lucrează (comparați cât de repede ar putea calcula ceva o persoană față de un supercomputer). În plus, depinde cât de multe date avem. În mod clar, este nevoie de mai mult timp pentru a căuta o listă de un milion de numere de telefon decât o listă de o sută.

Pentru a descrie costul unui algoritm, alegem mai întâi o operațiune din procedura care reprezintă un „pas” - de obicei ceva simplu, cum ar fi compararea sau adăugarea a două numere, care necesită o perioadă fixă de timp. Apoi, venim cu o formulă care descrie câți pași va face algoritmul, având în vedere un anumit număr de elemente de date. Din motive istorice, indicăm aproape întotdeauna numărul de elemente de date cu majuscule N.

De exemplu, examinarea unei liste de N numere de telefon face N pași. Căutarea prin listă de două ori durează 2N pași. Ambii sunt numiți algoritmi de timp liniari - numărul total de pași este un multiplu al dimensiunii de intrare. Alți algoritmi sunt pătratici (N timp pătrat) sau cubici (N cubiți) sau logaritmici (log N) sau o combinație a acestora. Unele dintre cele mai dificile probleme de calcul necesită algoritmi de timp exponențiali (2 ^ N).

OK, deci ce?

Când numărul de elemente de date N este mic, nu contează prea mult. De exemplu, pentru N = 10, 10N este acel nume ca N pătrat. Dar ce zici de N = 1000? sau N = 1000000? Un milion pătrat este un număr destul de mare. Chiar și pe un computer foarte rapid, un algoritm pătratic poate dura mult dacă intrarea este suficient de mare. Algoritmii exponențiali sunt mult mai anevoioși: pentru N = 50, un algoritm exponențial ar dura două săptămâni pentru a se finaliza chiar și pe un computer în care fiecare pas este doar o nanosecundă (1 miliardime de secundă). Vai!

La celălalt capăt al scalei avem algoritmi de timp logaritmici, care sunt foarte rapizi. Timpul jurnal este opusul timpului exponențial: dată dimensiunea de intrare N, numărul de pași este exponentul T din formula 2 ^ T = N. De exemplu, dacă dimensiunea noastră de intrare este de un miliard, atunci un algoritm de timp jurnal necesită doar 30 pași, de când 2 ^ 30 = 1, 000, 000, 000. Cât de dulce este asta?! ??!

S-ar putea să vă întrebați, cui îi pasă de dimensiunile de intrare de milioane sau miliarde? Gândește-te: câți utilizatori sunt pe Facebook? Câte pagini web sunt indexate de Google? Câte perechi de baze există în genomul uman? Câte măsurători intră într-o simulare a vremii?

Pasul 2: Algoritmii

Algorithm Machine implementează în prezent următorii algoritmi. Doi dintre ei sunt algoritmi de căutare (găsiți o anumită valoare în listă), restul sunt algoritmi de sortare (puneți valorile în ordine).

Căutare liniară

Căutați lista de valori una câte una începând de la început. Necesită timp liniar.

Căutare binară

Căutați o listă împărțind-o în mod repetat la jumătate. Necesită timp de înregistrare, dar lista trebuie să fie sortată pentru ca aceasta să funcționeze.

Sortare cu bule

Sortează o listă cu elemente învecinate care schimbă în mod repetat, care nu sunt în ordine. Necesită timp pătratic.

Sortare prin inserție

Sortează o listă plasând fiecare element în locul său corespunzător în lista valorilor deja sortate. Necesită timp pătratic.

Sortare rapida

Sortează o listă împărțind în mod repetat lista în jumătate și mutând toate valorile mai mici decât mediana în prima jumătate și toate valorile mai mari decât mediana în a doua jumătate. În practică, nu putem găsi în mod eficient mediana, așa că alegem o valoare la întâmplare. Ca rezultat, acest algoritm poate fi pătratic în cel mai rău caz, dar necesită de obicei N * logN timp.

Merge sort

Sortați o listă împărțind-o în jumătate, sortând cele două jumătăți separat (folosind sortare de îmbinare), apoi îmbinându-le împreună intercalând valorile. Necesită întotdeauna N * logN timp.

Sortare grămadă

Sortați o listă construind o structură de date numită heap, care vă permite să găsiți cea mai mică valoare în timpul jurnalului. Necesită întotdeauna N * logN timp.

Sortare bitonică

Similar cu fuzionarea sort și quicksort, împărțiți o listă în două, sortați jumătățile și recombinați-le. Acest algoritm necesită timp N * logN * logN, dar are avantajul că este ușor de paralelizat.

Pasul 3: Bara LED: Imprimați 3D masca

Primul pas în construirea barei cu LED-uri este imprimarea 3D a măștii care conferă luminilor forma lor. Fiecare modul acoperă zece elemente ale matricei, 10 valori (cercuri) și 10 indicatori (triunghiuri), deci veți avea nevoie de 10 module în totalitate. Fișierul STL pe care îl ofer aici conține două instanțe ale modulului, deci va trebui să faceți cinci cicluri de imprimare. Nu am cea mai bună imprimantă 3D, așa că a trebuit să fac câteva curățări manuale pe ele folosind un fișier și un șmirghel. Cel mai important lucru este că găurile circulare și triunghiulare sunt curate.

În fotografii veți vedea configurația mea de testare: am înregistrat cele două benzi LED în jos și le-am conectat la o placă cu un microcontroler. Acest pas nu este necesar, dar am vrut să văd cum va arăta înainte de a începe asamblarea incintei. Am aliniat modulele de mască de pe cele două benzi LED și am rulat o schiță simplă cu culori aleatorii. Cu o bandă de material de difuzie formele și culorile apar cu adevărat.

Pasul 4: Alternative cu bare LED

Când am început acest proiect, am experimentat alte modalități de realizare a măștii LED. Dacă nu aveți o imprimantă 3D, ați putea lua în considerare una dintre aceste opțiuni. Voi fi sincer: este o durere uriașă să faci aceste părți.

Pentru cercuri, am cumpărat un tub de alamă de 13/32, care are aproape exact 1cm în diametru. L-am tăiat în sute de segmente de 1cm și apoi le-am vopsit în alb.

Pentru triunghiuri, am folosit folie de aluminiu grea tăiată dintr-o tigaie de unică folosință. Am făcut o formă triunghiulară din lemn, apoi am înfășurat benzi scurte de folie în jurul formei și le-am lipit. Din nou, veți avea nevoie de o sută dintre aceste lucruri, așa că este nevoie de ceva timp și răbdare.

Pasul 5: carcasă cu bare LED

Carcasa mea este destul de simplă: două benzi de lemn pentru laturi și două benzi de plexiglas pentru partea superioară și inferioară. Toate piesele au o lungime de aproximativ 102cm (1 metru pentru LED-uri, plus un pic suplimentar pentru a găzdui cablajul). Părțile laterale ar trebui să fie puțin mai înalte de 1cm pentru a face loc benzilor cu LED-uri. După ce am tăiat fâșiile, am blocat piesele de mască imprimate 3D între ele pentru a măsura lățimea plexiglasului. Tăiați două bucăți de plexiglas lățimea și lungimea barei. În cele din urmă, tăiați o bandă de material de difuzie pentru a se potrivi peste mască.

Pentru difuzie îmi place foarte mult Lee Filters # 216 (difuzie complet albă). Este o foaie subțire de plastic care oferă o difuzie uniformă fără a pierde multă lumină. Dar sunt lucruri scumpe. Uneori puteți găsi foi mici de vânzare online, dar o rola întreagă vă va aduce înapoi aproximativ 125 USD. Alte opțiuni sunt hârtia albă sau orice alt tip de satin sau plastic mat. O alegere populară este covoarele subțiri de tăiere din plastic.

Înainte de a asambla bara LED, asigurați-vă că aveți conectorii corespunzători lipiți pe benzile LED. O mulțime de benzi vin cu cabluri pre-lipite, astfel încât să le puteți folosi.

Am început asamblarea prin înșurubarea piesei superioare de plexiglas pe părțile laterale din lemn (vezi foto). Apoi am dat-o peste cap și am așezat banda de difuzie, urmată de cele 10 bucăți de mască. Odată ce am fost fericit cu spațiul, i-am fixat în loc cu câteva puncte de adeziv fierbinte.

Apoi, așezați cele două benzi LED unul lângă altul deasupra măștilor. Asigurați-vă că LED-urile sunt orientate în jos și asigurați-vă că fiecare LED se aliniază cu orificiul corespunzător din mască. Adăugați niște adeziv fierbinte sau bandă pentru a menține benzile LED în poziție. În cele din urmă, înșurubați partea din spate de plexiglas.

Rulați un model de testare. Buna treaba! Ai făcut cea mai grea parte!

Pasul 6: Panou de control

Panoul de control este partea care oferă cea mai creativă libertate. Trebuie doar să țină toate comenzile și componentele electronice, împreună cu bara LED. Cel mai simplu design este o placă dreptunghiulară: găuriți pentru butoane și comenzi și atașați bara LED. Îmi place să combin lemnul, plexiglasul și alte materiale pentru a da un fel de aspect steampunk / retro-modern. În acest caz, am tăiat o bucată de plexiglas greu pentru a ține butoanele principale de alegere a algoritmului și o bară de lemn pentru a ține restul componentelor electronice. Am făcut găuri pentru a se potrivi cu dimensiunea butoanelor arcade. Cablurile arată pe spate, dar îmi place!

De asemenea, am forat spațiu pentru afișajul cu 7 segmente, codificatorul rotativ și unele cabluri din spate. Am tăiat un dado în partea de sus pentru a ține bara LED.

Pasul 7: Ham de butoane

Cablarea multor butoane poate fi o adevărată durere. Din fericire, oamenii care produc mașini arcade au venit cu niște conectori standard pe care îi puteți folosi. Fiecare cablu al conectorului buton are două fire, unul pentru VCC și unul pentru masă. Un capăt are conectori pică care se potrivesc cablurilor din spatele butonului - atașați solul la cablul „normal deschis”, iar VCC la cablul „comun”. În această configurație, când utilizatorul apasă butonul, circuitul este finalizat și microcontrolerul va citi HIGH pe pinul de intrare corespunzător.

Celălalt capăt al cablului are un conector JST (micul lucru alb). Ce este frumos la acești conectori este că intră doar în priză într-un fel, deci nu există nicio modalitate de a inversa accidental VCC și împământare.

Ceea ce am făcut este să construiesc un mic ham pentru acești conectori. Am lipit o serie de prize JST pe o bucată de protoboard și apoi rulez firele înapoi la conectorii Dupont pe care îi voi conecta la microcontroler. Firul roșu este linia VCC și se conectează la toate prizele JST. Firele albastre sunt cele care sunt separate pentru fiecare buton.

Pasul 8: Codificator rotativ

Codificatorul rotativ permite utilizatorului să controleze viteza algoritmului. Folosesc un modul care vine ca o placă care include rezistențe de tracțiune pentru cele două linii de date (fire galbene). Acesta este, de asemenea, un buton, dar nu folosesc această caracteristică. Celelalte două fire sunt VCC și împământate. De asemenea, am un bon buton gras.

Ceea ce îmi place la un codificator rotativ, spre deosebire de un potențiometru, este că semnalează doar rotația (în sensul acelor de ceasornic vs în sens invers acelor de ceasornic) către microcontroler, deci este ușor să schimbăm modul în care este interpretată valoarea. De exemplu, îi puteți da o senzație de accelerație (ca un mouse) atunci când utilizatorul o învârte rapid.

Pasul 9: afișaj pe 7 segmente

Nu sunt multe de spus aici. Aceste lucruri sunt peste tot. LED-urile sunt controlate de un cip numit TM1637, care comunică cu microcontrolerul printr-un protocol serial simplu. Folosesc o bibliotecă existentă care îmi permite să-i spun ce număr vreau să arăt și face restul.

Partea din spate are patru pini: VCC, masă și două fire pentru protocolul serial. Am lipit o bucată de antet cu 4 pini, care se conectează la un conector Dupont corespunzător cablat la microcontroler.

Pasul 10: placa principală a controlerului

Placa principală a controlerului găzduiește microcontrolerul în sine și toți conectorii la comenzi (butoane, afișaj, LED-uri). Microcontrolerul este un ESP32, care oferă multă putere de calcul și memorie și expune o mulțime de pini. Cablajul este destul de standard, dar voi arăta câteva bituri interesante.

NOTĂ: Este posibil să doriți să vă uitați la cod (https://github.com/samguyer/AlgorithmMachine) înainte de a începe să conectați placa principală, astfel încât configurația pinului să se potrivească cu a mea.

Am lipit un cric cu butoi pe placă pentru alimentare și am conectat două fire de cupru puternice la șinele de alimentare și de masă ale plăcii. Motivul este că bara LED poate extrage multă putere dacă luminozitatea este setată la un nivel ridicat și nu vreau să trag toată puterea respectivă prin conectorul USB de pe microcontroler.

Pentru a simplifica cablarea butonului am lipit o bandă de antet cu unghi drept bărbat-femeie pe toată fața microcontrolerului (partea superioară a plăcii, așa cum se arată). Conectorii Dupont de la cablajul butoanelor se conectează direct la acest antet.

IMPORTANT: alimentarea butoanelor (firul roșu) trebuie să fie conectată la linia de alimentare de 3,3V de pe microcontroler. ESP32 este un cip de 3,3 V, deci numai sursele de 3,3 V ar trebui să fie atașate vreodată pinilor de date.

Microcontrolerul atrage puterea (sau împinge puterea) către șine (partea inferioară a plăcii, așa cum se arată) prin pinul 5V USB și împământare. Toate celelalte fire roșii / negre sunt VCC și împământate.

Cele două fire albastre sunt liniile de date pentru benzile LED (WS2812s). Perechea galben / verde sunt liniile de date pentru codificatorul rotativ, iar perechea galbenă este conexiunea serială la afișajul cu 7 segmente.

Pasul 11: Asamblare

Această serie de fotografii prezintă ansamblul final și cablajul. Am atașat, de asemenea, placa principală a controlerului în spate în partea de sus.

Înainte de a-l alimenta, am făcut câteva verificări pentru a evita orice surpriză urâtă. În special, pentru a mă asigura că nu am niciun conector de alimentare / masă în spate și nici un scurtcircuit. Setați multimetrul să testeze continuitatea - va emite un sunet atunci când există o cale electrică între cele două cabluri. Atașați un cablu la linia VCC comună la butoane. Apoi atașați celălalt cablu la fiecare știft al hamului unul câte unul. Multimetrul ar trebui să emită un sunet numai atunci când apăsați butonul. Dacă primiți orice alte bipuri înseamnă că aveți o inversare sau un scurtcircuit. Urmăriți-l și remediați-l înainte de a porni alimentarea!

Pasul 12: Cod

Mai întâi, deschideți ID-ul Arduino și asigurați-vă că aveți instalată biblioteca FastLED.

Descărcați codul Algorithm Machine din GitHub:

github.com/samguyer/AlgorithmMachine.git

Puteți fie să o clonați direct în folderul Arduino, fie să o copiați manual.

Înainte de al încărca, asigurați-vă că setările PIN corespund configurației dvs. hardware. Am plasat toate setările pin în partea de sus a fișierului.

Încărcați și bucurați-vă!

Pasul 13: Cum se utilizează

Algorithm Machine este simplu de utilizat și aproape orice combinație de butoane este ok!

Mai întâi, utilizați butoanele de date pentru a inițializa valorile din matrice. Există trei opțiuni: (1) randomize, (2) adăugați o valoare aleatorie și (3) inversați matricea. Rețineți că valorile sunt persistente, deci puteți face lucruri cum ar fi sortarea lor mai întâi, apoi adăugați puțin zgomot, apoi rulați un alt algoritm de sortare sau căutare.

Alegeți un algoritm de căutare sau sortare dintre celelalte opțiuni de buton. În prezent, nu există feedback atunci când faceți această alegere (ceva pentru munca viitoare). Apoi apăsați butonul „redare”.

Butonul controlează viteza. De asemenea, puteți apăsa „redare” pentru a întrerupe și a întrerupe algoritmul.

Se va opri automat când se termină. De asemenea, puteți apăsa oricând un alt buton de algoritm. Aparatul va opri algoritmul curent și îl va inițializa pe cel nou, dar va păstra datele exact așa cum l-a lăsat algoritmul anterior.

Marele Premiu la Concursul STEM