Algoritmemaskinen: 13 trinn (med bilder)

2024 Forfatter: John Day | [email protected]. Sist endret: 2024-01-30 11:22

Jeg har undervist i informatikk på høyskolenivå i 15 år, og selv om min ekspertise er mer på programmeringssiden, bruker jeg fortsatt ganske mye tid på å dekke standardalgoritmer for søk og sortering. Fra et undervisningsmessig synspunkt er det sentrale spørsmålet beregningskompleksitet: hvor mye tid krever hver algoritme, gitt innspill av en bestemt størrelse? Men det er mange nyanser. Har for eksempel algoritmene forskjellige kjøretider avhengig av de spesifikke inngangsverdiene (i motsetning til størrelsen)? I hvilke tilfeller vil du velge en sorteringsalgoritme fremfor en annen? Selv om vi diskuterer disse problemene abstrakt, plaget det meg alltid at det ikke var noen enkel måte å se hvordan forskjellige algoritmer fungerer under forskjellige forhold.

Mål

Mitt overordnede mål for dette prosjektet var å lage en interaktiv skjerm for studenter å visualisere og utforske algoritmer. Jeg begrenset meg til algoritmer som arbeider med verdier (heltall), så jeg kan bruke en adresserbar RGB LED -stripe for å visualisere matrisens innhold. Matrisen har 100 elementer, og hvert heltall blir kartlagt til en farge i regnbue rekkefølge, slik at det umiddelbart er tydelig når matrisen er sortert, delvis sortert eller randomisert. I tillegg til verdiene ønsket jeg imidlertid en måte å visualisere kontrollaspekter ved algoritmen - for eksempel hvilke elementer i matrisen som for tiden blir sammenlignet eller byttet.

De spesifikke målene er:

- Tilbyr en rekke søke- og sorteringsalgoritmer

- Visualiser verdiene i matrisen på en måte som fremhever algoritmens fremgang

- Visualiser algoritmekontroll; spesielt elementene som vurderes.

- Tillat brukere å velge inndatamønstre i stedet for alltid å generere tilfeldige verdier

- La brukerne kontrollere hastigheten og sette algoritmen på pause

-La brukerne tvinge best case, worst case, gjennomsnittlig atferd (algoritmespesifikk)

- Vis antall trinn etter hvert som algoritmen fortsetter

Visualisering

Fra et fysisk design synspunkt er den mest interessante delen av dette prosjektet visualisering av matrisen. Jeg slet med hvordan jeg skulle vise data og kontroll, og hvordan jeg skulle bygge selve skjermenheten. Målet mitt var å vise dataverdiene som fargede sirkler og kontrollpunktene som fargede piler som peker på dataverdiene. Etter litt eksperimentering bestemte jeg meg for et design med to parallelle strimler med 100 RGB -lysdioder (WS2812) med en sirkulær maske over hver data -LED og en trekantet maske over hver kontroll -LED. Jeg laget en 3D -modell av masken med 10 par sirkler og trekanter, og deretter trykte jeg 3D av 10 av disse modulene for totalt 100 sirkler og 100 trekanter. Størrelsen og avstanden til masken min er designet for strimler med 100 lysdioder per meter. 3D -modellfilene er gitt senere i denne beskrivelsen.

Elektronikk og skap

Resten av enheten er grei, fra et elektronisk synspunkt. I tillegg til de to LED-stripene, er det en haug med øyeblikkelige knapper, en roterende encoder (for hastighetskontrollen) og et 7-segment display (for å vise trinn). Med så mange knapper og kontroller valgte jeg å bruke en ESP32 mikrokontroller fordi den avslører mange pinner og fordi den er ganske kraftig. Jeg skal gå over ledningsstrategien, men det er ganske grunnleggende. Du kan sannsynligvis gjøre noe smart med skiftregistre hvis du vil bruke færre pinner.

Du kan bygge kabinettet for denne enheten i mange forskjellige former. Jeg forestilte meg det først som et stort rektangulært brett med LED -stripen over toppen, og et rutenett med knapper i midten. Formen jeg endte opp med er inspirert av et slags 1960-talls syn på romalderteknologi. Du kan også bygge den med LED -stripene i vertikal retning. Eller gjør LED -delen mye større - fyll en hel vegg - med et eget kontrollpanel.

Programvare

Koden for denne enheten er fritt tilgjengelig på GitHub, og jeg har gjort mitt beste for å dokumentere hvordan den fungerer og hvordan den konfigureres. Det eneste eksterne biblioteket du trenger er FastLED for å kjøre WS2812 -stripene.

Rekvisita

Elektronikk

