Escuché diferentes interpretaciones de sonido y completas . Entiendo que lo completo significa encontrar una solución si hay una. ¿Qué significa decir que un algoritmo es sólido ?
¿Qué significa decir que un algoritmo es sólido y completo?
algorithms
terminology
mutelogan
fuente
fuente
Respuestas:
Estos son términos muy específicos relacionados con la lógica.
Aquí hay algunos puntos de partida:
http://en.wikipedia.org/wiki/Soundness
http://en.wikipedia.org/wiki/Completeness_(logic)
Básicamente, la solidez (de un algoritmo) significa que el algoritmo no produce ningún resultado que sea falso. Si, por ejemplo, tengo un algoritmo de clasificación que a veces no devuelve una lista ordenada, el algoritmo no funciona.
La integridad, por otro lado, significa que el algoritmo aborda todas las entradas posibles y no pierde ninguna. Entonces, si mi algoritmo de clasificación nunca devuelve una lista sin clasificar, sino que simplemente se niega a trabajar en listas que contenían el número 7, no estaría completa.
Está completo y suena si funciona en todas las entradas (semánticamente válidas en el mundo del programa) y siempre obtiene la respuesta correcta.
fuente
Encuentro la respuesta de Erik Dietrich un poco confusa. Lo siguiente es mejor:
Un algoritmo suena si, cada vez que devuelve una respuesta, esa respuesta es verdadera. Un algoritmo está completo si garantiza devolver una respuesta correcta para cualquier entrada arbitraria (o, si no existe una respuesta, garantiza devolver la falla).
Dos puntos importantes:
Considere, por ejemplo, un algoritmo de clasificación A que recibe como entrada una lista de números. Decimos que A es sólido si cada vez que devuelve un resultado ese resultado es una lista ordenada. Del mismo modo, decimos que A está completo si se garantiza que devolverá una lista ordenada cada vez que le demos una lista de números.
fuente
Estos términos provienen de la teoría de la computación, por lo que son más significativos en el contexto de la teoría de la computación que en el contexto de la ingeniería de software.
En la mayoría de los modelos estándar de computación, los problemas informáticos se representan como lenguajes . Un lenguaje es un conjunto de cadenas. Un algoritmo, entonces, es solo un sistema o procedimiento que decide si una cadena dada es miembro de algún lenguaje (devolviendo verdadero o falso). En términos de ingeniería de software, la teoría de la computación está específicamente relacionada con funciones que se ven así, suponiendo que las cadenas son inmutables:
Llamamos a esta función completa si devuelve verdadero para cada argumento que es miembro del lenguaje. Lo llamamos sonido si devuelve falso para cada argumento que no sea miembro del lenguaje.
En otras palabras, está completo si siempre devuelve verdadero cuando queremos que devuelva verdadero, y suena si siempre devuelve falso cuando queremos que devuelva falso.
¿Cómo se traduce esto a otros tipos de funciones? Como resultado, casi siempre es posible rellenar una cantidad arbitraria de datos en una cadena y reconstituirla dentro de la función. Entonces, la restricción sobre el tipo de argumento y la aridad no es más que una simplificación teórica. Sin embargo, la restricción en el tipo de devolución es más importante. Los problemas que requieren un resultado booleano se denominan problemas de decisión . Mucha teoría de la computación involucra problemas de decisión; los conjuntos P y NP están restringidos a problemas de decisión (y NP, al menos, no podría definirse razonablemente sin esta restricción). El problema de detención es otro ejemplo de un problema de decisión muy estudiado.
Es mi opinión que estos términos no se generalizan fuera del dominio de los problemas de decisión, por lo que la diferencia entre ellos no es realmente significativa cuando se discute una función general.
fuente
Hay respuestas mucho mejores en el SO . Básicamente, proporciona una recopilación de datos y criterios para buscar. El algoritmo de sonido solo captura el pez que coincide con los criterios, pero puede faltar algunos elementos de datos. El algoritmo completo produce un superconjunto de resultados solicitados, lo que significa que recibirá algo de basura además de los resultados solicitados. El algoritmo de sonido es más conservador.
El estadístico probablemente diría que el algoritmo de sonido está sesgado hacia errores de tipo I (no acepta los candidatos correctos), mientras que el algoritmo completo está sesgado hacia errores de tipo II (para aceptar los candidatos falsos).
fuente