Problema computacional

Problema computacional
En ciencia computacional teórica, un problema abstracto o problema computacional es una relación entre un conjunto de instancias y un conjunto de soluciones. Un problema abstracto permite establecer formalmente la relación deseada entre la entrada de un algoritmo y su salida. Una solución algorítmica a un problema abstracto consiste de un algoritmo que por cada instanciadel problema calcula al menos una solución correspondiente –en caso de haberla– o expide un certificado de que no existe solución alguna. Un problema abstracto se convierte en un problema concreto cuando las instancias y soluciones están codificadas en forma de lenguajes formales.
Los problemas abstractos suelen definirse en dos partes: en la primera se describe al conjunto de instancias y en lasegunda se describe la solución esperada para cada instancia
Tipos de problemas abstractos
En un problema de decisión cada instancia tiene asociada exactamente una solución "sí" o "no". Los problemas de decisión quedan completamente determinados por el conjunto Y de instancias que tienen asociada la solución "sí". Por ejemplo, el problema de decidir si una gráfica tiene o no un ciclo Hamiltonianoqueda completamente determinado su conjunto de soluciones "sí".
En los problemas de búsqueda la relación entre el conjunto de instancias y el de soluciones queda determinado por un predicado lógico P(i,s) que determina si s es una solución de i. Dada una instancia i el problema consiste en encontrar, si es que existe, una solución s de i. Es decir, buscar el elemento s que haga verdadera laproposición \exists s\in S.P(i,s). Cuando se fija el valor de i y la solución es única, se dice que es un problema matemático. Por ejemplo, el problema de factorización de un número entero n consiste en encontrar un factor no trivial de n; es decir, número entero m diferente de 1 y de n tal que m divida exactamente a n. En símbolos
Resolución de problemas de programación
La resolución de un problemamediante un ordenador consiste en el proceso que a partir de la descripción de un problema, expresado habitualmente en lenguaje natural y en términos propios del dominio del problema, permite desarrollar un programa que resuelva dicho problema.
Este proceso exige los siguientes pasos:
Análisis del problema.
Diseño o desarrollo de un algoritmo.
Transformación del algoritmo en un programa(codificación).
Ejecución y validación del programa.
Los dos primeros pasos son los más difíciles del proceso. Una vez analizado el problema y obtenido un algoritmo que lo resuelva, su transformación a un programa de ordenador es una tarea de mera traducción al lenguaje de programación deseado.
Pseudocódigo
En ciencias de la computación, y análisis numérico, el pseudocódigo (o falso lenguaje) es una descripciónde alto nivel compacta e informal1 del principio operativo de un programa informático u otro algoritmo.
Utiliza las convenciones estructurales de un lenguaje de programación real2, pero está diseñado para la lectura humana en lugar de la lectura mediante máquina, y con independencia de cualquier otro lenguaje de programación. Normalmente, el pseudocódigo omite detalles que no son esenciales para lacomprensión humana del algoritmo, tales como declaraciones de variables, código específico del sistema y algunas subrutinas. El lenguaje de programación se complementa, donde sea conveniente, con descripciones detalladas en lenguaje natural, o con notación matemática compacta. Se utiliza pseudocódigo pues este es más fácil de entender para las personas que el código del lenguaje de programaciónconvencional, ya que es una descripción eficiente y con un entorno independiente de los principios fundamentales de un algoritmo. Se utiliza comúnmente en los libros de texto y publicaciones científicas que se documentan varios algoritmos, y también en la planificación del desarrollo de programas informáticos, para esbozar la estructura del programa antes de realizar la efectiva codificación....