Машината за алгоритми: 13 стъпки (със снимки)

2024 Автор: John Day | [email protected]. Последно модифициран: 2024-01-30 07:51

Преподавам компютърни науки на ниво колеж в продължение на 15 години и въпреки че опитът ми е по -скоро в областта на програмирането, аз все още прекарвам доста време, обхващайки стандартни алгоритми за търсене и сортиране. От гледна точка на преподаването централният въпрос е изчислителната сложност: колко време отнема всеки алгоритъм, като се има предвид вход с определен размер? Но има много нюанси. Например, дали алгоритмите имат различно време на изпълнение в зависимост от конкретните входни стойности (за разлика от размера)? В кои случаи бихте избрали един алгоритъм за сортиране пред друг? Въпреки че обсъждаме тези въпроси абстрактно, винаги ме притесняваше, че няма лесен начин да се види как различните алгоритми работят при различни условия.

Цели

Основната ми цел за този проект беше да създам интерактивен дисплей за учениците, които да визуализират и изследват алгоритми. Ограничих се до алгоритми, които работят върху масиви от стойности (цели числа), така че мога да използвам адресируема RGB LED лента, за да визуализирам съдържанието на масива. Масивът има 100 елемента и всяко цяло число е съпоставено с цвят в ред на дъгата, така че веднага е очевидно, когато масивът е сортиран, частично сортиран или рандомизиран. В допълнение към стойностите обаче исках начин да визуализирам контролните аспекти на алгоритъма - например кои елементи от масива в момента се сравняват или разменят.

Конкретните цели са:

- Осигурете разнообразие от алгоритми за търсене и сортиране

- Визуализирайте стойностите в масива по начин, който подчертава напредъка на алгоритъма

- Визуализирайте управлението на алгоритъма; по -специално разглежданите елементи.

- Позволете на потребителите да избират моделите на входните данни, вместо винаги да генерират случайни стойности

- Позволете на потребителите да контролират скоростта и да поставят на пауза алгоритъма

-Позволете на потребителите да налагат поведение в най-добрия, най-лошия и средния случай (специфично за алгоритъма)

- Показвайте броя на стъпките, докато алгоритъмът продължава

Визуализация

От гледна точка на физическия дизайн най -интересната част от този проект е визуализацията на масива. Боря се с това как да показвам данните и контрола и как да изградя самото дисплейно устройство. Моята цел беше да покажа стойностите на данните като цветни кръгове, а контролните точки като цветни стрелки, които сочат към стойностите на данните. След известен експеримент се спрях на дизайн с две паралелни ленти от 100 RGB светодиода (WS2812) с кръгла маска над всеки светодиод с данни и триъгълна маска над всеки контролен светодиод. Направих 3D модел на маската с 10 двойки кръгове и триъгълници, след което 3D отпечатах 10 от тези модули за общо 100 кръга и 100 триъгълника. Размерът и разстоянието на маската ми са предназначени за ленти със 100 светодиода на метър. Файловете с 3D модели са предоставени по -късно в това описание.

Електроника и корпус

Останалата част от устройството е проста, от гледна точка на електрониката. В допълнение към двете LED ленти има куп моментни бутони, въртящ се енкодер (за контрол на скоростта) и 7-сегментен дисплей (за показване на стъпки). С толкова много бутони и контроли избрах да използвам микроконтролер ESP32, защото излага много пинове и защото е доста мощен. Ще разгледам стратегията за окабеляване, но тя е доста основна. Вероятно бихте могли да направите нещо умно с регистрите за смяна, ако искате да използвате по -малко щифтове.

Можете да изградите корпуса за това устройство в много различни форми. Първоначално си го представях като голяма правоъгълна дъска с LED лентата отгоре и решетка от бутони в средата. Формата, с която се озовах, е вдъхновена от един вид през 1960 г. на технологиите в космическата ера. Можете също така да го изградите с LED ленти във вертикална ориентация. Или направете LED частта много по -голяма - запълнете цяла стена - с отделен контролен панел.

Софтуер

Кодът за това устройство е свободно достъпен в GitHub и аз направих всичко възможно да документирам как работи и как да го конфигурирам. Единствената външна библиотека, от която се нуждаете, е FastLED за задвижване на ленти WS2812.

Консумативи

Електроника

