Mašina za algoritam: 13 koraka (sa slikama)

2024 Autor: John Day | [email protected]. Zadnja izmjena: 2024-01-30 08:05

Predajem informatiku na fakultetu 15 godina, i iako je moja stručnost više vezana za programiranje, i dalje provodim dosta vremena pokrivajući standardne algoritme za pretraživanje i sortiranje. Sa stanovišta nastave, centralno pitanje je računska složenost: koliko vremena treba svakom algoritmu, s obzirom na unos određene veličine? Ali postoje brojne nijanse. Na primjer, da li algoritmi imaju različito vrijeme izvođenja u zavisnosti od specifičnih ulaznih vrijednosti (za razliku od veličine)? U kojim slučajevima biste odabrali jedan algoritam sortiranja umjesto drugog? Iako o ovim pitanjima raspravljamo apstraktno, uvijek me mučilo da ne postoji jednostavan način da se vidi kako različiti algoritmi rade pod različitim uvjetima.

Ciljevi

Moj sveobuhvatni cilj ovog projekta bio je stvoriti interaktivni prikaz 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 mapiran u boju prema duginom redoslijedu, tako da je odmah vidljivo 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 naglašava napredak algoritma

- Vizualizujte upravljanje algoritmom; posebno elementi koji se razmatraju.

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

- Dopustite korisnicima da kontrolišu brzinu i pauziraju algoritam

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

- Prikažite broj koraka kako algoritam napreduje

Vizualizacija

Sa stanoviš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 tačke kao obojene strelice koje pokazuju na vrijednosti podataka. Nakon nekog eksperimentiranja odlučio sam se za dizajn s dvije paralelne trake od 100 RGB LED dioda (WS2812) sa kružnom maskom preko svake LED sa podacima i trokutastom maskom preko svake LED diode. Napravio sam 3D model maske s 10 parova krugova i trokuta, a zatim 3D odštampao 10 ovih modula za ukupno 100 krugova i 100 trokuta. Veličina i razmak moje maske dizajnirani su 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 stanovišta elektronike. Osim dvije LED trake, postoji i gomila trenutačnih tipki, okretni davač (za kontrolu brzine) i 7-segmentni zaslon (za prikaz koraka). S toliko dugmadi 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 sa 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 to zamišljao kao veliku pravokutnu ploču sa LED trakom na vrhu i rešetkom dugmadi u sredini. Forma sa kojom sam završio inspirirana je nekom vrstom pogleda na tehnologiju svemirskog doba iz 1960-ih. Možete ga izgraditi i s LED trakama u okomitom položaju. Ili LED dio uvećajte - ispunite cijeli zid - zasebnom kontrolnom pločom.

Softver

Kod za ovaj uređaj je slobodno dostupan na GitHub -u, 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.

Supplies

Elektronika

