¿Cómo formular un problema computacional rigurosamente?

20

A menudo interactúo con personas que desean solicitar un algoritmo para un problema computacional (o su complejidad), pero no lo expresan de manera rigurosa para que nosotros (los científicos informáticos) lo comprendamos.

Remitirlos a libros como CLRS no es útil porque los ejemplos allí generalmente tienen una forma bastante directa de establecer rigurosamente, por ejemplo, dada la lista de adyacencia de un gráfico y dos vértices, calculan el camino más corto entre esos vértices.

¿Existe algún buen libro (o algún otro recurso) en el que una persona con un conocimiento mínimo de CS pueda aprender cómo uno debe formular y establecer problemas computacionales de una manera rigurosa que sea comprensible para los informáticos?

Preferiblemente, el libro debería tener muchos ejemplos de cómo formular rigurosamente problemas computacionales a partir de varios dominios y ejemplos del mundo real.

Aclaración

Para hacer la pregunta más específica, supongamos que conocen la terminología básica de matemáticas / CS como conjuntos, funciones, gráficos, listas, etc. a nivel de estudiante de pregrado de 1 ° / 2 ° año (que es el caso de las personas que tengo en mente). Por ejemplo, han leído algunos libros de texto introductorios como Aho y Ullman (aunque podrían no haberlo entendido completamente).

algorithms reference-request books Kaveh
fuente
2
Creo que esta es una buena pregunta, pero no sé si hay una buena respuesta. Siento que es como preguntar "¿Hay alguna manera de que podamos enseñar a alguien que no es un informático a pensar como un informático?" Y la respuesta a eso es "sí, conviértalos en informáticos". Dicho esto, algunos investigadores de ingeniería de software pueden haber realizado estudios sobre cosas como esta.
jmite
3
Además, creo que para eso son los casos de uso, hasta cierto punto. Si alguien no comprende cómo formular adecuadamente su problema, enumere una serie de escenarios de lo que le gustaría que haga un programa determinado y el comportamiento esperado en cada caso. El programador luego desarrolla una especificación a partir de eso. Dicho esto, soy una persona teórica, no un ingeniero, así que si me equivoco, no dudes en corregirme.
jmite
@ jmite, gracias por los comentarios. Tienes razón en que parte de la Ingeniería de Software es tratar de entender lo que un cliente quiere (creo que lo llaman análisis de requisitos ). Pero eso suele ser para grandes proyectos. No estoy hablando de tales proyectos, sino de preguntas simples como las que recibimos en este sitio que no se mencionan rigurosamente. He visto libros que enseñan a las personas cómo formular una declaración en lógica con muchos ejemplos. Espero que haya algo similar para los algoritmos y los problemas computacionales.
Kaveh
1
Dicho esto, considero que requiere una cierta forma de pensar que no es fácil de adquirir, especialmente por los adultos. He tratado de hacer que la gente deje de lado las cosas técnicas y explique el problema de la manera más simple posible en términos de objetos cotidianos. El problema es que generalmente olvidarán alguna restricción, o harán que suene como una operación que es O (N) en su sistema real es O (1), y así sucesivamente. Así que terminaré con algo muy cercano a una definición rigurosa del problema incorrecto.
svinja
2
en cierto modo, lo que se pide es contradictorio, porque formular problemas de manera rigurosa es exactamente una de las habilidades aprendidas clave que separa a los profanos de los especialistas / profesionales ...
vzn

Respuestas:

3

Un buen recurso para esto, bastante conocido por los académicos pero no tan ampliamente conocido fuera de los especialistas, es la escritura matemática de Donald E. Knuth, Tracy L. Larrabee y Paul M. Roberts. Hay un libro publicado, videos de conferencias y un conjunto de notas. está más escrito desde la perspectiva de las personas que intentan dominar la escritura matemática, por ejemplo, para crear documentos, pero todos los consejos son muy aplicables al caso de los legos que intentan formular problemas con precisión. La escritura matemática, aunque formidable de aprender, es el enfoque científico para definir / formular rigurosamente, y como el libro detalla, resolver , por ejemplo, a través de algoritmos o pruebas, problemas computacionales / algorítmicos.

Además, el texto clásico de Garey & Johnson, Computadoras e Intractabilidad no describe exactamente cómo formular problemas con precisión, pero da muchos ejemplos y diversos "patrones" teóricos / conceptuales / técnicos, organizados en secciones de problemas similares, que pueden ser usado como "bloques de construcción" para describir problemas computacionales / algorítmicos.

vzn
fuente
Gracias vzn, estos son buenos recursos para escribir matemáticas, pero no estoy buscando algo diferente. El problema no es escribir bien en matemáticas, sino recursos para que las personas aprendan a formular problemas computacionales con la suficiente claridad como para que un experto pueda entender qué está buscando la persona que hace la pregunta y ayudarlos.
Kaveh
yw; usted dice que son dos cosas diferentes, y en palabras / frases lo son, pero y yo digo que son [para tomar prestada una frase de ingeniería de software] "estrechamente acoplados"
vzn
0

Compre el libro Algorithms and Data Structures de Robert Lafore.

En este libro, cada algoritmo se explica como una historia, muy parecida a una poesía. Luego, dele a la persona la versión Lafore de un algoritmo, y luego la versión CLRS.

Tal vez así, la persona tendrá una idea de cómo traducir de una descripción intuitiva a una rigurosa.

usuario5193682
fuente