Recherche par force brute

Recherche par force brute

Recherche exhaustive

La recherche exhaustive ou recherche par force brute, est un terme qui s'applique à une catégorie de méta-algorithmes. C'est une technique extrêmement simple, mais très générale, qui consiste à énumérer tous les candidats possibles, jusqu'à trouver le candidat qui satisfait au problème.

On peut distinguer plusieurs formes de recherche exhaustive.

Sommaire

Méthode

La recherche au sens unifications entre deux théories

exemple : trouver A et B tels que pour un prédicat à deux arguments f la propriété f(A, B) soit vraie. La recherche exhaustive est alors une méthode de recherche qui consiste à considérer l'ensemble des valeurs possibles pour A et B et à les tester toutes dans un ordre quelconque jusqu'à ce que la propriété soit vraie. Typiquement les algorithmes qui découvrent dynamiquement la structure des données pour optimiser leur calcul sont aussi considérés comme des algorithmes de recherche exhaustive. On peut citer SSS*, AlphaBeta, MinMax, A*, BackTrack, BackJump, BackMark, NC-AC(n), ForwardChecking, ... Dans cette catégorie on peut considérer que le terme "exhaustive" ne s'applique plus :

  • si dans le pire des cas il est possible que la solution ne soit pas trouvée malgré son existence.
  • si l'ensemble des valeurs à explorer est indénombrable.
  • si une combinaisons de valeurs peut être testée plus d'une fois dans au moins un schéma d'exécution.

La recherche au sens sélection des paramètres influents dans un contexte inconnu

Supposons que l'on se donne un problème et n variables dont on peut obtenir une grandeur. Alors un objectif sera de découvrir les p variables significative de ce problème. Pour cela une des premières méthodes de réalisation à envisager est la recherche exhaustive.

En effet ce genre de problème contient très souvent de nombreuses contraintes implicites liées à la structure propre du problème. Il suffit alors de construire l'hypergraphe des contraintes et en déduire les paramètres les plus influents. La méthode brutale la plus employée pour ce problème est l'ACP (Analyse en composante Principale).

Cette recherche est très souvent réalisée en robotique et en traitement automatique du langage naturel. Dans ces deux derniers il est très courant que les contraintes soient entrées 'à la main' via un expert. En effet construire un programme qui découvre automatiquement les caractéristiques d'un robot ou d'une langue est très compliqué. Cependant l'ordonnancement des paramètres les plus influents se fait souvent par recherche exhaustive sur des corpus obtenus empiriquement.

Voir aussi

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Recherche exhaustive ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Recherche par force brute de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Attaque Par Force Brute — Deep Crack, circuit dédié à l attaque par force brute de DES. L attaque par force brute est une méthode utilisée en cryptanalyse pour trouver un mot de passe ou une clé. Il s agit de tester, une à une, toutes les combinaisons possibles. Cette… …   Wikipédia en Français

  • Attaque par force brute — Deep Crack, circuit dédié à l attaque par force brute de DES. L attaque par force brute est une méthode utilisée en cryptanalyse pour trouver un mot de passe ou une clé. Il s agit de tester, une à une, toutes les combinaisons possibles. Cette… …   Wikipédia en Français

  • Brute Force — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. La méthode « Brute Force » est une approche exhaustive des problèmes: la solution est trouvée en testant tous les cas possible jusqu à la… …   Wikipédia en Français

  • Recherche exhaustive — La recherche exhaustive ou recherche par force brute, est un terme qui s applique à une catégorie de méta algorithmes. C est une technique extrêmement simple, mais très générale, qui consiste à énumérer tous les candidats possibles, jusqu à… …   Wikipédia en Français

  • brute — [ bryt ] n. f. • 1669; brut 1559; de brut 1 ♦ Littér. L animal considéré dans ce qu il a de plus éloigné de l homme. ⇒ bête. « La création est une ascension perpétuelle, de la brute vers l homme, de l homme vers Dieu » (Hugo). 2 ♦ Personne… …   Encyclopédie Universelle

  • Algorithme De Recherche — Pour les articles homonymes, voir recherche (homonymie). En informatique, un algorithme de recherche est un type d algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions… …   Wikipédia en Français

  • Algorithme de recherche — Pour les articles homonymes, voir recherche (homonymie). En informatique, un algorithme de recherche est un type d algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions… …   Wikipédia en Français

  • Algorithmes de recherche — Algorithme de recherche Pour les articles homonymes, voir recherche (homonymie). En informatique, un algorithme de recherche est un type d algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un… …   Wikipédia en Français

  • Attaque par brute force — Attaque par force brute Deep Crack, circuit dédié à l attaque par force brute de DES. L attaque par force brute est une méthode utilisée en cryptanalyse pour trouver un mot de passe ou une clé. Il s agit de tester, une à une, toutes les… …   Wikipédia en Français

  • Attaque par biais statistique — Cryptanalyse La cryptanalyse s oppose, en quelque sorte, à la cryptographie. En effet, si déchiffrer consiste à retrouver le clair au moyen d une clé, cryptanalyser c est tenter de se passer de cette dernière. Même si on décrit les cryptanalystes …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”