1 razvojna ploča ESP32 (npr.

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

1 Trokutno dugme "start" (npr.

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

1 Paket (20) konektora sa dugmadima sa žicom (npr.

1 Pakirajte JST konektore (npr.

1 Rotacijski koder (npr.

1 Dugme za rotacioni davač (npr.

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

1 Utikač za cijev (za napajanje) (npr.

1 TM1637 numerički zaslon sa 7 segmenata (npr.

Oprema za lemljenje i ožičenje

Datoteke 3D modela

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

www.thingiverse.com/thing:4178181

Ovaj model ćete morati odštampati pet puta za ukupno 10 modula.

Softver

github.com/samguyer/AlgorithmMachine

Enclosure

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

Difuzijski materijal. Moj omiljeni je Lee Filters #216 potpuno bijela difuzija, ali postoje i druge opcije. Čak i običan bijeli papir dobro radi.

Korak 1: Algoritmi 101

Mnogi ljudi misle da je informatika u osnovi 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, Alonzo Churcha i Edsgera Dijkstre, razmišljale su o ovim idejama prije nego što su računari kakvi ih poznajemo uopće postojali.

Ključna značajka algoritma za rješavanje određenog problema je da je detaljan i precizan, tako da bi ga neko mogao koristiti za dobivanje rješenja bez razumijevanja kako uopće funkcionira; samo slijedite korake na mehanički način i dobit ćete pravi odgovor. Možete vidjeti kako ovo pomaže u programiranju računara, jer im je potreban ovaj nivo detalja. Računar ne može popuniti nedostajuće detalje niti donositi prosudbe, na način na koji to može osoba.

Koliko će to trajati?

Nakon što imamo detaljnu proceduru, prirodno je pitanje koliko će vremena trebati da se dobije odgovor? Ne možemo koristiti obične jedinice vremena, jer to ovisi o tome ko radi (uporedite koliko je brzo osoba mogla izračunati nešto u odnosu na superračunalo). Osim toga, ovisi o tome koliko podataka imamo. Očigledno je da je potrebno duže da se pretraži lista od milion telefonskih brojeva nego lista 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 koraka će algoritam poduzeti s obzirom na određeni broj stavki podataka. Iz povijesnih razloga, gotovo uvijek označavamo broj stavki podataka velikim početnim slovom N.

Na primjer, pregledavanje liste od N telefonskih brojeva poduzima N koraka. Dvaput pregledavanje liste zahtijeva 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 šta?

Kada je broj stavki podataka N mali, to nije važno. Na primjer, za N = 10, 10N je to ime kao N na kvadrat. Ali šta je sa N = 1000? ili N = 1000000? Milion na kvadrat je prilično veliki broj. Čak i na vrlo brzom računaru, kvadratni algoritam može potrajati dugo ako je ulaz dovoljno velik. Eksponencijalni algoritmi su mnogo problematičniji: za N = 50 eksponencijalnom algoritmu bi trebale dvije sedmice da se završi čak i na računaru gdje je svaki korak samo jedna nanosekunda (1 milijarditi dio sekunde). Ouch!

Na drugom kraju ljestvice imamo logaritamske vremenske algoritme, koji su vrlo brzi. Vrijeme dnevnika je suprotno od eksponencijalnog vremena: 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 miliona 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

Mašina 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 listu vrijednosti jednu po jednu počevši od početka. Zahteva linearno vreme.

Binarno pretraživanje

Pretražujte popis tako što ćete ga uzastopno dijeliti na pola. Zahtijeva vrijeme evidencije, ali lista mora biti sortirana da bi radila.

Sortiranje mjehurića

Sortirajte listu koja neprestano razmjenjuje susjedne elemente koji nisu u redu. Zahtijeva kvadratno vrijeme.

Sortiranje umetanja

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

Quicksort

Sortirajte listu tako što ćete je više puta podijeliti na pola i pomaknuti sve vrijednosti manje od medijane u prvu polovicu, a sve vrijednosti veće od medijane u drugu polovicu. U praksi ne možemo efikasno pronaći medijanu, pa vrijednost biramo 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 listu tako što ćete je podijeliti na pola, razvrstavajući dvije polovine odvojeno (koristeći sortiranje stapanjem), a zatim ih spojivši ispreplićući 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 dnevnika. Uvijek zahtijeva N * logN vrijeme.

Bitonic sort

Slično spajanju i ubrzanom razvrstavanju, podijelite listu na pola, sortirajte polovine i ponovno ih spojite. Ovaj algoritam zahtijeva vrijeme N * logN * logN, ali ima prednost š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 (krugovi) i 10 indikatora (trokuti), tako da ć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 štampač, pa sam morao da ih ručno očistim 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 neophodan, ali htio sam vidjeti kako će to izgledati prije nego što počnem sastavljati kućište. Postavio sam module maske na dvije LED trake i pokrenuo jednostavnu skicu sa nasumičnim bojama. Uz traku 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 štampač, razmislite o jednoj od ovih opcija. Biću iskren: praviti ove dijelove velika je bol.

Za krugove sam kupio mjedenu cijev 13/32, promjera gotovo točno 1 cm. Rezao sam ga na sto segmenata od 1 cm, a zatim sam ih obojio bijelom bojom.

Za trokute sam koristio aluminijsku foliju teške težine izrezanu iz jednokratne posude za pečenje. Napravio sam trokutastu formu od drveta, zatim omotao kratke trake folije oko forme i zalijepio ih trakom. Opet će vam trebati 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 gornju i donju stranu. Svi dijelovi su dugački oko 102 cm (1 metar za LED diode, plus malo dodatnog za ožičenje). Stranice bi trebale biti malo više od 1 cm kako bi se napravilo mjesta za LED trake. Nakon rezanja traka, stisnuo sam 3D štampane komade maske između njih kako bih izmjerio širinu pleksiglasa. Izrežite dva komada pleksiglasa po širini i dužini š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 tanak plastični lim koji daje ravnomjernu difuziju bez gubitka puno svjetla. Ali to je skupa stvar. Ponekad na internetu možete pronaći manje listove za prodaju, ali cijela rola će vam vratiti oko 125 USD. Neke druge opcije 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 šipku, 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 pored 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 da držite LED trake na mjestu. Na kraju, pričvrstite stražnji komad pleksiglasa.

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

Korak 6: Kontrolna tabla

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

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

Korak 7: Pojas za dugmad

Ožičenje velikog broja dugmadi može biti pravi bol. Srećom, ljudi koji proizvode arkadne mašine smislili su neke standardne konektore koje možete koristiti. Svaki kabel konektora tipki 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" vodič. U ovoj konfiguraciji, kada korisnik pritisne dugme, krug se dovršava i mikrokontroler će očitati HIGH na odgovarajućem ulaznom pinu.

Drugi kraj kabla 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, tako da ne postoji način da se slučajno obrne VCC i masa.

Ono što sam učinio je izgradio mali pojas za ove konektore. Lemio sam niz JST utičnica na komad protobora, a zatim vodio žice nazad 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 svako dugme.

Korak 8: Rotacijski koder

Rotacijski koder omogućava korisniku kontrolu brzine algoritma. Koristim modul koji dolazi kao zaštitna ploča koja uključuje otpornike za povlačenje za dvije podatkovne linije (žute žice). Slučajno je i ovo dugme, ali ja ne koristim tu funkciju. Druge dvije žice su VCC i uzemljene. Imam i lijepu debelu ručicu.

Ono što mi se sviđa kod rotacijskog kodera, 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 ekran

Nema tu mnogo šta da se kaže. Ove stvari su svuda. 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 konektor ožičen na mikrokontroler.

Korak 10: Glavna ploča kontrolera

Na glavnoj ploči kontrolera nalazi se sam mikrokontroler i svi priključci za kontrole (dugmad, ekran, LED diode). Mikrokontroler je ESP32, koji pruža mnogo računarske snage i memorije, te izlaže mnogo pinova. Ožičenje je prilično standardno, ali istaknut ću nekoliko zanimljivih detalja.

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 pina 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 letvice 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 povlačiti kroz USB konektor na mikrokontroleru.

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

VAŽNO: Napajanje tipki (crvena žica) mora biti spojeno na naponski vod od 3,3 V na mikrokontroleru. ESP32 je čip od 3,3 V, tako da samo 3,3 V izvore treba priključiti na pinove za podatke.

Mikrokontroler napaja (ili potiskuje napajanje) šine (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 linije podataka za okretni davač, a žuti par su serijska veza sa 7-segmentnim ekranom.

Korak 11: Montaža

Ova serija fotografija prikazuje konačnu montažu i ožičenje. Takođe sam pričvrstio glavnu kontrolnu ploču sa zadnje 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 da testira kontinuitet - oglasit će se zvučnim signalom kada postoji električni put između dva vodiča. Pričvrstite jedan provodnik na zajedničku VCC liniju na dugmad. Zatim jedan po jedan pričvrstite drugi provodnik na svaki zatik pojasa. Multimetar bi trebao piskati samo kada pritisnete dugme. Ako čujete bilo koji drugi zvučni signal, to znači da imate preokret ili kratak spoj. Pronađite ga i popravite prije nego uključite napajanje!

Korak 12: Šifra

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

Preuzmite Algorithm Machine code sa GitHub -a:

github.com/samguyer/AlgorithmMachine.git

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

Prije nego što ga učitate, provjerite odgovaraju li postavke pin -a vašoj hardverskoj konfiguraciji. Postavio sam sve postavke pin -a na vrh datoteke.

Otpremite i uživajte!

Korak 13: Kako se koristi

Algoritamska mašina je jednostavna za upotrebu i gotovo svaka kombinacija dugmadi je u redu!

Prvo, pomoću gumba za podatke 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 dugme "play".

Dugme kontroliše brzinu. Također možete pritisnuti "play" za pauziranje i poništavanje algoritma.

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

Velika nagrada na STEM takmičenju