Algoritemski stroj: 13 korakov (s slikami)

2024 Avtor: John Day | [email protected]. Nazadnje spremenjeno: 2024-01-30 12:03

Računalništvo na ravni fakultete poučujem že 15 let, in čeprav je moje znanje bolj na strani programiranja, še vedno porabim kar nekaj časa za pokrivanje standardnih algoritmov za iskanje in razvrščanje. Z vidika poučevanja je osrednje vprašanje računalniška zapletenost: koliko časa potrebuje vsak algoritem glede na vnos določene velikosti? Vendar obstajajo številne nianse. Ali imajo na primer algoritmi različne čase delovanja, odvisno od posebnih vhodnih vrednosti (v nasprotju z velikostjo)? V katerih primerih bi izbrali en algoritem razvrščanja pred drugim? Čeprav o teh vprašanjih razpravljamo abstraktno, me je vedno motilo, da ni bilo mogoče enostavno videti, kako različni algoritmi delujejo v različnih pogojih.

Cilji

Moj splošni cilj tega projekta je bil ustvariti interaktivni zaslon za študente za vizualizacijo in raziskovanje algoritmov. Omejil sem se na algoritme, ki delujejo na nizih vrednosti (cela števila), zato lahko za prikaz vsebine matrike uporabim naslovljiv RGB LED trak. Niz ima 100 elementov in vsako celo število je preslikano v barvo v mavričnem vrstnem redu, tako da je takoj razvidno, kdaj je matrika razvrščena, delno razvrščena ali naključno izbrana. Poleg vrednosti pa sem želel način vizualizacije nadzornih vidikov algoritma - na primer, katere elemente matrike trenutno primerjamo ali zamenjamo.

Posebni cilji so:

- Zagotovite različne algoritme iskanja in razvrščanja

- Vizualizirajte vrednosti v matriki na način, ki poudarja napredek algoritma

- Vizualizirajte upravljanje algoritmov; zlasti upoštevane elemente.

- Uporabnikom dovolite, da izberejo vzorce vhodnih podatkov, namesto da vedno generirajo naključne vrednosti

- Uporabnikom omogočite nadzor hitrosti in zaustavite algoritem

-Dovoli uporabnikom, da vsiljujejo najboljše, najslabše in povprečno vedenje (specifično za algoritem)

- Pokažite število korakov, ko se algoritem nadaljuje

Vizualizacija

Z vidika fizičnega oblikovanja je najbolj zanimiv del tega projekta vizualizacija matrike. Mučil sem se s tem, kako prikazati podatke in nadzor ter kako zgraditi samo prikazovalno napravo. Moj cilj je bil prikazati vrednosti podatkov kot barvne kroge, kontrolne točke pa kot barvne puščice, ki kažejo na vrednosti podatkov. Po nekaj poskusih sem se odločil za zasnovo z dvema vzporednima trakoma 100 RGB LED (WS2812) s krožno masko nad vsako podatkovno LED in trikotno masko nad vsako kontrolno LED. Naredil sem 3D model maske z 10 pari krogov in trikotnikov, nato pa 3D natisnil 10 teh modulov za skupno 100 krogov in 100 trikotnikov. Velikost in razmik moje maske sta zasnovana za trakove s 100 LED na meter. Datoteke 3D -modelov so navedene v nadaljevanju tega opisa.

Elektronika in ohišje

Preostali del naprave je z vidika elektronike preprost. Poleg dveh LED trakov je še kup trenutnih gumbov, vrtljivi dajalnik (za nadzor hitrosti) in 7-segmentni zaslon (za prikaz korakov). S toliko gumbi in kontrolami sem se odločil za uporabo mikrokrmilnika ESP32, ker izpostavlja veliko zatičev in ker je precej močan. Preučil bom strategijo ožičenja, vendar je precej osnovna. Če želite uporabiti manj zatičev, bi verjetno lahko naredili kaj pametnega s premičnimi registri.

