De algoritmemachine: 13 stappen (met afbeeldingen)

2024 Auteur: John Day | [email protected]. Laatst gewijzigd: 2024-01-30 11:16

Ik geef al 15 jaar informatica op hbo-niveau, en hoewel mijn expertise meer aan de programmeerkant ligt, besteed ik nog steeds behoorlijk veel tijd aan het behandelen van standaardalgoritmen voor zoeken en sorteren. Vanuit een onderwijskundig oogpunt is de centrale kwestie computationele complexiteit: hoeveel tijd kost elk algoritme, gegeven invoer van een bepaalde grootte? Maar er zijn tal van nuances. Hebben de algoritmen bijvoorbeeld verschillende looptijden, afhankelijk van de specifieke invoerwaarden (in tegenstelling tot de grootte)? In welke gevallen zou u het ene sorteeralgoritme boven het andere verkiezen? Hoewel we deze kwesties in abstracto bespreken, irriteerde het me altijd dat er geen gemakkelijke manier was om te zien hoe verschillende algoritmen werken onder verschillende omstandigheden.

doelen

Mijn overkoepelende doel voor dit project was het creëren van een interactief display voor studenten om algoritmen te visualiseren en te verkennen. Ik heb me beperkt tot algoritmen die werken op arrays van waarden (integers), zodat ik een adresseerbare RGB-ledstrip kan gebruiken om de array-inhoud te visualiseren. De array heeft 100 elementen en elk geheel getal is toegewezen aan een kleur in regenboogvolgorde, zodat het meteen duidelijk is wanneer de array gesorteerd, gedeeltelijk gesorteerd of willekeurig is gesorteerd. Naast de waarden wilde ik echter een manier om controleaspecten van het algoritme te visualiseren - bijvoorbeeld welke elementen van de array momenteel worden vergeleken of verwisseld.

De specifieke doelen zijn:

- Bied een verscheidenheid aan zoek- en sorteeralgoritmen

- Visualiseer de waarden in de array op een manier die de voortgang van het algoritme benadrukt

- Visualiseer algoritmecontrole; in het bijzonder de elementen die in aanmerking worden genomen.

- Sta gebruikers toe om de invoergegevenspatronen te kiezen in plaats van altijd willekeurige waarden te genereren

- Sta gebruikers toe om de snelheid te regelen en het algoritme te pauzeren

- Sta gebruikers toe om best-case, worst-case, gemiddeld-case gedrag te forceren (algoritme-specifiek)

- Toon het aantal stappen naarmate het algoritme vordert

visualisatie

Vanuit een fysiek ontwerpstandpunt is het meest interessante onderdeel van dit project de visualisatie van de array. Ik worstelde met het tonen van de gegevens en controle, en hoe ik het weergaveapparaat zelf moest bouwen. Mijn doel was om de gegevenswaarden weer te geven als gekleurde cirkels en de controlepunten als gekleurde pijlen die naar de gegevenswaarden wijzen. Na wat experimenteren kwam ik uit op een ontwerp met twee parallelle strips van 100 RGB-LED's (WS2812) met een cirkelvormig masker over elke data-LED en een driehoekig masker over elke controle-LED. Ik heb een 3D-model van het masker gemaakt met 10 paar cirkels en driehoeken, en vervolgens 10 van deze modules in 3D geprint voor een totaal van 100 cirkels en 100 driehoeken. De grootte en afstand van mijn masker is ontworpen voor strips met 100 LED's per meter. De 3D-modelbestanden vindt u verderop in deze beschrijving.

Elektronica en behuizing

De rest van het apparaat is eenvoudig, vanuit een elektronicastandpunt. Naast de twee LED-strips zijn er een aantal momentane knoppen, een roterende encoder (voor de snelheidsregeling) en een 7-segments display (om stappen weer te geven). Met zoveel knoppen en bedieningselementen heb ik ervoor gekozen om een ESP32-microcontroller te gebruiken omdat deze veel pinnen blootlegt en omdat hij vrij krachtig is. Ik zal de bedradingsstrategie bespreken, maar het is vrij eenvoudig. Je zou waarschijnlijk iets slims kunnen doen met schuifregisters als je minder pinnen wilt gebruiken.

