La máquina de algoritmos: 13 pasos (con imágenes)

2024 Autor: John Day | [email protected]. Última modificación: 2024-01-30 08:41

He estado enseñando ciencias de la computación a nivel universitario durante 15 años, y aunque mi experiencia está más en el lado de la programación, todavía dedico bastante tiempo a cubrir algoritmos estándar para buscar y clasificar. Desde el punto de vista de la enseñanza, la cuestión central es la complejidad computacional: ¿cuánto tiempo requiere cada algoritmo, dada una entrada de un tamaño particular? Pero hay numerosos matices. Por ejemplo, ¿los algoritmos tienen diferentes tiempos de ejecución dependiendo de los valores de entrada específicos (en contraposición al tamaño)? ¿En qué casos elegiría un algoritmo de clasificación sobre otro? Aunque discutimos estos temas en abstracto, siempre me molestó que no hubiera una manera fácil de ver cómo funcionan los diferentes algoritmos en diversas condiciones.

Metas

Mi objetivo principal para este proyecto era crear una pantalla interactiva para que los estudiantes visualizaran y exploraran algoritmos. Me limité a algoritmos que funcionan en matrices de valores (enteros), por lo que puedo usar una tira de LED RGB direccionable para visualizar el contenido de la matriz. La matriz tiene 100 elementos y cada número entero se asigna a un color en el orden del arco iris, por lo que es inmediatamente obvio cuando la matriz se ordena, se ordena parcialmente o se aleatoriza. Sin embargo, además de los valores, quería una forma de visualizar los aspectos de control del algoritmo, por ejemplo, qué elementos de la matriz se están comparando o intercambiando actualmente.

Los objetivos específicos son:

- Proporcionar una variedad de algoritmos de búsqueda y clasificación.

- Visualice los valores en la matriz de una manera que resalte el progreso del algoritmo

- Visualizar el control del algoritmo; en particular, los elementos que se están considerando.

- Permitir a los usuarios elegir los patrones de datos de entrada en lugar de generar siempre valores aleatorios

- Permitir a los usuarios controlar la velocidad y pausar el algoritmo

- Permitir a los usuarios forzar el mejor, el peor de los casos, el comportamiento del caso promedio (específico del algoritmo)

- Muestra el número de pasos a medida que avanza el algoritmo.

Visualización

Desde el punto de vista del diseño físico, la parte más interesante de este proyecto es la visualización de la matriz. Luché con cómo mostrar los datos y el control, y cómo construir el dispositivo de visualización en sí. Mi objetivo era mostrar los valores de los datos como círculos de colores y los puntos de control como flechas de colores que apuntan a los valores de los datos. Después de un poco de experimentación, me decidí por un diseño con dos tiras paralelas de 100 LED RGB (WS2812) con una máscara circular sobre cada LED de datos y una máscara triangular sobre cada LED de control. Hice un modelo 3D de la máscara con 10 pares de círculos y triángulos, y luego imprimí en 3D 10 de estos módulos para un total de 100 círculos y 100 triángulos. El tamaño y el espaciado de mi máscara están diseñados para tiras con 100 LED por metro. Los archivos del modelo 3D se proporcionan más adelante en esta descripción.

Electrónica y envolvente

El resto del dispositivo es sencillo, desde el punto de vista de la electrónica. Además de las dos tiras de LED, hay un montón de botones momentáneos, un codificador giratorio (para el control de velocidad) y una pantalla de 7 segmentos (para mostrar los pasos). Con tantos botones y controles, opté por usar un microcontrolador ESP32 porque expone muchos pines y porque es bastante potente. Repasaré la estrategia de cableado, pero es bastante básica. Probablemente podría hacer algo inteligente con los registros de desplazamiento si desea usar menos pines.

Puede construir el gabinete para este dispositivo de muchas formas diferentes. Inicialmente lo imaginé como un tablero rectangular grande con la tira de LED en la parte superior y una cuadrícula de botones en el medio. La forma con la que terminé está inspirada en una especie de visión de la tecnología de la era espacial de los años sesenta. También puede construirlo con las tiras de LED en orientación vertical. O haga que la parte LED sea mucho más grande, llene una pared completa, con un panel de control separado.

Software

El código para este dispositivo está disponible gratuitamente en GitHub, y he hecho todo lo posible para documentar cómo funciona y cómo configurarlo. La única biblioteca externa que necesita es FastLED para controlar las tiras WS2812.

Suministros

Electrónica

