Algoritmový stroj: 13 kroků (s obrázky)

2024 Autor: John Day | [email protected]. Naposledy změněno: 2024-01-30 08:20

Už 15 let učím informatiku na vysokoškolské úrovni, a přestože moje odbornost je spíše na straně programování, stále trávím poměrně dost času pokrýváním standardních algoritmů pro vyhledávání a třídění. Z hlediska výuky je ústředním problémem výpočetní složitost: kolik času každý algoritmus vyžaduje při daném vstupu konkrétní velikosti? Existuje však mnoho nuancí. Mají například algoritmy různé doby běhu v závislosti na konkrétních vstupních hodnotách (na rozdíl od velikosti)? V jakých případech byste zvolili jeden třídící algoritmus před druhým? Ačkoli diskutujeme tyto problémy abstraktně, vždy mě naštvalo, že neexistuje snadný způsob, jak zjistit, jak různé algoritmy fungují za různých podmínek.

Cíle

Mým zastřešujícím cílem tohoto projektu bylo vytvořit interaktivní displej pro studenty k vizualizaci a prozkoumání algoritmů. Omezil jsem se na algoritmy, které pracují na polích hodnot (celá čísla), takže mohu použít adresovatelný RGB LED pás k vizualizaci obsahu pole. Pole má 100 prvků a každé celé číslo je mapováno na barvu v duhovém pořadí, takže je okamžitě zřejmé, kdy je pole tříděno, částečně tříděno nebo randomizováno. Kromě hodnot jsem však chtěl způsob, jak vizualizovat kontrolní aspekty algoritmu - například, které prvky pole jsou aktuálně porovnávány nebo prohozovány.

Konkrétní cíle jsou:

- Poskytněte řadu vyhledávacích a třídicích algoritmů

- Vizualizujte hodnoty v poli způsobem, který zdůrazňuje průběh algoritmu

- Vizualizace řízení algoritmů; zejména zvažované prvky.

- Umožněte uživatelům zvolit si vzory vstupních dat místo generování náhodných hodnot

- Umožněte uživatelům ovládat rychlost a pozastavit algoritmus

-Umožněte uživatelům vynutit si chování v nejlepším, nejhorším a průměrném případě (specifické pro algoritmus)

- Ukažte počet kroků, jak algoritmus pokračuje

Vizualizace

Z hlediska fyzického návrhu je nejzajímavější částí tohoto projektu vizualizace pole. Bojoval jsem s tím, jak zobrazit data a ovládání a jak sestavit samotné zobrazovací zařízení. Mým cílem bylo ukázat hodnoty dat jako barevné kruhy a kontrolní body jako barevné šipky, které ukazují na hodnoty dat. Po nějakém experimentování jsem se rozhodl pro návrh se dvěma paralelními proužky 100 RGB LED (WS2812) s kruhovou maskou nad každou datovou LED a trojúhelníkovou maskou nad každou kontrolní LED. Vytvořil jsem 3D model masky s 10 páry kruhů a trojúhelníků a poté 3D vytiskl 10 z těchto modulů pro celkem 100 kruhů a 100 trojúhelníků. Velikost a rozestup mé masky je určen pro pásy se 100 LED na metr. Soubory 3D modelu jsou uvedeny dále v tomto popisu.

Elektronika a skříň

Zbytek zařízení je přímočarý, z hlediska elektroniky. Kromě dvou LED pásků je tu spousta momentálních tlačítek, otočný kodér (pro ovládání rychlosti) a 7segmentový displej (pro zobrazení kroků). S tolika tlačítky a ovládacími prvky jsem se rozhodl použít mikrokontrolér ESP32, protože odhaluje mnoho pinů a protože je poměrně silný. Projdu si strategii zapojení, ale ta je docela základní. Pokud chcete použít méně pinů, pravděpodobně byste mohli udělat něco chytrého s posuvnými registry.

