Algoritmemaskinen: 13 trin (med billeder)

2024 Forfatter: John Day | [email protected]. Sidst ændret: 2024-01-30 08:26

Jeg har undervist i datalogi på college -niveau i 15 år, og selvom min ekspertise er mere på programmeringssiden, bruger jeg stadig ret meget tid på at dække standardalgoritmer til søgning og sortering. Fra et undervisningsmæssigt synspunkt er det centrale problem beregningskompleksitet: hvor meget tid kræver hver algoritme, givet input af en bestemt størrelse? Men der er mange nuancer. Har algoritmerne f.eks. Forskellige driftstider afhængigt af de specifikke inputværdier (i modsætning til størrelsen)? I hvilke tilfælde ville du vælge en sorteringsalgoritme frem for en anden? Selvom vi diskuterer disse emner abstrakt, bugede det mig altid, at der ikke var nogen nem måde at se, hvordan forskellige algoritmer fungerer under forskellige forhold.

Mål

Mit overordnede mål for dette projekt var at skabe et interaktivt display, hvor eleverne kan visualisere og udforske algoritmer. Jeg begrænsede mig til algoritmer, der arbejder på arrays af værdier (heltal), så jeg kan bruge en adresserbar RGB LED -strimmel til at visualisere matrixindholdet. Arrayen har 100 elementer, og hvert helt tal kortlægges til en farve i regnbue rækkefølge, så det umiddelbart er tydeligt, når arrayet er sorteret, delvist sorteret eller randomiseret. Udover værdierne ville jeg dog have en måde at visualisere kontrolaspekter ved algoritmen - f.eks. Hvilke elementer i arrayet der i øjeblikket sammenlignes eller byttes.

De specifikke mål er:

- Tilvejebring en række søge- og sorteringsalgoritmer

- Visualiser værdierne i arrayet på en måde, der fremhæver algoritmens fremskridt

- Visualiser algoritmekontrol; især de elementer, der overvejes.

- Tillad brugere at vælge inputdatamønstre frem for altid at generere tilfældige værdier

- Tillad brugere at kontrollere hastigheden og sætte algoritmen på pause

-Tillad brugere at tvinge bedst case, worst-case, gennemsnitlig case adfærd (algoritmespecifik)

- Vis antallet af trin, efterhånden som algoritmen skrider frem

Visualisering

Fra et fysisk design synspunkt er den mest interessante del af dette projekt visualisering af arrayet. Jeg kæmpede med, hvordan jeg skulle vise data og kontrol, og hvordan jeg skulle bygge selve displayenheden. Mit mål var at vise dataværdierne som farvede cirkler og kontrolpunkterne som farvede pile, der peger på dataværdierne. Efter nogle eksperimenter besluttede jeg mig for et design med to parallelle strimler med 100 RGB LED'er (WS2812) med en cirkulær maske over hver data -LED og en trekantet maske over hver kontrol -LED. Jeg lavede en 3D -model af masken med 10 par cirkler og trekanter, og derefter 3D -printede 10 af disse moduler for i alt 100 cirkler og 100 trekanter. Størrelsen og afstanden på min maske er designet til strimler med 100 lysdioder pr. Meter. 3D -modelfilerne findes senere i denne beskrivelse.

Elektronik og kabinet

Resten af enheden er ligetil set fra et elektronisk synspunkt. Ud over de to LED-strimler er der en masse øjeblikkelige knapper, en roterende encoder (til hastighedskontrol) og et 7-segment display (for at vise trin). Med så mange knapper og kontroller valgte jeg at bruge en ESP32 mikrokontroller, fordi den udsætter mange stifter, og fordi den er temmelig kraftfuld. Jeg vil gå over ledningsstrategien, men det er temmelig grundlæggende. Du kan sandsynligvis gøre noget smart med skiftregistre, hvis du vil bruge færre pins.

Du kan bygge kabinettet til denne enhed i mange forskellige former. Jeg forestillede mig det oprindeligt som et stort rektangulært bord med LED -strimlen på tværs af toppen og et gitter med knapper i midten. Den form, jeg endte med, er inspireret af en slags 1960'ers opfattelse af rumalderteknologi. Du kan også bygge den med LED -strimlerne i lodret retning. Eller gør LED -delen meget større - fyld en hel væg - med et separat kontrolpanel.

Software

Koden til denne enhed er frit tilgængelig på GitHub, og jeg har gjort mit bedste for at dokumentere, hvordan den fungerer, og hvordan den konfigureres. Det eneste eksterne bibliotek, du har brug for, er FastLED til at køre WS2812 -strips.

