Algoritmimasin: 13 sammu (piltidega)

2024 Autor: John Day | [email protected]. Viimati modifitseeritud: 2024-01-30 08:47

Olen õpetanud infotehnoloogiat kolledži tasemel 15 aastat ja kuigi minu asjatundlikkus on rohkem programmeerimise poolel, kulutan siiski üsna palju aega otsimis- ja sorteerimisstandardite algoritmide katmiseks. Õpetamise seisukohalt on keskne küsimus arvutuslik keerukus: kui palju aega iga algoritm konkreetse suurusega sisendi puhul nõuab? Kuid on palju nüansse. Näiteks kas algoritmidel on olenevalt konkreetsetest sisendväärtustest erinevad käitusajad (erinevalt suurusest)? Millistel juhtudel valiksite ühe sortimisalgoritmi teise asemel? Kuigi me arutame neid küsimusi abstraktselt, häiris mind alati see, et polnud lihtsat viisi näha, kuidas erinevad algoritmid erinevates tingimustes töötavad.

Eesmärgid

Minu selle projekti üldeesmärk oli luua õpilastele interaktiivne kuvar algoritmide visualiseerimiseks ja uurimiseks. Ma piirdusin algoritmidega, mis töötavad väärtuste massidega (täisarvud), nii et saan massiivi sisu visualiseerimiseks kasutada adresseeritavat RGB LED -riba. Massiivil on 100 elementi ja iga täisarv kaardistatakse vikerkaare järjekorras värviks, nii et massiivi sorteerimisel, osalisel sortimisel või randomiseerimisel on see kohe ilmne. Lisaks väärtustele tahtsin aga võimalust visualiseerida algoritmi juhtimisaspekte - näiteks milliseid massiivi elemente praegu võrreldakse või vahetatakse.

Konkreetsed eesmärgid on järgmised:

- Pakkuge erinevaid otsingu- ja sortimisalgoritme

- Kujutage massiivi väärtusi viisil, mis toob esile algoritmi edenemise

- visualiseerida algoritmi juhtimine; eelkõige kaalutavaid elemente.

- Luba kasutajatel valida sisendandmete mustrid, mitte alati genereerida juhuslikke väärtusi

- Luba kasutajatel kiirust juhtida ja algoritm peatada

-Luba kasutajatel sundida parimate, halvimate ja keskmiste juhtumite käitumist (algoritmipõhine)

- Näidake algoritmi edenedes sammude arvu

Visualiseerimine

Füüsilise disaini seisukohast on selle projekti kõige huvitavam osa massiivi visualiseerimine. Ma nägin vaeva, kuidas andmeid ja juhtimist näidata ning kuvariseadet ise ehitada. Minu eesmärk oli näidata andmeväärtusi värviliste ringidena ja kontrollpunkte värviliste nooltena, mis osutavad andmeväärtustele. Pärast mõningast katsetamist otsustasin disaini, millel oli kaks paralleelset riba 100 RGB LED -iga (WS2812), mille ümmargune mask oli üle iga LED -i ja kolmnurkne mask iga juht -LED -i kohal. Tegin maski 3D -mudeli 10 paari ringide ja kolmnurkadega ning seejärel printisin 3D -st 10 neist moodulitest kokku 100 ringi ja 100 kolmnurga jaoks. Minu maski suurus ja vahekaugus on ette nähtud ribadeks, millel on 100 LED -i meetri kohta. 3D -mudelifailid on toodud selles kirjelduses hiljem.

Elektroonika ja korpus

Ülejäänud seade on elektroonika seisukohast lihtne. Lisaks kahele LED-ribale on hunnik hetkelisi nuppe, pöörlev kodeerija (kiiruse reguleerimiseks) ja 7-segmendiline ekraan (sammude näitamiseks). Nii paljude nuppude ja juhtseadistega otsustasin kasutada ESP32 mikrokontrollerit, kuna see paljastab palju nööpe ja kuna see on üsna võimas. Ma vaatan üle juhtmestiku strateegia, kuid see on üsna lihtne. Tõenäoliselt saaksite vahetusregistritega midagi tarka teha, kui soovite kasutada vähem nööpnõelu.

