Introduction à l'algorithme de force brute
«Les données sont le nouveau pétrole», tel est le nouveau mantra qui régit l'économie mondiale. Nous vivons dans le monde numérique et chaque entreprise s'articule autour de données qui se traduisent par des profits et aident les industries à garder une longueur d'avance sur leurs concurrents. Avec la numérisation rapide, une augmentation exponentielle du modèle commercial basé sur les applications, les cybercrimes sont une menace constante. Une de ces activités communes que les pirates exécutent est la force brute.
Brute Force est une approche par essais et erreurs où les attaquants utilisent des programmes pour essayer différentes combinaisons pour pénétrer dans n'importe quel site Web ou système. Ils utilisent un logiciel automatisé pour générer de manière répétitive les combinaisons d'ID utilisateur et de mots de passe jusqu'à ce qu'il génère finalement la bonne combinaison.
Recherche Brute-Force
La recherche par force brute est l'algorithme de recherche le plus courant car il ne nécessite aucune connaissance du domaine, tout ce qui est requis est une description d'état, des opérateurs juridiques, l'état initial et la description d'un état objectif. Il n'améliore pas les performances et repose entièrement sur la puissance de calcul pour essayer les combinaisons possibles.
L'algorithme de force brute recherche toutes les positions dans le texte entre 0 et nm, que l'occurrence du motif commence là ou non. Après chaque tentative, il déplace le motif vers la droite de 1 position exactement. La complexité temporelle de cet algorithme est O (m * n). donc si nous recherchons n caractères dans une chaîne de m caractères, cela prendra n * m essais.
Voyons un exemple classique d'un vendeur itinérant pour comprendre l'algorithme de manière simple.
Supposons qu'un vendeur doive parcourir 10 villes différentes dans un pays et qu'il souhaite déterminer les itinéraires les plus courts possibles parmi toutes les combinaisons possibles. Ici, l'algorithme de force brute calcule simplement la distance entre toutes les villes et sélectionne la plus courte.
Un autre exemple est de tenter de casser le mot de passe à 5 chiffres, puis la force brute peut prendre jusqu'à 10 5 tentatives pour déchiffrer le code.
Tri de la force brute
Dans la technique de tri par force brute, la liste de données est analysée plusieurs fois pour trouver le plus petit élément de la liste. Après chaque itération sur la liste, il remplace le plus petit élément en haut de la pile et démarre l'itération suivante à partir des deuxièmes plus petites données de la liste.
L'instruction ci-dessus peut être écrite en pseudo-code comme suit.
Ici, le problème est de taille «n» et l'opération de base est «si» teste où les éléments de données sont comparés à chaque itération. Il n'y aura aucune différence entre le pire et le meilleur des cas, car le nombre de swaps est toujours n-1.
Brute Force String Matching
Si tous les caractères du motif sont uniques, la correspondance de chaîne de force brutale peut être appliquée avec la complexité de Big O (n). où n est la longueur de la chaîne. Brute force La correspondance de chaînes compare le motif avec la sous-chaîne d'un texte caractère par caractère jusqu'à ce qu'il obtienne un caractère incompatible. Dès qu'une incompatibilité est détectée, le caractère restant de la sous-chaîne est supprimé et l'algorithme passe à la sous-chaîne suivante.
Les pseudo-codes ci-dessous expliquent la logique de correspondance des chaînes. Ici, l'algorithme tente de rechercher un motif de P (0… m-1) dans le texte T (0… .n-1).
ici, le pire des cas serait celui où un passage à une autre sous-chaîne n'est pas effectué avant la comparaison M Th .
Paire la plus proche
Énoncé du problème: trouver les deux points les plus proches dans un ensemble de n points dans le plan cartésien bidimensionnel. Il existe n nombre de scénarios où ce problème se pose. Un exemple réel serait dans un système de contrôle de la circulation aérienne où vous devez surveiller les avions volant près les uns des autres et vous devez trouver la distance minimale la plus sûre que ces avions devraient maintenir.
Source: Wikipedia
L'algorithme de force brute calcule la distance entre chaque ensemble distinct de points et renvoie les index du point pour lequel la distance est la plus petite.
La force brute résout ce problème avec la complexité temporelle de (O (n2)) où n est le nombre de points.
En dessous du pseudo-code utilise l'algorithme de force brute pour trouver le point le plus proche.
Enveloppe convexe
Énoncé du problème : Une coque convexe est le plus petit polygone contenant tous les points. La coque convexe d'un ensemble s du point est le plus petit polygone convexe contenant s.
La coque convexe de cet ensemble de points est le polygone convexe avec des sommets à P1, P5, P6, P7, P3
Un segment de ligne P1 et Pn d'un ensemble de n points fait partie de la coque convexe si et seulement si tous les autres points de l'ensemble se trouvent à l'intérieur de la limite du polygone formée par le segment de ligne.
Relions-le à l'élastique,
Les points (x1, y1), (x2, y2) font la ligne ax + by = c
Lorsque a = y2-y1, b = x2-x1 et c = x1 * y2 - x2 * y1 et divise le plan par ax + by-c 0
Nous devons donc vérifier ax + by-c pour les autres points.
La force brute résout ce problème avec la complexité temporelle de O (n 3 )
Une recherche exhaustive
Pour les problèmes discrets dans lesquels il n'existe pas de solution efficace connue, il devient nécessaire de tester chaque solution possible de manière séquentielle.
La recherche exhaustive est une activité permettant de trouver systématiquement toutes les solutions possibles à un problème.
Essayons de résoudre le problème du voyageur de commerce (TSP) en utilisant l'algorithme de recherche exhaustive Brute.
Énoncé du problème: Il n'y a pas de villes où le vendeur doit voyager, il veut découvrir l'itinéraire le plus court qui couvre toutes les villes.
Nous envisageons le circuit de Hamilton pour résoudre ce problème. Si un circuit existe, n'importe quel point peut commencer des sommets et terminer des sommets. Une fois les sommets de départ sélectionnés, nous n'avons besoin que de l'ordre des sommets restants, c'est-à-dire n-1
Il y aurait alors (n-1)! Les combinaisons possibles et le coût total pour calculer le chemin seraient O (n). ainsi la complexité temporelle totale serait O (n!).
Conclusion
Maintenant que nous avons atteint la fin de ce tutoriel, j'espère que vous avez maintenant une bonne idée de ce qu'est Brute Force. Nous avons également vu les différents algorithmes de force brute que vous pouvez appliquer dans votre application.
Articles recommandés
Cela a été un guide pour l'algorithme de force brute. Ici, nous avons discuté des concepts de base de l'algorithme de force brute. Vous pouvez également consulter nos autres articles suggérés pour en savoir plus -
- Qu'est-ce qu'un algorithme?
- Questions d'entretiens chez Algorithm
- Introduction à l'algorithme
- Algorithme de programmation