Stroj za algoritam: 13 koraka (sa slikama)

2024 Autor: John Day | [email protected]. Zadnja promjena: 2024-01-30 09:34

Predajem informatiku na fakultetu 15 godina, i iako je moja stručnost više na strani programiranja, i dalje provodim dosta vremena pokrivajući standardne algoritme za pretraživanje i razvrstavanje. S nastavnog stajališta središnje je pitanje računalna složenost: koliko vremena zahtijeva svaki algoritam, s obzirom na unos određene veličine? No, postoje brojne nijanse. Na primjer, imaju li algoritmi različito vrijeme izvođenja ovisno o specifičnim ulaznim vrijednostima (za razliku od veličine)? U kojim slučajevima biste odabrali jedan algoritam sortiranja umjesto drugog? Iako apstraktno raspravljamo o tim pitanjima, uvijek me mučilo da ne postoji jednostavan način da se vidi kako različiti algoritmi rade pod različitim uvjetima.

Ciljevi

Moj glavni cilj ovog projekta bio je stvoriti interaktivni zaslon za studente koji će vizualizirati i istraživati algoritme. Ograničio sam se na algoritme koji rade na nizovima vrijednosti (cijeli brojevi), pa mogu upotrijebiti adresabilnu RGB LED traku za vizualizaciju sadržaja niza. Niz ima 100 elemenata, a svaki cijeli broj je preslikan u boju prema duginom redoslijedu, tako da je odmah očito kada je niz sortiran, djelomično sortiran ili nasumičan. Međutim, osim vrijednosti, želio sam način vizualizacije kontrolnih aspekata algoritma - na primjer, koji se elementi niza trenutno uspoređuju ili zamjenjuju.

Konkretni ciljevi su:

- Omogućite različite algoritme pretraživanja i sortiranja

- Vizualizirajte vrijednosti u nizu na način koji ističe napredak algoritma

- Vizualizirati upravljanje algoritmom; osobito elementi koji se razmatraju.

- Dopustite korisnicima da odaberu uzorke ulaznih podataka, a ne uvijek generiraju slučajne vrijednosti

- Dopustite korisnicima kontrolu brzine i pauziranje algoritma

-Dopustite korisnicima da nametnu ponašanje u najboljem slučaju, u najgorem slučaju, u prosjeku (specifično za algoritam)

- Pokažite broj koraka kako algoritam napreduje

Vizualizacija

Sa stajališta fizičkog dizajna, najzanimljiviji dio ovog projekta je vizualizacija niza. Mučio sam se s tim kako prikazati podatke i kontrolu te kako izgraditi sam uređaj za prikaz. Moj cilj je bio prikazati vrijednosti podataka kao obojene krugove, a kontrolne točke kao strelice u boji koje upućuju na vrijednosti podataka. Nakon nekog eksperimentiranja odlučio sam se za dizajn s dvije paralelne trake od 100 RGB LED dioda (WS2812) s kružnom maskom iznad svake LED sa podacima i trokutastom maskom iznad svake LED diode. Napravio sam 3D model maske s 10 parova krugova i trokuta, a zatim 3D ispisao 10 ovih modula za ukupno 100 krugova i 100 trokuta. Veličina i razmak moje maske dizajniran je za trake sa 100 LED dioda po metru. Datoteke 3D modela nalaze se kasnije u ovom opisu.

Elektronika i kućište

Ostatak uređaja je jednostavan, sa stajališta elektronike. Osim dvije LED trake, postoji hrpa trenutačnih tipki, rotacijski davač (za kontrolu brzine) i 7-segmentni zaslon (za prikaz koraka). S toliko gumba i kontrola odlučio sam se za korištenje ESP32 mikrokontrolera jer izlaže mnogo pinova i jer je prilično moćan. Preći ću na strategiju ožičenja, ali ona je prilično osnovna. Vjerojatno biste mogli učiniti nešto pametno s registrima pomaka ako želite koristiti manje pinova.