1 placa de desarrollo ESP32 (por ejemplo, 2 tiras de LED WS2812 o similares, densidad 100 LED por metro (por ejemplo, 1 botón de "inicio" de triángulo (p. Ej., 12 botones momentáneos (por ejemplo, https://amzn.com/B01N4D4750): diferentes formas si lo desea

1 paquete (20) conectores de botón precableados (por ejemplo, 1 paquete de conectores JST (por ejemplo, 1 codificador rotatorio (por ejemplo, 1 mando para codificador rotatorio (por ejemplo, 1 paquete de conectores Dupont (por ejemplo, https://amzn.com/B014YTPFT8); también vale la pena adquirir la herramienta de engarzado.

1 conector de barril (para alimentación) (por ejemplo, 1 pantalla numérica de 7 segmentos TM1637 (por ejemplo, Equipo de soldadura y cableado

Archivos de modelo 3D

Puede encontrar el modelo 3D para un par de módulos de 10 luces en Thingiverse:

www.thingiverse.com/thing:4178181

Deberá imprimir este modelo cinco veces para un total de 10 módulos.

Software

github.com/samguyer/AlgorithmMachine

Recinto

Madera, plexiglás, pernos y tornillos de acero inoxidable

Material de difusión. Mi favorito es Lee Filters # 216 de difusión completa en blanco, pero hay otras opciones. Incluso el papel blanco normal hace un buen trabajo.

Paso 1: Algoritmos 101

Mucha gente piensa que la informática es esencialmente el estudio de la programación. Pero el verdadero corazón y alma de este campo son los algoritmos: el estudio de procedimientos sistemáticos para resolver problemas y su costo (típicamente, cuánto tiempo toman). Figuras fundamentales en el campo, como Alan Turing, Alonzo Church y Edsger Dijkstra, pensaban en estas ideas antes de que existieran las computadoras tal como las conocemos.

La característica clave de un algoritmo para resolver un problema en particular es que es detallado y preciso, de modo que alguien podría usarlo para obtener una solución sin comprender en absoluto cómo funciona; simplemente siga los pasos de forma mecánica y obtendrá la respuesta correcta. Puede ver cómo esto ayuda con la programación de computadoras, ya que necesitan este nivel de detalle. Una computadora no puede completar los detalles que faltan o emitir juicios, como lo hace una persona.

¿Cuánto tiempo tardará?

Una vez que tenemos un procedimiento detallado, una pregunta natural es cuánto tiempo tomará obtener la respuesta. No podemos usar unidades de tiempo ordinarias, ya que depende de quién está haciendo el trabajo (compare qué tan rápido una persona podría calcular algo con una supercomputadora). Además, depende de la cantidad de datos que tengamos. Claramente, se necesita más tiempo para buscar en una lista de un millón de números de teléfono que en una lista de cien.

Para describir el costo de un algoritmo, primero elegimos alguna operación en el procedimiento que representa un "paso", generalmente algo simple, como comparar o sumar dos números, que requiere una cantidad fija de tiempo. Luego, creamos una fórmula que describe cuántos pasos tomará el algoritmo dada una cierta cantidad de elementos de datos. Por razones históricas, casi siempre denotamos el número de elementos de datos con una N mayúscula.

Por ejemplo, mirar a través de una lista de N números de teléfono requiere N pasos. Mirar la lista dos veces requiere 2N pasos. Ambos se denominan algoritmos de tiempo lineal: el número total de pasos es un múltiplo del tamaño de entrada. Otros algoritmos son cuadráticos (N tiempo al cuadrado) o cúbicos (N al cubo) o logarítmicos (log N) o alguna combinación de estos. Algunos de los problemas computacionales más difíciles requieren algoritmos de tiempo exponencial (2 ^ N).

¿OK y eso qué?

Cuando el número de elementos de datos N es pequeño, no importa mucho. Por ejemplo, para N = 10, 10N es ese nombre como N al cuadrado. Pero, ¿qué pasa con N = 1000? o N = 1000000? Un millón al cuadrado es un número bastante grande. Incluso en una computadora muy rápida, un algoritmo cuadrático puede llevar mucho tiempo si la entrada es lo suficientemente grande. Los algoritmos exponenciales son mucho más problemáticos: para N = 50, un algoritmo exponencial tardaría dos semanas en completarse incluso en una computadora donde cada paso es de solo un nanosegundo (una mil millonésima de segundo). ¡Ay!

En el otro extremo de la escala tenemos algoritmos de tiempo logarítmico, que son muy rápidos. El tiempo de registro es lo opuesto al tiempo exponencial: dado el tamaño de entrada N, el número de pasos es el exponente T en la fórmula 2 ^ T = N. Por ejemplo, si nuestro tamaño de entrada es mil millones, entonces un algoritmo de tiempo de registro solo requiere 30 pasos, ya que 2 ^ 30 = 1, 000, 000, 000. ¡¿Qué dulce es eso?! ??!

Quizás se esté preguntando, ¿a quién le importan los tamaños de entrada de millones o miles de millones? Piénselo: ¿cuántos usuarios hay en Facebook? ¿Cuántas páginas web indexa Google? ¿Cuántos pares de bases hay en el genoma humano? ¿Cuántas mediciones se incluyen en una simulación meteorológica?

Paso 2: los algoritmos

La máquina de algoritmos actualmente implementa los siguientes algoritmos. Dos de ellos son algoritmos de búsqueda (encuentre un valor particular en la lista), el resto son algoritmos de clasificación (ponga los valores en orden).

Búsqueda lineal

Busque en la lista de valores uno por uno comenzando desde el principio. Requiere tiempo lineal.

Búsqueda binaria

Busque una lista dividiéndola repetidamente por la mitad. Requiere tiempo de registro, pero la lista debe estar ordenada para que funcione.

Ordenamiento de burbuja

Ordene una lista intercambiando repetidamente elementos vecinos que no estén en orden. Requiere tiempo cuadrático.

Tipo de inserción

Ordene una lista colocando cada elemento en su lugar apropiado en la lista de valores ya ordenados. Requiere tiempo cuadrático.

Ordenación rápida

Ordene una lista dividiendo repetidamente la lista por la mitad y moviendo todos los valores menores que la mediana a la primera mitad y todos los valores mayores que la mediana a la segunda mitad. En la práctica, no podemos encontrar la mediana de manera eficiente, por lo que elegimos un valor al azar. Como resultado, este algoritmo puede ser cuadrático en el peor de los casos, pero normalmente requiere un tiempo N * logN.

Combinar ordenación

Ordene una lista dividiéndola por la mitad, clasificando las dos mitades por separado (usando la clasificación por combinación) y luego combinándolas entrelazando los valores. Siempre requiere tiempo N * logN.

Tipo de pila

Ordene una lista construyendo una estructura de datos llamada montón, que le permite encontrar el valor más pequeño en el tiempo de registro. Siempre requiere tiempo N * logN.

Tipo bitónico

Similar a fusionar ordenación y ordenación rápida, divida una lista por la mitad, ordene las mitades y vuelva a combinarlas. Este algoritmo requiere un tiempo N * logN * logN, pero tiene la ventaja de que es fácil de paralelizar.

Paso 3: Barra de LED: imprima la máscara en 3D

El primer paso para construir la barra de LED es imprimir en 3D la máscara que da forma a las luces. Cada módulo cubre diez elementos de la matriz, 10 valores (círculos) y 10 indicadores (triángulos), por lo que necesitará 10 módulos en total. El archivo STL que proporciono aquí contiene dos instancias del módulo, por lo que deberá realizar cinco ciclos de impresión. No tengo la mejor impresora 3D, así que tuve que limpiarlas manualmente con una lima y papel de lija. Lo más importante es que los agujeros circulares y triangulares estén limpios.

En las fotos, verá mi configuración de prueba: pegué las dos tiras de LED y las conecté a una placa de pruebas con un microcontrolador. Este paso no es necesario, pero quería ver cómo se vería antes de comenzar a ensamblar el gabinete. Alineé los módulos de máscara en las dos tiras de LED y ejecuté un boceto simple con colores aleatorios. Con una tira del material de difusión, las formas y los colores realmente resaltan.

Paso 4: Alternativas de barras LED

Cuando comencé este proyecto, experimenté con otras formas de hacer la máscara LED. Si no tiene una impresora 3D, podría considerar una de estas opciones. Seré honesto: es un gran dolor hacer estas piezas.

Para los círculos, compré un tubo de latón 13/32, que tiene casi exactamente 1 cm de diámetro. Lo corté en cien segmentos de 1 cm y luego los pinté con spray de blanco.

Para los triángulos, utilicé papel de aluminio grueso cortado de una bandeja para hornear desechable. Hice una forma triangular de madera, luego envolví tiras cortas de papel de aluminio alrededor de la forma y las pegué. Nuevamente, necesitará cien de estas cosas, por lo que se necesita algo de tiempo y paciencia.

Paso 5: Caja de barra LED

Mi cerramiento es bastante simple: dos listones de madera para los lados y dos listones de plexiglás para la parte superior e inferior. Todas las piezas miden unos 102 cm de largo (1 metro para los LED, más un poco más para acomodar el cableado). Los lados deben medir un poco más de 1 cm para dejar espacio para las tiras de LED. Después de cortar las tiras, coloqué las piezas de la máscara impresas en 3D entre ellas para medir el ancho del plexiglás. Corta dos piezas de plexiglás del ancho y largo de la barra. Finalmente, corte una tira del material de difusión para que encaje sobre la máscara.

Para la difusión, me gusta mucho Lee Filters # 216 (difusión blanca completa). Es una fina lámina de plástico que da una difusión uniforme sin perder mucha luz. Pero es algo caro. A veces puede encontrar hojas más pequeñas a la venta en línea, pero un rollo completo le costará alrededor de $ 125. Algunas otras opciones son papel blanco o cualquier otro tipo de plástico satinado o esmerilado. Una opción popular son las esteras de corte de plástico delgadas.

Antes de ensamblar la barra de LED, asegúrese de tener los conectores adecuados soldados a las tiras de LED. Muchas tiras vienen con cables presoldados, por lo que puede usarlos.

Comencé el montaje atornillando la pieza superior de plexiglás en los lados de madera (ver foto). Luego le di la vuelta y coloqué la tira de difusión, seguida de las 10 piezas de máscara. Una vez que estuve satisfecho con el espaciado, los fijé en su lugar con algunos puntos de pegamento termofusible.

A continuación, coloque las dos tiras de LED una al lado de la otra sobre las máscaras. Asegúrese de que los LED estén hacia abajo y asegúrese de que cada LED se alinee con el orificio correspondiente en la máscara. Agregue un poco de pegamento caliente o cinta adhesiva para mantener las tiras de LED en su lugar. Finalmente, atornille la pieza trasera de plexiglás.

Ejecute un patrón de prueba. ¡Buen trabajo! ¡Has hecho la parte más difícil!

Paso 6: Panel de control

El panel de control es la parte que ofrece mayor libertad creativa. Solo necesita contener todos los controles y la electrónica, junto con la barra LED. El diseño más simple es un tablero rectangular: taladre agujeros para los botones y controles, y coloque la barra LED. Me gusta combinar madera, plexiglás y otros materiales para dar una especie de estilo steampunk / retro-moderno. En este caso, corté un trozo de plexiglás resistente para sujetar los botones de elección del algoritmo principal y una barra de madera para sujetar el resto de la electrónica. Perforé agujeros para que coincidieran con el tamaño de los botones de la sala de juegos. El cableado se ve en la parte de atrás, ¡pero me gusta!

También perforé espacio para la pantalla de 7 segmentos, el codificador rotatorio y parte del cableado en la parte posterior. Corté una ranura en la parte superior para sostener la barra LED.

Paso 7: arnés de botones

Conectar muchos botones puede ser un verdadero dolor de cabeza. Afortunadamente, las personas que fabrican máquinas recreativas han creado algunos conectores estándar que puedes usar. Cada cable conector de botón tiene dos cables, uno para VCC y otro para tierra. Un extremo tiene conectores de pala que se ajustan a los cables en la parte posterior del botón; conecte la tierra al cable "normalmente abierto" y VCC al cable "común". En esta configuración, cuando el usuario presiona el botón, el circuito se completa y el microcontrolador leerá ALTO en el pin de entrada correspondiente.

El otro extremo del cable tiene un conector JST (la cosita blanca). Lo bueno de estos conectores es que solo entran en el receptáculo de una manera, por lo que no hay forma de invertir accidentalmente VCC y tierra.

Lo que hice fue construir un pequeño arnés para estos conectores. Sueldo una serie de receptáculos JST en una pieza de protoboard y luego paso los cables de regreso a los conectores Dupont que conectaré al microcontrolador. El cable rojo es la línea VCC y se conecta a todos los receptáculos JST. Los cables azules son los que están separados para cada botón.

Paso 8: codificador rotatorio

El codificador rotatorio permite al usuario controlar la velocidad del algoritmo. Utilizo un módulo que viene como una placa de conexión que incluye resistencias pull-up para las dos líneas de datos (cables amarillos). Este también es un botón, pero no estoy usando esa función. Los otros dos cables son VCC y tierra. También tengo una bonita perilla gorda.

Lo que me gusta de un codificador rotatorio, a diferencia de un potenciómetro, es que solo indica la rotación (en el sentido de las agujas del reloj o en el sentido contrario) al microcontrolador, por lo que es fácil cambiar la forma en que se interpreta el valor. Por ejemplo, puede darle una sensación de aceleración (como un mouse) cuando el usuario lo gira rápidamente.

Paso 9: pantalla de 7 segmentos

No hay mucho que decir aquí. Estas cosas están en todas partes. Los LED están controlados por un chip llamado TM1637, que se comunica con el microcontrolador a través de un simple protocolo en serie. Utilizo una biblioteca existente que me permite decirle qué número quiero mostrar y hace el resto.

La parte trasera tiene cuatro pines: VCC, tierra y dos cables para el protocolo serial. Soldé una pieza de cabezal de 4 pines, que se conecta a un conector Dupont correspondiente cableado al microcontrolador.

Paso 10: placa del controlador principal

La placa controladora principal alberga el microcontrolador en sí y todos los conectores a los controles (botones, pantalla, LED). El microcontrolador es un ESP32, que proporciona mucha potencia de cálculo y memoria, y expone muchos pines. El cableado es bastante estándar, pero señalaré algunos puntos interesantes.

NOTA: Es posible que desee ver el código (https://github.com/samguyer/AlgorithmMachine) antes de comenzar a cablear la placa principal, para que la configuración de su pin coincida con la mía.

Soldé un conector de barril a la placa para obtener energía y conecté dos cables de cobre fornidos a los rieles de energía y tierra de la placa. La razón es que la barra de LED puede consumir mucha energía si el brillo se establece alto, y no quiero extraer toda esa energía a través del conector USB del microcontrolador.

Para simplificar el cableado del botón, soldé una tira de cabezal en ángulo recto de macho a hembra por todo el lado del microcontrolador (lado superior de la placa como se muestra). Los conectores Dupont del arnés de botones se conectan directamente a este encabezado.

IMPORTANTE: la alimentación de los botones (el cable rojo) debe conectarse a la línea de alimentación de 3,3 V del microcontrolador. El ESP32 es un chip de 3.3V, por lo que solo se deben conectar fuentes de 3.3V a los pines de datos.

El microcontrolador extrae energía (o empuja energía) a los rieles (lado inferior de la placa como se muestra) a través del pin USB de 5V y tierra. Todos los demás cables rojo / negro son VCC y tierra.

Los dos cables azules son las líneas de datos de las tiras de LED (el WS2812). El par amarillo / verde son las líneas de datos para el codificador rotatorio y el par amarillo son la conexión en serie a la pantalla de 7 segmentos.

Paso 11: Montaje

Esta serie de fotografías muestra el montaje final y el cableado. También conecté la placa del controlador principal a la parte posterior en la parte superior.

Antes de encenderlo, hice algunas comprobaciones para evitar sorpresas desagradables. En particular, para asegurarme de que no tenía ningún conector de alimentación / tierra al revés, ni cortocircuitos. Configure su multímetro para probar la continuidad; emitirá un pitido cuando haya una ruta eléctrica entre los dos cables. Conecte un cable a la línea VCC común a los botones. Luego, conecte el otro cable a cada pin del arnés uno por uno. El multímetro solo debería emitir un pitido cuando presione el botón. Si recibe otros pitidos, significa que tiene una reversión o un corto. ¡Localícelo y arréglelo antes de encenderlo!

Paso 12: Código

Primero, abra su Arduino IDE y asegúrese de tener instalada la biblioteca FastLED.

Descargue el código de la máquina de algoritmos de GitHub:

github.com/samguyer/AlgorithmMachine.git

Puede clonarlo directamente en su carpeta Arduino o copiarlo a mano.

Antes de cargarlo, asegúrese de que la configuración de los pines coincida con la configuración de su hardware. He colocado todas las configuraciones de los pines en la parte superior del archivo.

¡Sube y disfruta!

Paso 13: Cómo usar

La máquina de algoritmos es fácil de usar y casi cualquier combinación de botones está bien.

Primero, use los botones de datos para inicializar los valores en la matriz. Hay tres opciones: (1) aleatorizar, (2) agregar un valor aleatorio y (3) invertir la matriz. Tenga en cuenta que los valores son persistentes, por lo que puede hacer cosas como ordenarlos primero, luego agregar algo de ruido y luego ejecutar un algoritmo de búsqueda o clasificación diferente.

Elija un algoritmo de búsqueda u ordenación de las otras opciones de botones. Actualmente, no hay comentarios cuando toma esta decisión (algo para el trabajo futuro). Luego presiona el botón "reproducir".

La perilla controla la velocidad. También puede presionar "reproducir" para pausar y reanudar el algoritmo.

Se detendrá automáticamente cuando termine. También puede presionar otro botón de algoritmo en cualquier momento. La máquina detendrá el algoritmo actual e inicializará el nuevo, pero mantendrá los datos exactamente como los dejó el algoritmo anterior.

Gran Premio en el Concurso STEM