Explication des algorithmes de force brute

Les algorithmes Brute Force sont exactement ce à quoi ils ressemblent: des méthodes simples pour résoudre un problème qui reposent sur une puissance de calcul pure et qui essaient toutes les possibilités plutôt que des techniques avancées pour améliorer l'efficacité.

Par exemple, imaginez que vous avez un petit cadenas avec 4 chiffres, chacun de 0 à 9. Vous avez oublié votre combinaison, mais vous ne voulez pas acheter un autre cadenas. Comme vous ne vous souvenez d'aucun des chiffres, vous devez utiliser une méthode de force brute pour ouvrir le verrou.

Vous remettez donc tous les nombres à 0 et essayez-les un par un: 0001, 0002, 0003, et ainsi de suite jusqu'à ce qu'il s'ouvre. Dans le pire des cas, il faudrait 104 ou 10 000 essais pour trouver votre combinaison.

Un exemple classique en informatique est le problème du voyageur de commerce (TSP). Supposons qu'un vendeur doive visiter 10 villes à travers le pays. Comment déterminer l'ordre dans lequel ces villes doivent être visitées de manière à minimiser la distance totale parcourue?

La solution de force brute consiste simplement à calculer la distance totale pour chaque itinéraire possible, puis à sélectionner le plus court. Ce n'est pas particulièrement efficace car il est possible d'éliminer de nombreuses routes possibles grâce à des algorithmes intelligents.

La complexité temporelle de la force brute est O (m n ) , qui s'écrit parfois O (n * m). Donc, si nous cherchions une chaîne de "n" caractères dans une chaîne de "m" caractères en utilisant la force brute, cela nous prendrait n * m essais.

Plus d'informations sur les algorithmes

En informatique, un algorithme est simplement un ensemble de procédures étape par étape pour résoudre un problème donné. Les algorithmes peuvent être conçus pour effectuer des calculs, traiter des données ou effectuer des tâches de raisonnement automatisées.

Voici comment Wikipédia les définit:

Un algorithme est une méthode efficace qui peut être exprimée dans une quantité finie d'espace et de temps et dans un langage formel bien défini pour le calcul d'une fonction. Partant d'un état initial et d'une entrée initiale (peut-être vide), les instructions décrivent un calcul qui, lorsqu'il est exécuté, passe par un nombre fini d'états successifs bien définis, produisant finalement une «sortie» et se terminant à un état final final. Le passage d'un état au suivant n'est pas nécessairement déterministe; certains algorithmes, appelés algorithmes aléatoires, incorporent une entrée aléatoire.

Un algorithme doit respecter certaines exigences:

  1. Définition: chaque étape du processus est énoncée avec précision.
  2. Calculabilité efficace: chaque étape du processus peut être effectuée par un ordinateur.
  3. Finitude: le programme finira par se terminer avec succès.

Certains types d'algorithmes courants comprennent:

  • algorithmes de tri
  • algorithmes de recherche
  • algorithmes de compression.

Les classes d'algorithmes comprennent

  • Graphique
  • Programmation dynamique
  • Tri
  • Recherche
  • Cordes
  • Math
  • Géométrie de calcul
  • Optimisation
  • Divers.

Bien que techniquement pas une classe d'algorithmes, les structures de données sont souvent regroupées avec eux.

Efficacité

Les algorithmes sont le plus souvent jugés en fonction de leur efficacité et de la quantité de ressources informatiques dont ils ont besoin pour accomplir leur tâche.

Une manière courante d'évaluer un algorithme consiste à examiner sa complexité temporelle. Cela montre comment le temps d'exécution de l'algorithme augmente à mesure que la taille d'entrée augmente. Étant donné que les algorithmes doivent aujourd'hui fonctionner sur de grandes entrées de données, il est essentiel que nos algorithmes aient un temps d'exécution raisonnablement rapide.

Algorithmes de tri

Les algorithmes de tri se déclinent en différentes saveurs selon vos besoins. Certains, très courants et largement utilisés sont:

Tri rapide

Il n'y a pas de discussion de tri qui puisse se terminer sans un tri rapide. Voici le concept de base: Tri rapide

Tri par fusion

Un algorithme de tri qui repose sur le concept selon lequel les tableaux triés sont fusionnés pour donner un tableau trié. En savoir plus ici: Mergesort

Le programme de freeCodeCamp met fortement l'accent sur la création d'algorithmes. En effet, l'apprentissage des algorithmes est un bon moyen de pratiquer les compétences en programmation. Les intervieweurs testent le plus souvent les candidats sur des algorithmes lors des entretiens d'embauche des développeurs.

Livres sur les algorithmes en JavaScript:

Structures de données en JavaScript

  • Livre gratuit qui couvre les structures de données en JavaScript
  • GitBook

Apprentissage des structures de données et des algorithmes JavaScript - Deuxième édition

  • Couvre la programmation orientée objet, l'héritage prototypique, les algorithmes de tri et de recherche, le tri rapide, le tri par fusion, les arbres de recherche binaires et les concepts d'algorithmes avancés
  • Amazone
  • ISBN-13: 978-1785285493

Structures de données et algorithmes avec JavaScript: Apporter des approches informatiques classiques au Web

  • Couvre la récursivité, les algorithmes de tri et de recherche, les listes chaînées et les arbres de recherche binaires.
  • Amazone
  • ISBN-13: 978-1449364939