Saate selle seadme jaoks korpuse ehitada mitmel erineval kujul. Esialgu kujutasin seda ette suure ristkülikukujulise tahvlina, mille ülaosas oli LED -riba ja keskel nuppude võre. Vorm, millega ma lõpuks sattusin, on inspireeritud omamoodi 1960. aastate vaatest kosmoseajastu tehnoloogiale. Saate selle ehitada ka vertikaalselt LED -ribadega. Või tehke LED -osa palju suuremaks - täitke terve sein - eraldi juhtpaneeliga.

Tarkvara

Selle seadme kood on GitHubis vabalt saadaval ja olen andnud endast parima, et dokumenteerida, kuidas see töötab ja kuidas seda konfigureerida. Ainus väline raamatukogu, mida vajate, on FastLED WS2812 ribade juhtimiseks.

Tarvikud

Elektroonika

1 ESP32 arendusplaat (nt

2 WS2812 vms LED -riba, tihedus 100 LED -i meetri kohta (nt

1 kolmnurga käivitusnupp (nt

12 hetkelist nuppu (nt https://amzn.com/B01N4D4750) - soovi korral erinevad kujud

1 komplekt (20) eeljuhtmega nupuliidesed (nt

1 pakk JST -pistikuid (nt

1 pöörlev kodeerija (nt

1 Pöörleva kodeerija nupp (nt

1 Pack Duponti pistikud (nt https://amzn.com/B014YTPFT8) - tasub hankida ka pressimisvahend.

1 tünni pistik (toide) (nt

1 TM1637 7-segmendiline numbrinäidik (nt

Jootmis- ja juhtmestik

3D mudelifailid

3D-mudeli leiate 10-valgusallika mooduli paari jaoks Thingiversest:

www.thingiverse.com/thing:4178181

Seda mudelit peate printima viis korda, kokku 10 moodulit.

Tarkvara

github.com/samguyer/AlgorithmMachine

Korpus

Puit, pleksiklaas, roostevabast terasest poldid ja kruvid

Difusioonmaterjal. Minu lemmik on Lee Filters #216 täisvalge difusioon, kuid on ka teisi võimalusi. Isegi tavaline valge paber teeb head tööd.

1. samm: algoritmid 101

Paljud inimesed arvavad, et informaatika on sisuliselt programmeerimise uurimine. Kuid selle valdkonna tõeline süda ja hing on algoritmid: probleemide lahendamise süstemaatiliste protseduuride ja nende maksumuse (tavaliselt selle kestus) uurimine. Valdkonna peamised tegelased, nagu Alan Turing, Alonzo Church ja Edsger Dijkstra, mõtlesid nendele ideedele enne arvuteid, nagu me neid teame.

Algoritmi põhijooneks konkreetse probleemi lahendamiseks on see, et see on üksikasjalik ja täpne, nii et keegi saaks seda kasutada lahenduse leidmiseks, mõistmata selle toimimist; järgige lihtsalt mehaanilisi samme ja saate õige vastuse. Näete, kuidas see aitab arvutite programmeerimisel, kuna need vajavad sellist detailsust. Arvuti ei saa täita puuduvaid üksikasju ega teha otsuseid, nagu inimene saab.

Kui kaua see aega võtab?

Kui meil on üksikasjalik menetlus, on loomulik küsimus, kui kaua võtab vastuse saamine aega? Me ei saa kasutada tavalisi ajaühikuid, kuna see sõltub sellest, kes seda tööd teeb (võrrelge, kui kiiresti inimene midagi arvutada saab, võrreldes superarvutiga). Lisaks sõltub see sellest, kui palju andmeid meil on. On selge, et miljoni telefoninumbri loendi otsimine võtab kauem aega kui saja numbriga loend.

Algoritmi maksumuse kirjeldamiseks valime esmalt mõne toimingu, mis kujutab endast ühte "sammu" - tavaliselt midagi lihtsat, näiteks kahe numbri võrdlemine või lisamine, mille tegemiseks kulub kindel aeg. Seejärel leiame valemi, mis kirjeldab, kui palju samme algoritm teatud arvu andmeühikute puhul teeb. Ajaloolistel põhjustel tähistame peaaegu alati N -tähega andmeühikute arvu.

Näiteks N -telefoninumbrite loendi vaatamine võtab N sammu. Loendi kaks korda läbi vaatamine võtab 2N sammu. Mõlemaid nimetatakse lineaarseteks ajaalgoritmideks - sammude koguarv on sisendi suuruse mõni kord. Teised algoritmid on ruutmeetriline (aeg ruudus N) või kuup (N kuup) või logaritmiline (log N) või nende kombinatsioon. Mõned kõige raskemad arvutusprobleemid nõuavad eksponentsiaalseid ajaalgoritme (2^N).

OK, mis siis?

Kui andmeüksuste arv N on väike, pole sellel suurt tähtsust. Näiteks kui N = 10, on 10N see nimi N ruudus. Aga kuidas on N = 1000? või N = 1000000? Miljon ruutu on päris suur number. Isegi väga kiirel arvutil võib ruutmeetriline algoritm kaua aega võtta, kui sisend on piisavalt suur. Eksponentsiaalsed algoritmid on palju tülikamad: N = 50 korral kuluks eksponentsiaalse algoritmi valmimiseks kaks nädalat isegi arvutis, kus iga samm on vaid üks nanosekund (1 miljardik sekundit). Oh!

Skaala teises otsas on meil logaritmilised ajaalgoritmid, mis on väga kiired. Logiaeg on eksponentsiaalsele ajale vastupidine: antud sisendisuuruse N korral on sammude arv astendaja T valemis 2^T = N. Näiteks kui meie sisendi suurus on miljard, siis logiaja algoritm nõuab ainult 30 sammu, kuna 2^30 = 1, 000, 000, 000. Kui armas see on?! ??!

Teil võib tekkida küsimus, keda huvitab miljonite või miljardite sisendite suurus? Mõelge sellele: kui palju on Facebookis kasutajaid? Mitu veebilehte Google indekseerib? Mitu aluspaari on inimese genoomis? Mitu mõõtmist läheb ilmastiku simulatsiooniks?

2. samm: algoritmid

Algoritmimasin rakendab praegu järgmisi algoritme. Kaks neist on otsingualgoritmid (leidke loendist konkreetne väärtus), ülejäänud on sortimisalgoritmid (pange väärtused järjekorda).

Lineaarne otsing

Otsige väärtuste loendist ükshaaval, alustades algusest. Nõuab lineaarset aega.

Binaarotsing

Otsige loendist, jagades selle korduvalt pooleks. Nõuab logimisaega, kuid loend peab toimima, et see toimiks.

Mullide sorteerimine

Sorteerige loend korduvalt vahetatavate naaberelementide vahel, mis pole korras. Nõuab ruutmeetrit.

Sisestamise sort

Sorteerige loend, paigutades iga elemendi juba sorteeritud väärtuste loendisse õigesse kohta. Nõuab ruutmeetrit.

Kiire sortimine

Sorteerige loend, jagades loendi korduvalt pooleks ja nihutades kõik väärtused keskmisest väiksemaks esimesele poolele ja kõik väärtused, mis on mediaanist suuremad teisele poole. Praktikas ei suuda me mediaani tõhusalt leida, seega valime väärtuse juhuslikult. Selle tulemusena võib see algoritm halvimal juhul olla ruudukujuline, kuid nõuab tavaliselt N * logN aega.

Ühenda sorteerimine

Sorteerige loend, jagades selle pooleks, sorteerides mõlemad pooled eraldi (kasutades ühendamise sortimist) ja seejärel ühendades need väärtuste põimimisel kokku. Vajab alati N * logN aega.

Hunnik sorteerida

Sorteerige loend, ehitades hunnikuks nimetatava andmestruktuuri, mis võimaldab teil leida logiaja väikseima väärtuse. Vajab alati N * logN aega.

Bitooniline sort

Sarnaselt ühendamise ja kiirvalikuga ühendage loend pooleks, sorteerige pooled ja ühendage need uuesti. See algoritm nõuab aega N * logN * logN, kuid selle eeliseks on lihtne paralleelida.

3. samm: LED -riba: 3D -maski printimine

LED -riba ehitamise esimene samm on tulede kuju andva maski 3D -printimine. Iga moodul hõlmab massiivi kümme elementi, 10 väärtust (ringi) ja 10 indikaatorit (kolmnurka), seega vajate kokku 10 moodulit. Siin pakutav STL -fail sisaldab kahte mooduli eksemplari, nii et peate tegema viis printimistsüklit. Mul pole parimat 3D -printerit, nii et pidin faili ja liivapaberi abil nende käsitsi puhastama. Kõige tähtsam on see, et ümmargused ja kolmnurksed augud oleksid puhtad.

Fotodel näete minu testiseadistust: teipisin kaks LED -riba alla ja ühendasin need mikrokontrolleriga leivalaua külge. See samm pole vajalik, kuid tahtsin enne korpuse kokkupanekut näha, kuidas see välja näeb. Rivistasin kahele LED -ribale maskimoodulid ja joonistasin lihtsa visandi juhuslike värvidega. Hajutusmaterjali riba abil tõusevad vormid ja värvid tõesti esile.

Samm: LED -riba alternatiivid

Selle projekti esmakordsel käivitamisel katsetasin muid LED -maski valmistamise viise. Kui teil pole 3D -printerit, võite kaaluda ühte neist valikutest. Ütlen ausalt: nende osade tegemine on tohutu piin.

Ringide jaoks ostsin 13/32 messingist toru, mille läbimõõt on peaaegu täpselt 1 cm. Lõikasin selle sajaks 1 cm pikkuseks segmendiks ja värvisin seejärel pihustiga valgeks.

Kolmnurkade jaoks kasutasin ühekordselt kasutatavast küpsetuspannist lõigatud rasket alumiiniumfooliumi. Tegin puidust kolmnurkse vormi, seejärel keerasin vormi ümber lühikesed fooliumiribad ja teipisin. Jällegi vajate sada sellist asja, nii et see võtab natuke aega ja kannatlikkust.

Samm: LED -riba korpus

Minu ümbris on üsna lihtne: kaks puitriba külgedele ja kaks pleksiklaasiriba üla- ja alaosale. Kõik osad on umbes 102 cm pikad (1 meeter valgusdioodide jaoks, millele lisandub juhtmestiku lisamiseks veidi lisa). LED -ribade jaoks ruumi tegemiseks peaksid küljed olema veidi kõrgemad kui 1 cm. Pärast ribade lõikamist panin nende vahele 3D -prinditud maski tükid, et mõõta pleksiklaasi laiust. Lõika kaks pleksiklaasist riba laiust ja pikkust. Lõpuks lõigake difusioonmaterjalist riba, et see sobiks maskiga.

Hajutamiseks mulle väga meeldivad Lee filtrid #216 (täisvalge difusioon). See on õhuke plastleht, mis annab ühtlase hajumise ilma palju valgust kaotamata. Aga see on kallis asi. Mõnikord leiate veebist väiksemaid lehti, kuid terve rull maksab teile tagasi umbes 125 dollarit. Mõned muud võimalused on valge paber või muu satiin või mattplast. Populaarne valik on õhukesed plastist lõikamismatid.

Enne LED -riba kokkupanekut veenduge, et LED -ribade külge on joodetud sobivad pistikud. Paljud ribad on eelnevalt joodetud juhtmetega, nii et saate neid lihtsalt kasutada.

Alustasin kokkupanekut, keerates pleksiklaasi ülemise osa puidust külgedele (vt foto). Seejärel pöörasin selle ümber ja asetasin difusiooniriba, millele järgnesid 10 maskitükki. Kui olin vahekaugusega rahul, kinnitasin need mõne kuuma kuuma liimiga kohale.

Seejärel asetage kaks LED -riba maskide peale kõrvuti. Veenduge, et valgusdioodid jääksid allapoole, ja veenduge, et iga LED oleks kooskõlas maski vastava avaga. LED -ribade hoidmiseks lisage kuuma liimi või linti. Lõpuks keerake pleksiklaasi tagumine osa kinni.

Käivitage testmuster. Hea töö! Olete teinud kõige raskema osa!

6. samm: juhtpaneel

Juhtpaneel on see osa, mis annab kõige loomingulisema vabaduse. See peab lihtsalt hoidma kõiki juhtnuppe ja elektroonikat koos LED -ribaga. Lihtsaim disain on ristkülikukujulised lauad: puurige nuppude ja juhtnuppude jaoks augud ning kinnitage LED -riba. Mulle meeldib kombineerida puitu, pleksiklaasi ja muid materjale, et anda omamoodi aurupunk / retro-kaasaegne välimus. Sel juhul lõikasin algoritmi peamiste valikunuppude hoidmiseks tüki raskeveokite pleksiklaasi ja ülejäänud elektroonika hoidmiseks puidust varda. Puurisin augud, mis vastavad arkaadnuppude suurusele. Juhtmestik on tagaküljel näha, aga mulle meeldib!

Samuti puurisin ruumi välja 7-segmendilise ekraani, pöörleva kodeerija ja mõne juhtme jaoks tagaküljel. Lõikasin ülaossa dado, et hoida LED -riba.

7. samm: nuppude rakmed

Paljude nuppude ühendamine võib olla tõeline valu. Õnneks on arkaadimasinaid valmistavad inimesed välja pakkunud mõned standardsed pistikud, mida saate kasutada. Igal nupuliidese kaablil on kaks juhtmest, üks VCC jaoks ja teine maandamiseks. Ühes otsas on labidaühendused, mis sobivad nupu tagaküljel asuvate juhtmetega - kinnitage maapind "tavaliselt avatud" juhtme külge ja VCC "tavalise" juhtme külge. Selles konfiguratsioonis, kui kasutaja nuppu vajutab, on vooluring lõpule viidud ja mikrokontroller loeb vastaval sisendpoldil HIGH.

Kaabli teises otsas on JST -pistik (väike valge asi). Nende pistikute juures on tore see, et need lähevad mahutisse ainult ühel viisil, seega ei ole võimalik kogemata VCC -d ja maandust ümber pöörata.

Ma tegin nende pistikute jaoks väikese rakmete ehitamise. Joodan seeria JST -anumaid prototapi tükile ja seejärel juhin juhtmed tagasi Duponti pistikutesse, mille ühendan mikrokontrolleriga. Punane juhe on VCC liin ja see ühendub kõigi JST -anumatega. Sinised juhtmed on need, mis on iga nupu jaoks eraldi.

8. samm: pöörlev kodeerija

Pöörlev kodeerija võimaldab kasutajal algoritmi kiirust juhtida. Ma kasutan moodulit, mis on väljalülitusplaadina ja sisaldab kahe andmeliini (kollased juhtmed) tõmbetakistit. See on ka nupp, kuid ma ei kasuta seda funktsiooni. Ülejäänud kaks juhtmest on VCC ja maandus. Sain ka kena rasvapulga.

Mis mulle pöörleva kodeerija puhul meeldib, erinevalt potentsiomeetrist, on see, et see lihtsalt annab mikrokontrollerile märku pöörlemisest (päripäeva ja vastupäeva), seega on väärtuse tõlgendamist lihtne muuta. Näiteks saate anda sellele kiirendustunde (nagu hiir), kui kasutaja seda kiiresti keerutab.

9. samm: 7-segmendiline kuva

Siin pole palju öelda. Neid asju on igal pool. LED -e juhib kiip nimega TM1637, mis suhtleb mikrokontrolleriga lihtsa jadaprotokolli kaudu. Ma kasutan olemasolevat raamatukogu, mis võimaldab mul öelda, millist numbrit ma tahan näidata, ja see teeb ülejäänu.

Tagaküljel on neli tihvti: VCC, maandus ja kaks jadaprotokolli juhtmest. Jootsin 4-kontaktilise päise, mis ühendatakse vastava mikrokontrolleriga ühendatud Duponti pistikuga.

Samm 10: peamine kontrollerplaat

Põhikontrolleri plaadil on mikrokontroller ise ja kõik juhtnuppude pistikud (nupud, ekraan, LED -id). Mikrokontroller on ESP32, mis pakub palju arvutusvõimsust ja mälu ning paljastab palju kontakte. Juhtmestik on üsna tavaline, kuid toon välja mõned huvitavad nipid.

MÄRKUS. Enne põhiplaadi ühendamist võiksite vaadata koodi (https://github.com/samguyer/AlgorithmMachine), et teie tihvti konfiguratsioon vastaks minu omale.

Jootsin tahvli jaoks tünni tungraua ja ühendasin kaks lihavat vasktraati plaadi toite- ja maandusrööbastega. Põhjus on selles, et LED -riba võib suure heleduse korral palju energiat tarbida ja ma ei taha kogu seda võimsust mikrokontrolleri USB -pistiku kaudu tõmmata.

Nuppude juhtmestiku lihtsustamiseks jootsin meessoost naissoost täisnurga päise riba kogu mikrokontrolleri külje alla (plaadi ülemine külg, nagu näidatud). Nuppude rakmete Duponti pistikud ühendatakse otse selle päisega.

TÄHTIS: nuppude toide (punane juhe) peab olema ühendatud mikrokontrolleri 3,3 V toiteliiniga. ESP32 on 3,3 V kiip, nii et andmekontaktidele tuleks kunagi kinnitada ainult 3,3 V allikad.

Mikrokontroller võtab toite (või surub toite) rööbastele (plaadi alumine külg, nagu näidatud) läbi 5 V USB -pistiku ja maanduse. Kõik muud punased/mustad juhtmed on VCC ja maandatud.

Kaks sinist juhet on LED -ribade (WS2812) andmeliinid. Kollane/roheline paar on pöörleva kodeerija andmejooned ja kollane paar on jadaühendus 7-segmendilise kuvariga.

11. samm: kokkupanek

See fotoseeria näitab lõplikku kokkupanekut ja juhtmestikku. Kinnitasin ka põhikontrolleri plaadi ülaossa tagaküljele.

Enne sisselülitamist tegin paar kontrolli, et vältida vastikuid üllatusi. Eelkõige selleks, et veenduda, et mul pole tagurpidi toite-/maanduspistikuid ega lühiseid. Seadistage oma multimeeter järjepidevuse testimiseks - see piiksub, kui kahe juhtme vahel on elektriline tee. Kinnitage üks juhe tavalise VCC -joone külge nuppude külge. Seejärel kinnitage teine juhtmestik ükshaaval rakmete iga tihvti külge. Multimeeter peaks piiksuma ainult siis, kui vajutate nuppu. Kui saate muid piiksu, tähendab see, et teil on tagasikäik või lühis. Jälgige seda ja parandage see enne toite sisselülitamist!

12. samm: kood

Esmalt avage oma Arduino IDE ja veenduge, et teil on installitud FastLED -kogu.

Laadige algoritmimasina kood alla GitHubist:

github.com/samguyer/AlgorithmMachine.git

Saate selle kloonida otse oma Arduino kausta või kopeerida käsitsi.

Enne selle üleslaadimist veenduge, et tihvti seaded vastavad teie riistvarakonfiguratsioonile. Olen paigutanud kõik pin -seaded faili ülaossa.

Laadige üles ja nautige!

Samm 13: Kuidas kasutada

Algoritmimasinat on lihtne kasutada ja peaaegu kõik nuppude kombinatsioonid on korras!

Esmalt kasutage massiivi väärtuste lähtestamiseks andmenuppe. Valikuid on kolm: (1) randomiseerida, (2) lisada üks juhuslik väärtus ja (3) massiiv ümber pöörata. Pange tähele, et väärtused on püsivad, nii et saate kõigepealt sortida neid, seejärel lisada müra ja seejärel käivitada muu sortimis- või otsimisalgoritm.

Valige teiste nupuvalikute hulgast otsingu- või sortimisalgoritm. Praegu ei ole selle valiku tegemisel tagasisidet (midagi edaspidiseks tööks). Seejärel vajutage nuppu "Esita".

Nupp juhib kiirust. Algoritmi peatamiseks ja tühistamiseks võite vajutada ka nuppu "Esita".

See peatub automaatselt, kui see on tehtud. Samuti võite igal ajal vajutada mõnda muud algoritmi nuppu. Masin peatab praeguse algoritmi ja lähtestab uue, kuid säilitab andmed täpselt nii, nagu eelmine algoritm selle jättis.

Peaauhind STEM konkursil