Ohišje za to napravo lahko zgradite v različnih oblikah. Sprva sem si ga predstavljal kot veliko pravokotno ploščo z LED trakom na vrhu in mrežo gumbov na sredini. Oblika, s katero sem končal, je navdihnjena z nekakšnim pogledom na tehnologijo vesoljske dobe iz leta 1960. Lahko ga zgradite tudi z LED trakovi v navpični usmeritvi. Ali pa LED del naredite veliko večje - napolnite celotno steno - z ločeno nadzorno ploščo.

Programska oprema

Koda za to napravo je prosto dostopna na GitHubu in potrudil sem se, da dokumentiram, kako deluje in kako jo konfiguriram. Edina zunanja knjižnica, ki jo potrebujete, je FastLED za pogon trakov WS2812.

Zaloge

Elektronika

1 razvojna plošča ESP32 (npr.

2 LED trakovi WS2812 ali podobni, gostota 100 LED na meter (npr.

1 Trikotni gumb "start" (npr.

12 trenutnih gumbov (npr. Https://amzn.com/B01N4D4750) - različne oblike, če želite

1 Paket (20) vnaprej priključenih gumbnih priključkov (npr.

1 Pakirajte priključke JST (npr.

1 Rotacijski dajalnik (npr.

1 Ročaj za rotacijski dajalnik (npr.

1 Pakirajte priključke Dupont (npr. Https://amzn.com/B014YTPFT8) - vredno je dobiti tudi orodje za stiskanje.

1 Cevni priključek (za napajanje) (npr.

1 TM1637 7-segmentni številski zaslon (npr.

Spajkanje in ožičenje

Datoteke 3D modelov

3D model za par modulov z 10 svetlobami najdete na Thingiverse:

www.thingiverse.com/thing:4178181

Ta model boste morali natisniti petkrat za skupno 10 modulov.

Programska oprema

github.com/samguyer/AlgorithmMachine

Ohišje

Vijaki in vijaki iz lesa, pleksi stekla, nerjavečega jekla

Difuzijski material. Najljubši mi je Lee Filters #216, ki je popolnoma bel, vendar obstajajo še druge možnosti. Tudi navaden bel papir dobro opravi svoje delo.

1. korak: Algoritmi 101

Veliko ljudi misli, da je računalništvo v bistvu študij programiranja. Toda resnično srce in duša tega področja so algoritmi: preučevanje sistematičnih postopkov za reševanje problemov in njihovih stroškov (običajno, kako dolgo trajajo). Seminarji na tem področju, kot so Alan Turing, Alonzo Church in Edsger Dijkstra, so razmišljali o teh idejah, še preden so računalniki, kot jih poznamo, sploh obstajali.

Ključna značilnost algoritma za reševanje določene težave je, da je podroben in natančen, tako da ga lahko nekdo uporabi za rešitev, ne da bi sploh razumel, kako deluje; samo sledite korakom na mehanski način in dobili boste pravi odgovor. Vidite, kako to pomaga pri programiranju računalnikov, saj potrebujejo to raven podrobnosti. Računalnik ne more zapolniti manjkajočih podrobnosti ali presojati tako, kot to zmore oseba.

Kako dolgo bo to trajalo?

Ko imamo podroben postopek, je naravno vprašanje, koliko časa bo trajalo, da dobimo odgovor? Navadnih časovnih enot ne moremo uporabiti, saj je odvisno od tega, kdo opravlja delo (primerjajte, kako hitro bi lahko nekdo izračunal v primerjavi s superračunalnikom). Poleg tega je odvisno od tega, koliko podatkov imamo. Jasno je, da iskanje po seznamu milijonov telefonskih številk traja dlje kot po seznamu sto.

Za opis stroškov algoritma najprej izberemo neko operacijo v postopku, ki predstavlja en "korak" - običajno nekaj preprostega, na primer primerjavo ali dodajanje dveh števil, za kar je potreben določen čas. Nato pridemo do formule, ki opisuje, koliko korakov bo algoritem naredil glede na določeno število podatkovnih postavk. Zaradi zgodovinskih razlogov skoraj vedno označujemo število podatkovnih postavk z veliko začetnico N.

Če na primer pregledate seznam N telefonskih številk, je potrebnih N korakov. Dvakratni pregled seznama zahteva 2N korakov. Oba se imenujeta linearni časovni algoritmi - skupno število korakov je nekajkratnik velikosti vnosa. Drugi algoritmi so kvadratni (N na kvadratni čas) ali kubični (N kockasti) ali logaritemski (log N) ali njihova kombinacija. Nekateri najtežji računski problemi zahtevajo eksponentne časovne algoritme (2^N).

V redu, kaj pa?

Ko je število podatkovnih podatkov N majhno, to ni pomembno. Na primer, za N = 10 je 10N to ime kot N na kvadrat. Kaj pa N = 1000? ali N = 1000000? Milijon na kvadrat je precej velika številka. Tudi pri zelo hitrem računalniku lahko kvadratni algoritem traja dolgo, če je vnos dovolj velik. Eksponentni algoritmi so veliko bolj moteči: za N = 50 bi eksponencialni algoritem potreboval dva tedna, da se dokonča tudi v računalniku, kjer je vsak korak le ena nanosekunda (1 milijarditi del sekunde). Joj!

Na drugem koncu lestvice imamo logaritmične časovne algoritme, ki so zelo hitri. Čas dnevnika je nasproten eksponentnemu času: glede na velikost vnosa N je število korakov eksponent T v formuli 2^T = N. Na primer, če je naša vnosna milijarda milijarda, potem algoritem časovnega dnevnika zahteva le 30 korakov, saj je 2^30 = 1, 000, 000, 000. Kako sladko je to?! ??!

Morda se sprašujete, koga brigajo velikosti vnosov v milijonih ali milijardah? Pomislite: koliko uporabnikov je na Facebooku? Koliko spletnih strani indeksira Google? Koliko baznih parov je v človeškem genomu? Koliko meritev gre za simulacijo vremena?

2. korak: Algoritmi

Algoritemski stroj trenutno izvaja naslednje algoritme. Dva od njih sta iskalna algoritma (na seznamu poiščite določeno vrednost), preostala sta algoritma za razvrščanje (vrednosti uredite).

Linearno iskanje

Iščite po seznamu vrednosti eno za drugo od začetka. Zahteva linearni čas.

Binarno iskanje

Poiščite seznam tako, da ga večkrat razdelite na polovico. Zahteva čas dnevnika, vendar mora biti seznam razvrščen, da lahko deluje.

Razvrstitev mehurčkov

Razvrstite seznam, pri katerem večkrat zamenjate sosednje elemente, ki niso v redu. Zahteva kvadratni čas.

Razvrstitev vstavljanja

Seznam razvrstite tako, da vsak element postavite na ustrezno mesto na seznamu že razvrščenih vrednosti. Zahteva kvadratni čas.

Quicksort

Razvrstite seznam tako, da ga večkrat razdelite na polovico in vse vrednosti, manjše od mediane, premaknete v prvo polovico, vse vrednosti, ki so večje od mediane, pa v drugo polovico. V praksi mediane ne moremo učinkovito najti, zato vrednost izberemo naključno. Posledično je lahko ta algoritem v najslabšem primeru kvadraten, vendar običajno zahteva čas N * logN.

Združi razvrščanje

Seznam razvrstite tako, da ga razdelite na polovico, ločite dve polovici ločeno (z razvrščanjem po združevanju) in jih nato združite s prepletanjem vrednosti. Vedno zahteva čas N * logN.

Razvrsti kup

Seznam razvrstite tako, da zgradite podatkovno strukturo, imenovano kup, ki vam omogoča, da poiščete najmanjšo vrednost v času dnevnika. Vedno zahteva čas N * logN.

Bitonic sort

Podobno kot pri združevanju in hitrem razvrščanju razdelite seznam na pol, razvrstite polovice in jih znova združite. Ta algoritem zahteva čas N * logN * logN, vendar ima to prednost, da ga je enostavno vzporediti.

3. korak: LED vrstica: 3D natisnite masko

Prvi korak pri izdelavi LED palice je 3D tiskanje maske, ki daje luči obliko. Vsak modul zajema deset elementov matrike, 10 vrednosti (krogi) in 10 kazalnikov (trikotniki), zato boste skupaj potrebovali 10 modulov. Datoteka STL, ki jo predstavljam, vsebuje dva primerka modula, zato boste morali opraviti pet ciklov tiskanja. Nimam najboljšega 3D tiskalnika, zato sem jih moral ročno očistiti z datoteko in brusnim papirjem. Najpomembnejše je, da so krožne in trikotne luknje čiste.

Na fotografijah boste videli mojo testno nastavitev: LED trakove sem prilepila navzdol in jih z mikrokrmilnikom priklopila na ploščo. Ta korak ni nujen, vendar sem želel videti, kako bo videti, preden začnem sestavljati ohišje. Module maske sem postavil na dva LED traku in položil preprosto skico z naključnimi barvami. S trakom razpršenega materiala oblike in barve resnično poparijo.

Korak: Alternative LED bar

Ko sem prvič začel s tem projektom, sem eksperimentiral z drugimi načini izdelave LED maske. Če nimate 3D tiskalnika, razmislite o eni od teh možnosti. Iskreno povedano: izdelava teh delov je velika bolečina.

Za kroge sem kupil medeninasto cev 13/32, ki ima premer skoraj natančno 1 cm. Narezala sem ga na sto segmentov po 1 cm in jih nato pobarvala z belo barvo.

Za trikotnike sem uporabil težko aluminijasto folijo, izrezano iz pekača za enkratno uporabo. Iz lesa sem naredil trikotno obliko, nato sem okoli oblike zavil kratke trakove folije in jih lepil. Spet boste potrebovali sto teh stvari, zato boste potrebovali nekaj časa in potrpljenja.

5. korak: Ohišje LED palice

Moje ohišje je dokaj preprosto: dva lesena traka za stranice in dva traka iz pleksi stekla za zgornji in spodnji del. Vsi deli so dolgi približno 102 cm (1 meter za LED diode in nekaj dodatnega za namestitev ožičenja). Strani naj bodo nekoliko višje od 1 cm, da se naredi prostor za LED trakove. Po rezanju trakov sem med njimi stisnil koščke 3D natisnjene maske, da izmerim širino pleksi stekla. Izrežite dva kosa pleksi stekla po širini in dolžini palice. Na koncu izrežite trak difuzijskega materiala, da se prilega maski.

Za difuzijo so mi všeč Lee filtri #216 (polna bela difuzija). To je tanka plastična folija, ki daje enakomerno razpršitev brez izgube veliko svetlobe. Ampak to so drage stvari. Včasih lahko na spletu prodate manjše liste, vendar vam bo cel zvitek povrnil približno 125 USD. Nekatere druge možnosti so bel papir ali katera koli druga vrsta satena ali matirane plastike. Priljubljena izbira so tanke plastične rezalne preproge.

Preden sestavite LED palico, se prepričajte, da imate ustrezne priključke, spajkane na LED trakove. Veliko trakov je opremljenih z vnaprej spajkanimi vodi, zato jih lahko preprosto uporabite.

Montažo sem začel tako, da sem zgornji kos pleksi stekla privil na lesene stranice (glej fotografijo). Nato sem ga obrnil in vstavil difuzijski trak, nato pa še 10 kosov maske. Ko sem bil zadovoljen z razmikom, sem jih pritrdil z nekaj pikami vročega lepila.

Nato dva LED traka položite drug na drugega na maske. Prepričajte se, da so LED diode obrnjene navzdol in da se vsaka LED poravna z ustrezno luknjo v maski. Dodajte nekaj vročega lepila ali traku, da LED trakove pritrdite na svoje mesto. Na koncu privijte zadnji del pleksi stekla.

Zaženite preskusni vzorec. Dobro opravljeno! Naredil si najtežji del!

6. korak: Nadzorna plošča

Nadzorna plošča je tisti del, ki ponuja največ ustvarjalne svobode. Vse skupaj mora držati vse kontrole in elektroniko skupaj z LED palico. Najenostavnejša oblika so pravokotne plošče: izvrtajte luknje za gumbe in kontrole ter pritrdite LED palico. Rad kombiniram les, pleksi steklo in druge materiale, da dobim nekakšen steampunk / retro-sodoben videz. V tem primeru sem odrezal kos trpežnega pleksi stekla za držanje gumbov za izbiro glavnega algoritma in leseno palico za preostanek elektronike. Izvrtal sem luknje, ki ustrezajo velikosti arkadnih gumbov. Ožičenje se kaže na zadnji strani, vendar mi je všeč!

Izkopal sem tudi prostor za 7-segmentni zaslon, vrtljivi dajalnik in nekaj ožičenja na zadnji strani. Na vrhu sem izrezal dado, da drži LED palico.

Korak 7: Gumbni pas

Ožičenje veliko gumbov je lahko prava bolečina. Na srečo so ljudje, ki izdelujejo arkadne stroje, pripravili nekaj standardnih priključkov, ki jih lahko uporabite. Vsak priključni kabel gumbov ima dve žici, eno za VCC in eno za ozemljitev. Na enem koncu so priključki za lopate, ki se prilegajo vodi na hrbtni strani gumba - pritrdite ozemljitev na "normalno odprt" kabel, VCC pa na "skupni" kabel. V tej konfiguraciji, ko uporabnik pritisne gumb, se vezje zaključi in mikrokrmilnik bo prebral HIGH na ustreznem vhodnem zatiču.

Na drugem koncu kabla je priključek JST (majhna bela stvar). Pri teh konektorjih je lepo, da gredo v vtičnico samo na en način, zato ni možnosti, da bi VCC in maso pomotoma obrnili.

Kar sem naredil, sem zgradil majhen pas za te priključke. Spajal sem vrsto posod JST na kos protobora, nato pa napeljal žice nazaj do priključkov Dupont, ki jih bom priključil v mikrokrmilnik. Rdeča žica je linija VCC in je povezana z vsemi posodami JST. Modre žice so tiste, ki so ločene za vsak gumb.

8. korak: rotacijski dajalnik

Rotacijski dajalnik uporabniku omogoča nadzor hitrosti algoritma. Uporabljam modul, ki prihaja kot odklopna plošča, ki vključuje vlečne upore za dve podatkovni liniji (rumene žice). Ta je tudi gumb, vendar te funkcije ne uporabljam. Drugi dve žici sta VCC in ozemljeni. Dobil sem tudi lep debel gumb.

Pri rotacijskem kodirniku mi je v nasprotju s potenciometrom všeč, da samo signalizira vrtenje (v smeri urinega kazalca v nasprotni smeri urinega kazalca) mikrokrmilniku, zato je enostavno spremeniti način razlage vrednosti. Na primer, lahko mu daš občutek pospeška (kot miška), ko ga uporabnik hitro vrti.

9. korak: 7-segmentni zaslon

Tukaj ni veliko za povedati. Te stvari so povsod. LED diode krmili čip TM1637, ki komunicira z mikrokrmilnikom po preprostem serijskem protokolu. Uporabljam obstoječo knjižnico, ki mi pove, katero številko želim prikazati, in naredi ostalo.

Na zadnji strani so štirje zatiči: VCC, ozemljitev in dve žici za serijski protokol. Spajkal sem 4-pinski kos glave, ki se poveže z ustreznim priključkom Dupont, povezanim z mikrokrmilnikom.

10. korak: Glavni nadzorni odbor

Na glavni krmilni plošči je sam mikrokrmilnik in vsi priključki za krmiljenje (gumbi, zaslon, LED). Mikrokrmilnik je ESP32, ki zagotavlja veliko računalniške moči in pomnilnika ter izpostavlja veliko zatičev. Ožičenje je precej standardno, vendar bom izpostavil nekaj zanimivih delov.

OPOMBA: Preden začnete ožičenje glavne plošče, si oglejte kodo (https://github.com/samguyer/AlgorithmMachine), tako da se vaša konfiguracija pin ujema z mojo.

Za napajanje sem na ploščo spajkal cevni vtič in dve močni bakreni žici priključil na napajalne in ozemljene tirnice plošče. Razlog je v tem, da lahko LED -črtica porabi veliko energije, če je svetlost nastavljena visoko, in ne želim povleči vse te moči skozi priključek USB na mikrokrmilniku.

Za poenostavitev ožičenja gumbov sem po celotni strani mikrokrmilnika (zgornja stran plošče, kot je prikazano) spajkal trak pravokotne glave moški-ženska. Priključki Dupont iz kabelskega snopa se vtaknejo neposredno v to glavo.

POMEMBNO: Napajanje gumbov (rdeča žica) mora biti priključeno na napajalni vod 3,3 V na mikrokrmilniku. ESP32 je 3.3V čip, zato je treba na podatkovne zatiče priključiti le 3.3V vire.

Mikrokrmilnik črpa moč (ali potiska moč) na tirnice (spodnja stran plošče, kot je prikazano) skozi 5V USB -pin in maso. Vse druge rdeče/črne žice so VCC in ozemljene.

Dve modri žici sta podatkovni liniji za LED trakove (WS2812s). Rumeno/zeleni par sta podatkovni vrstici za rotacijski dajalnik, rumeni par pa serijska povezava s 7-segmentnim zaslonom.

11. korak: Montaža

Ta serija fotografij prikazuje končno montažo in ožičenje. Na hrbtno stran na vrhu sem pritrdil tudi glavno krmilno ploščo.

Pred vklopom sem naredil nekaj pregledov, da bi se izognil neprijetnim presenečenjem. Zlasti zato, da se prepričam, da nimam priključkov za napajanje/ozemljitev nazaj in da nimam kratkega stika. Multimeter nastavite tako, da preizkusi neprekinjenost - oglasil se bo zvočni signal, ko je med dvema vodiloma električna pot. Na gumbe pritrdite en vod na skupno linijo VCC. Nato pritrdite drugi kabel na vsak zatič pasu enega za drugim. Multimeter mora piskati le, ko pritisnete gumb. Če zaslišite kakšen drug pisk, to pomeni, da imate preobrat ali kratek čas. Zasledite ga in popravite, preden vklopite napajanje!

12. korak: Koda

Najprej odprite svoj Arduino IDE in se prepričajte, da imate nameščeno knjižnico FastLED.

Prenesite strojno kodo algoritma z GitHub -a:

github.com/samguyer/AlgorithmMachine.git

Lahko ga klonirate neposredno v mapo Arduino ali pa ga ročno kopirate.

Preden ga naložite, se prepričajte, da nastavitve pin ustrezajo konfiguraciji strojne opreme. Vse nastavitve pin sem postavil na vrh datoteke.

Naložite in uživajte!

13. korak: Kako uporabljati

Algoritemski stroj je enostaven za uporabo in skoraj vsaka kombinacija gumbov je v redu!

Najprej uporabite podatkovne gumbe za inicializacijo vrednosti v matriki. Obstajajo tri izbire: (1) naključno, (2) dodajte eno naključno vrednost in (3) obrnite matriko. Upoštevajte, da so vrednosti obstojne, zato jih lahko najprej razvrstite, nato dodate nekaj hrupa in nato zaženete drug algoritem za razvrščanje ali iskanje.

Izberite drug algoritem iskanja ali razvrščanja med drugimi gumbi. Pri tej izbiri trenutno ni povratnih informacij (nekaj za prihodnje delo). Nato pritisnite gumb "predvajaj".

Gumb nadzoruje hitrost. Lahko tudi pritisnete »predvajaj«, da zaustavite in prekličete algoritem.

Ko se konča, se bo samodejno ustavil. Kadar koli lahko pritisnete tudi drug gumb algoritma. Naprava bo ustavila trenutni algoritem in inicializirala novega, podatke pa ohranila točno tako, kot jih je pustil prejšnji algoritem.

Velika nagrada na tekmovanju STEM