Kućište za ovaj uređaj možete izgraditi u mnogo različitih oblika. U početku sam ga zamišljao kao veliku pravokutnu ploču s LED trakom na vrhu i rešetkom gumba u sredini. Oblik s kojim sam završio inspiriran je svojevrsnim pogledom na tehnologiju svemirskog doba iz 1960-ih. Također ga možete izgraditi s LED trakama u okomitom položaju. Ili LED dio uvećajte - ispunite cijeli zid - zasebnom upravljačkom pločom.

Softver

Kôd za ovaj uređaj je slobodno dostupan na GitHubu, a ja sam se potrudio dokumentirati kako radi i kako ga konfigurirati. Jedina vanjska biblioteka koja vam je potrebna je FastLED za pogon WS2812 traka.

Pribor

Elektronika

1 razvojna ploča ESP32 (npr.

2 LED trake WS2812 ili slične, gustoće 100 LED dioda po metru (npr.

1 Trokutasta tipka "start" (npr.

12 trenutačnih gumba (npr. Https://amzn.com/B01N4D4750) - različiti oblici ako želite

1 Paket (20) prethodno spojenih konektora s gumbima (npr.

1 Pakirajte JST konektore (npr.

1 Rotacijski koder (npr.

1 Ručica za rotacijski davač (npr.

1 Pakirajte Dupont konektore (npr. Https://amzn.com/B014YTPFT8) - vrijedi nabaviti i alat za presovanje.

1 Bačvasta utičnica (za napajanje) (npr.

1 TM1637 7-segmentni numerički zaslon (npr.

Oprema za lemljenje i ožičenje

Datoteke 3D modela

3D model za par modula od 10 svjetla možete pronaći na Thingiverseu:

www.thingiverse.com/thing:4178181

Ovaj ćete model morati ispisati pet puta za ukupno 10 modula.

Softver

github.com/samguyer/AlgorithmMachine

Kućište

Vijci i vijci od drva, pleksiglasa, nehrđajućeg čelika

Difuzijski materijal. Najdraži su mi Lee Filters #216 potpuno bijela difuzija, ali postoje i druge mogućnosti. Čak i običan bijeli papir dobro radi.

Korak 1: Algoritmi 101

Mnogi ljudi misle da je računalna znanost u biti proučavanje programiranja. No pravo srce i duša ovog područja su algoritmi: proučavanje sustavnih postupaka za rješavanje problema i njihove cijene (obično, koliko dugo traju). Uspješne figure na terenu, poput Alana Turinga, Alonza Churcha i Edsgera Dijkstre, razmišljale su o tim idejama prije nego što su računala za koja znamo da su uopće postojala.

Ključna značajka algoritma za rješavanje određenog problema je da je detaljan i precizan, tako da bi ga netko mogao koristiti za dobivanje rješenja bez razumijevanja kako uopće radi; samo slijedite korake na mehanički način i dobit ćete pravi odgovor. Možete vidjeti kako to pomaže pri programiranju računala jer im je potrebna ova razina detalja. Računalo ne može popuniti nedostajuće detalje niti donositi prosudbe, na način na koji to osoba može.

Koliko će to trajati?

Nakon što imamo detaljan postupak, prirodno je pitanje koliko će vremena trebati da se dobije odgovor? Ne možemo koristiti obične jedinice vremena, jer to ovisi o tome tko radi (usporedite koliko je brzo osoba mogla izračunati nešto u odnosu na superračunalo). Osim toga, ovisi o tome koliko podataka imamo. Jasno je da je za pretraživanje popisa od milijun telefonskih brojeva potrebno više vremena nego od stotinu.

Da bismo opisali cijenu algoritma, prvo odaberemo neku operaciju u postupku koja predstavlja jedan "korak" - obično nešto jednostavno, poput usporedbe ili zbrajanja dva broja, za što je potrebno određeno vrijeme. Zatim dolazimo do formule koja opisuje koliko će koraka algoritam poduzeti s obzirom na određeni broj stavki podataka. Iz povijesnih razloga, gotovo uvijek označavamo broj stavki podataka s velikim N.

Na primjer, pregledavanje popisa N telefonskih brojeva poduzima N koraka. Dvaput pregledavajući popis potrebno je 2N koraka. Obojica se nazivaju linearni vremenski algoritmi - ukupan broj koraka je neki višekratnik veličine ulaza. Ostali algoritmi su kvadratni (N na kvadrat vremena) ili kubični (N kockasto) ili logaritamski (log N) ili neka njihova kombinacija. Neki od najtežih računskih problema zahtijevaju eksponencijalne vremenske algoritme (2^N).

U redu, pa što?

Kad je broj stavki podataka N mali, to nije važno. Na primjer, za N = 10, 10N je to ime kao N na kvadrat. Ali što je s N = 1000? ili N = 1000000? Milijun na kvadrat je prilično velik broj. Čak i na vrlo brzom računalu, kvadratni algoritam može potrajati dugo ako je ulaz dovoljno velik. Eksponencijalni algoritmi mnogo su problematičniji: za N = 50 eksponencijalni algoritam bi trebao završiti čak dva tjedna čak i na računalu gdje je svaki korak samo jedna nanosekunda (1 milijarditi dio sekunde). Au!

Na drugom kraju ljestvice imamo logaritamske vremenske algoritme, koji su vrlo brzi. Vrijeme bilježenja suprotno je eksponencijalnom vremenu: s obzirom na veličinu unosa N, broj koraka je eksponent T u formuli 2^T = N. Na primjer, ako je naša veličina unosa milijardu, tada algoritam vremena zapisnika zahtijeva samo 30 koraka, budući da je 2^30 = 1, 000, 000, 000. Kako je to slatko?! ??!

Možda se pitate, koga briga za veličine unosa milijuna ili milijardi? Razmislite: koliko korisnika ima na Facebooku? Koliko web stranica Google indeksira? Koliko parova baza postoji u ljudskom genomu? Koliko mjerenja ide u simulaciju vremena?

Korak 2: Algoritmi

Stroj za algoritme trenutno implementira sljedeće algoritme. Dva od njih su algoritmi pretraživanja (pronađite određenu vrijednost na popisu), ostali su algoritmi za sortiranje (postavite vrijednosti po redu).

Linearno pretraživanje

Pretražujte popis vrijednosti jednu po jednu počevši od početka. Zahtijeva linearno vrijeme.

Binarno pretraživanje

Pretražujte popis ponavljajući ga dijeljenjem na pola. Zahtijeva vrijeme evidencije, ali popis mora biti sortiran kako bi funkcionirao.

Sortiranje mjehurića

Poredajte popis koji neprestano izmjenjuje susjedne elemente koji nisu u redu. Zahtijeva kvadratno vrijeme.

Razvrstavanje umetanja

Sortirajte popis postavljanjem svakog elementa na odgovarajuće mjesto u popisu već sortiranih vrijednosti. Zahtijeva kvadratno vrijeme.

Quicksort

Sortirajte popis tako da ga više puta podijelite na pola i pomaknete sve vrijednosti manje od medijane u prvu polovicu, a sve vrijednosti veće od medijane u drugu polovicu. U praksi ne možemo učinkovito pronaći medijanu, pa vrijednost odabiremo nasumično. Kao rezultat toga, ovaj algoritam može biti kvadratni u najgorem slučaju, ali obično zahtijeva N * logN vrijeme.

Spoji sortiranje

Sortirajte popis tako da ga podijelite na pola, razvrstavajući dvije polovice zasebno (pomoću sortiranja stapanjem), a zatim ih spojite isprepletanjem vrijednosti. Uvijek zahtijeva N * logN vrijeme.

Heap sort

Sortirajte popis izgradnjom strukture podataka koja se naziva hrpa, što vam omogućuje da pronađete najmanju vrijednost u vremenu zapisnika. Uvijek zahtijeva N * logN vrijeme.

Bitonic sort

Slično spajanju i brzom razvrstavanju, podijelite popis na pola, razvrstite polovice i ponovno ih spojite. Ovaj algoritam zahtijeva vrijeme N * logN * logN, ali ima prednost u tome što se lako paralelizira.

Korak 3: LED traka: 3D ispis maske

Prvi korak u izgradnji LED trake je 3D ispis maske koja svjetlima daje oblik. Svaki modul pokriva deset elemenata niza, 10 vrijednosti (kružići) i 10 pokazatelja (trokuti), pa će vam trebati ukupno 10 modula. STL datoteka koju ovdje dajem sadrži dvije instance modula, pa ćete morati obaviti pet ciklusa ispisa. Nemam najbolji 3D pisač pa sam ih morao ručno očistiti pomoću datoteke i brusnog papira. Najvažnije je da su kružne i trokutaste rupe čiste.

Na fotografijama ćete vidjeti moje testno postavljanje: Zalijepio sam dvije LED trake prema dolje i spojio ih na ploču s mikrokontrolerom. Ovaj korak nije nužan, ali htio sam vidjeti kako će to izgledati prije nego što počnem sastavljati kućište. Postavio sam module maski na dvije LED trake i pokrenuo jednostavnu skicu sa nasumičnim bojama. S trakom difuzijskog materijala oblici i boje zaista iskaču.

Korak 4: Alternative LED trakama

Kad sam tek započeo ovaj projekt, eksperimentirao sam s drugim načinima izrade LED maske. Ako nemate 3D pisač, razmislite o jednoj od ovih opcija. Bit ću iskren: izrada ovih dijelova velika je bol.

Za krugove sam kupio mjedenu cijev 13/32, promjera gotovo točno 1 cm. Rezala sam ga na sto dijelova od 1 cm, a zatim ih sprejom obojila u bijelo.

Za trokute sam koristio aluminijsku foliju teške težine izrezanu iz jednokratne posude za pečenje. Napravio sam trokutasti oblik od drveta, zatim omotao kratke trake folije oko obrasca i zalijepio ih trakom. Opet, trebat će vam stotinu ovih stvari pa je potrebno malo vremena i strpljenja.

Korak 5: Kućište LED šipki

Moje kućište je prilično jednostavno: dvije drvene trake za stranice i dvije trake od pleksiglasa za vrh i dno. Svi su dijelovi dugački oko 102 cm (1 metar za LED diode, plus malo više za smještaj ožičenja). Stranice bi trebale biti malo više od 1 cm kako bi se napravilo mjesta za LED trake. Nakon izrezivanja traka, umetnuo sam 3D tiskane dijelove maske između njih kako bih izmjerio širinu pleksiglasa. Izrežite dva komada pleksiglasa po širini i duljini šipke. Na kraju, izrežite traku difuzijskog materijala tako da stane preko maske.

Za difuziju jako volim Lee filtere #216 (potpuno bijela difuzija). To je tanka plastična folija koja daje ravnomjernu difuziju bez gubitka puno svjetla. Ali to je skupa stvar. Ponekad možete pronaći manje listove za prodaju na internetu, ali cijela rola vratit će vam se oko 125 USD. Neke druge mogućnosti su bijeli papir ili bilo koja druga vrsta satena ili matirane plastike. Popularan izbor su tanke plastične prostirke za rezanje.

Prije nego sastavite LED traku, provjerite imate li odgovarajuće konektore lemljene na LED trakama. Mnogo traka dolazi s prethodno lemljenim elektrodama, pa ih možete jednostavno koristiti.

Započeo sam montažu tako što sam gornji komad pleksiglasa pričvrstio na drvene stranice (vidi fotografiju). Zatim sam je okrenuo i stavio difuzijsku traku, a zatim 10 komada maske. Kad sam bio zadovoljan razmakom, pričvrstio sam ih na mjesto s nekoliko točaka vrućeg ljepila.

Zatim položite dvije LED trake jednu do druge na maske. Neka LED diode budu okrenute prema dolje i pobrinite se da se svaka LED poravna s odgovarajućom rupom u masci. Dodajte malo vrućeg ljepila ili trake kako biste LED trake držali na mjestu. Na kraju, pričvrstite stražnji dio pleksiglasa.

Pokrenite testni obrazac. Dobar posao! Napravili ste najteži dio posla!

Korak 6: Upravljačka ploča

Upravljačka ploča dio je koji pruža najveću kreativnu slobodu. Samo treba držati sve kontrole i elektroniku, zajedno s LED trakom. Najjednostavniji dizajn su pravokutne ploče: izbušite rupe za gumbe i kontrole te pričvrstite LED traku. Volim kombinirati drvo, pleksiglas i druge materijale dajući neku vrstu steampunk / retro-modernog izgleda. U ovom slučaju izrezao sam komad teškog pleksiglasa za držanje gumba za odabir glavnog algoritma i drvenu šipku za držanje ostatka elektronike. Izbušio sam rupe koje odgovaraju veličini arkadnih gumba. Ožičenje se vidi na stražnjoj strani, ali sviđa mi se!

Također sam izbušio prostor za 7-segmentni zaslon, rotacijski enkoder i dio ožičenja na stražnjoj strani. Izrezao sam dado na vrhu kako bih držao LED traku.

Korak 7: Pojas za gumbe

Ožičenje velikog broja gumba može biti prava muka. Srećom, ljudi koji proizvode arkadne strojeve smislili su neke standardne priključke koje možete koristiti. Svaki kabel priključne tipke ima dvije žice, jednu za VCC i jednu za uzemljenje. Jedan kraj ima konektore lopatica koji odgovaraju žicama na stražnjoj strani gumba - pričvrstite masu na "normalno otvoreni" vodič, a VCC na "zajednički" kabel. U ovoj konfiguraciji, kada korisnik pritisne gumb, krug se dovršava i mikrokontroler će očitati HIGH na odgovarajućem ulaznom pinu.

Drugi kraj kabela ima JST konektor (mala bijela stvarčica). Ono što je lijepo kod ovih konektora je to što ulaze u utičnicu samo na jedan način, pa ne postoji način da se slučajno obrne VCC i uzemljenje.

Ono što sam učinio je izgraditi mali pojas za ove konektore. Lemio sam niz JST utičnica na komad protobora, a zatim provodio žice natrag do Dupont konektora koje ću priključiti u mikrokontroler. Crvena žica je VCC linija i povezuje se sa svim JST utičnicama. Plave žice su zasebne za svaki gumb.

Korak 8: Rotacijski davač

Rotacijski davač omogućuje korisniku kontrolu brzine algoritma. Koristim modul koji dolazi kao razvodna ploča koja uključuje otpornike za povlačenje za dvije podatkovne linije (žute žice). I ovaj je gumb, ali ne koristim tu značajku. Druge dvije žice su VCC i uzemljene. Također sam dobio lijepu masnu tipku.

Ono što mi se sviđa kod rotacijskog davača, za razliku od potenciometra, je to što samo signalizira rotaciju (u smjeru kazaljke na satu protiv kazaljke na satu) mikrokontroleru, pa je lako promijeniti način na koji se vrijednost tumači. Na primjer, možete mu dati osjećaj ubrzanja (poput miša) kada ga korisnik brzo okreće.

Korak 9: 7-segmentni zaslon

Ovdje nema puno za reći. Ove stvari su posvuda. LED diodama upravlja čip TM1637, koji komunicira s mikrokontrolerom putem jednostavnog serijskog protokola. Koristim postojeću biblioteku koja mi omogućuje da joj kažem koji broj želim prikazati, a ona radi ostalo.

Stražnja strana ima četiri pina: VCC, uzemljenje i dvije žice za serijski protokol. Lemio sam 4-pinski komad zaglavlja koji se spaja na odgovarajući Dupont priključak ožičen na mikrokontroler.

Korak 10: Glavna ploča upravljača

Na glavnoj upravljačkoj ploči nalazi se sam mikrokontroler i svi priključci za kontrole (gumbi, zaslon, LED diode). Mikrokontroler je ESP32, koji pruža mnogo računalne snage i memorije te izlaže obilje pinova. Ožičenje je prilično standardno, ali istaknut ću nekoliko zanimljivih dijelova.

NAPOMENA: Možda ćete htjeti pogledati kôd (https://github.com/samguyer/AlgorithmMachine) prije nego počnete ožičavati glavnu ploču, tako da vaša konfiguracija pinova odgovara mojoj.

Lemio sam bačvastu utičnicu na ploču radi napajanja i spojio dvije goleme bakrene žice na ožičenje i uzemljene tračnice ploče. Razlog je taj što LED traka može privući mnogo energije ako je svjetlina postavljena visoko, a ja ne želim svu tu snagu vući kroz USB priključak na mikrokontroleru.

Da bih pojednostavio ožičenje gumba, lemio sam traku zaglavlja pod pravim kutom muško-žensko niz cijelu stranu mikrokontrolera (gornja strana ploče kao što je prikazano). Dupont priključci s kabelskog svežnja priključuju se izravno u ovo zaglavlje.

VAŽNO: napajanje gumba (crvena žica) mora biti spojeno na naponski vod od 3,3 V na mikrokontroleru. ESP32 je 3.3V čip, pa se samo 3.3V izvori trebaju priključiti na podatkovne pinove.

Mikrokontroler napaja (ili gura snagu) tračnice (donja strana ploče kao što je prikazano) kroz 5V USB pin i masu. Sve ostale crveno/crne žice su VCC i uzemljene.

Dvije plave žice su podatkovne linije za LED trake (WS2812s). Žuti/zeleni par su podatkovne linije za okretni davač, a žuti par su serijska veza sa 7-segmentnim zaslonom.

Korak 11: Montaža

Ova serija fotografija prikazuje konačnu montažu i ožičenje. Također sam pričvrstio glavnu upravljačku ploču sa stražnje strane na vrhu.

Prije nego što sam ga uključio, napravio sam nekoliko provjera kako bih izbjegao neugodna iznenađenja. Konkretno, kako bih bio siguran da nemam konektora za napajanje/uzemljenje unatrag i da nema kratkih spojeva. Postavite svoj multimetar na ispitivanje kontinuiteta - oglasit će se zvučni signal kada postoji električni put između dva vodiča. Spojite jedan vodič na zajedničku VCC liniju s gumbima. Zatim jedan po jedan pričvrstite drugi kabel na svaki zatik pojasa. Multimetar bi trebao zvučati samo kad pritisnete gumb. Ako čujete bilo koji drugi zvučni signal, to znači da imate preokret ili kratki spoj. Pratite ga i popravite prije nego uključite napajanje!

Korak 12: Kôd

Prvo otvorite svoj Arduino IDE i provjerite imate li instaliranu biblioteku FastLED.

Preuzmite strojni kod algoritma s GitHub -a:

github.com/samguyer/AlgorithmMachine.git

Možete ga klonirati izravno u mapu Arduino ili kopirati ručno.

Prije učitavanja provjerite odgovaraju li postavke pin -a vašoj hardverskoj konfiguraciji. Postavio sam sve postavke pribadače pri vrhu datoteke.

Prenesite i uživajte!

Korak 13: Kako se koristi

Stroj za algoritme jednostavan je za upotrebu i gotovo svaka kombinacija tipki je u redu!

Prvo, pomoću podatkovnih gumba inicijalizirajte vrijednosti u nizu. Postoje tri izbora: (1) nasumično, (2) dodajte jednu slučajnu vrijednost i (3) obrnite niz. Imajte na umu da su vrijednosti trajne, pa možete učiniti sljedeće: prvo ih sortirati, zatim dodati malo buke, a zatim pokrenuti drugi algoritam sortiranja ili pretraživanja.

Odaberite algoritam pretraživanja ili razvrstavanja među ostalim gumbima. Trenutno nema povratnih informacija kada napravite ovaj izbor (nešto za budući rad). Zatim pritisnite gumb "play".

Gumb kontrolira brzinu. Također možete pritisnuti "play" za pauziranje i poništavanje algoritma.

Automatski će se zaustaviti kada završi. Također možete pritisnuti drugi gumb algoritma u bilo kojem trenutku. Stroj će zaustaviti trenutni algoritam i inicijalizirati novi, ali zadržati podatke točno onako kako ih je prethodni algoritam ostavio.

Velika nagrada na STEM natjecanju