Forbrugsvarer

Elektronik

1 ESP32 udviklingsplade (f.eks.

2 WS2812 eller lignende LED -strips, densitet 100 LED'er pr. Meter (f.eks.

1 trekant "start" -knap (f.eks.

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

1 pakke (20) knapforbindelser, der er forbundet på forhånd (f.eks.

1 pakke JST -stik (f.eks.

1 Rotary encoder (f.eks.

1 Knap til roterende encoder (f.eks.

1 pakke Dupont -stik (f.eks. Https://amzn.com/B014YTPFT8) - det er også værd at få krympeværktøjet.

1 tønde jack (for strøm) (f.eks.

1 TM1637 7-segment numerisk display (f.eks.

Lodde- og ledningsudstyr

3D -model filer

Du kan finde 3D-modellen til et par 10-lys moduler på Thingiverse:

www.thingiverse.com/thing:4178181

Du skal udskrive denne model fem gange for i alt 10 moduler.

Software

github.com/samguyer/AlgorithmMachine

Kabinet

Træ, plexiglas, bolte og skruer i rustfrit stål

Spredningsmateriale. Min favorit er Lee Filters #216 fuld hvid diffusion, men der er andre muligheder. Selv almindeligt hvidt papir gør et godt stykke arbejde.

Trin 1: Algoritmer 101

Mange mennesker tror, at datalogi i det væsentlige er studiet af programmering. Men det virkelige hjerte og sjæl i dette felt er algoritmer: undersøgelse af systematiske procedurer til løsning af problemer og deres omkostninger (typisk, hvor lang tid de tager). Højtidelige figurer i feltet, som Alan Turing, Alonzo Church og Edsger Dijkstra, tænkte på disse ideer, før computere, som vi kender dem, overhovedet fandtes.

Nøglefunktionen i en algoritme til at løse et bestemt problem er, at det er detaljeret og præcist, så nogen kan bruge det til at få en løsning uden at forstå, hvordan det overhovedet fungerer; bare følg trinene mekanisk, og du får det rigtige svar. Du kan se, hvordan dette hjælper med programmering af computere, da de har brug for dette detaljeringsniveau. En computer kan ikke udfylde manglende detaljer eller foretage domme, som en person kan.

Hvor lang tid vil det tage?

Når vi har en detaljeret procedure, er et naturligt spørgsmål, hvor lang tid det tager at få svaret? Vi kan ikke bruge almindelige tidsenheder, da det afhænger af, hvem der udfører arbejdet (sammenlign hvor hurtigt en person kunne beregne noget versus en supercomputer). Derudover afhænger det af, hvor mange data vi har. Det tager klart længere tid at søge på en liste med en million telefonnumre end en liste med hundrede.

For at beskrive omkostningerne ved en algoritme vælger vi først en handling i proceduren, der repræsenterer et "trin" - normalt noget simpelt, som at sammenligne eller tilføje to tal, der tager en fast tid. Derefter kommer vi med en formel, der beskriver, hvor mange trin algoritmen vil tage givet et vist antal dataelementer. Af historiske årsager betegner vi næsten altid antallet af dataelementer med stort N.

For eksempel tager N trin at kigge gennem en liste over N -telefonnumre. At kigge igennem listen to gange tager 2N trin. Begge disse kaldes lineære tidsalgoritmer - det samlede antal trin er et multiplum af inputstørrelsen. Andre algoritmer er kvadratisk (N i kvadratisk tid) eller kubisk (N i terninger) eller logaritmisk (log N) eller en kombination af disse. Nogle af de vanskeligste beregningsproblemer kræver eksponentielle tidsalgoritmer (2^N).

Okay, hvad så?

Når antallet af dataelementer N er lille, betyder det ikke meget. For eksempel, for N = 10, er 10N det navn som N i firkant. Men hvad med N = 1000? eller N = 1000000? En million i kvadrat er et ret stort tal. Selv på en meget hurtig computer kan en kvadratisk algoritme tage lang tid, hvis input er stort nok. Eksponentielle algoritmer er meget mere besværlige: for N = 50 ville en eksponentiel algoritme tage to uger at afslutte, selv på en computer, hvor hvert trin kun er et nanosekund (1 milliarddel af et sekund). Av!

I den anden ende af skalaen har vi logaritmiske tidsalgoritmer, som er meget hurtige. Logtid er det modsatte af eksponentiel tid: givet inputstørrelse N er antallet af trin eksponenten T i formlen 2^T = N. Hvis vores inputstørrelse for eksempel er en milliard, kræver en logtidsalgoritme kun 30 trin, siden 2^30 = 1, 000, 000, 000. Hvor sødt er det?! ??!

Du undrer dig måske, hvem bekymrer sig om inputstørrelser på millioner eller milliarder? Tænk over det: hvor mange brugere er der på Facebook? Hvor mange websider er indekseret af Google? Hvor mange basepar er der i det menneskelige genom? Hvor mange målinger går ind i en vejrsimulering?

Trin 2: Algoritmerne

Algoritmemaskinen implementerer i øjeblikket følgende algoritmer. To af dem er søge -algoritmer (find en bestemt værdi på listen), resten er sorteringsalgoritmer (sæt værdierne i rækkefølge).

Lineær søgning

Søg gennem listen over værdier en efter en fra begyndelsen. Kræver lineær tid.

Binær søgning

Søg på en liste ved gentagne gange at dele den i to. Kræver logtid, men listen skal sorteres for at den fungerer.

Boblesort

Sorter en liste og gentagne gange udveksler naboelementer, der ikke er i orden. Kræver kvadratisk tid.

Indsætningssort

Sorter en liste ved at placere hvert element på det rigtige sted på listen over allerede sorterede værdier. Kræver kvadratisk tid.

Quicksort

Sorter en liste ved gentagne gange at dele listen i halvdelen og flytte alle værdierne mindre end medianen til første halvdel og alle værdierne større end medianen til anden halvdel. I praksis kan vi ikke effektivt finde medianen, så vi vælger en værdi tilfældigt. Som følge heraf kan denne algoritme i værste fald være kvadratisk, men kræver typisk N * logN -tid.

Flet sorter

Sorter en liste ved at dele den i to, sortere de to halvdele hver for sig (ved hjælp af flettesortering) og derefter flette dem sammen ved at indflette værdierne. Kræver altid N * logN -tid.

Bunke sortering

Sorter en liste ved at opbygge en datastruktur kaldet en bunke, som giver dig mulighed for at finde den mindste værdi i logtid. Kræver altid N * logN -tid.

Bitonisk slags

Ligesom sammenlægningssortering og kvicksort, deler du en liste i to, sorterer halvdelene og rekombinerer dem. Denne algoritme kræver N * logN * logN -tid, men har den fordel, at det er let at parallelisere.

Trin 3: LED -bjælke: 3D -udskriv masken

Det første trin i opbygningen af LED -bjælken er at 3D -udskrive den maske, der giver lysene deres form. Hvert modul dækker ti elementer i arrayet, 10 værdier (cirkler) og 10 indikatorer (trekanter), så du skal bruge 10 moduler i alt. STL -filen, jeg leverer her, indeholder to forekomster af modulet, så du skal udføre fem udskrivningscyklusser. Jeg har ikke den bedste 3D -printer, så jeg var nødt til at foretage en manuel oprydning på dem ved hjælp af en fil og sandpapir. Det vigtigste er, at de cirkulære og trekantede huller er rene.

På billederne kan du se min testopsætning: Jeg tapede de to LED -strimler ned og tilsluttede dem til et brødbræt med en mikrokontroller. Dette trin er ikke nødvendigt, men jeg ville se, hvordan det ville se ud, før jeg begyndte at samle kabinettet. Jeg stillede maskemodulerne op på de to LED -strimler og kørte en simpel skitse med tilfældige farver. Med en stribe af diffusionsmaterialet popper formerne og farverne virkelig.

Trin 4: LED -bjælke -alternativer

Da jeg først startede dette projekt, eksperimenterede jeg med andre måder at lave LED -masken på. Hvis du ikke har en 3D -printer, kan du overveje en af disse muligheder. Jeg vil være ærlig: det er en enorm smerte at lave disse dele.

Til cirklerne købte jeg et 13/32 messingrør, som er næsten nøjagtigt 1 cm i diameter. Jeg skar det i hundrede 1 cm segmenter og sprøjtede dem derefter hvide.

Til trekanterne brugte jeg tung aluminiumsfolie skåret fra en engangspande. Jeg lavede en trekantet form af træ, så viklede korte strimler folie rundt om formen og tapede dem. Igen skal du bruge hundrede af disse ting, så det tager lidt tid og tålmodighed.

Trin 5: LED bar kabinet

Mit kabinet er ret enkelt: to træstrimler til siderne og to strimler af plexiglas til top og bund. Alle delene er cirka 102 cm lange (1 meter til lysdioderne, plus lidt ekstra til at rumme ledningerne). Siderne skal være lidt højere end 1 cm for at give plads til LED -strimlerne. Efter at have skåret strimlerne sandwichede jeg de 3D -trykte maskestykker mellem dem for at måle bredden til plexiglasset. Skær to stykker plexiglas i bredden og længden af stangen. Til sidst skæres en strimmel af diffusionsmaterialet, så det passer over masken.

Til diffusion kan jeg virkelig godt lide Lee Filters #216 (fuld hvid diffusion). Det er et tyndt plastark, der giver jævn diffusion uden at miste meget lys. Men det er dyre ting. Nogle gange kan du finde mindre ark til salg online, men en hel rulle sætter dig tilbage omkring $ 125. Nogle andre muligheder er hvidt papir eller anden form for satin eller frostet plast. Et populært valg er tynde plastskæremåtter.

Inden du samler LED -stangen, skal du sørge for at have de passende stik loddet til LED -strimlerne. En masse strimler leveres med før-loddede elektroder, så du kan bare bruge dem.

Jeg startede samlingen med at skrue det øverste stykke plexiglas på træets sider (se foto). Derefter vendte jeg den om og placerede diffusionsstrimlen i, efterfulgt af de 10 maske stykker. Når jeg var tilfreds med afstanden, fastgjorde jeg dem på plads med et par prikker varm lim.

Læg derefter de to LED -strimler side om side oven på maskerne. Sørg for, at lysdioderne vender nedad, og sørg for, at hver LED er på linje med det tilsvarende hul i masken. Tilføj lidt lim eller tape for at holde LED -strimlerne på plads. Til sidst skrues bagstykket af plexiglas på.

Kør et testmønster. Godt job! Du har gjort den sværeste del!

Trin 6: Kontrolpanel

Kontrolpanelet er den del, der giver den mest kreative frihed. Det skal bare holde alle kontrolelementer og elektronik sammen med LED -stangen. Det enkleste design er et rektangulært bræt: bor huller til knapperne og betjeningselementerne, og fastgør LED -stangen. Jeg kan godt lide at kombinere træ, plexiglas og andre materialer for at give et slags steampunk / retro-moderne look. I dette tilfælde skar jeg et stykke kraftigt plexiglas til at holde de vigtigste algoritmevalgsknapper og en træstang til at holde resten af elektronikken. Jeg borede huller for at matche størrelsen på arkadeknapperne. Ledningerne viser på bagsiden, men jeg kan lide det!

Jeg borede også plads til 7-segment displayet, den roterende encoder og nogle af ledningerne på bagsiden. Jeg skar en dado i toppen for at holde LED -stangen.

Trin 7: Knap sele

Tilslutning af mange knapper kan være en rigtig smerte. Heldigvis er de mennesker, der laver arkademaskiner, kommet med nogle standardstik, som du kan bruge. Hvert knapstikskabel har to ledninger, en til VCC og en til jord. Den ene ende har spade -stik, der passer til ledningerne på bagsiden af knappen - fastgør jorden til den "normalt åbne" ledning og VCC til den "fælles" ledning. I denne konfiguration, når brugeren trykker på knappen, er kredsløbet afsluttet, og mikrokontrolleren læser HØJ på den tilsvarende indgangsstift.

Den anden ende af kablet har et JST -stik (den lille hvide ting). Det gode ved disse stik er, at de kun går ind i beholderen på en måde, så der er ingen måde ved et uheld at vende VCC og jord.

Hvad jeg gjorde er at bygge en lille sele til disse stik. Jeg lodder en række JST -beholdere på et stykke protoboard og kører derefter ledninger tilbage til Dupont -stik, som jeg tilslutter til mikrokontrolleren. Den røde ledning er VCC -linjen, og den forbinder til alle JST -beholdere. De blå ledninger er dem, der er separate for hver knap.

Trin 8: Rotary Encoder

Den roterende encoder lader brugeren styre algoritmens hastighed. Jeg bruger et modul, der kommer som et breakout board, der indeholder pull-up modstande til de to datalinjer (gule ledninger). Denne er tilfældigvis også en knap, men jeg bruger ikke den funktion. De to andre ledninger er VCC og jord. Jeg fik også en fin fed knap.

Det, jeg godt kan lide ved en roterende encoder, i modsætning til et potentiometer, er, at den bare signalerer rotation (med uret mod uret) til mikrokontrolleren, så det er let at ændre, hvordan værdien fortolkes. For eksempel kan du give den en følelse af acceleration (som en mus), når brugeren snurrer hurtigt.

Trin 9: 7-segment display

Ikke meget at sige her. Disse ting er overalt. Lysdioderne styres af en chip kaldet TM1637, som kommunikerer med mikrokontrolleren gennem en simpel seriel protokol. Jeg bruger et eksisterende bibliotek, der lader mig fortælle det, hvilket nummer jeg vil vise, og det gør resten.

Bagsiden har fire ben: VCC, jord og to ledninger til den serielle protokol. Jeg loddet et 4-benet stykke header, som forbinder til et tilsvarende Dupont-stik, der er forbundet til mikrokontrolleren.

Trin 10: Main Controller Board

Hovedkontrolkortet huser selve mikrokontrolleren og alle stik til betjeningselementerne (knapper, display, lysdioder). Mikrocontrolleren er en ESP32, som giver meget computerkraft og hukommelse og udsætter masser af stifter. Ledningerne er temmelig standard, men jeg vil påpege et par interessante bits.

BEMÆRK: Du vil måske se på koden (https://github.com/samguyer/AlgorithmMachine), før du begynder at tilslutte hovedkortet, så din pin -konfiguration matcher min.

Jeg lodde et tøndejord på brættet for at få strøm, og tilsluttede to oksekødede kobbertråde til tavlens strøm- og jordskinner. Årsagen er, at LED -bjælken kan trække meget strøm, hvis lysstyrken er sat højt, og jeg vil ikke trække al den strøm gennem USB -stikket på mikrokontrolleren.

For at forenkle kabelføringerne lodde jeg en stribe mand-til-hun-retvinklet header ned langs hele siden af mikrokontrolleren (oversiden af brættet som vist). Dupont -konnektorerne fra knapsele sættes direkte i denne header.

VIGTIGT: strømmen til knapperne (den røde ledning) skal tilsluttes 3,3V -strømledningen på mikrokontrolleren. ESP32 er en 3.3V -chip, så kun 3.3V -kilder bør nogensinde være knyttet til datastifterne.

Mikrocontrolleren trækker strøm (eller skubber strøm) til skinnerne (undersiden af kortet som vist) gennem 5V USB -stiften og jord. Alle de andre røde/sorte ledninger er VCC og slebet.

De to blå ledninger er datalinjer for LED -strimlerne (WS2812'erne). Det gule/grønne par er datalinjer for den roterende encoder, og det gule par er den serielle forbindelse til 7-segment displayet.

Trin 11: Montering

Denne billedserie viser den sidste samling og ledninger. Jeg fastgjorde også hovedkontrolkortet bag på toppen.

Inden jeg startede den, foretog jeg et par kontroller for at undgå ubehagelige overraskelser. Især for at sikre, at jeg ikke havde nogen strøm-/jordforbindelser bagud og ingen kortslutninger. Indstil dit multimeter til at teste for kontinuitet - det bipper, når der er en elektrisk vej mellem de to ledninger. Sæt en ledning til den fælles VCC -linje på knapperne. Sæt derefter den anden ledning fast på hver pin i selen en efter en. Multimeteret bør kun bippe, når du trykker på knappen. Hvis du får andre bip, betyder det, at du har en vending eller en kort. Spor det og fix det, før du tænder for strømmen!

Trin 12: Kode

Først skal du åbne din Arduino IDE og sikre dig, at du har FastLED -biblioteket installeret.

Download algoritme maskinkoden fra GitHub:

github.com/samguyer/AlgorithmMachine.git

Du kan enten klone det direkte ind i din Arduino -mappe eller kopiere det i hånden.

Inden du uploader den, skal du kontrollere, at pin -indstillingerne matcher din hardwarekonfiguration. Jeg har placeret alle pin -indstillingerne øverst i filen.

Upload og nyd!

Trin 13: Sådan bruges

Algoritmemaskinen er enkel at bruge, og næsten enhver kombination af knapper er ok!

Brug først dataknapperne til at initialisere værdierne i arrayet. Der er tre valgmuligheder: (1) randomiser, (2) tilføj en tilfældig værdi og (3) vend arrayet om. Bemærk, at værdierne er vedvarende, så du kan gøre ting som at sortere dem først, derefter tilføje lidt støj og derefter køre en anden sorterings- eller søge -algoritme.

Vælg en søge- eller sorteringsalgoritme fra de andre knapvalg. I øjeblikket er der ingen feedback, når du træffer dette valg (noget til fremtidigt arbejde). Tryk derefter på knappen "play".

Knappen styrer hastigheden. Du kan også trykke på "play" for at sætte algoritmen på pause og afbryde den.

Det stopper automatisk, når det er gjort. Du kan også når som helst trykke på en anden algoritmeknap. Maskinen stopper den aktuelle algoritme og initialiserer den nye, men beholder dataene nøjagtigt som den forrige algoritme forlod den.

Storpris i STEM -konkurrencen