J'ai entendu différentes interprétations sonores et complètes . Je comprends que l' exhaustivité signifie trouver une solution s'il y en a une. Que signifie dire qu'un algorithme est sain .
Que signifie dire qu'un algorithme est sain et complet?
algorithms
terminology
mutelogan
la source
la source
Réponses:
Ce sont des termes très spécifiques liés à la logique.
Voici quelques points de départ:
http://en.wikipedia.org/wiki/Soundness
http://en.wikipedia.org/wiki/Completeness_(logic)
Fondamentalement, la solidité (d'un algorithme) signifie que l'algorithme ne donne aucun résultat faux. Si, par exemple, j'ai un algorithme de tri qui parfois ne renvoie pas de liste triée, l'algorithme n'est pas sain.
L'exhaustivité, d'autre part, signifie que l'algorithme traite toutes les entrées possibles et n'en manque aucune. Donc, si mon algorithme de tri ne renvoyait jamais une liste non triée, mais refusait simplement de travailler sur des listes contenant le numéro 7, il ne serait pas complet.
Il est complet et sain s'il fonctionne sur toutes les entrées (sémantiquement valable dans le monde du programme) et obtient toujours la bonne réponse.
la source
Je trouve la réponse d'Erik Dietrich un peu déroutante. C'est mieux:
Un algorithme est valable si, à chaque fois qu'il renvoie une réponse, cette réponse est vraie. Un algorithme est complet s'il garantit de retourner une réponse correcte pour toute entrée arbitraire (ou, s'il n'y a pas de réponse, il garantit de retourner l'échec).
Deux points importants:
Considérons par exemple un algorithme de tri A qui reçoit en entrée une liste de nombres. Nous disons que A est sain si à chaque fois qu'il renvoie un résultat, ce résultat est une liste triée. De même, nous disons que A est complet si nous garantissons de renvoyer une liste triée chaque fois que nous lui donnons une liste de nombres.
la source
Ces termes proviennent de la théorie du calcul, ils sont donc plus significatifs dans le contexte de la théorie du calcul que dans le contexte du génie logiciel
Dans la plupart des modèles de calcul standard, les problèmes informatiques sont représentés comme des langages . Une langue est un ensemble de chaînes. Un algorithme n'est donc qu'un système ou une procédure qui décide si une chaîne donnée est membre d'une langue (en renvoyant true ou false). En termes de génie logiciel, la théorie du calcul s'intéresse spécifiquement aux fonctions qui ressemblent à ceci, en supposant que les chaînes sont immuables:
Nous appelons cette fonction complète si elle retourne vrai pour chaque argument qui est membre du langage. Nous l'appelons son s'il renvoie faux pour chaque argument qui n'est pas membre du langage.
En d'autres termes, il est complet s'il retourne toujours vrai quand nous voulons qu'il revienne vrai, et son s'il retourne toujours faux quand nous voulons qu'il retourne faux.
Comment cela se traduit-il dans d'autres types de fonctions? En fait, il est presque toujours possible de bourrer une quantité arbitraire de données dans une chaîne et de la reconstituer à l'intérieur de la fonction. La restriction du type d'argument et de l'arité n'est donc rien d'autre qu'une simplification théorique. La restriction sur le type de retour est cependant plus importante. Les problèmes qui appellent un résultat booléen sont appelés problèmes de décision . Une grande partie de la théorie du calcul implique des problèmes de décision; les ensembles P et NP sont limités aux problèmes de décision (et NP, au moins, ne pourrait pas être raisonnablement défini sans cette restriction). Le problème de l'arrêt est un autre exemple d'un problème de décision très étudié.
À mon avis, ces termes ne se généralisent pas en dehors du domaine des problèmes de décision, de sorte que la différence entre eux n'est pas vraiment significative lorsque l'on discute d'une fonction générale.
la source
Il y a de bien meilleures réponses au SO . Fondamentalement, vous fournissez une collecte de données et des critères de recherche. Un algorithme sonore ne capture que le poisson qui correspond aux critères, mais il peut manquer certains éléments de données. L'algorithme complet produit un surensemble de résultats demandés, ce qui signifie que vous recevez des ordures en plus des résultats demandés. L'algorithme du son est plus conservateur.
Le statisticien dirait probablement que l'algorithme du son est biaisé par rapport aux erreurs de type I (il n'accepte pas les bons candidats), tandis que l'algorithme complet est biaisé par les erreurs de type II (pour accepter les faux candidats).
la source