1 платка за разработка на ESP32 (например

2 WS2812 или подобни LED ленти, плътност 100 светодиода на метър (напр.

1 Бутон "Старт" на триъгълник (напр.

12 моментални бутона (например https://amzn.com/B01N4D4750) - различни форми, ако искате

1 пакет (20) предварително свързани кабелни конектори (напр.

1 пакет JST конектори (напр.

1 Ротационен енкодер (напр.

1 Копче за въртящ се енкодер (напр.

1 Опаковайте съединители Dupont (например https://amzn.com/B014YTPFT8) - заслужава си да вземете и инструмента за кримпване.

1 Варел (за захранване) (напр.

1 TM1637 7-сегментен цифров дисплей (напр.

Съоръжения за запояване и окабеляване

Файлове с 3D модели

Можете да намерите 3D модела за чифт 10 светлинни модула в Thingiverse:

www.thingiverse.com/thing:4178181

Ще трябва да отпечатате този модел пет пъти за общо 10 модула.

Софтуер

github.com/samguyer/AlgorithmMachine

Корпус

Болтове и винтове от дърво, плексиглас, неръждаема стомана

Дифузионен материал. Любимият ми е Lee Filters #216 пълно бяла дифузия, но има и други опции. Дори обикновената бяла хартия върши добра работа.

Стъпка 1: Алгоритми 101

Много хора смятат, че компютърните науки по същество са изучаване на програмирането. Но истинското сърце и душа в тази област са алгоритмите: изучаването на систематични процедури за решаване на проблеми и тяхната цена (обикновено колко време отнемат). Условни фигури в областта, като Алън Тюринг, Алонзо Чърч и Едсгер Дайкстра, мислеха за тези идеи преди компютрите, каквито ги познаваме, дори да са съществували.

Ключовата характеристика на алгоритъма за решаване на определен проблем е, че той е подробен и прецизен, така че някой да може да го използва, за да получи решение, без изобщо да разбира как работи; просто следвайте стъпките по механичен начин и ще получите правилния отговор. Можете да видите как това помага при програмирането на компютри, тъй като те се нуждаят от това ниво на детайлност. Компютърът не може да попълва липсващи подробности или да преценява, както може човек.

Колко време ще отнеме?

След като имаме подробна процедура, естественият въпрос е колко време ще отнеме, за да получим отговора? Не можем да използваме обикновени мерни единици, тъй като това зависи от това кой върши работата (сравнете колко бързо човек може да изчисли нещо спрямо суперкомпютър). Освен това зависи от това колко данни имаме. Ясно е, че търсенето в списък с милион телефонни номера отнема повече време, отколкото в списък със сто.

За да опишем цената на алгоритъм, първо избираме някаква операция в процедурата, която представлява една „стъпка“- обикновено нещо просто, като сравняване или добавяне на две числа, което отнема фиксирано време. След това измисляме формула, която описва колко стъпки ще предприеме алгоритъмът при определен брой елементи от данни. По исторически причини почти винаги обозначаваме броя на данните с главни букви N.

Например разглеждането на списък с N телефонни номера отнема N стъпки. Разглеждането на списъка два пъти отнема 2N стъпки. И двете се наричат линейни алгоритми за време - общият брой стъпки е кратно на размера на входа. Други алгоритми са квадратични (N на квадрат време) или кубични (N куб.) Или логаритмични (log N) или някаква комбинация от тях. Някои от най -трудните изчислителни проблеми изискват алгоритми за експоненциално време (2^N).

Добре, и какво?

Когато броят на елементите от данни N е малък, това няма голямо значение. Например, за N = 10, 10N е това име като N на квадрат. Но какво да кажем за N = 1000? или N = 1000000? Милион на квадрат е доста голямо число. Дори на много бърз компютър квадратичният алгоритъм може да отнеме много време, ако входът е достатъчно голям. Експоненциалните алгоритми са много по -обезпокоителни: за N = 50 експоненциалният алгоритъм ще отнеме две седмици, за да завърши дори на компютър, където всяка стъпка е само една наносекунда (1 милиардна част от секундата). Ох!

В другия край на скалата имаме логаритмични алгоритми за време, които са много бързи. Времето за регистрация е обратното на експоненциалното време: при даден входен размер N, броят на стъпките е показателят T във формулата 2^T = N. Например, ако нашият входен размер е един милиард, тогава алгоритъмът за регистрационно време изисква само 30 стъпки, тъй като 2^30 = 1 000 000 000 000. Колко сладко е това?! ??!

Може би се чудите, кой се интересува от размера на входящите милиони или милиарди? Помислете: колко потребители има във Facebook? Колко уеб страници са индексирани от Google? Колко базови двойки има в човешкия геном? Колко измервания влизат в симулация на времето?

Стъпка 2: Алгоритмите

В момента машината за алгоритми изпълнява следните алгоритми. Два от тях са алгоритми за търсене (намерете определена стойност в списъка), останалите са алгоритми за сортиране (подредете стойностите).

Линейно търсене

Търсете в списъка със стойности една по една, започвайки от началото. Изисква линейно време.

Двоично търсене

Търсете в списък, като го разделяте многократно наполовина. Изисква време за регистрация, но списъкът трябва да бъде сортиран, за да работи.

Сортиране на балончета

Сортирайте списък, който многократно обменя съседни елементи, които не са в ред. Изисква квадратично време.

Сортиране на вмъкване

Сортирайте списък, като поставите всеки елемент на правилното му място в списъка със вече сортирани стойности. Изисква квадратично време.

Бързо сортиране

Сортирайте списък, като многократно разделяте списъка наполовина и премествате всички стойности, по -малки от медианата към първата половина, и всички стойности, по -големи от медианата към втората половина. На практика не можем ефективно да намерим медианата, затова избираме стойност на случаен принцип. В резултат на това този алгоритъм може да бъде квадратичен в най -лошия случай, но обикновено изисква N * logN време.

Обединяване на сортиране

Сортирайте списък, като го разделите наполовина, сортирате двете половини поотделно (с помощта на сортиране при сливане) и след това ги обедините заедно, като преплитате стойностите. Винаги изисква N * logN време.

Сортиране на купчини

Сортирайте списък, като изградите структура от данни, наречена купчина, която ви позволява да намерите най -малката стойност за времето на регистрация. Винаги изисква N * logN време.

Битонично сортиране

Подобно на обединяването и бързото сортиране, разделете списъка наполовина, сортирайте половините и ги комбинирайте отново. Този алгоритъм изисква N * logN * logN време, но има предимството, че е лесен за паралелизиране.

Стъпка 3: LED лента: 3D отпечатване на маската

Първата стъпка в изграждането на LED лентата е 3D отпечатването на маската, която придава формата на светлините. Всеки модул обхваща десет елемента от масива, 10 стойности (кръгове) и 10 индикатора (триъгълници), така че ще ви трябват общо 10 модула. Предлаганият от мен STL файл съдържа два екземпляра на модула, така че ще трябва да направите пет цикъла на печат. Нямам най -добрия 3D принтер, затова се наложи да ги почистя ръчно с помощта на файл и шкурка. Най -важното е кръглите и триъгълните дупки да са чисти.

На снимките ще видите моята тестова настройка: залепих двете LED ленти надолу и ги закачих към макет с микроконтролер. Тази стъпка не е необходима, но исках да видя как ще изглежда, преди да започна да сглобявам заграждението. Подредих модулите на маската на двете LED ленти и пуснах обикновена скица със случайни цветове. С лента от дифузионния материал формите и цветовете наистина изпъкват.

Стъпка 4: Алтернативи на LED лентата

Когато за първи път започнах този проект, експериментирах с други начини за правене на LED маска. Ако нямате 3D принтер, можете да помислите за една от тези опции. Ще бъда честен: създаването на тези части е огромна болка.

За кръговете купих месингова тръба 13/32, която е с диаметър почти точно 1 см. Нарязах го на сто сегмента по 1 см и след това ги боядисах със спрей в бяло.

За триъгълниците използвах алуминиево фолио, изрязано от тава за еднократна употреба. Направих триъгълна форма от дърво, след това увих къси ивици фолио около формата и ги залепих с лепенка. Отново ще ви трябват сто от тези неща, така че отнемете известно време и търпение.

Стъпка 5: Корпус с LED лента

Моят корпус е сравнително прост: две дървени ленти отстрани и две ленти от плексиглас за горната и долната част. Всички части са с дължина около 102 см (1 метър за светодиодите, плюс малко допълнително за настаняване на окабеляването). Страните трябва да са малко по -високи от 1 см, за да се освободи място за LED лентите. След като изрязах лентите, поставих 3D печатни парчета маска между тях, за да измеря ширината на плексигласа. Изрежете две парчета плексиглас по ширината и дължината на шината. Накрая изрежете лента от дифузионния материал, за да се побере върху маската.

За дифузия много харесвам Lee Filters #216 (пълна бяла дифузия). Това е тънък пластмасов лист, който дава равномерна дифузия, без да губи много светлина. Но това са скъпи неща. Понякога можете да намерите по -малки листове за продажба онлайн, но цяла ролка ще ви върне около 125 долара. Някои други опции са бяла хартия или друг вид сатен или матова пластмаса. Популярен избор са тънки пластмасови подложки за рязане.

Преди да сглобите LED лентата, уверете се, че имате подходящи конектори, запоени към LED лентите. Много ленти идват с предварително запоени проводници, така че можете просто да ги използвате.

Започнах сглобяването, като завинтих горното парче от плексиглас върху дървените страни (вижте снимката). След това го обърнах и поставих дифузионната лента, последвана от 10 парчета маска. След като бях доволен от разстоянието, ги закрепих на място с няколко точки горещо лепило.

След това поставете двете LED ленти една до друга върху маските. Уверете се, че светодиодите са обърнати надолу и се уверете, че всеки светодиод е подравнен със съответния отвор в маската. Добавете малко горещо лепило или лента, за да задържите LED лентите на място. Накрая завийте задното парче от плексиглас.

Изпълнете тест модел. Хубава работа! Направихте най -трудната част!

Стъпка 6: Контролен панел

Контролният панел е частта, която осигурява най -голяма творческа свобода. Просто трябва да държи всички контроли и електроника, заедно с LED лентата. Най -простият дизайн е правоъгълна дъска: пробийте дупки за бутоните и контролите и прикрепете LED лентата. Обичам да комбинирам дърво, плексиглас и други материали, за да придавам вид стимпанк / ретро-модерен вид. В този случай изрязах парче тежък плексиглас, за да държи основните бутони за избор на алгоритъм, и дървена лента, която да побере останалата част от електрониката. Пробих дупки, за да съответстват на размера на аркадните бутони. Кабелите се показват на гърба, но ми харесва!

Също така пробих място за 7-сегментния дисплей, въртящия се енкодер и част от окабеляването на гърба. Изрязах дадо в горната част, за да държа LED лентата.

Стъпка 7: Копчета за копчета

Окабеляването на много бутони може да бъде истинска болка. За щастие хората, които правят аркадни машини, са измислили някои стандартни конектори, които можете да използвате. Всеки кабел за свързване на бутони има два проводника, един за VCC и един за заземяване. Единият край има конектори за лопатки, които пасват на проводниците на гърба на бутона - прикрепете земята към "нормално отворения" проводник, а VCC към "общия" проводник. В тази конфигурация, когато потребителят натисне бутона, веригата е завършена и микроконтролерът ще прочете HIGH на съответния входен щифт.

Другият край на кабела има JST конектор (малкото бяло нещо). Хубавото на тези съединители е, че те влизат в гнездото само по един начин, така че няма начин случайно да обърнете VCC и земята.

Това, което направих, е да изградя малко сбруя за тези конектори. Запоявам серия JST съдове върху парче протоборд и след това пускам кабели обратно към съединителите на Dupont, които ще включа в микроконтролера. Червеният проводник е VCC линията и се свързва с всички JST кутии. Сините проводници са тези, които са отделни за всеки бутон.

Стъпка 8: Ротационен енкодер

Ротационният енкодер позволява на потребителя да контролира скоростта на алгоритъма. Използвам модул, който се предлага като пробивна платка, включваща издърпващи се резистори за двете линии за данни (жълти проводници). Това също е бутон, но не използвам тази функция. Другите два проводника са VCC и заземени. Взех и хубаво дебело копче.

Това, което харесвам в ротационен енкодер, за разлика от потенциометъра, е, че той просто сигнализира въртенето (по часовниковата стрелка срещу часовниковата стрелка) към микроконтролера, така че е лесно да промените начина, по който се интерпретира стойността. Например, можете да му дадете усещане за ускорение (като мишка), когато потребителят го върти бързо.

Стъпка 9: 7-сегментен дисплей

Тук няма какво да се каже. Тези неща са навсякъде. Светодиодите се управляват от чип, наречен TM1637, който комуникира с микроконтролера чрез прост сериен протокол. Използвам съществуваща библиотека, която ми позволява да й кажа какъв номер искам да покажа, а тя прави останалото.

На гърба има четири пина: VCC, заземяване и два проводника за серийния протокол. Запоявах 4-пинов хедър, който се свързва със съответния конектор Dupont, свързан към микроконтролера.

Стъпка 10: Главна платка за контролер

Основната платка за управление съдържа самия микроконтролер и всички съединители към органите за управление (бутони, дисплей, светодиоди). Микроконтролерът е ESP32, който осигурява много изчислителна мощност и памет и излага много пинове. Окабеляването е доста стандартно, но ще посоча няколко интересни бита.

ЗАБЕЛЕЖКА: Може да искате да разгледате кода (https://github.com/samguyer/AlgorithmMachine), преди да започнете да окабелявате основната платка, така че конфигурацията на вашия щифт да съвпада с моята.

Запоявах жак на дъската за платка за захранване и свързах два меки жици с мека тел към захранващите и заземителните релси на дъската. Причината е, че LED лентата може да черпи много енергия, ако яркостта е настроена висока, и не искам да изтегля цялата тази мощност през USB конектора на микроконтролера.

За да опростя окабеляването на бутоните, запоявах лента от мъжки към женски правоъгълен хедър по цялата страна на микроконтролера (горната страна на платката, както е показано). Съединителите на Dupont от конектора на бутоните се включват директно в тази заглавка.

ВАЖНО: захранването на бутоните (червеният проводник) трябва да бъде свързано към захранващата линия 3.3V на микроконтролера. ESP32 е 3.3V чип, така че само 3.3V източници трябва да бъдат свързани към пиновете за данни.

Микроконтролерът черпи захранване (или избутва захранване) към релсите (долната страна на платката, както е показано) през 5V USB щифт и маса. Всички останали червени/черни проводници са VCC и заземени.

Двата сини проводника са линиите за данни за LED лентите (WS2812s). Жълтата/зелената двойка са линиите за данни за въртящия се енкодер, а жълтата двойка е серийната връзка към 7-сегментния дисплей.

Стъпка 11: Монтаж

Тази поредица от снимки показва окончателното сглобяване и окабеляване. Прикрепих и основната платка за управление към задната част в горната част.

Преди да го включа, направих няколко проверки, за да избегна неприятни изненади. По -специално, за да се уверя, че нямам връзки за захранване/заземяване назад и няма къси съединения. Настройте вашия мултицет да тества за непрекъснатост - той ще издава звуков сигнал, когато има електрически път между двата проводника. Прикрепете един проводник към общата VCC линия към бутоните. След това прикрепете другия проводник към всеки щифт на сбруята един по един. Мултицетът трябва да издава звуков сигнал само когато натиснете бутона. Ако получите други звукови сигнали, това означава, че имате обръщане или късо. Проследете го и го поправете, преди да включите захранването!

Стъпка 12: Код

Първо отворете вашата Arduino IDE и се уверете, че имате инсталирана библиотеката FastLED.

Изтеглете машинния код на алгоритъма от GitHub:

github.com/samguyer/AlgorithmMachine.git

Можете или да го клонирате директно във вашата папка Arduino, или да го копирате на ръка.

Преди да го качите, уверете се, че настройките на щифта съвпадат с вашата хардуерна конфигурация. Поставих всички настройки на пина в горната част на файла.

Качете и се наслаждавайте!

Стъпка 13: Как да използвате

Алгоритмичната машина е лесна за използване и почти всяка комбинация от бутони е ОК!

Първо, използвайте бутоните за данни, за да инициализирате стойностите в масива. Има три избора: (1) на случаен принцип, (2) добавяне на една произволна стойност и (3) обръщане на масива. Обърнете внимание, че стойностите са постоянни, така че можете да правите неща като първо да ги сортирате, след това да добавите малко шум, след това да изпълните различен алгоритъм за сортиране или търсене.

Изберете алгоритъм за търсене или сортиране от другите възможности за избор на бутони. Понастоящем няма обратна връзка, когато направите този избор (нещо за бъдеща работа). След това натиснете бутона "възпроизвеждане".

Копчето контролира скоростта. Можете също така да натиснете "play", за да поставите на пауза и да спрете алгоритъма.

Той ще спре автоматично, когато приключи. Можете също да натиснете друг бутон за алгоритъм по всяко време. Машината ще спре текущия алгоритъм и ще инициализира новия, но ще запази данните точно както ги е оставил предишният алгоритъм.

Голяма награда в конкурса STEM