Алгоритмная машина: 13 шагов (с изображениями)

2024 Автор: John Day | [email protected]. Последнее изменение: 2024-01-30 11:50

Я преподаю информатику в колледже в течение 15 лет, и, хотя мой опыт больше связан с программированием, я все еще трачу довольно много времени на изучение стандартных алгоритмов поиска и сортировки. С точки зрения обучения центральным вопросом является сложность вычислений: сколько времени требуется для каждого алгоритма, учитывая входные данные определенного размера? Но есть множество нюансов. Например, имеют ли алгоритмы разное время выполнения в зависимости от конкретных входных значений (в отличие от размера)? В каких случаях вы бы предпочли один алгоритм сортировки другому? Хотя мы обсуждаем эти вопросы абстрактно, меня всегда беспокоило, что нет простого способа увидеть, как разные алгоритмы работают в разных условиях.

Цели

Моей главной целью в этом проекте было создание интерактивного дисплея, на котором студенты могли бы визуализировать и исследовать алгоритмы. Я ограничился алгоритмами, которые работают с массивами значений (целыми числами), поэтому я могу использовать адресуемую светодиодную ленту RGB для визуализации содержимого массива. Массив состоит из 100 элементов, и каждому целому числу соответствует цвет в радужном порядке, поэтому сразу становится очевидным, когда массив отсортирован, частично отсортирован или рандомизирован. Однако помимо значений мне нужен был способ визуализировать управляющие аспекты алгоритма - например, какие элементы массива в настоящее время сравниваются или меняются местами.

Конкретные цели:

- Предоставлять различные алгоритмы поиска и сортировки

- Визуализируйте значения в массиве таким образом, чтобы подчеркнуть ход выполнения алгоритма

- Визуализировать алгоритм управления; в частности, рассматриваемые элементы.

- Разрешить пользователям выбирать шаблоны входных данных, а не всегда генерировать случайные значения

- Разрешить пользователям контролировать скорость и приостанавливать алгоритм

- Разрешить пользователям устанавливать оптимальное, наихудшее и среднее поведение (в зависимости от алгоритма).

- Показывать количество шагов по мере выполнения алгоритма

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

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

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

В остальном устройство простое с точки зрения электроники. Помимо двух светодиодных лент, есть несколько кнопок мгновенного действия, поворотный энкодер (для управления скоростью) и 7-сегментный дисплей (для отображения шагов). С таким количеством кнопок и элементов управления я решил использовать микроконтроллер ESP32, потому что он предоставляет много контактов и потому, что он довольно мощный. Я рассмотрю схему подключения, но она довольно проста. Вы, вероятно, могли бы сделать что-нибудь умное со сдвиговыми регистрами, если хотите использовать меньше контактов.

Вы можете изготовить корпус для этого устройства в самых разных формах. Изначально я представлял его как большую прямоугольную плату со светодиодной лентой сверху и сеткой кнопок посередине. Форма, к которой я пришел, вдохновлена своего рода взглядом на космические технологии 1960-х годов. Вы также можете построить его с помощью светодиодных лент в вертикальной ориентации. Или сделайте светодиодную часть намного больше - заполните всю стену - с отдельной панелью управления.

Программное обеспечение

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

Запасы

Электроника

