The Big Bang Theory : Jim Parsons fait discrètement son coming-out
Le comédien qui incarne le délirant et génial Sheldon Cooper dans la série The Big Bang Theory n'avait jamais vraiment parlé de sa vie privée. Certains pensaient même qu'il était finalement asexué, comme son personnage. Mais dans les colonnes du New York Times qui lui ont accordé un...
Recherche exhaustive
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Consultez la liste des tâches à accomplir en page de discussion. |
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 unification 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 Composantes Principales).
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
- Attaque par force brute en cryptanalyse
mentions légales Wikipédia
politique de confidentialité
à propos de Wikipédia
avertissements
contacts
faire un don
politique de confidentialité
à propos de Wikipédia
avertissements
contacts
faire un don
En direct des marchés
Cannes consacre sous la pluie Michael Haneke et son "Amour"
Michael Haneke a été sacré dimanche à Cannes Palme d'Or pour la seconde fois de sa carrière à 70 ans avec "Amour", un film qui a fait l'unanimité au sein d'une sélection discutée et d'un palmarès qui consacre de nombreux habitués de la Croisette mais pas de stars.