La recherche exhaustive ou recherche par force brute est une méthode algorithmique qui consiste principalement à essayer toutes les solutions possibles. Par exemple pour trouver le maximum d'un certain ensemble de valeurs, on consulte toutes les valeurs. En cryptanalyse on parle d'attaque par force brute, ou par recherche exhaustive pour les attaques utilisant cette méthode. Le principe de cet algorithme est d'essayer toutes les possibilités dans un intervalle. Un exemple courant est l'attaque par force brute des mots de passe. Si on sait que le mot de passe contient obligatoirement 4 chiffres, alors on essaie tous les nombres de 0000 à 9999 jusqu'à trouver le bon mot de passe. 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 combinaison de valeurs peut être testée plus d'une fois dans au moins un schéma d'exécution. À supposer qu'il y a un problème et n variables dont il est possible d'obtenir une grandeur. Alors un objectif sera de découvrir les p variables significatives 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.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (4)
COM-401: Cryptography and security
This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how
CS-430: Intelligent agents
Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by prog
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
Afficher plus
Publications associées (55)
Concepts associés (16)
Retour sur trace
En informatique, plus précisément en algorithmique, le retour sur trace ou retour arrière (appelé aussi backtracking en anglais) est une famille d'algorithmes pour trouver des solutions à des problèmes algorithmiques, notamment de satisfaction de contraintes. Contrairement à une recherche exhaustive, un algorithme de retour sur trace construit incrémentalement des solutions candidates. Il abandonne la construction lorsqu'il ne peut compléter le candidat courant en solution valide.
Cryptographie
thumb|La machine de Lorenz utilisée par les nazis durant la Seconde Guerre mondiale pour chiffrer les communications militaires de haut niveau entre Berlin et les quartiers-généraux des différentes armées. La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets ou clés. Elle se distingue de la stéganographie qui fait passer inaperçu un message dans un autre message alors que la cryptographie rend un message supposément inintelligible à autre que qui de droit.
Programmation par contraintes
La programmation par contraintes (PPC, ou CP pour constraint programming en anglais) est un paradigme de programmation apparu dans les années 1970 et 1980 permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement. En programmation par contraintes, on sépare la partie modélisation à l'aide de problèmes de satisfaction de contraintes (ou CSP pour Constraint Satisfaction Problem), de la partie résolution dont la particularité réside dans l'utilisation active des contraintes du problème pour réduire la taille de l'espace des solutions à parcourir (on parle de propagation de contraintes).
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.