A máquina de algoritmo: 13 etapas (com imagens)

2024 Autor: John Day | [email protected]. Última modificação: 2024-01-30 11:36

Tenho ensinado ciência da computação em nível universitário há 15 anos e, embora minha especialidade seja mais no lado de programação, ainda passo muito tempo cobrindo algoritmos padrão para pesquisa e classificação. Do ponto de vista do ensino, a questão central é a complexidade computacional: quanto tempo cada algoritmo requer, dada a entrada de um tamanho específico? Mas existem inúmeras nuances. Por exemplo, os algoritmos têm tempos de execução diferentes dependendo dos valores de entrada específicos (em oposição ao tamanho)? Em quais casos você escolheria um algoritmo de classificação em vez de outro? Embora discutamos essas questões em abstrato, sempre me incomodou que não houvesse uma maneira fácil de ver como algoritmos diferentes funcionam sob várias condições.

Metas

Meu objetivo geral para este projeto era criar uma tela interativa para os alunos visualizarem e explorarem algoritmos. Limitei-me a algoritmos que funcionam em matrizes de valores (inteiros), então posso usar uma faixa de LED RGB endereçável para visualizar o conteúdo da matriz. A matriz tem 100 elementos e cada inteiro é mapeado para uma cor na ordem do arco-íris, de modo que seja imediatamente óbvio quando a matriz é classificada, parcialmente classificada ou aleatória. Além dos valores, no entanto, eu queria uma maneira de visualizar os aspectos de controle do algoritmo - por exemplo, quais elementos do array estão sendo comparados ou trocados.

Os objetivos específicos são:

- Fornece uma variedade de algoritmos de pesquisa e classificação

- Visualize os valores na matriz de uma forma que destaque o progresso do algoritmo

- Visualize o controle do algoritmo; em particular, os elementos que estão sendo considerados.

- Permitir que os usuários escolham os padrões de dados de entrada em vez de sempre gerar valores aleatórios

- Permitir que os usuários controlem a velocidade e pausem o algoritmo

- Permitir que os usuários forcem o melhor caso, o pior caso, o comportamento médio (específico do algoritmo)

- Mostrar o número de etapas conforme o algoritmo prossegue

Visualização

Do ponto de vista de design físico, a parte mais interessante deste projeto é a visualização do array. Eu me esforcei para mostrar os dados e o controle e como construir o próprio dispositivo de exibição. Meu objetivo era mostrar os valores dos dados como círculos coloridos e os pontos de controle como setas coloridas que apontam para os valores dos dados. Após algumas experiências, decidi por um projeto com duas tiras paralelas de 100 LEDs RGB (WS2812) com uma máscara circular sobre cada LED de dados e uma máscara triangular sobre cada LED de controle. Fiz um modelo 3D da máscara com 10 pares de círculos e triângulos e, em seguida, imprimi em 3D 10 desses módulos para um total de 100 círculos e 100 triângulos. O tamanho e o espaçamento da minha máscara são projetados para tiras com 100 LEDs por metro. Os arquivos do modelo 3D são fornecidos posteriormente nesta descrição.

Eletrônica e gabinete

O resto do dispositivo é simples, do ponto de vista eletrônico. Além das duas faixas de LED, há vários botões momentâneos, um codificador rotativo (para o controle de velocidade) e um display de 7 segmentos (para mostrar as etapas). Com tantos botões e controles, optei por usar um microcontrolador ESP32 porque expõe muitos pinos e é bastante poderoso. Vou repassar a estratégia de fiação, mas é bem básica. Você provavelmente poderia fazer algo inteligente com registradores de deslocamento se quiser usar menos pinos.

Você pode construir o invólucro para este dispositivo em muitas formas diferentes. Inicialmente, imaginei-o como uma grande placa retangular com a faixa de LED na parte superior e uma grade de botões no meio. A forma que terminei é inspirada por uma espécie de visão dos anos 1960 da tecnologia da era espacial. Você também pode construí-lo com as tiras de LED na orientação vertical. Ou torne a parte LED muito maior - preencha uma parede inteira - com um painel de controle separado.

Programas

O código para este dispositivo está disponível gratuitamente no GitHub, e fiz o meu melhor para documentar como ele funciona e como configurá-lo. A única biblioteca externa de que você precisa é FastLED para acionar as tiras WS2812.

Suprimentos

Eletrônicos