Kryt pro toto zařízení můžete postavit v mnoha různých formách. Původně jsem si to představoval jako velkou obdélníkovou desku s LED páskem přes horní část a mřížkou tlačítek uprostřed. Forma, u které jsem skončil, je inspirována jakýmsi pohledem šedesátých let na technologii vesmírného věku. Můžete jej také postavit pomocí LED pásů ve svislé orientaci. Nebo můžete LED část mnohem zvětšit - vyplnit celou zeď - samostatným ovládacím panelem.

Software

Kód pro toto zařízení je volně dostupný na GitHubu a já jsem udělal vše pro to, abych zdokumentoval, jak funguje a jak jej konfigurovat. Jediná externí knihovna, kterou potřebujete, je FastLED pro pohon pásů WS2812.

Zásoby

Elektronika

1 vývojová deska ESP32 (např.

2 LED pásky WS2812 nebo podobné, hustota 100 LED na metr (např.

1 Tlačítko „trojúhelník“start (např.

12 Okamžitá tlačítka (např. Https://amzn.com/B01N4D4750) - různé tvary, pokud chcete

1 balíček (20) předem zapojených konektorů tlačítek (např.

1 balíček konektorů JST (např.

1 rotační kodér (např.

1 knoflík pro rotační kodér (např.

1 balení konektorů Dupont (např. Https://amzn.com/B014YTPFT8) - vyplatí se pořídit si také krimpovací nástroj.

1 hlavní konektor (pro napájení) (např.

1 TM1637 7segmentový numerický displej (např.

Pájecí a kabelážní zařízení

Soubory 3D modelu

3D model pro dvojici 10světelných modulů najdete na Thingiverse:

www.thingiverse.com/thing:4178181

Tento model budete muset vytisknout pětkrát pro celkem 10 modulů.

Software

github.com/samguyer/AlgorithmMachine

Ohrada

Šrouby a šrouby do dřeva, plexiskla, nerezové oceli

Difúzní materiál. Můj oblíbený je Lee Filters #216 plná bílá difúze, ale existují i další možnosti. I obyčejný bílý papír odvede dobrou práci.

Krok 1: Algoritmy 101

Mnoho lidí si myslí, že informatika je v podstatě studium programování. Ale skutečným srdcem a duší této oblasti jsou algoritmy: studium systematických postupů pro řešení problémů a jejich cena (obvykle, jak dlouho trvají). Klíčové postavy v této oblasti, jako Alan Turing, Alonzo Church a Edsger Dijkstra, o těchto myšlenkách přemýšlely dříve, než počítače, jak je známe, vůbec existovaly.

Klíčovou vlastností algoritmu k řešení konkrétního problému je, že je podrobný a přesný, takže ho někdo mohl použít k získání řešení, aniž by vůbec rozuměl tomu, jak funguje; stačí mechanicky postupovat podle kroků a dostanete správnou odpověď. Můžete vidět, jak to pomáhá s programováním počítačů, protože potřebují tuto úroveň podrobností. Počítač nemůže vyplňovat chybějící údaje ani provádět úsudky tak, jak to člověk dokáže.

Jak dlouho to trvá?

Jakmile máme podrobný postup, přirozenou otázkou je, jak dlouho bude trvat odpověď? Běžné jednotky času použít nemůžeme, protože to závisí na tom, kdo tu práci dělá (porovnejte, jak rychle by člověk dokázal něco vypočítat oproti superpočítači). Navíc záleží na tom, kolik dat máme. Je jasné, že hledání v seznamu miliónů telefonních čísel trvá déle než v seznamu stovek.

Abychom popsali náklady na algoritmus, nejprve vybereme nějakou operaci v postupu, která představuje jeden „krok“- obvykle něco jednoduchého, jako je porovnávání nebo přidávání dvou čísel, jehož provedení vyžaduje pevně stanovený čas. Poté vymyslíme vzorec, který popisuje, kolik kroků algoritmus provede s určitým počtem datových položek. Z historických důvodů téměř vždy označujeme počet datových položek s velkým N.

Například procházení seznamu N telefonních čísel trvá N kroků. Prohlížení seznamu dvakrát trvá 2N kroků. Oba se nazývají lineární časové algoritmy - celkový počet kroků je několikanásobkem vstupní velikosti. Jiné algoritmy jsou kvadratické (N na druhou) nebo krychlové (N na kostky) nebo logaritmické (log N) nebo jejich kombinace. Některé z nejtěžších výpočetních problémů vyžadují exponenciální časové algoritmy (2^N).

Dobře, tak co?

Když je počet datových položek N malý, na tom moc nezáleží. Například pro N = 10 je 10N ten název jako N na druhou. Ale co N = 1000? nebo N = 10 000 000? Milión na druhou je docela velké číslo. I na velmi rychlém počítači může kvadratický algoritmus trvat dlouho, pokud je vstup dostatečně velký. Exponenciální algoritmy jsou mnohem problematičtější: pro N = 50 by dokončení exponenciálního algoritmu trvalo dva týdny i na počítači, kde každý krok je pouze jedna nanosekunda (1 miliardtina sekundy). Au!

Na druhém konci stupnice máme logaritmické časové algoritmy, které jsou velmi rychlé. Čas záznamu je opakem exponenciálního času: vzhledem k velikosti vstupu N je počet kroků exponentem T ve vzorci 2^T = N. Například pokud je naše velikost vstupu jedna miliarda, pak algoritmus záznamu času vyžaduje pouze 30 kroky, protože 2^30 = 1 000 000 000 000. Jak sladké to je?! ??!

Možná si říkáte, komu záleží na vstupních velikostech milionů nebo miliard? Zamyslete se: kolik uživatelů je na Facebooku? Kolik webových stránek Google indexuje? Kolik párů bází je v lidském genomu? Kolik měření jde do simulace počasí?

Krok 2: Algoritmy

Algoritmový stroj aktuálně implementuje následující algoritmy. Dva z nich jsou vyhledávací algoritmy (najděte konkrétní hodnotu v seznamu), zbytek jsou algoritmy řazení (uspořádejte hodnoty v pořádku).

Lineární vyhledávání

Procházejte seznam hodnot jednu po druhé od začátku. Vyžaduje lineární čas.

Binární vyhledávání

Prohledejte seznam opakovaným rozdělením na polovinu. Vyžaduje čas přihlášení, ale seznam musí být seřazen, aby fungoval.

Bublinkové řazení

Seřaďte seznam a opakovaně vyměňujte sousední prvky, které nejsou v pořádku. Vyžaduje kvadratický čas.

Třídění vložení

Seřaďte seznam umístěním každého prvku na správné místo v seznamu již seřazených hodnot. Vyžaduje kvadratický čas.

Rychlé řazení

Seřadit seznam opakovaným rozdělením seznamu na polovinu a přesunutím všech hodnot menších než medián do první poloviny a všech hodnot větších než medián do druhé poloviny. V praxi nemůžeme efektivně najít medián, takže vybereme hodnotu náhodně. Výsledkem je, že tento algoritmus může být v nejhorším případě kvadratický, ale obvykle vyžaduje čas N * logN.

Sloučit třídění

Seřaďte seznam tak, že ho rozdělíte na polovinu, roztřídíte obě poloviny samostatně (pomocí sloučení) a poté je spojíte dohromady prokládáním hodnot. Vždy vyžaduje N * čas přihlášení.

Haldy

Seřaďte seznam vytvořením datové struktury zvané halda, která vám umožní najít nejmenší hodnotu v čase záznamu. Vždy vyžaduje N * čas přihlášení.

Bitonické řazení

Podobně jako u sloučení a rychlého řazení rozdělte seznam na polovinu, roztřiďte poloviny a znovu je zkombinujte. Tento algoritmus vyžaduje čas N * logN * logN, ale má tu výhodu, že je snadno paralelizovatelný.

Krok 3: LED Bar: 3D tisk masky

Prvním krokem při stavbě LED lišty je 3D tisk masky, která dává světlům tvar. Každý modul pokrývá deset prvků pole, 10 hodnot (kruhy) a 10 indikátorů (trojúhelníky), takže budete potřebovat celkem 10 modulů. Soubor STL, který zde poskytuji, obsahuje dvě instance modulu, takže budete muset provést pět tiskových cyklů. Nemám nejlepší 3D tiskárnu, takže jsem na nich musel provést ruční vyčištění pomocí souboru a smirkového papíru. Nejdůležitější je, aby kruhové a trojúhelníkové otvory byly čisté.

Na fotografiích uvidíte moje testovací nastavení: Přilepil jsem dva LED pásy dolů a připojil je k prkénku s mikrokontrolérem. Tento krok není nutný, ale chtěl jsem zjistit, jak to bude vypadat, než jsem začal sestavovat skříň. Seřadil jsem moduly masky na dva LED pásy a spustil jednoduchou skicu s náhodnými barvami. S pruhem difuzního materiálu tvary a barvy opravdu vyniknou.

Krok 4: Alternativy lišty LED

Když jsem poprvé zahájil tento projekt, experimentoval jsem s jinými způsoby výroby masky LED. Pokud nemáte 3D tiskárnu, můžete zvážit jednu z těchto možností. Budu upřímný: vyrábět tyto díly je obrovská bolest.

Na kruhy jsem koupil mosaznou trubku 13/32, která má průměr téměř přesně 1 cm. Rozstříhal jsem ho na sto 1 cm segmentů a poté je nastříkal bílou barvou.

Na trojúhelníky jsem použil těžkou hliníkovou fólii nařezanou z jednorázového pekáče. Ze dřeva jsem vytvořil trojúhelníkovou formu, pak jsem kolem formy omotal krátké proužky fólie a podlepil je. Opět budete potřebovat sto těchto věcí, takže to chce nějaký čas a trpělivost.

Krok 5: Kryt lišty LED

Moje ohrada je poměrně jednoduchá: dva pásy dřeva po stranách a dva pásy plexiskla nahoře a dole. Všechny díly jsou asi 102 cm dlouhé (1 metr pro LED diody a něco navíc pro zapojení). Boky by měly být o něco vyšší než 1 cm, aby se vytvořil prostor pro LED pásky. Po odříznutí proužků jsem mezi ně vložil kousky 3D tištěné masky, abych změřil šířku plexiskla. Odřízněte dva kusy plexiskla o šířce a délce tyče. Nakonec odřízněte proužek difuzního materiálu, aby se vešel přes masku.

Pro difúzi se mi moc líbí Lee Filters #216 (plná bílá difúze). Jedná se o tenkou plastovou fólii, která poskytuje rovnoměrnou difuzi, aniž by ztratila mnoho světla. Ale jsou to drahé věci. Někdy můžete najít menší archy k prodeji online, ale celá role vás vrátí asi 125 $. Některé další možnosti jsou bílý papír nebo jakýkoli jiný druh saténu nebo matného plastu. Oblíbenou volbou jsou tenké plastové řezací podložky.

Před montáží LED lišty se ujistěte, že máte k LED páskům připájené příslušné konektory. Mnoho pásků je dodáváno s předpájenými svody, takže je můžete použít.

Montáž jsem zahájil přišroubováním horního kusu plexiskla na dřevěné boky (viz foto). Pak jsem to převrátil a vložil difúzní proužek dovnitř a poté 10 kusů masky. Jakmile jsem byl s rozestupem spokojený, připnul jsem je na místo několika tečkami horkého lepidla.

Dále položte dva LED pásy vedle sebe na masky. Ujistěte se, že LED diody směřují dolů, a ujistěte se, že každá LED svítí s odpovídajícím otvorem v masce. Přidejte nějaké horké lepidlo nebo pásku, aby LED pásky držely na svém místě. Nakonec přišroubujte zadní část plexiskla.

Spusťte testovací vzor. Dobrá práce! Zvládli jste to nejtěžší!

Krok 6: Ovládací panely

Ovládací panel je část, která poskytuje největší tvůrčí svobodu. Jen musí obsahovat všechny ovládací prvky a elektroniku spolu s LED lištou. Nejjednodušší konstrukce je obdélníková deska: vyvrtejte otvory pro tlačítka a ovládací prvky a připevněte lištu LED. Rád kombinuji dřevo, plexisklo a další materiály, abych získal jakýsi steampunk / retro-moderní vzhled. V tomto případě jsem uřízl kus těžkého plexiskla, které přidrží tlačítka pro výběr hlavního algoritmu, a dřevěnou tyč, do které se vejde zbytek elektroniky. Vyvrtal jsem otvory, aby odpovídaly velikosti arkádových knoflíků. Zapojení se ukazuje na zadní straně, ale líbí se mi to!

Také jsem vyvrtal prostor pro 7segmentový displej, rotační kodér a některé kabely na zadní straně. Nahoře jsem nařezal dado, abych držel lištu LED.

Krok 7: Kabelový svazek

Zapojení spousty tlačítek může být skutečná bolest. Naštěstí lidé, kteří vyrábějí arkádové stroje, přišli s některými standardními konektory, které můžete použít. Každý kabel konektoru tlačítka má dva vodiče, jeden pro VCC a jeden pro uzemnění. Jeden konec má rýčové konektory, které pasují na vodiče na zadní straně tlačítka - uzemnění připojte k „normálně otevřenému“kabelu a VCC ke „společnému“kabelu. V této konfiguraci, když uživatel stiskne tlačítko, je obvod dokončen a mikrokontrolér bude číst HIGH na odpovídajícím vstupním pinu.

Druhý konec kabelu má konektor JST (malá bílá věc). Na těchto konektorech je hezké, že jdou do zásuvky pouze jedním způsobem, takže neexistuje způsob, jak omylem obrátit VCC a uzemnění.

To, co jsem udělal, je vybudování malého svazku pro tyto konektory. Na kus protoboardu připájím sérii JST zásuvek a poté vedu vodiče zpět ke konektorům Dupont, které zapojím do mikrokontroléru. Červený vodič je linka VCC a připojuje se ke všem zásuvkám JST. Modré vodiče jsou ty, které jsou pro každé tlačítko samostatné.

Krok 8: Rotační kodér

Rotační kodér umožňuje uživateli ovládat rychlost algoritmu. Používám modul, který je dodáván jako odpojovací deska, která obsahuje výsuvné odpory pro dvě datová vedení (žluté vodiče). Toto je také tlačítko, ale tuto funkci nepoužívám. Další dva vodiče jsou VCC a uzemnění. Také jsem dostal pěkný tlustý knoflík.

Na rotačním kodéru se mi na rozdíl od potenciometru líbí to, že mikrokontroléru pouze signalizuje rotaci (ve směru hodinových ručiček vs. proti směru hodinových ručiček), takže je snadné změnit způsob interpretace hodnoty. Například mu můžete dát pocit zrychlení (jako myš), když jej uživatel rychle točí.

Krok 9: 7segmentový displej

Tady není moc co říct. Tyto věci jsou všude. LED diody jsou ovládány čipem TM1637, který komunikuje s mikrokontrolérem pomocí jednoduchého sériového protokolu. Používám existující knihovnu, která mi umožňuje sdělit, jaké číslo chci ukázat, a to ostatní.

Zadní strana má čtyři piny: VCC, uzemnění a dva vodiče pro sériový protokol. Pájel jsem 4pinový kus záhlaví, který se připojuje k odpovídajícímu konektoru Dupont připojenému k mikrokontroléru.

Krok 10: Hlavní řídicí deska

Na hlavní desce řadiče je umístěn samotný mikrokontrolér a všechny konektory k ovládacím prvkům (tlačítka, displej, diody LED). Mikrokontrolér je ESP32, který poskytuje spoustu výpočetního výkonu a paměti a odhaluje spoustu pinů. Zapojení je celkem standardní, ale upozorním na pár zajímavých kousků.

POZNÁMKA: Možná se budete chtít podívat na kód (https://github.com/samguyer/AlgorithmMachine), než začnete zapojovat hlavní desku, aby se vaše konfigurace pinů shodovala s mojí.

Na desku jsem připájel sudový konektor pro napájení a připojil dva silné měděné dráty k napájecím a zemnicím kolejnicím desky. Důvodem je, že lišta LED může čerpat hodně energie, pokud je jas nastaven na vysokou úroveň, a nechci celou tu energii tahat přes konektor USB na mikrokontroléru.

Aby se zjednodušilo zapojení tlačítek, připájel jsem pásek pravoúhlého konektoru muž-k-ženě po celé straně mikrokontroléru (horní strana desky, jak je znázorněno). Konektory Dupont z kabelového svazku se zapojují přímo do této hlavičky.

DŮLEŽITÉ: napájení tlačítek (červený vodič) musí být připojeno k napájecímu vedení 3,3 V na mikrokontroléru. ESP32 je čip 3,3 V, takže k datovým pinům by měly být připojeny pouze zdroje 3,3 V.

Mikrokontrolér odebírá energii (nebo tlačí energii) na kolejnice (spodní strana desky, jak je znázorněno) prostřednictvím 5V USB kolíku a uzemnění. Všechny ostatní červené/černé vodiče jsou VCC a uzemněné.

Dva modré vodiče jsou datové linky pro LED pásky (WS2812s). Žlutý/zelený pár jsou datové řádky rotačního kodéru a žlutý pár je sériové připojení k 7segmentovému displeji.

Krok 11: Sestavení

Tato série fotografií ukazuje konečnou montáž a zapojení. Také jsem připojil hlavní desku řadiče k zadní straně nahoře.

Před zapnutím jsem provedl několik kontrol, abych se vyhnul nepříjemným překvapením. Zejména abych se ujistil, že nemám žádné napájecí/uzemňovací konektory dozadu a žádné zkraty. Nastavte multimetr tak, aby testoval spojitost - pípne, když je mezi oběma vodiči elektrická dráha. Připojte jeden svod ke společné řadě VCC k tlačítkům. Poté připojte druhý vodič ke každému kolíku postroje jeden po druhém. Multimetr by měl pípat pouze při stisknutí tlačítka. Pokud se ozve další pípnutí, znamená to, že máte reverz nebo zkrat. Vystopujte to a opravte, než zapnete napájení!

Krok 12: Kód

Nejprve otevřete IDE Arduino a ujistěte se, že máte nainstalovanou knihovnu FastLED.

Stáhněte si strojový kód algoritmu z GitHub:

github.com/samguyer/AlgorithmMachine.git

Můžete jej buď klonovat přímo do složky Arduino, nebo jej zkopírovat ručně.

Před odesláním se ujistěte, že nastavení pinů odpovídá vaší hardwarové konfiguraci. Umístil jsem všechna nastavení pinů do horní části souboru.

Nahrajte a užívejte si!

Krok 13: Jak používat

Algoritmový stroj se snadno používá a téměř jakákoli kombinace tlačítek je v pořádku!

Nejprve pomocí datových tlačítek inicializujte hodnoty v poli. Existují tři možnosti: (1) randomize, (2) add one random value, and (3) reverse the array. Hodnoty jsou trvalé, takže můžete dělat věci, jako je nejprve seřadit, pak přidat trochu šumu a poté spustit jiný algoritmus řazení nebo vyhledávání.

Z dalších voleb tlačítek vyberte vyhledávací nebo třídicí algoritmus. V současné době při této volbě neexistuje žádná zpětná vazba (něco pro budoucí práci). Poté stiskněte tlačítko „přehrát“.

Knoflík ovládá rychlost. Algoritmus můžete pozastavit a zrušit také stisknutím „Přehrát“.

Po dokončení se automaticky zastaví. Můžete také kdykoli stisknout tlačítko jiného algoritmu. Stroj zastaví aktuální algoritmus a inicializuje nový, ale zachová data přesně tak, jak je opustil předchozí algoritmus.

Velká cena v soutěži STEM