La macchina algoritmica: 13 passaggi (con immagini)

2024 Autore: John Day | [email protected]. Ultima modifica: 2024-01-30 10:01

Insegno informatica a livello universitario da 15 anni e, sebbene la mia esperienza sia più orientata alla programmazione, passo ancora molto tempo a studiare algoritmi standard per la ricerca e l'ordinamento. Dal punto di vista didattico il problema centrale è la complessità computazionale: quanto tempo richiede ciascun algoritmo, dato un input di una particolare dimensione? Ma ci sono numerose sfumature. Ad esempio, gli algoritmi hanno tempi di esecuzione diversi a seconda dei valori di input specifici (invece della dimensione)? In quali casi sceglieresti un algoritmo di ordinamento rispetto a un altro? Sebbene discutiamo di questi problemi in astratto, mi ha sempre infastidito il fatto che non esistesse un modo semplice per vedere come funzionano i diversi algoritmi in varie condizioni.

Obiettivi

Il mio obiettivo principale per questo progetto era creare un display interattivo per consentire agli studenti di visualizzare ed esplorare gli algoritmi. Mi sono limitato agli algoritmi che lavorano su array di valori (interi), quindi posso utilizzare una striscia LED RGB indirizzabile per visualizzare il contenuto dell'array. L'array ha 100 elementi e ogni intero è mappato a un colore in ordine arcobaleno, in modo che sia immediatamente ovvio quando l'array è ordinato, parzialmente ordinato o randomizzato. Oltre ai valori, tuttavia, volevo un modo per visualizzare gli aspetti di controllo dell'algoritmo, ad esempio quali elementi dell'array vengono attualmente confrontati o scambiati.

Gli obiettivi specifici sono:

- Fornire una varietà di algoritmi di ricerca e ordinamento

- Visualizza i valori nell'array in modo da evidenziare l'avanzamento dell'algoritmo

- Visualizzare l'algoritmo di controllo; in particolare, gli elementi considerati.

- Consenti agli utenti di scegliere i modelli di dati di input anziché generare sempre valori casuali

- Consenti agli utenti di controllare la velocità e mettere in pausa l'algoritmo

- Consenti agli utenti di forzare il comportamento nel caso migliore, nel caso peggiore e nel caso medio (specifico per algoritmo)

- Mostra il numero di passaggi man mano che l'algoritmo procede

Visualizzazione

Dal punto di vista del design fisico, la parte più interessante di questo progetto è la visualizzazione dell'array. Ho lottato con come mostrare i dati e il controllo e come costruire il dispositivo di visualizzazione stesso. Il mio obiettivo era mostrare i valori dei dati come cerchi colorati e i punti di controllo come frecce colorate che puntano ai valori dei dati. Dopo alcune sperimentazioni, ho optato per un design con due strisce parallele di 100 LED RGB (WS2812) con una maschera circolare su ciascun LED dati e una maschera triangolare su ciascun LED di controllo. Ho realizzato un modello 3D della maschera con 10 paia di cerchi e triangoli, quindi ho stampato in 3D 10 di questi moduli per un totale di 100 cerchi e 100 triangoli. La dimensione e la spaziatura della mia maschera sono progettate per strisce con 100 LED al metro. I file del modello 3D sono forniti più avanti in questa descrizione.

Elettronica e custodia

Il resto del dispositivo è semplice, dal punto di vista dell'elettronica. Oltre alle due strisce LED, ci sono una serie di pulsanti momentanei, un encoder rotativo (per il controllo della velocità) e un display a 7 segmenti (per mostrare i passaggi). Con così tanti pulsanti e controlli ho scelto di utilizzare un microcontrollore ESP32 perché espone molti pin e perché è abbastanza potente. Esaminerò la strategia di cablaggio, ma è piuttosto semplice. Probabilmente potresti fare qualcosa di intelligente con i registri a scorrimento se vuoi usare meno pin.