1 плата разработки ESP32 (например, 2 светодиодные ленты WS2812 или аналогичные, плотность 100 светодиодов на метр (например, 1 кнопка "Пуск" в виде треугольника (например, 12 мгновенных кнопок (например, https://amzn.com/B01N4D4750) - разные формы, если хотите

1 упаковка (20) предварительно смонтированных кнопочных разъемов (например, 1 упаковка соединителей JST (например, 1 поворотный регулятор (например, 1 ручка для поворотного энкодера (например, 1 упаковка разъемов Dupont (например, https://amzn.com/B014YTPFT8) - также стоит приобрести инструмент для обжима.

1 разъем для бочки (для питания) (например, 1 7-сегментный цифровой дисплей TM1637 (например, Паяльное и электромонтажное оборудование

Файлы 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. Как это мило?! ??!

Вы можете спросить, кого волнуют миллионы или миллиарды входных данных? Подумайте: сколько пользователей на Facebook? Сколько веб-страниц индексирует Google? Сколько пар оснований содержится в геноме человека? Сколько измерений входит в моделирование погоды?

Шаг 2: алгоритмы

В настоящее время Algorithm Machine реализует следующие алгоритмы. Два из них - алгоритмы поиска (найти конкретное значение в списке), остальные - алгоритмы сортировки (расположить значения по порядку).

Линейный поиск

Просмотрите список значений по одному, начиная с начала. Требуется линейное время.

Бинарный поиск

Выполните поиск по списку, несколько раз разделив его пополам. Требуется время журнала, но для работы список должен быть отсортирован.

Пузырьковая сортировка

Отсортируйте список, постоянно меняя соседние элементы, которые не в порядке. Требуется квадратичное время.

Вставка сортировки

Отсортируйте список, поместив каждый элемент на свое место в списке уже отсортированных значений. Требуется квадратичное время.

Быстрая сортировка

Отсортируйте список, несколько раз разделив список пополам и переместив все значения меньше медианы в первую половину и все значения больше медианы во вторую половину. На практике мы не можем эффективно найти медиану, поэтому выбираем значение случайным образом. В результате этот алгоритм может быть квадратичным в худшем случае, но обычно требует времени N * logN.

Сортировка слиянием

Отсортируйте список, разделив его пополам, отсортировав две половины по отдельности (используя сортировку слиянием), а затем объединив их вместе, чередуя значения. Всегда требует времени N * logN.

Сортировка в куче

Отсортируйте список, создав структуру данных, называемую кучей, которая позволяет вам найти наименьшее значение во времени журнала. Всегда требует времени N * logN.

Битоническая сортировка

Подобно сортировке слиянием и быстрой сортировке, разделите список пополам, отсортируйте половинки и снова объедините их. Этот алгоритм требует времени N * logN * logN, но имеет то преимущество, что его легко распараллелить.

Шаг 3: Светодиодная панель: 3D-печать маски

Первым шагом в создании светодиодной панели является 3D-печать маски, которая придает свету их форму. Каждый модуль охватывает десять элементов массива, 10 значений (кружки) и 10 индикаторов (треугольники), так что всего вам понадобится 10 модулей. Предоставляемый мной файл STL содержит два экземпляра модуля, поэтому вам потребуется выполнить пять циклов печати. У меня нет лучшего 3D-принтера, поэтому мне пришлось вручную очистить их с помощью напильника и наждачной бумаги. Самое главное, чтобы круглые и треугольные отверстия были чистыми.

На фотографиях вы увидите мою тестовую установку: я приклеил две светодиодные ленты и подключил их к макетной плате с помощью микроконтроллера. В этом шаге нет необходимости, но я хотел посмотреть, как он будет выглядеть, прежде чем приступить к сборке корпуса. Я выровнял модули маски на двух светодиодных лентах и сделал простой набросок со случайными цветами. С полосой диффузионного материала формы и цвета действительно выделяются.

Шаг 4: альтернативы светодиодной панели

Когда я только начинал этот проект, я экспериментировал с другими способами изготовления светодиодной маски. Если у вас нет 3D-принтера, вы можете рассмотреть один из этих вариантов. Скажу честно: делать эти детали - огромная боль.

Для кругов я купил латунную трубку 13/32, которая почти ровно 1 см в диаметре. Я разрезал его на сто сегментов по 1 см и затем покрасил их в белый цвет.

Для треугольников я использовала толстую алюминиевую фольгу, вырезанную из одноразового противня. Я сделал треугольную форму из дерева, затем обернул ее короткими полосками фольги и приклеил их. Опять же, вам понадобится сотня таких вещей, так что это потребует времени и терпения.

Шаг 5: корпус светодиодной панели

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

Что касается диффузии, мне очень нравится Lee Filters # 216 (полностью белая диффузия). Это тонкий пластиковый лист, который обеспечивает равномерное рассеивание без потери большого количества света. Но это дорогое удовольствие. Иногда в Интернете можно найти листы меньшего размера, но весь рулон обойдется вам примерно в 125 долларов. Некоторые другие варианты - белая бумага или любой другой сатин или матовый пластик. Популярным выбором являются тонкие пластиковые коврики для резки.

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

Я начал сборку с прикручивания верхней части оргстекла к деревянным стенкам (см. Фото). Затем я перевернул его и поместил диффузионную полосу, а затем 10 частей маски. Как только я был доволен расстоянием, я приколол их на место несколькими точками горячего клея.

Затем положите две светодиодные ленты бок о бок поверх масок. Убедитесь, что светодиоды направлены вниз, и убедитесь, что каждый светодиод совпадает с соответствующим отверстием в маске. Добавьте немного горячего клея или ленты, чтобы удерживать светодиодные ленты на месте. Наконец, прикрутите заднюю панель из оргстекла.

Запустите тестовый шаблон. Хорошая работа! Вы сделали самое сложное!

Шаг 6: Панель управления

Панель управления предоставляет максимальную свободу творчества. Он просто должен содержать все элементы управления и электронику, а также светодиодную панель. Самая простая конструкция - это доски прямоугольной формы: просверлите отверстия под кнопки и элементы управления и прикрепите светодиодную планку. Мне нравится комбинировать дерево, оргстекло и другие материалы, чтобы создать что-то в стиле стимпанк / ретро-модерн. В данном случае я вырезал кусок сверхпрочного плексигласа, чтобы удерживать основные кнопки выбора алгоритма, и деревянную планку, чтобы удерживать остальную электронику. Я просверлил отверстия под размер кнопок аркады. Электропроводка видна сзади, но она мне нравится!

Я также просверлил место для 7-сегментного дисплея, поворотного энкодера и некоторых проводов на задней панели. Я вырезал дадо сверху, чтобы удерживать светодиодную панель.

Шаг 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), прежде чем приступить к подключению основной платы, чтобы ваша конфигурация контактов соответствовала моей.

Я припаял цилиндрический разъем к плате для питания и подключил два толстых медных провода к шинам питания и заземления на плате. Причина в том, что светодиодная полоса может потреблять много энергии, если яркость установлена высокой, и я не хочу, чтобы вся эта мощность проходила через USB-разъем на микроконтроллере.

Чтобы упростить разводку кнопок, я припаял полоску прямоугольного разъема «папа-мама» по всей стороне микроконтроллера (верхняя сторона платы, как показано). Разъемы Dupont от жгута проводов кнопок подключаются непосредственно к этому разъему.

ВАЖНО: питание кнопок (красный провод) должно быть подключено к линии питания 3,3 В на микроконтроллере. ESP32 представляет собой микросхему 3,3 В, поэтому к выводам данных следует подключать только источники 3,3 В.

Микроконтроллер потребляет питание (или подает питание) на шины (нижняя сторона платы, как показано) через вывод USB 5 В и землю. Все остальные красно-черные провода - это VCC и земля.

Два синих провода - это линии передачи данных для светодиодных лент (WS2812s). Желто-зеленая пара - это линии данных для поворотного энкодера, а желтая пара - это последовательное соединение с 7-сегментным дисплеем.

Шаг 11: Сборка

В этой серии фотографий показана окончательная сборка и электромонтаж. Я также прикрепил основную плату контроллера к задней части вверху.

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

Шаг 12: Код

Сначала откройте свою Arduino IDE и убедитесь, что у вас установлена библиотека FastLED.

Загрузите машинный код алгоритма с GitHub:

github.com/samguyer/AlgorithmMachine.git

Вы можете либо клонировать его прямо в папку Arduino, либо скопировать вручную.

Перед загрузкой убедитесь, что настройки контактов соответствуют конфигурации вашего оборудования. Я разместил все настройки контактов в верхней части файла.

Загрузите и наслаждайтесь!

Шаг 13: как использовать

Алгоритмическая машина проста в использовании, и подойдет практически любая комбинация кнопок!

Сначала используйте кнопки данных для инициализации значений в массиве. Есть три варианта: (1) рандомизировать, (2) добавить одно случайное значение и (3) перевернуть массив. Обратите внимание, что значения являются постоянными, поэтому вы можете сначала отсортировать их, затем добавить немного шума, а затем запустить другой алгоритм сортировки или поиска.

Выберите алгоритм поиска или сортировки из других вариантов кнопок. В настоящее время нет обратной связи, когда вы делаете этот выбор (что-то для будущей работы). Затем нажмите кнопку «Играть».

Ручка регулирует скорость. Вы также можете нажать «play», чтобы приостановить и возобновить работу алгоритма.

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

Главный приз конкурса STEM