Articolo originale: Brute Force Algorithms Explained di freeCodeCamp.org

Tradotto e adattato da: Dario Di Cillo

Gli algoritmi di forza bruta (o ricerca esaustiva) sono esattamente ciò che il loro nome suggerisce: sono dei metodi diretti di risoluzione di problemi che si basano sulla pura potenza computazionale utilizzando ogni possibilità, piuttosto che tecniche avanzate mirate a migliorare l'efficienza.

Ad esempio, immagina di avere un lucchetto con una combinazione a 4 cifre, ognuna da 0 a 9. Hai dimenticato la combinazione, ma non vuoi comprarne uno nuovo. Visto che non ricordi nessuna cifra, devi usare un metodo di forza bruta per aprirlo.

Quindi riporti tutti i numeri su 0 e inizi a provare tutti le possibili combinazioni, una alla volta: 0001, 0002, 0003 e così via finché non si apre. Nel caso peggiore, ti serviranno 104 (10,000) tentativi prima di trovare la combinazione corretta.

Nel campo informatico, un esempio classico è quello del problema del commesso viaggiatore. Supponiamo che un commesso abbia bisogno di recarsi in 10 città del Paese. Come si può determinare l'ordine in cui dovrà visitarle in modo da minimizzare la distanza totale percorsa?

La soluzione forza bruta si basa semplicemente sul calcolo della distanza di ogni possibile percorso per poi selezionare il più corto. Questo modo di operare non è particolarmente efficiente perché è possibile eliminare molti percorsi utilizzando degli algoritmi ingegnosi.

La complessità temporale di forza bruta è O(mn), talvolta riportata come O(n*m), quindi se cerchiamo una stringa di "n" caratteri in una stringa di "m" caratteri usando un metodo forza bruta, ci occorreranno n * m tentativi.

Più informazioni sugli algoritmi

In informatica, un algoritmo è semplicemente un insieme di procedure sistematiche per risolvere un determinato problema. Gli algoritmi possono essere progettati per effettuare calcoli, processare dati o compiere operazioni logiche automatizzate.

Ecco la definizione di algoritmo secondo Wikipedia:

Un algoritmo è un metodo efficace che può essere espresso in uno spazio e in un tempo finiti e in un ben definito linguaggio formale per calcolare una funzione. Partendo da uno step iniziale e un input iniziale (anche nullo), le istruzioni descrivono un calcolo che, quando eseguito, procede attraverso un numero finito di stati ben precisati, producendo infine un "output" e terminando in uno stato finale. La transizione tra uno stato al successivo non è necessariamente deterministica; alcuni algoritmi, noti come randomizzati, utilizzano input casuali.

Ci sono alcuni requisiti a cui un algoritmo deve attenersi. Un algoritmo deve essere:

  1. Deterministico: ogni step del processo deve essere definito in modo preciso.
  2. Calcolabile: ogni step del processo deve poter essere svolto da un computer.
  3. Finito: alla fine, il programma deve terminare con successo.

Tra i tipi più comuni ci sono gli algoritmi di:

  • Ordinamento
  • Ricerca
  • Compressione

Le classi degli algoritmi includono

  • Grafi
  • Programmazione dinamica
  • Ordinamento
  • Ricerca
  • Stringhe
  • Matematica
  • Geometria computazionale
  • Ottimizzazione
  • Altro

Anche se tecnicamente non sono classi di algoritmi, le strutture di dati vengono spesso incluse nell'elenco.

Efficienza

Gli algoritmi vengono spesso valutati in base alla loro efficienza e alla quantità di risorse di calcolo di cui hanno bisogno per operare.

Un modo comune di valutare un algoritmo è considerare la sua complessità temporale, che riflette la crescita del tempo di esecuzione di un algoritmo all'aumentare della dimensione degli input. Dato che gli algoritmi al giorno d'oggi devono operare su dati di input consistenti, è essenziale che abbiano un tempo di esecuzione ragionevole.

Algoritmi di ordinamento

Gli algoritmi di ordinamento sono piuttosto variabili a seconda della necessità. Tra quelli più comuni ci sono:

Quicksort

Non c'è discussione sull'ordinamento che possa terminare senza l'algoritmo quicksort. Qui troverai i concetti di base.

Mergesort

È un algoritmo che si basa sul concetto usato per unire degli array in un unico array ordinato. Qui puoi approfondire questo argomento.

Il curriculum di freeCodeCamp dà molta importanza alla creazione di algoritmi. Questo perché l'utilizzo di algoritmi è un ottimo modo per fare pratica con la programmazione ed è un'abilità molto richiesta per un lavoro da sviluppatore.

Libri sugli algoritmi in JavaScript:

Data Structures in JavaScript

  • Libro gratuito che parla di strutture di dati in JavaScript.
  • GitBook

Learning JavaScript Data Structures and Algorithms - Second Edition

  • Tratta di programmazione orientata agli oggetti, Covers object oriented programming, ereditarietà prototipale, algoritmi di ordinamento e ricerca, quicksort, mergesort, alberi di ricerca binaria e concetti avanzati degli algoritmi.
  • Amazon
  • ISBN-13: 978-1785285493

Data Structures and Algorithms with JavaScript: Bringing classic computing approaches to the Web

  • Tratta di ricorsività, ordinamento e ricerca, Covers recursion, sorting and searching algorithms, liste concatenate e alberi di ricerca binaria.
  • Amazon
  • ISBN-13: 978-1449364939