1 placa de desenvolvimento ESP32 (por exemplo, 2 WS2812 ou tiras de LED semelhantes, densidade 100 LEDs por metro (por exemplo, 1 botão Triângulo "Iniciar" (por exemplo, 12 botões momentâneos (por exemplo, https://amzn.com/B01N4D4750) - formatos diferentes, se desejar

1 pacote (20) de conectores de botão com fio (por exemplo, 1 Pacote de conectores JST (por exemplo, 1 codificador rotativo (por exemplo, 1 botão para codificador rotativo (por exemplo, 1 Pack conectores Dupont (por exemplo, https://amzn.com/B014YTPFT8) - vale a pena obter a ferramenta de crimpagem também.

1 conector de barril (para alimentação) (por exemplo, 1 display numérico de 7 segmentos TM1637 (por exemplo, Equipamento de solda e fiação

Arquivos de modelo 3D

Você pode encontrar o modelo 3D para um par de módulos de 10 luzes no Thingiverse:

www.thingiverse.com/thing:4178181

Você precisará imprimir este modelo cinco vezes para um total de 10 módulos.

Programas

github.com/samguyer/AlgorithmMachine

Gabinete

Madeira, plexiglass, parafusos e parafusos de aço inoxidável

Material de difusão. Meu favorito é o Lee Filters # 216 difusão totalmente branca, mas há outras opções. Mesmo o papel branco comum faz um bom trabalho.

Etapa 1: Algoritmos 101

Muitas pessoas pensam que a ciência da computação é essencialmente o estudo da programação. Mas o verdadeiro coração e alma deste campo são os algoritmos: o estudo de procedimentos sistemáticos para resolver problemas e seu custo (normalmente, quanto tempo demoram). Figuras seminais no campo, como Alan Turing, Alonzo Church e Edsger Dijkstra, estavam pensando nessas ideias antes que os computadores como os conhecemos sequer existissem.

A principal característica de um algoritmo para resolver um problema específico é que ele é detalhado e preciso, de forma que alguém poderia usá-lo para obter uma solução sem entender como ele funciona; basta seguir os passos de forma mecânica e obterá a resposta certa. Você pode ver como isso ajuda na programação de computadores, já que eles precisam desse nível de detalhe. Um computador não pode preencher os detalhes que faltam ou fazer julgamentos, como uma pessoa pode.

Quanto tempo vai demorar?

Depois de termos um procedimento detalhado, uma pergunta natural é quanto tempo levará para obter a resposta? Não podemos usar unidades de tempo comuns, pois depende de quem está fazendo o trabalho (compare a rapidez com que uma pessoa pode computar algo com um supercomputador). Além disso, depende da quantidade de dados que temos. Claramente, leva mais tempo para pesquisar uma lista de um milhão de números de telefone do que uma lista de cem.

Para descrever o custo de um algoritmo, primeiro escolhemos alguma operação no procedimento que representa uma "etapa" - geralmente algo simples, como comparar ou adicionar dois números, que leva um determinado período de tempo para ser feito. Em seguida, criamos uma fórmula que descreve quantas etapas o algoritmo executará, dado um determinado número de itens de dados. Por razões históricas, quase sempre denotamos o número de itens de dados com N maiúsculo.

Por exemplo, examinar uma lista de N números de telefone requer N etapas. Examinar a lista duas vezes leva 2N etapas. Ambos são chamados de algoritmos de tempo linear - o número total de etapas é algum múltiplo do tamanho de entrada. Outros algoritmos são quadráticos (N ao quadrado) ou cúbicos (N ao cubo) ou logarítmicos (log N) ou alguma combinação destes. Alguns dos problemas computacionais mais difíceis requerem algoritmos de tempo exponencial (2 ^ N).

Tá, e daí?

Quando o número de itens de dados N é pequeno, não importa muito. Por exemplo, para N = 10, 10N é o nome de N ao quadrado. Mas e quanto a N = 1000? ou N = 1000000? Um milhão ao quadrado é um número muito grande. Mesmo em um computador muito rápido, um algoritmo quadrático pode demorar muito se a entrada for grande o suficiente. Algoritmos exponenciais são muito mais problemáticos: para N = 50, um algoritmo exponencial levaria duas semanas para terminar, mesmo em um computador onde cada etapa é de apenas um nanossegundo (1 bilionésimo de segundo). Ai!

No outro extremo da escala, temos algoritmos de tempo logarítmico, que são muito rápidos. O tempo de log é o oposto do tempo exponencial: dado o tamanho de entrada N, o número de etapas é o expoente T na fórmula 2 ^ T = N. Por exemplo, se nosso tamanho de entrada é um bilhão, então um algoritmo de tempo de log requer apenas 30 passos, uma vez que 2 ^ 30 = 1, 000, 000, 000. Quão doce é isso?! ??!

Você deve estar se perguntando: quem se importa com os tamanhos de entrada de milhões ou bilhões? Pense nisso: quantos usuários existem no Facebook? Quantas páginas da web são indexadas pelo Google? Quantos pares de bases existem no genoma humano? Quantas medições vão para uma simulação do tempo?

Etapa 2: os algoritmos

A Máquina de Algoritmo atualmente implementa os seguintes algoritmos. Dois deles são algoritmos de pesquisa (encontre um valor específico na lista), o resto são algoritmos de classificação (coloque os valores em ordem).

Pesquisa linear

Pesquise na lista de valores um por um, começando do início. Requer tempo linear.

Busca binária

Pesquise uma lista dividindo-a repetidamente ao meio. Requer tempo de registro, mas a lista deve ser classificada para que funcione.

Tipo de bolha

Classifique uma lista trocando repetidamente os elementos vizinhos que não estão em ordem. Requer tempo quadrático.

Classificação de inserção

Classifique uma lista colocando cada elemento em seu devido lugar na lista de valores já classificados. Requer tempo quadrático.

Ordenação rápida

Classifique uma lista dividindo-a repetidamente pela metade e movendo todos os valores menores que a mediana para a primeira metade e todos os valores maiores que a mediana para a segunda metade. Na prática, não podemos encontrar a mediana com eficiência, então escolhemos um valor aleatoriamente. Como resultado, esse algoritmo pode ser quadrático no pior caso, mas normalmente requer tempo N * logN.

Mesclar classificação

Classifique uma lista dividindo-a ao meio, classificando as duas metades separadamente (usando classificação por mesclagem) e, em seguida, mesclando-as intercalando os valores. Sempre requer tempo N * logN.

Classificação de heap

Classifique uma lista construindo uma estrutura de dados chamada heap, que permite encontrar o menor valor em tempo de log. Sempre requer tempo N * logN.

Tipo bitônico

Semelhante a merge sort e quicksort, divida uma lista ao meio, classifique as metades e recombine-as. Este algoritmo requer tempo N * logN * logN, mas tem a vantagem de ser fácil de paralelizar.

Etapa 3: Barra de LED: impressão 3D da máscara

A primeira etapa na construção da barra de LED é imprimir em 3D a máscara que dá forma às luzes. Cada módulo cobre dez elementos da matriz, 10 valores (círculos) e 10 indicadores (triângulos), portanto, você precisará de 10 módulos no total. O arquivo STL que estou fornecendo aqui contém duas instâncias do módulo, portanto, você precisará fazer cinco ciclos de impressão. Não tenho a melhor impressora 3D, então tive que fazer uma limpeza manual nelas usando um arquivo e uma lixa. O mais importante é que os orifícios circulares e triangulares estejam limpos.

Nas fotos você verá minha configuração de teste: Prendi as duas tiras de LED e as conectei a uma placa de ensaio com um microcontrolador. Essa etapa não é necessária, mas eu queria ver como ficaria antes de começar a montar o gabinete. Alinhei os módulos de máscara nas duas faixas de LED e fiz um esboço simples com cores aleatórias. Com uma tira de material de difusão as formas e cores realmente se destacam.

Etapa 4: alternativas de barra de LED

Quando comecei este projeto, experimentei outras maneiras de fazer a máscara de LED. Se você não tiver uma impressora 3D, pode considerar uma dessas opções. Vou ser sincero: é uma dor enorme fazer essas peças.

Para os círculos, comprei um tubo de latão 13/32, que tem quase exatamente 1cm de diâmetro. Cortei em cem segmentos de 1 cm e depois pintei de branco com spray.

Para os triângulos, usei uma folha de alumínio pesada cortada de uma assadeira descartável. Fiz uma forma triangular de madeira, enrolei pequenas tiras de papel alumínio em volta da forma e as colei com fita adesiva. Novamente, você precisará de uma centena dessas coisas, então isso requer algum tempo e paciência.

Etapa 5: Caixa de barra de LED

Meu gabinete é bastante simples: duas tiras de madeira para as laterais e duas tiras de acrílico para a parte superior e inferior. Todas as peças têm cerca de 102 cm de comprimento (1 metro para os LEDs, mais um pequeno extra para acomodar a fiação). As laterais devem ser um pouco mais altas do que 1 cm para abrir espaço para as tiras de LED. Depois de cortar as tiras, coloquei as peças da máscara impressa em 3D entre elas para medir a largura do acrílico. Corte dois pedaços de acrílico na largura e no comprimento da barra. Finalmente, corte uma tira do material de difusão para caber na máscara.

Para difusão, eu realmente gosto de Lee Filters # 216 (difusão totalmente branca). É uma fina folha de plástico que dá difusão uniforme sem perder muita luz. Mas é um material caro. Às vezes, você pode encontrar folhas menores à venda online, mas um rolo inteiro custará cerca de US $ 125. Algumas outras opções são papel branco ou qualquer outro tipo de plástico acetinado ou fosco. Uma escolha popular são as esteiras de corte de plástico finas.

Antes de montar a barra de LED, certifique-se de ter os conectores apropriados soldados às tiras de LED. Muitas tiras vêm com cabos pré-soldados, então você pode usá-los.

Comecei a montagem aparafusando a parte superior de acrílico nas laterais de madeira (ver foto). Então, virei e coloquei a faixa de difusão, seguida pelas 10 peças da máscara. Quando fiquei satisfeito com o espaçamento, prendi-os no lugar com alguns pontos de cola quente.

Em seguida, coloque as duas faixas de LED lado a lado sobre as máscaras. Certifique-se de que os LEDs estejam voltados para baixo e que cada LED esteja alinhado com o orifício correspondente na máscara. Adicione um pouco de cola quente ou fita para segurar as tiras de LED no lugar. Finalmente, aparafuse a parte de trás do acrílico.

Execute um padrão de teste. Bom trabalho! Você fez a parte mais difícil!

Etapa 6: Painel de Controle

O painel de controle é a parte que oferece a maior liberdade criativa. Ele só precisa conter todos os controles e eletrônicos, junto com a barra de LED. O design mais simples são placas retangulares: faça furos para os botões e controles e prenda a barra de LED. Gosto de combinar madeira, plexiglass e outros materiais para dar uma aparência tipo steampunk / retro-moderna. Neste caso, cortei um pedaço de acrílico resistente para segurar os botões de escolha do algoritmo principal e uma barra de madeira para segurar o resto da eletrônica. Fiz furos para combinar com o tamanho dos botões do fliperama. A fiação mostra na parte de trás, mas eu gosto!

Também perfurei espaço para o display de 7 segmentos, o codificador rotativo e parte da fiação na parte traseira. Cortei um dado na parte superior para segurar a barra de LED.

Etapa 7: Chicote de Botões

Conectar muitos botões pode ser uma verdadeira dor. Felizmente, as pessoas que fazem máquinas de arcade criaram alguns conectores padrão que você pode usar. Cada cabo de conector de botão tem dois fios, um para VCC e outro para aterramento. Uma das extremidades tem conectores tipo espada que se encaixam nos fios na parte de trás do botão - conecte o aterramento ao fio "normalmente aberto" e o VCC ao fio "comum". Nesta configuração, quando o usuário pressiona o botão, o circuito é concluído e o microcontrolador lê HIGH no pino de entrada correspondente.

A outra ponta do cabo tem um conector JST (a coisinha branca). O que é bom sobre esses conectores é que eles só entram no receptáculo de uma maneira, portanto, não há como inverter acidentalmente o VCC e o aterramento.

O que fiz foi construir um pequeno arnês para esses conectores. Eu soldo uma série de receptáculos JST em um pedaço de protoboard e, em seguida, passo os fios de volta para os conectores Dupont que irei conectar ao microcontrolador. O fio vermelho é a linha VCC e se conecta a todas as tomadas JST. Os fios azuis são aqueles separados para cada botão.

Etapa 8: Codificador Rotativo

O codificador rotativo permite que o usuário controle a velocidade do algoritmo. Eu uso um módulo que vem como uma placa de breakout que inclui resistores pull-up para as duas linhas de dados (fios amarelos). Este também é um botão, mas não estou usando esse recurso. Os outros dois fios são VCC e terra. Eu também tenho um bom botão gordo.

O que eu gosto em um codificador rotativo, ao contrário de um potenciômetro, é que ele apenas sinaliza a rotação (no sentido horário vs anti-horário) para o microcontrolador, então é fácil mudar como o valor é interpretado. Por exemplo, você pode dar uma sensação de aceleração (como um mouse) quando o usuário está girando rapidamente.

Etapa 9: display de 7 segmentos

Não há muito a dizer aqui. Essas coisas estão por toda parte. Os LEDs são controlados por um chip denominado TM1637, que se comunica com o microcontrolador por meio de um protocolo serial simples. Eu uso uma biblioteca existente que me permite dizer qual número desejo mostrar e ela faz o resto.

A parte traseira tem quatro pinos: VCC, terra e dois fios para o protocolo serial. Soldei um pedaço de conector de 4 pinos, que se conecta a um conector Dupont correspondente ligado ao microcontrolador.

Etapa 10: Placa do controlador principal

A placa controladora principal hospeda o próprio microcontrolador e todos os conectores para os controles (botões, display, LEDs). O microcontrolador é um ESP32, que fornece muito poder de computação e memória, e expõe muitos pinos. A fiação é bem padrão, mas vou apontar alguns pontos interessantes.

NOTA: Você pode querer olhar o código (https://github.com/samguyer/AlgorithmMachine) antes de iniciar a fiação da placa principal, para que a configuração do seu pino corresponda à minha.

Eu soldei um conector de barril na placa para alimentação e conectei dois fios de cobre robustos aos trilhos de alimentação e aterramento da placa. O motivo é que a barra de LED pode consumir muita energia se o brilho estiver alto, e não quero extrair toda essa energia do conector USB no microcontrolador.

Para simplificar a fiação do botão, soldei uma tira de cabeçote em ângulo reto macho-fêmea em todo o lado do microcontrolador (lado superior da placa, conforme mostrado). Os conectores Dupont do chicote de botões se encaixam diretamente neste conector.

IMPORTANTE: a alimentação dos botões (o fio vermelho) deve ser conectada à linha de alimentação de 3,3 V do microcontrolador. O ESP32 é um chip de 3,3 V, portanto, apenas fontes de 3,3 V devem ser conectadas aos pinos de dados.

O microcontrolador puxa energia (ou empurra energia) para os trilhos (lado inferior da placa, conforme mostrado) por meio do pino USB de 5 V e aterramento. Todos os outros fios vermelho / preto são VCC e aterramento.

Os dois fios azuis são as linhas de dados para as tiras de LED (WS2812s). O par amarelo / verde são as linhas de dados para o codificador rotativo e o par amarelo é a conexão serial para o display de 7 segmentos.

Etapa 11: Montagem

Esta série de fotos mostra a montagem final e a fiação. Também anexei a placa controladora principal na parte superior traseira.

Antes de ligá-lo, fiz algumas verificações para evitar surpresas desagradáveis. Em particular, para ter certeza de que não havia conectores de alimentação / aterramento invertidos e nenhum curto-circuito. Configure o multímetro para testar a continuidade - ele emitirá um bipe quando houver um caminho elétrico entre os dois terminais. Conecte um cabo à linha VCC comum aos botões. Em seguida, conecte o outro cabo a cada pino do chicote, um por um. O multímetro só deve emitir um bipe quando você pressiona o botão. Se você receber qualquer outro sinal sonoro, significa que houve uma reversão ou um curto. Rastreie e conserte antes de ligar a energia!

Etapa 12: Código

Primeiro, abra seu Arduino IDE e certifique-se de ter a biblioteca FastLED instalada.

Baixe o código da máquina do algoritmo do GitHub:

github.com/samguyer/AlgorithmMachine.git

Você pode cloná-lo diretamente na pasta Arduino ou copiá-lo manualmente.

Antes de carregá-lo, certifique-se de que as configurações de pinos correspondem à configuração de seu hardware. Coloquei todas as configurações de pinos na parte superior do arquivo.

Faça upload e divirta-se!

Etapa 13: como usar

A Máquina de Algoritmo é simples de usar e quase qualquer combinação de botões é adequada!

Primeiro, use os botões de dados para inicializar os valores na matriz. Existem três opções: (1) randomizar, (2) adicionar um valor aleatório e (3) inverter a matriz. Observe que os valores são persistentes, portanto, você pode fazer coisas como classificá-los primeiro, adicionar algum ruído e, em seguida, executar uma classificação diferente ou algoritmo de pesquisa.

Escolha um algoritmo de pesquisa ou classificação entre as outras opções de botão. Atualmente, não há feedback quando você faz essa escolha (algo para trabalho futuro). Em seguida, aperte o botão "play".

O botão controla a velocidade. Você também pode clicar em "reproduzir" para pausar e retomar o algoritmo.

Ele irá parar automaticamente quando terminar. Você também pode clicar em outro botão de algoritmo a qualquer momento. A máquina irá parar o algoritmo atual e inicializar o novo, mas manterá os dados exatamente como o algoritmo anterior os deixou.

Grande Prêmio no Concurso STEM