Puoi costruire la custodia per questo dispositivo in molte forme diverse. Inizialmente l'ho immaginato come una grande lavagna rettangolare con la striscia LED nella parte superiore e una griglia di pulsanti nel mezzo. La forma con cui sono finito è ispirata a una sorta di visione degli anni '60 della tecnologia dell'era spaziale. Potresti anche costruirlo con le strisce LED in orientamento verticale. Oppure rendi la parte LED molto più grande - riempi un'intera parete - con un pannello di controllo separato.

Software

Il codice per questo dispositivo è disponibile gratuitamente su GitHub e ho fatto del mio meglio per documentare come funziona e come configurarlo. L'unica libreria esterna di cui hai bisogno è FastLED per pilotare le strisce WS2812.

Forniture

Elettronica

1 scheda di sviluppo ESP32 (ad es.

2 strisce LED WS2812 o simili, densità 100 LED per metro (ad es.

1 Pulsante triangolo "start" (ad es.

12 pulsanti momentanei (ad es. https://amzn.com/B01N4D4750) -- forme diverse se lo desideri

1 confezione (20) di connettori per pulsanti precablati (ad es.

1 confezione di connettori JST (ad es.

1 Encoder rotativo (ad es.

1 Manopola per encoder rotativo (es.

1 confezione di connettori Dupont (ad es. https://amzn.com/B014YTPFT8): vale la pena procurarsi anche lo strumento di crimpatura.

1 barile jack (per alimentazione) (ad es.

1 TM1637 Display numerico a 7 segmenti (es.

Saldatura e cablaggio

File modello 3D

Puoi trovare il modello 3D per una coppia di moduli a 10 luci su Thingiverse:

www.thingiverse.com/thing:4178181

Dovrai stampare questo modello cinque volte per un totale di 10 moduli.

Software

github.com/samguyer/AlgorithmMachine

Allegato

Bulloneria in legno, plexiglass, acciaio inox

Materiale di diffusione. Il mio preferito è Lee Filters #216 full white diffusion, ma ci sono altre opzioni. Anche la semplice carta bianca fa un buon lavoro.

Passaggio 1: Algoritmi 101

Molte persone pensano che l'informatica sia essenzialmente lo studio della programmazione. Ma il vero cuore e l'anima di questo campo sono gli algoritmi: lo studio di procedure sistematiche per risolvere i problemi e il loro costo (tipicamente, quanto tempo impiegano). Figure seminali del settore, come Alan Turing, Alonzo Church e Edsger Dijkstra, stavano pensando a queste idee prima ancora che esistessero i computer come li conosciamo.

La caratteristica fondamentale di un algoritmo per risolvere un particolare problema è che è dettagliato e preciso, in modo che qualcuno possa usarlo per ottenere una soluzione senza capire affatto come funziona; segui semplicemente i passaggi in modo meccanico e otterrai la risposta giusta. Puoi vedere come questo aiuta con la programmazione dei computer, poiché hanno bisogno di questo livello di dettaglio. Un computer non può riempire i dettagli mancanti o dare giudizi, come può fare una persona.

Quanto tempo ci vorrà?

Una volta che abbiamo una procedura dettagliata, una domanda naturale è quanto tempo ci vorrà per ottenere la risposta? Non possiamo usare unità di tempo ordinarie, poiché dipende da chi sta facendo il lavoro (confronta la velocità con cui una persona potrebbe calcolare qualcosa rispetto a un supercomputer). Inoltre, dipende da quanti dati abbiamo. Chiaramente, ci vuole più tempo per cercare un elenco di un milione di numeri di telefono rispetto a un elenco di cento.

Per descrivere il costo di un algoritmo scegliamo prima un'operazione nella procedura che rappresenta un "passo" - di solito qualcosa di semplice, come confrontare o sommare due numeri, che richiede un tempo fisso per essere eseguito. Quindi otteniamo una formula che descrive quanti passaggi eseguirà l'algoritmo dato un certo numero di elementi di dati. Per ragioni storiche, indichiamo quasi sempre il numero di elementi di dati con la N maiuscola.

Ad esempio, la ricerca in un elenco di N numeri di telefono richiede N passaggi. La consultazione dell'elenco due volte richiede 2N passaggi. Entrambi sono chiamati algoritmi di tempo lineare: il numero totale di passaggi è un multiplo della dimensione dell'input. Altri algoritmi sono quadratici (N tempo al quadrato) o cubici (N cubi) o logaritmici (log N) o una combinazione di questi. Alcuni dei problemi computazionali più difficili richiedono algoritmi a tempo esponenziale (2^N).

OK, e allora?

Quando il numero di elementi di dati N è piccolo, non importa molto. Ad esempio, per N=10, 10N è quel nome come N al quadrato. Ma per quanto riguarda N=1000? o N=1000000? Un milione al quadrato è un numero piuttosto grande. Anche su un computer molto veloce, un algoritmo quadratico può richiedere molto tempo se l'input è sufficientemente grande. Gli algoritmi esponenziali sono molto più problematici: per N=50 un algoritmo esponenziale impiegherebbe due settimane per finire anche su un computer in cui ogni passo è solo un nanosecondo (1 miliardesimo di secondo). Ahia!

All'altra estremità della scala abbiamo algoritmi del tempo logaritmico, che sono molto veloci. Il tempo di log è l'opposto del tempo esponenziale: data la dimensione di input N, il numero di passaggi è l'esponente T nella formula 2^T = N. Ad esempio, se la nostra dimensione di input è un miliardo, un algoritmo di tempo di log richiede solo 30 passi, da 2^30 = 1, 000, 000, 000. Quanto è dolce?!??!

Ti starai chiedendo, a chi importa delle dimensioni di input di milioni o miliardi? Pensaci: quanti utenti ci sono su Facebook? Quante pagine web vengono indicizzate da Google? Quante coppie di basi ci sono nel genoma umano? Quante misurazioni entrano in una simulazione meteorologica?

Passaggio 2: gli algoritmi

La Algorithm Machine attualmente implementa i seguenti algoritmi. Due di questi sono algoritmi di ricerca (trova un valore particolare nell'elenco), il resto sono algoritmi di ordinamento (metti i valori in ordine).

Ricerca lineare

Cerca nell'elenco dei valori uno per uno partendo dall'inizio. Richiede tempo lineare.

Ricerca binaria

Cerca un elenco dividendolo ripetutamente a metà. Richiede tempo di registrazione, ma l'elenco deve essere ordinato affinché funzioni.

Ordinare le bolle

Ordina una lista scambiando ripetutamente elementi vicini che non sono in ordine. Richiede tempo quadratico.

Ordinamento inserimento

Ordina un elenco posizionando ogni elemento nella posizione corretta nell'elenco dei valori già ordinati. Richiede tempo quadratico.

Quicksort

Ordina un elenco dividendo ripetutamente l'elenco a metà e spostando tutti i valori minori della mediana nella prima metà e tutti i valori maggiori della mediana nella seconda metà. In pratica, non possiamo trovare in modo efficiente la mediana, quindi scegliamo un valore a caso. Di conseguenza questo algoritmo può essere quadratico nel caso peggiore, ma in genere richiede N * logN tempo.

Unisci ordinamento

Ordina un elenco dividendolo a metà, ordinando le due metà separatamente (usando l'ordinamento di unione) e quindi unendole insieme intercalando i valori. Richiede sempre N * logN tempo.

Ordinamento dell'heap

Ordina un elenco creando una struttura dati denominata heap, che consente di trovare il valore più piccolo nel tempo di registrazione. Richiede sempre N * logN tempo.

ordinamento bitonico

Simile a unire sort e quicksort, dividere un elenco a metà, ordinare le metà e ricombinarle. Questo algoritmo richiede N * logN * logN tempo, ma ha il vantaggio che è facile da parallelizzare.

Passaggio 3: barra LED: stampa 3D della maschera

Il primo passo per costruire la barra LED è stampare in 3D la maschera che dà la forma alle luci. Ogni modulo copre dieci elementi dell'array, 10 valori (cerchi) e 10 indicatori (triangoli), quindi avrai bisogno di 10 moduli in tutto. Il file STL che sto fornendo qui contiene due istanze del modulo, quindi dovrai eseguire cinque cicli di stampa. Non ho la migliore stampante 3D, quindi ho dovuto ripulirle manualmente utilizzando una lima e carta vetrata. La cosa più importante è che i fori circolari e triangolari siano puliti.

Nelle foto vedrai la mia configurazione di prova: ho fissato le due strisce LED e le ho collegate a una breadboard con un microcontrollore. Questo passaggio non è necessario, ma volevo vedere come sarebbe stato prima di iniziare a montare il contenitore. Ho allineato i moduli maschera sulle due strisce LED e ho eseguito un semplice schizzo con colori casuali. Con una striscia del materiale di diffusione le forme e i colori risaltano davvero.

Passaggio 4: alternative alla barra LED

Quando ho iniziato questo progetto ho sperimentato altri modi per realizzare la maschera LED. Se non hai una stampante 3D potresti prendere in considerazione una di queste opzioni. Sarò onesto: è un grande dolore fare queste parti.

Per i cerchi ho comprato un tubo di ottone 13/32, che ha quasi esattamente 1 cm di diametro. L'ho tagliato in cento segmenti da 1 cm e poi li ho verniciati a spruzzo di bianco.

Per i triangoli, ho usato un foglio di alluminio pesante tagliato da una teglia usa e getta. Ho fatto una forma triangolare di legno, poi ho avvolto delle brevi strisce di pellicola attorno alla forma e le ho fissate con del nastro adesivo. Di nuovo, avrai bisogno di un centinaio di queste cose, quindi ci vorrà un po' di tempo e pazienza.

Passaggio 5: custodia per barra LED

Il mio recinto è abbastanza semplice: due listelli di legno per i lati e due listelli di plexiglass per la parte superiore e inferiore. Tutte le parti sono lunghe circa 102 cm (1 metro per i LED, più un piccolo extra per sistemare il cablaggio). I lati dovrebbero essere un po' più alti di 1 cm per fare spazio alle strisce LED. Dopo aver tagliato le strisce, ho inserito tra loro i pezzi della maschera stampata in 3D per misurare la larghezza del plexiglass. Taglia due pezzi di plexiglass della larghezza e della lunghezza della barra. Infine, tagliare una striscia del materiale di diffusione per adattarla alla maschera.

Per la diffusione mi piacciono molto i Lee Filters #216 (diffusione completamente bianca). È un sottile foglio di plastica che dà una diffusione uniforme senza perdere molta luce. Ma è roba costosa. A volte puoi trovare fogli più piccoli in vendita online, ma un intero rotolo ti costerà circa $ 125. Alcune altre opzioni sono la carta bianca o qualsiasi altro tipo di plastica satinata o smerigliata. Una scelta popolare sono i sottili tappetini da taglio in plastica.

Prima di assemblare la barra LED, assicurati di aver saldato i connettori appropriati alle strisce LED. Molte strisce vengono fornite con cavi pre-saldati, quindi puoi semplicemente usarli.

Ho iniziato il montaggio avvitando la parte superiore di plexiglass sui lati in legno (vedi foto). Poi l'ho capovolto e ho inserito la striscia di diffusione, seguita dai 10 pezzi di maschera. Una volta soddisfatto della spaziatura, le ho fissate con alcuni punti di colla a caldo.

Quindi, appoggia le due strisce LED una accanto all'altra sopra le maschere. Assicurati che i LED siano rivolti verso il basso e che ogni LED sia allineato con il foro corrispondente nella maschera. Aggiungi della colla a caldo o del nastro adesivo per tenere in posizione le strisce LED. Infine, avvitare il pezzo posteriore di plexiglass.

Esegui un modello di prova. Bel lavoro! Hai fatto la parte più difficile!

Passaggio 6: pannello di controllo

Il pannello di controllo è la parte che offre la massima libertà creativa. Deve solo contenere tutti i controlli e l'elettronica, insieme alla barra LED. Il design più semplice è una scheda rettangolare: praticare i fori per i pulsanti e i controlli e collegare la barra LED. Mi piace combinare legno, plexiglass e altri materiali per dare una sorta di look steampunk/retro-moderno. In questo caso, ho tagliato un pezzo di plexiglass resistente per contenere i pulsanti di scelta dell'algoritmo principale e una barra di legno per contenere il resto dell'elettronica. Ho praticato dei fori per abbinare le dimensioni dei pulsanti arcade. Il cablaggio si vede sul retro, ma mi piace!

Ho anche ricavato lo spazio per il display a 7 segmenti, l'encoder rotativo e alcuni cavi sul retro. Ho tagliato un dado nella parte superiore per tenere la barra LED.

Passaggio 7: cablaggio del pulsante

Il cablaggio di molti pulsanti può essere una vera seccatura. Fortunatamente, le persone che realizzano macchine arcade hanno escogitato alcuni connettori standard che puoi usare. Ciascun cavo del connettore del pulsante ha due fili, uno per VCC e uno per la terra. Un'estremità ha connettori a forcella che si adattano ai cavi sul retro del pulsante: collega la terra al cavo "normalmente aperto" e VCC al cavo "comune". In questa configurazione, quando l'utente preme il pulsante, il circuito è completato e il microcontrollore leggerà HIGH sul pin di ingresso corrispondente.

L'altra estremità del cavo ha un connettore JST (la piccola cosa bianca). La cosa bella di questi connettori è che entrano nella presa solo in un modo, quindi non c'è modo di invertire accidentalmente VCC e massa.

Quello che ho fatto è costruire un piccolo cablaggio per questi connettori. Saldo una serie di prese JST su un pezzo di scheda prototipi e poi riporto i cavi ai connettori Dupont che collegherò al microcontrollore. Il filo rosso è la linea VCC e si collega a tutte le prese JST. I fili blu sono quelli separati per ogni pulsante.

Passaggio 8: codificatore rotante

L'encoder rotativo consente all'utente di controllare la velocità dell'algoritmo. Uso un modulo che viene fornito come una scheda di breakout che include resistori di pull-up per le due linee dati (fili gialli). Anche questo è un pulsante, ma non sto usando quella funzione. Gli altri due fili sono VCC e terra. Ho anche un bel pomello grasso.

Quello che mi piace di un encoder rotativo, al contrario di un potenziometro, è che segnala solo la rotazione (in senso orario o antiorario) al microcontrollore, quindi è facile modificare il modo in cui viene interpretato il valore. Ad esempio, puoi dargli un senso di accelerazione (come un mouse) quando l'utente lo fa girare velocemente.

Passaggio 9: display a 7 segmenti

Non c'è molto da dire qui. Queste cose sono ovunque. I LED sono controllati da un chip chiamato TM1637, che comunica con il microcontrollore tramite un semplice protocollo seriale. Uso una libreria esistente che mi consente di dire quale numero voglio mostrare e lui fa il resto.

Il retro ha quattro pin: VCC, terra e due fili per il protocollo seriale. Ho saldato un pezzo di intestazione a 4 pin, che si collega a un corrispondente connettore Dupont collegato al microcontrollore.

Passaggio 10: scheda controller principale

La scheda controller principale ospita il microcontrollore stesso e tutti i connettori ai controlli (pulsanti, display, LED). Il microcontrollore è un ESP32, che fornisce molta potenza di calcolo e memoria ed espone molti pin. Il cablaggio è abbastanza standard, ma indicherò alcuni punti interessanti.

NOTA: potresti voler guardare il codice (https://github.com/samguyer/AlgorithmMachine) prima di iniziare a cablare la scheda madre, in modo che la configurazione dei pin corrisponda alla mia.

Ho saldato un jack a botte sulla scheda per l'alimentazione e ho collegato due robusti fili di rame ai binari di alimentazione e di massa della scheda. Il motivo è che la barra LED può assorbire molta energia se la luminosità è impostata su un valore elevato e non voglio estrarre tutta quella potenza attraverso il connettore USB sul microcontrollore.

Per semplificare il cablaggio dei pulsanti ho saldato una striscia di intestazione ad angolo retto maschio-femmina lungo l'intero lato del microcontrollore (lato superiore della scheda come mostrato). I connettori Dupont dal cablaggio dei pulsanti si collegano direttamente a questa intestazione.

IMPORTANTE: l'alimentazione dei pulsanti (il filo rosso) deve essere collegata alla linea di alimentazione 3.3V del microcontrollore. L'ESP32 è un chip da 3,3 V, quindi solo le sorgenti da 3,3 V dovrebbero essere collegate ai pin dei dati.

Il microcontrollore assorbe l'alimentazione (o spinge l'alimentazione) ai binari (lato inferiore della scheda come mostrato) attraverso il pin USB da 5 V e la messa a terra. Tutti gli altri fili rosso/nero sono VCC e massa.

I due fili blu sono le linee dati per le strisce LED (i WS2812). La coppia giallo/verde sono le linee dati per l'encoder rotativo e la coppia gialla sono la connessione seriale al display a 7 segmenti.

Passaggio 11: assemblaggio

Questa serie di fotografie mostra l'assemblaggio finale e il cablaggio. Ho anche attaccato la scheda del controller principale sul retro in alto.

Prima di accenderlo ho fatto alcuni controlli per evitare brutte sorprese. In particolare, per essere sicuro di non avere connettori di alimentazione/massa al contrario e nessun cortocircuito. Imposta il tuo multimetro per verificare la continuità: emetterà un segnale acustico quando c'è un percorso elettrico tra i due cavi. Collegare un cavo alla linea VCC comune ai pulsanti. Quindi collegare l'altro cavo a ciascun perno dell'imbracatura uno per uno. Il multimetro dovrebbe emettere un segnale acustico solo quando si preme il pulsante. Se ricevi altri segnali acustici, significa che hai un'inversione o un cortocircuito. Rintraccialo e riparalo prima di accendere la corrente!

Passaggio 12: codice

Innanzitutto, apri il tuo IDE Arduino e assicurati di aver installato la libreria FastLED.

Scarica il codice Algorithm Machine da GitHub:

github.com/samguyer/AlgorithmMachine.git

Puoi clonarlo direttamente nella cartella Arduino o copiarlo manualmente.

Prima di caricarlo, assicurati che le impostazioni dei pin corrispondano alla tua configurazione hardware. Ho posizionato tutte le impostazioni dei pin nella parte superiore del file.

Carica e divertiti!

Passaggio 13: come utilizzare

La Algorithm Machine è semplice da usare e quasi ogni combinazione di pulsanti va bene!

Innanzitutto, utilizzare i pulsanti dei dati per inizializzare i valori nell'array. Ci sono tre scelte: (1) randomizzare, (2) aggiungere un valore casuale e (3) invertire l'array. Nota che i valori sono persistenti, quindi puoi fare cose come ordinarli prima, quindi aggiungere un po' di rumore, quindi eseguire un diverso ordinamento o algoritmo di ricerca.

Scegli un algoritmo di ricerca o di ordinamento dalle altre scelte di pulsanti. Attualmente, non ci sono feedback quando fai questa scelta (qualcosa per il lavoro futuro). Quindi premi il pulsante "riproduci".

La manopola controlla la velocità. Puoi anche premere "play" per mettere in pausa e riattivare l'algoritmo.

Si fermerà automaticamente al termine. Puoi anche premere un altro pulsante dell'algoritmo in qualsiasi momento. La macchina fermerà l'algoritmo corrente e inizializzerà quello nuovo, ma manterrà i dati esattamente come li ha lasciati l'algoritmo precedente.

Gran Premio al Concorso STEM