1 ESP32 utviklingstavle (f.eks.

2 WS2812 eller lignende LED -strips, tetthet 100 LED per meter (f.eks.

1 "Start" -knapp for trekanten (f.eks.

12 Midlertidige knapper (f.eks. Https://amzn.com/B01N4D4750) - forskjellige former hvis du vil

1 pakke (20) forhåndskoblede knappekontakter (f.eks.

1 pakke JST -kontakter (f.eks.

1 roterende encoder (f.eks.

1 Knott for roterende encoder (f.eks.

1 pakke Dupont -kontakter (f.eks. Https://amzn.com/B014YTPFT8) - det er verdt å få krympeverktøyet også.

1 fatkontakt (for strøm) (f.eks.

1 TM1637 7-segmenters numerisk skjerm (f.eks.

Lodde- og ledningsutstyr

3D -modellfiler

Du finner 3D-modellen for et par 10-lysmoduler på Thingiverse:

www.thingiverse.com/thing:4178181

Du må skrive ut denne modellen fem ganger for totalt 10 moduler.

Programvare

github.com/samguyer/AlgorithmMachine

Innhegning

Tre, plexiglass, bolter og skruer i rustfritt stål

Spredningsmateriale. Min favoritt er Lee Filters #216 full white diffusion, men det er andre alternativer. Selv vanlig hvitt papir gjør en god jobb.

Trinn 1: Algoritmer 101

Mange tror at informatikk egentlig er studiet av programmering. Men det virkelige hjertet og sjelen til dette feltet er algoritmer: studiet av systematiske prosedyrer for å løse problemer og kostnadene deres (vanligvis hvor lang tid de tar). Seminalfigurer i feltet, som Alan Turing, Alonzo Church og Edsger Dijkstra, tenkte på disse ideene før datamaskiner som vi kjenner dem eksisterte.

Hovedtrekk ved en algoritme for å løse et bestemt problem er at det er detaljert og presist, slik at noen kan bruke det til å få en løsning uten å forstå hvordan det fungerer i det hele tatt; bare følg trinnene på en mekanisk måte, så får du det riktige svaret. Du kan se hvordan dette hjelper med programmering av datamaskiner, siden de trenger dette detaljnivået. En datamaskin kan ikke fylle ut manglende detaljer eller foreta vurderinger, slik en person kan.

Hvor lang tid vil det ta?

Når vi har en detaljert prosedyre, er et naturlig spørsmål hvor lang tid det vil ta å få svaret? Vi kan ikke bruke vanlige tidsenheter, siden det avhenger av hvem som gjør jobben (sammenlign hvor raskt en person kan beregne noe kontra en superdatamaskin). I tillegg kommer det an på hvor mye data vi har. Det tar klart lengre tid å søke i en liste med en million telefonnumre enn en liste med hundre.

For å beskrive kostnaden for en algoritme velger vi først en operasjon i prosedyren som representerer ett "trinn" - vanligvis noe enkelt, som å sammenligne eller legge til to tall, som tar en bestemt tid å gjøre. Deretter kommer vi med en formel som beskriver hvor mange trinn algoritmen vil ta gitt et visst antall dataelementer. Av historiske årsaker angir vi nesten alltid antall dataelementer med stort N.

For eksempel tar N trinn å se gjennom en liste over N telefonnumre. Å se gjennom listen to ganger tar 2N trinn. Begge disse kalles lineære tidsalgoritmer - det totale antall trinn er et multiplum av inngangsstørrelsen. Andre algoritmer er kvadratisk (N kvadrat tid) eller kubikk (N kubert) eller logaritmisk (log N) eller en kombinasjon av disse. Noen av de vanskeligste beregningsproblemene krever eksponentielle tidsalgoritmer (2^N).

OK, så hva?

Når antallet dataelementer N er lite, spiller det ingen rolle. For eksempel, for N = 10, er 10N det navnet som N i kvadrat. Men hva med N = 1000? eller N = 1000000? En million i kvadrat er et ganske stort tall. Selv på en veldig rask datamaskin kan en kvadratisk algoritme ta lang tid hvis inngangen er stor nok. Eksponensielle algoritmer er mye mer plagsomme: for N = 50 vil en eksponentiell algoritme ta to uker å fullføre, selv på en datamaskin hvor hvert trinn bare er ett nanosekund (1 milliarddel av et sekund). Au!

I den andre enden av skalaen har vi logaritmiske tidsalgoritmer, som er veldig raske. Loggtid er det motsatte av eksponentiell tid: gitt inndatastørrelse N, antall trinn er eksponenten T i formelen 2^T = N. Hvis for eksempel inndatastørrelsen er en milliard, krever en loggetidsalgoritme bare 30 trinn, siden 2^30 = 1, 000, 000, 000. Hvor søtt er det?! ??!

Du lurer kanskje på, hvem bryr seg om inngangsstørrelser på millioner eller milliarder? Tenk på det: hvor mange brukere er det på Facebook? Hvor mange nettsider er indeksert av Google? Hvor mange basepar er det i det menneskelige genomet? Hvor mange målinger går inn i en værsimulering?

Trinn 2: Algoritmene

Algoritmemaskinen implementerer for tiden følgende algoritmer. To av dem er søkealgoritmer (finn en bestemt verdi i listen), resten er sorteringsalgoritmer (sett verdiene i rekkefølge).

Lineært søk

Søk gjennom listen over verdier en etter en fra begynnelsen. Krever lineær tid.

Binært søk

Søk i en liste ved å dele den i to. Krever loggetid, men listen må sorteres for at den skal fungere.

Boblesort

Sorter en liste og utveksler naboelementer flere ganger som ikke er i orden. Krever kvadratisk tid.

Innsettingssortering

Sorter en liste ved å plassere hvert element på riktig sted i listen over allerede sorterte verdier. Krever kvadratisk tid.

Quicksort

Sorter en liste ved å dele listen gjentatte ganger i to og flytte alle verdiene mindre enn medianen til første halvdel, og alle verdiene større enn medianen til andre halvdel. I praksis kan vi ikke effektivt finne medianen, så vi velger en verdi tilfeldig. Som et resultat kan denne algoritmen i verste fall være kvadratisk, men krever vanligvis N * logN -tid.

Slå sammen sortering

Sorter en liste ved å dele den i to, sortere de to halvdelene separat (ved hjelp av sammenslåingssortering), og deretter slå dem sammen ved å blande verdiene. Krever alltid N * logN -tid.

Heap sort

Sorter en liste ved å bygge en datastruktur kalt en haug, som lar deg finne den minste verdien i loggtid. Krever alltid N * logN -tid.

Bitonisk sortering

På samme måte som sammenslåingssortering og quicksort, deler du en liste i to, sorterer halvdelene og rekombinerer dem. Denne algoritmen krever N * logN * logN -tid, men har fordelen at den er enkel å parallellisere.

Trinn 3: LED -stolpe: 3D -utskrift av masken

Det første trinnet i å bygge LED -linjen er å 3D -skrive ut masken som gir lysene sin form. Hver modul dekker ti elementer i matrisen, 10 verdier (sirkler) og 10 indikatorer (trekanter), så du trenger totalt 10 moduler. STL -filen jeg gir her inneholder to forekomster av modulen, så du må gjøre fem utskriftssykluser. Jeg har ikke den beste 3D -skriveren, så jeg måtte gjøre noen manuell opprydding på dem ved hjelp av en fil og sandpapir. Det viktigste er at de sirkulære og trekantede hullene er rene.

På bildene ser du testoppsettet mitt: Jeg teipet de to LED -stripene ned og festet dem til et brødbrett med en mikrokontroller. Dette trinnet er ikke nødvendig, men jeg ville se hvordan det ville se ut før jeg begynte å montere skapet. Jeg stilte opp maskemodulene på de to LED -stripene og kjørte en enkel skisse med tilfeldige farger. Med en stripe av diffusjonsmaterialet dukker formene og fargene virkelig opp.

Trinn 4: LED -baralternativer

Da jeg først startet dette prosjektet, eksperimenterte jeg med andre måter å lage LED -masken på. Hvis du ikke har en 3D -skriver, kan du vurdere et av disse alternativene. Jeg skal være ærlig: det er en enorm smerte å lage disse delene.

Til sirklene kjøpte jeg et 13/32 messingrør, som er nesten nøyaktig 1 cm i diameter. Jeg kuttet den i hundre 1 cm segmenter og spraymalt dem deretter hvite.

Til trekanter brukte jeg tung aluminiumsfolie kuttet fra en engangsform. Jeg laget en trekantet form av tre, deretter pakket jeg korte bånd av folie rundt formen og teipet dem. Igjen trenger du hundre av disse tingene, så det tar litt tid og tålmodighet.

Trinn 5: LED -stangkapsling

Kapslingen min er ganske enkel: to trelister for sidene og to strimler av plexiglass for topp og bunn. Alle delene er omtrent 102 cm lange (1 meter for lysdiodene, pluss litt ekstra for å imøtekomme ledningene). Sidene skal være litt høyere enn 1 cm for å få plass til LED -stripene. Etter å ha klippet stripene, klemte jeg inn de 3D -trykte maskebitene mellom dem for å måle bredden på plexiglasset. Skjær to stykker plexiglass i bredden og lengden på stangen. Til slutt skjærer du en stripe av diffusjonsmaterialet for å passe over masken.

For diffusjon liker jeg Lee Filters #216 (full hvit diffusjon). Det er et tynt plastark som gir jevn diffusjon uten å miste mye lys. Men det er dyre ting. Noen ganger kan du finne mindre ark til salgs på nettet, men en hel rulle gir deg tilbake $ 125. Noen andre alternativer er hvitt papir eller annen form for sateng eller frostet plast. Et populært valg er tynne skjærematter i plast.

Før du monterer LED -stangen, må du kontrollere at du har de riktige kontaktene loddet til LED -stripene. Mange strimler har førelodde lodninger, så du kan bare bruke dem.

Jeg startet monteringen med å skru det øverste stykket plexiglass på tresidene (se bildet). Deretter snudde jeg den og plasserte diffusjonsstrimmelen i, etterfulgt av de 10 maskebitene. Når jeg var fornøyd med avstanden, festet jeg dem på plass med et par prikker varmt lim.

Legg deretter de to LED -stripene side om side oppå maskene. Sørg for at lysdiodene vender ned og sørg for at hver lysdiode står på linje med det tilsvarende hullet i masken. Legg til litt lim eller tape for å holde LED -stripene på plass. Til slutt skrur du på bakstykket av plexiglass.

Kjør et testmønster. Fin jobb! Du har gjort det vanskeligste!

Trinn 6: Kontrollpanel

Kontrollpanelet er den delen som gir mest kreativ frihet. Den trenger bare å holde alle kontrollene og elektronikken, sammen med LED -stangen. Den enkleste designen er et rektangulært brett: bor hull for knappene og kontrollene, og fest LED -stangen. Jeg liker å kombinere tre, plexiglass og andre materialer for å gi et slags steampunk / retro-moderne utseende. I dette tilfellet kuttet jeg et stykke kraftig plexiglass for å holde de viktigste algoritmeknappene, og en trebjelke for å holde resten av elektronikken. Jeg boret hull for å matche størrelsen på arkadeknappene. Ledningene viser på baksiden, men jeg liker det!

Jeg boret også ut plass til 7-segmenters skjerm, roterende encoder og noen av ledningene på baksiden. Jeg kuttet en dado i toppen for å holde LED -stangen.

Trinn 7: Knappesele

Å koble til mange knapper kan være en skikkelig smerte. Heldigvis har folk som lager arkademaskiner kommet med noen standardkontakter som du kan bruke. Hver knappkontaktkabel har to ledninger, en for VCC og en for jord. Den ene enden har spadekontakter som passer til ledningene på baksiden av knappen - fest bakken til den "normalt åpne" ledningen, og VCC til den "vanlige" ledningen. I denne konfigurasjonen, når brukeren trykker på knappen, er kretsen fullført og mikrokontrolleren vil lese HØYT på den tilsvarende inngangspinnen.

Den andre enden av kabelen har en JST -kontakt (den lille hvite tingen). Det som er fint med disse kontaktene er at de bare går inn i beholderen på en måte, så det er ingen måte å utilsiktet reversere VCC og bakken.

Det jeg gjorde er å bygge en liten sele for disse kontaktene. Jeg lodder en serie JST -beholdere på et stykke protoboard og kjører deretter ledninger tilbake til Dupont -kontakter som jeg skal koble til mikrokontrolleren. Den røde ledningen er VCC -linjen, og den kobles til alle JST -beholdere. De blå ledningene er de som er separate for hver knapp.

Trinn 8: Rotary Encoder

Den roterende koderen lar brukeren kontrollere hastigheten på algoritmen. Jeg bruker en modul som kommer som et utbruddskort som inkluderer opptrekkmotstander for de to datalinjene (gule ledninger). Denne er også en knapp, men jeg bruker ikke den funksjonen. De to andre ledningene er VCC og bakken. Jeg fikk også en fin fettknott.

Det jeg liker med en roterende koder, i motsetning til et potensiometer, er at den bare signaliserer rotasjon (med klokken mot klokken) til mikrokontrolleren, så det er enkelt å endre hvordan verdien blir tolket. For eksempel kan du gi den en følelse av akselerasjon (som en mus) når brukeren snurrer den raskt.

Trinn 9: 7-segmenters display

Ikke mye å si her. Disse tingene er overalt. Lysdiodene styres av en brikke kalt TM1637, som kommuniserer med mikrokontrolleren gjennom en enkel seriell protokoll. Jeg bruker et eksisterende bibliotek som lar meg fortelle det hvilket nummer jeg vil vise, og det gjør resten.

Baksiden har fire pinner: VCC, bakken og to ledninger for den serielle protokollen. Jeg loddet et 4-pinners stykke header, som kobles til en tilsvarende Dupont-kontakt som er koblet til mikrokontrolleren.

Trinn 10: Hovedkontrollkort

Hovedkontrollkortet inneholder selve mikrokontrolleren og alle kontaktene til kontrollene (knapper, display, lysdioder). Mikrokontrolleren er en ESP32, som gir mye datakraft og minne, og avslører mange pinner. Ledningene er ganske standard, men jeg vil påpeke noen interessante biter.

MERK: Det kan være lurt å se på koden (https://github.com/samguyer/AlgorithmMachine) før du begynner å koble hovedkortet, slik at pin -konfigurasjonen samsvarer med min.

Jeg loddet en tønnekontakt på brettet for å få strøm, og koblet to tøffe kobbertråder til brettets strøm- og bakkeskinner. Grunnen er at LED -linjen kan trekke mye strøm hvis lysstyrken er satt høyt, og jeg vil ikke trekke all den strømmen gjennom USB -kontakten på mikrokontrolleren.

For å forenkle knappeledningene loddet jeg en stripe med mannlig til kvinne rettvinklet topptekst nedover hele siden av mikrokontrolleren (oversiden av brettet som vist). Dupont -kontaktene fra knappene kobles direkte til denne overskriften.

VIKTIG: strømmen til knappene (den røde ledningen) må kobles til 3,3V strømlinjen på mikrokontrolleren. ESP32 er en 3.3V -brikke, så bare 3.3V -kilder bør noen gang være festet til datapinnene.

Mikrokontrolleren trekker strøm (eller skyver strøm) til skinnene (undersiden av brettet som vist) gjennom 5V USB -pinnen og bakken. Alle de andre røde/svarte ledningene er VCC og malt.

De to blå ledningene er datalinjene for LED -stripene (WS2812s). Det gule/grønne paret er datalinjene for den roterende koderen, og det gule paret er den serielle tilkoblingen til 7-segmenters display.

Trinn 11: Montering

Denne bildeserien viser den siste montering og ledninger. Jeg festet også hovedkontrollkortet bak på toppen.

Før jeg satte den på, gjorde jeg noen sjekker for å unngå stygge overraskelser. Spesielt for å sikre at jeg ikke hadde noen strøm/jordkontakter bakover, og ingen kortslutninger. Sett multimeteret ditt til å teste for kontinuitet - det piper når det er en elektrisk bane mellom de to ledningene. Fest den ene ledningen til den vanlige VCC -linjen til knappene. Fest deretter den andre ledningen til hver pinne i selen en etter en. Multimeteret skal bare pippe når du trykker på knappen. Hvis du får andre pip, betyr det at du har en reversering eller en kort. Spor det og fikse det før du slår på strømmen!

Trinn 12: Kode

Først åpner du Arduino IDE og sørger for at FastLED -biblioteket er installert.

Last ned Algorithm Machine -koden fra GitHub:

github.com/samguyer/AlgorithmMachine.git

Du kan enten klone den direkte i Arduino -mappen, eller kopiere den inn for hånd.

Før du laster den opp, må du kontrollere at pin -innstillingene samsvarer med maskinvarekonfigurasjonen. Jeg har plassert alle pin -innstillingene øverst i filen.

Last opp og nyt!

Trinn 13: Hvordan bruke

Algoritmemaskinen er enkel å bruke, og nesten hvilken som helst kombinasjon av knapper er ok!

Bruk først dataknappene til å initialisere verdiene i matrisen. Det er tre valg: (1) randomisere, (2) legge til en tilfeldig verdi, og (3) reversere matrisen. Vær oppmerksom på at verdiene er vedvarende, så du kan gjøre ting som å sortere dem først, deretter legge til litt støy og deretter kjøre en annen sorterings- eller søkeralgoritme.

Velg en søke- eller sorteringsalgoritme fra de andre knappene. Foreløpig er det ingen tilbakemelding når du gjør dette valget (noe for fremtidig arbeid). Trykk deretter på "play" -knappen.

Knappen styrer hastigheten. Du kan også trykke "play" for å sette algoritmen på pause og sette den på pause.

Den stopper automatisk når den er ferdig. Du kan også trykke på en annen algoritmeknapp når som helst. Maskinen vil stoppe den nåværende algoritmen og initialisere den nye, men beholde dataene nøyaktig slik den forrige algoritmen forlot den.

Storpris i STEM -konkurransen