U kunt de behuizing voor dit apparaat in veel verschillende vormen bouwen. Ik stelde me het aanvankelijk voor als een groot rechthoekig bord met de LED-strip aan de bovenkant en een raster van knoppen in het midden. De vorm waarmee ik eindigde, is geïnspireerd op een soort jaren 60-visie op de technologie van het ruimtetijdperk. Je zou het ook kunnen bouwen met de LED-strips in een verticale oriëntatie. Of maak het LED-gedeelte veel groter -- vul een hele muur -- met een apart bedieningspaneel.

Software

De code voor dit apparaat is gratis beschikbaar op GitHub en ik heb mijn best gedaan om te documenteren hoe het werkt en hoe het te configureren. De enige externe bibliotheek die u nodig hebt, is FastLED om de WS2812-strips aan te sturen.

Benodigdheden

Elektronica

1 ESP32-ontwikkelbord (bijv.

2 WS2812 of vergelijkbare LED-strips, dichtheid 100 LED's per meter (bijv.

1 driehoekige "start"-knop (bijv.

12 tijdelijke knoppen (bijv. https://amzn.com/B01N4D4750) - verschillende vormen als je wilt

1 pakket (20) voorbedrade knopconnectoren (bijv.

1 pak JST-connectoren (bijv.

1 roterende encoder (bijv.

1 knop voor roterende encoder (bijv.

1-pack Dupont-connectoren (bijv. https://amzn.com/B014YTPFT8) - het is de moeite waard om ook de krimptang te kopen.

1 Barrel jack (voor stroom) (bijv.

1 TM1637 7-segments numeriek display (bijv.

Soldeer- en bedradingsuitrusting

3D-modelbestanden

U vindt het 3D-model voor een paar 10-lichtmodules op Thingiverse:

www.thingiverse.com/thing:4178181

U moet dit model vijf keer afdrukken voor in totaal 10 modules.

Software

github.com/samguyer/AlgorithmMachine

Behuizing

Hout, plexiglas, roestvrijstalen bouten en schroeven

Diffusie materiaal. Mijn favoriet is Lee Filters #216 volledig witte diffusie, maar er zijn andere opties. Zelfs gewoon wit papier doet het goed.

Stap 1: Algoritmen 101

Veel mensen denken dat informatica in wezen de studie van programmeren is. Maar het echte hart en de ziel van dit vakgebied zijn algoritmen: de studie van systematische procedures voor het oplossen van problemen en hun kosten (meestal hoe lang ze duren). Baanbrekende figuren in het veld, zoals Alan Turing, Alonzo Church en Edsger Dijkstra, dachten over deze ideeën na voordat computers zoals we die kennen zelfs bestonden.

Het belangrijkste kenmerk van een algoritme om een bepaald probleem op te lossen, is dat het gedetailleerd en nauwkeurig is, zodat iemand het kan gebruiken om een oplossing te vinden zonder te begrijpen hoe het werkt; volg gewoon de stappen op een mechanische manier en je krijgt het juiste antwoord. U kunt zien hoe dit helpt bij het programmeren van computers, aangezien ze dit detailniveau nodig hebben. Een computer kan geen ontbrekende details invullen of oordelen, zoals een mens dat kan.

Hoelang zal het duren?

Als we eenmaal een gedetailleerde procedure hebben, is een natuurlijke vraag hoe lang het duurt om het antwoord te krijgen? We kunnen geen gewone tijdseenheden gebruiken, omdat het afhangt van wie het werk doet (vergelijk hoe snel iemand iets kan berekenen versus een supercomputer). Daarnaast hangt het af van hoeveel data we hebben. Het is duidelijk dat het langer duurt om een lijst van een miljoen telefoonnummers te doorzoeken dan een lijst van honderd.

Om de kosten van een algoritme te beschrijven, kiezen we eerst een bewerking in de procedure die één "stap" vertegenwoordigt -- meestal iets eenvoudigs, zoals het vergelijken of optellen van twee getallen, dat een vaste hoeveelheid tijd in beslag neemt. Vervolgens bedenken we een formule die beschrijft hoeveel stappen het algoritme zal nemen bij een bepaald aantal gegevensitems. Om historische redenen geven we het aantal data-items bijna altijd met een hoofdletter N.

Als u bijvoorbeeld door een lijst met N telefoonnummers kijkt, zijn er N stappen nodig. Twee keer door de lijst bladeren kost 2N stappen. Beide worden lineaire tijdalgoritmen genoemd - het totale aantal stappen is een veelvoud van de invoergrootte. Andere algoritmen zijn kwadratisch (N kwadraat tijd) of kubisch (N in derdemachten) of logaritmisch (log N) of een combinatie hiervan. Enkele van de moeilijkste rekenproblemen vereisen exponentiële tijdalgoritmen (2^N).

Oke, dus wat?

Als het aantal data-items N klein is, maakt het niet veel uit. Voor N=10 is 10N bijvoorbeeld die naam als N in het kwadraat. Maar hoe zit het met N=1000? of N=1000000? Een miljoen kwadraat is een behoorlijk groot aantal. Zelfs op een zeer snelle computer kan een kwadratisch algoritme lang duren als de invoer groot genoeg is. Exponentiële algoritmen zijn veel lastiger: voor N=50 zou een exponentieel algoritme twee weken nodig hebben om te voltooien, zelfs op een computer waar elke stap slechts één nanoseconde is (1 miljardste van een seconde). Au!

Aan de andere kant van de schaal hebben we logaritmische tijdalgoritmen, die erg snel zijn. Logtijd is het tegenovergestelde van exponentiële tijd: gegeven invoergrootte N, is het aantal stappen de exponent T in de formule 2^T = N. Als onze invoergrootte bijvoorbeeld één miljard is, heeft een logtijdalgoritme slechts 30 nodig stappen, aangezien 2^30 = 1, 000, 000, 000. Hoe lief is dat?!??!

Je vraagt je misschien af, wie geeft er om inputgroottes van miljoenen of miljarden? Denk er eens over na: hoeveel gebruikers zijn er op Facebook? Hoeveel webpagina's worden door Google geïndexeerd? Hoeveel basenparen zijn er in het menselijk genoom? Hoeveel metingen gaan er in een weersimulatie?

Stap 2: De algoritmen

De Algorithm Machine implementeert momenteel de volgende algoritmen. Twee daarvan zijn zoekalgoritmen (zoek een bepaalde waarde in de lijst), de rest zijn sorteeralgoritmen (zet de waarden op volgorde).

Lineair zoeken

Doorzoek de lijst met waarden een voor een vanaf het begin. Vereist lineaire tijd.

Binaire zoekopdracht

Doorzoek een lijst door deze herhaaldelijk in tweeën te delen. Vereist logtijd, maar de lijst moet worden gesorteerd om te werken.

Bellen sorteren

Sorteer een lijst en wissel herhaaldelijk aangrenzende elementen uit die niet op volgorde staan. Vereist kwadratische tijd.

Invoegsortering

Sorteer een lijst door elk element op de juiste plaats in de lijst met reeds gesorteerde waarden te plaatsen. Vereist kwadratische tijd.

Snel sorteren

Sorteer een lijst door de lijst herhaaldelijk in tweeën te delen en alle waarden kleiner dan de mediaan naar de eerste helft te verplaatsen en alle waarden die groter zijn dan de mediaan naar de tweede helft. In de praktijk kunnen we de mediaan niet efficiënt vinden, dus kiezen we willekeurig een waarde. Als gevolg hiervan kan dit algoritme in het ergste geval kwadratisch zijn, maar vereist dit meestal N * logN tijd.

Sorteren samenvoegen

Sorteer een lijst door deze in tweeën te delen, de twee helften afzonderlijk te sorteren (met behulp van merge sort), en ze vervolgens samen te voegen door de waarden te verweven. Vereist altijd N * logN tijd.

Hoop sorteren

Sorteer een lijst door een gegevensstructuur te bouwen die een heap wordt genoemd, waarmee u de kleinste waarde in logtijd kunt vinden. Vereist altijd N * logN tijd.

Bitonische sortering

Vergelijkbaar met merge sort en quicksort, deel een lijst in tweeën, sorteer de helften en combineer ze opnieuw. Dit algoritme vereist N * logN * logN tijd, maar heeft als voordeel dat het gemakkelijk te parallelliseren is.

Stap 3: LED-balk: 3D-print het masker

De eerste stap bij het bouwen van de LED-balk is het 3D-printen van het masker dat de lichten hun vorm geeft. Elke module omvat tien elementen van de array, 10 waarden (cirkels) en 10 indicatoren (driehoeken), dus je hebt in totaal 10 modules nodig. Het STL-bestand dat ik hier aanlever, bevat twee exemplaren van de module, dus u moet vijf afdrukcycli uitvoeren. Ik heb niet de beste 3D-printer, dus ik moest ze handmatig opruimen met een vijl en schuurpapier. Het belangrijkste is dat de ronde en driehoekige gaten schoon zijn.

Op de foto's zie je mijn testopstelling: ik heb de twee ledstrips vastgeplakt en met een microcontroller op een breadboard aangesloten. Deze stap is niet nodig, maar ik wilde zien hoe het eruit zou zien voordat ik begon met het monteren van de behuizing. Ik zette de maskermodules op de twee LED-strips en maakte een eenvoudige schets met willekeurige kleuren. Met een strook van het diffusiemateriaal springen de vormen en kleuren er echt uit.

Stap 4: Alternatieven voor LED-balken

Toen ik voor het eerst aan dit project begon, experimenteerde ik met andere manieren om het LED-masker te maken. Als u geen 3D-printer heeft, kunt u een van deze opties overwegen. Ik zal eerlijk zijn: het is een enorme klus om deze onderdelen te maken.

Voor de cirkels kocht ik een 13/32 koperen buis, die bijna precies 1 cm in diameter is. Ik heb het in honderd segmenten van 1 cm gesneden en ze vervolgens wit gespoten.

Voor de driehoeken gebruikte ik zware aluminiumfolie gesneden uit een wegwerpbakvorm. Ik maakte een driehoekige vorm van hout, wikkelde vervolgens korte stroken folie om de vorm en plakte ze vast. Nogmaals, je hebt honderd van deze dingen nodig, dus het kost wat tijd en geduld.

Stap 5: LED-balkbehuizing

Mijn behuizing is vrij eenvoudig: twee stroken hout voor de zijkanten en twee stroken plexiglas voor de boven- en onderkant. Alle onderdelen zijn ongeveer 102 cm lang (1 meter voor de LED's, plus een beetje extra voor de bedrading). De zijkanten moeten iets hoger zijn dan 1 cm om ruimte te maken voor de LED-strips. Na het snijden van de stroken heb ik de 3D-geprinte maskerstukken ertussen ingeklemd om de breedte voor het plexiglas te meten. Snijd twee stukken plexiglas over de breedte en lengte van de staaf. Knip ten slotte een strook van het diffusiemateriaal af om over het masker te passen.

Voor diffusie hou ik echt van Lee Filters #216 (volledig witte diffusie). Het is een dunne kunststof plaat die een gelijkmatige verspreiding geeft zonder veel licht te verliezen. Maar het is duur spul. Soms kun je kleinere vellen online te koop vinden, maar een hele rol kost je ongeveer $ 125. Enkele andere opties zijn wit papier of een ander soort satijn of mat plastic. Een populaire keuze zijn dunne kunststof snijmatten.

Voordat u de LED-balk monteert, moet u ervoor zorgen dat u de juiste connectoren op de LED-strips hebt gesoldeerd. Veel strips worden geleverd met voorgesoldeerde leads, dus die kun je gewoon gebruiken.

Ik begon de montage door het bovenste stuk plexiglas op de houten zijkanten te schroeven (zie foto). Toen draaide ik het om en plaatste de diffusiestrip erin, gevolgd door de 10 maskerstukken. Toen ik eenmaal tevreden was met de afstand, spelde ik ze op hun plaats met een paar stippen hete lijm.

Leg vervolgens de twee LED-strips naast elkaar op de maskers. Zorg ervoor dat de LED's naar beneden zijn gericht en zorg ervoor dat elke LED is uitgelijnd met het overeenkomstige gat in het masker. Voeg wat hete lijm of tape toe om de LED-strips op hun plaats te houden. Schroef tot slot het achterstuk van plexiglas vast.

Voer een testpatroon uit. Goed werk! Je hebt het moeilijkste gedaan!

Stap 6: Configuratiescherm

Het bedieningspaneel is het onderdeel dat de meeste creatieve vrijheid biedt. Het moet alleen alle bedieningselementen en elektronica bevatten, samen met de LED-balk. Het eenvoudigste ontwerp is een rechthoekig bord: boor gaten voor de knoppen en bedieningselementen en bevestig de LED-balk. Ik combineer graag hout, plexiglas en andere materialen om een soort steampunk / retro-moderne look te geven. In dit geval heb ik een stuk zwaar plexiglas gesneden om de belangrijkste keuzeknoppen voor het algoritme vast te houden, en een houten balk om de rest van de elektronica vast te houden. Ik heb gaten geboord die passen bij de grootte van de arcade-knoppen. De bedrading is op de achterkant te zien, maar ik vind het leuk!

Ik heb ook ruimte geboord voor het 7-segments display, de roterende encoder en een deel van de bedrading aan de achterkant. Ik heb een dado in de bovenkant gesneden om de LED-balk vast te houden.

Stap 7: Knoopharnas

Het bedraden van veel knoppen kan lastig zijn. Gelukkig hebben de mensen die arcade-machines maken een aantal standaardconnectoren bedacht die je kunt gebruiken. Elke knopconnectorkabel heeft twee draden, één voor VCC en één voor aarde. Het ene uiteinde heeft spade-connectoren die passen op de kabels aan de achterkant van de knop - bevestig de grond aan de "normaal open" kabel en VCC aan de "gewone" kabel. In deze configuratie, wanneer de gebruiker op de knop drukt, is het circuit voltooid en zal de microcontroller HIGH lezen op de corresponderende invoerpin.

Het andere uiteinde van de kabel heeft een JST-connector (het kleine witte ding). Het mooie van deze connectoren is dat ze maar op één manier in de houder gaan, dus er is geen manier om VCC en aarde per ongeluk om te keren.

Wat ik deed is een klein harnas bouwen voor deze connectoren. Ik soldeer een reeks JST-aansluitingen op een stuk protoboard en leid dan draden terug naar Dupont-connectoren die ik in de microcontroller steek. De rode draad is de VCC-lijn en wordt aangesloten op alle JST-aansluitingen. De blauwe draden zijn de draden die voor elke knop apart zijn.

Stap 8: roterende encoder

Met de roterende encoder kan de gebruiker de snelheid van het algoritme regelen. Ik gebruik een module die wordt geleverd als een breakout-bord met pull-up-weerstanden voor de twee datalijnen (gele draden). Deze is toevallig ook een knop, maar die functie gebruik ik niet. De andere twee draden zijn VCC en aarde. Ik heb ook een mooie dikke knop.

Wat ik leuk vind aan een roterende encoder, in tegenstelling tot een potentiometer, is dat deze alleen rotatie (met de klok mee versus tegen de klok in) doorgeeft aan de microcontroller, dus het is gemakkelijk om te veranderen hoe de waarde wordt geïnterpreteerd. U kunt het bijvoorbeeld een gevoel van versnelling geven (zoals een muis) wanneer de gebruiker het snel ronddraait.

Stap 9: 7-segments display

Niet veel te zeggen hier. Deze dingen zijn overal. De LED's worden aangestuurd door een chip genaamd TM1637, die via een eenvoudig serieel protocol met de microcontroller communiceert. Ik gebruik een bestaande bibliotheek waarmee ik het nummer kan vertellen dat ik wil laten zien, en het doet de rest.

De achterkant heeft vier pinnen: VCC, aarde en twee draden voor het seriële protocol. Ik heb een 4-pins stuk header gesoldeerd, die wordt aangesloten op een overeenkomstige Dupont-connector die is aangesloten op de microcontroller.

Stap 10: Hoofdcontrollerkaart

De hoofdcontrollerkaart bevat de microcontroller zelf en alle connectoren voor de bedieningselementen (knoppen, display, LED's). De microcontroller is een ESP32, die veel rekenkracht en geheugen biedt en veel pinnen blootlegt. De bedrading is vrij standaard, maar ik zal op een paar interessante stukjes wijzen.

OPMERKING: Misschien wilt u de code (https://github.com/samguyer/AlgorithmMachine) bekijken voordat u begint met het bedraden van het moederbord, zodat uw pinconfiguratie overeenkomt met de mijne.

Ik soldeerde een vataansluiting op het bord voor stroom, en verbond twee stevige koperdraden met de stroom- en grondrails van het bord. De reden is dat de LED-balk veel stroom kan trekken als de helderheid hoog is ingesteld, en ik wil niet al die stroom door de USB-connector op de microcontroller trekken.

Om de knopbedrading te vereenvoudigen, heb ik een strook mannelijk-naar-vrouwelijk haakse header langs de hele zijkant van de microcontroller gesoldeerd (bovenkant van het bord zoals weergegeven). De Dupont-connectoren van de knopharnas worden rechtstreeks op deze header aangesloten.

BELANGRIJK: de voeding voor de knoppen (de rode draad) moet worden aangesloten op de 3,3V-voedingslijn op de microcontroller. De ESP32 is een 3.3V-chip, dus er mogen alleen 3.3V-bronnen op de datapinnen worden aangesloten.

De microcontroller trekt stroom (of duwt stroom) naar de rails (onderkant van het bord zoals afgebeeld) via de 5V USB-pin en aarde. Alle andere rood/zwarte draden zijn VCC en aarde.

De twee blauwe draden zijn de datalijnen voor de ledstrips (de WS2812s). Het geel/groene paar zijn de datalijnen voor de roterende encoder en het gele paar zijn de seriële verbinding met het 7-segments display.

Stap 11: Montage

Deze serie foto's toont de eindmontage en bedrading. Ik heb ook de hoofdcontrollerkaart aan de achterkant bovenaan bevestigd.

Voordat ik hem opstartte, deed ik een paar controles om onaangename verrassingen te voorkomen. In het bijzonder om ervoor te zorgen dat ik geen stroom/aarde-connectoren naar achteren had en geen kortsluiting. Stel uw multimeter in om te testen op continuïteit - hij piept wanneer er een elektrisch pad is tussen de twee draden. Bevestig een kabel aan de gemeenschappelijke VCC-lijn van de knoppen. Bevestig vervolgens de andere lijn één voor één aan elke pin van het harnas. De multimeter hoort alleen piepen als u op de knop drukt. Als u andere pieptonen hoort, betekent dit dat u een omkering of kortsluiting heeft. Zoek het op en repareer het voordat je de stroom inschakelt!

Stap 12: Coderen

Open eerst uw Arduino IDE en zorg ervoor dat u de FastLED-bibliotheek hebt geïnstalleerd.

Download de Algorithm Machine-code van GitHub:

github.com/samguyer/AlgorithmMachine.git

Je kunt het rechtstreeks naar je Arduino-map klonen of met de hand kopiëren.

Zorg ervoor dat de pin-instellingen overeenkomen met uw hardwareconfiguratie voordat u het uploadt. Ik heb alle pin-instellingen bovenaan het bestand geplaatst.

Uploaden en genieten!

Stap 13: Hoe te gebruiken?

De Algorithm Machine is eenvoudig te gebruiken en bijna elke combinatie van knoppen is ok!

Gebruik eerst de gegevensknoppen om de waarden in de array te initialiseren. Er zijn drie keuzes: (1) willekeurig maken, (2) één willekeurige waarde toevoegen en (3) de array omkeren. Houd er rekening mee dat de waarden persistent zijn, dus u kunt dingen doen zoals ze eerst sorteren, dan wat ruis toevoegen en vervolgens een ander sorteer- of zoekalgoritme uitvoeren.

Kies een zoek- of sorteeralgoritme uit de andere knopkeuzes. Momenteel is er geen feedback wanneer u deze keuze maakt (iets voor toekomstig werk). Druk dan op de "play"-knop.

De knop regelt de snelheid. U kunt ook op "afspelen" drukken om het algoritme te pauzeren en te hervatten.

Het stopt automatisch als het klaar is. U kunt ook op elk moment op een andere algoritmeknop drukken. De machine stopt het huidige algoritme en initialiseert het nieuwe, maar behoudt de gegevens precies zoals het vorige algoritme het achterliet.

Hoofdprijs in de STEM-wedstrijd