Problema abstracto

Problema abstracto

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 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 instancia del 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 la segunda se describe la solución esperada para cada instancia. Por ejemplo, el problema de ordenación de números enteros se suele definir como sigue:

Entrada: Una sucesión finita de números enteros \left(a_1,a_2,\ldots,a_n\right)
Salida: Una permutación \left(a_1^\prime,a_2^\prime,\ldots,a_n^\prime\right) de la sucesión de entrada tal que a_1^\prime\le a_2^\prime\le \cdots,a_n^\prime

Aquí tanto el conjunto de instancias y el de soluciones es el mismo, pues se trata del conjunto de todas las sucesiones finitas de números enteros. La relación que hay entre ellos asigna a cada sucesión \left(a_1,a_2,\ldots,a_n\right) la única permutación \left(a_1^\prime,a_2^\prime,\ldots,a_n^\prime\right) tal que a_1^\prime\le a_2^\prime\le \cdots,a_n^\prime. Por ejemplo, \left(6,9,4,5\right) tiene como solución a \left(4,5,6,9\right). Una solución algorítmica al problema de ordenamiento es el ordenamiento de burbuja.

Tipos de problemas abstractos

Artículo principal: Problema de decisión

En un problema de decisión cada instancia tiene asociada exactamente una solución "" o "no". Los problemas de decisión quedan completamente determinados por el conjunto Y de instancias que tienen asociada la solución "". Por ejemplo, el problema de decidir si una gráfica tiene o no un ciclo Hamiltoniano queda completamente determinado su conjunto de soluciones "":

\mathrm{HAM}=\left\{G\mid G\text{ es una gráfica hamiltoniana}\right\}

Con esta representación el problema equivale a preguntar si una instancia i pertenece o no al conjunto HAM. En general, los problemas de decisión siempre equivalen a decidir la proposición i\in Y donde Y es el conjunto de instancias con solución "". Una solución algorítmica para un problema de decisión es un algoritmo que calcula la función característica de Y o equivalente:

\chi_Y(i)=\begin{cases}1&\text{si }i\in Y\\0&\text{si }i\notin Y\end{cases}

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 la proposició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 m. En símbolos

\exists m\in\mathbf Z.m\ne 1\wedge m\ne n\wedge\frac n m \in \mathbf Z

Esta fórmula simplemente está preguntando la existencia de un factor no trivial de n. Una solución algorítmica a un problema de búsqueda viene dador por un algoritmo f tal que P\left(i,f(i)\right) es verdadera siempre y cuando exista solución para i, es decir, f siempre calcula una solución si es que esta existe. En el caso del problema de la factorización de enteros se cuenta con el algoritmo de la división por tentativa.

Artículo principal: Optimización (matemática)

En un problema de optimización no solo se busca una solución, sino que se busca "la mejor" de todas. Cada problema de optimización puede concebirse como un problema de búsqueda y una función g, comúnmente conocida como función objetivo, que determina la calidad de las soluciones. El problema de optimización (que a su vez es de búsqueda) consiste en encontrar la solución maximice o minimice el valor de g. Por ejemplo, el problema del viajante no solamente exige determinar si una gráfica tiene o no un ciclo hamiltoniano, sino que además pregunta cuál es el ciclo hamiltoniano más corto. En este caso el problema de búsqueda subyacente es encontrar un ciclo hamiltoniano cualquiera y la función objetivo mide la distancia recorrida por ese ciclo.

Referencias

  • Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). Introduction to algorithms. Cambridge, Massachusetts: The MIT Press. ISBN 978-0-262-53305-8.
Obtenido de "Problema abstracto"

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Problema didáctico — Saltar a navegación, búsqueda Un problema didáctico es un ejercicio de raciocinio que se puede resolver utilizando las matemáticas y la lógica. Un problema planteado tiene tres elementos básicos: los datos necesarios para resolverlo (que son… …   Wikipedia Español

  • Problema del ángel — Saltar a navegación, búsqueda La región azul de puntos indica a dónde podría ir un ángel de poder 3. El problema del ángel es un problema perteneciente a la Teoría de Juegos, propuesto por John Horton Conway.[1 …   Wikipedia Español

  • Problema del barbero durmiente — Saltar a navegación, búsqueda En ciencias de la computación, el problema del barbero durmiente es un problema de sincronización. El problema consiste en una barbería en la que trabaja un barbero que tiene un único sillón de barbero y varias… …   Wikipedia Español

  • Problema matemático — Un problema matemático es un problema que se puede resolver utilizando las matemáticas. Los problemas matemáticos se utilizan en todos los niveles educativos de matemáticas para enseñar a los alumnos a asociar situaciones del mundo real con el… …   Enciclopedia Universal

  • Tipo de dato abstracto — Un tipo de dato abstracto (TDA) o Tipo abstracto de datos (TAD) es un modelo matemático compuesto por una colección de operaciones definidas sobre un conjunto de datos para el modelo. Contenido 1 Introducción 2 Historia 3 Definición …   Wikipedia Español

  • Tipo abstracto — Este artículo trata sobre tipos sin miembros directos; ver también Tipo de dato abstracto. En ingeniería de software, un tipo abstracto es un tipo en un sistema de tipo nominativo que es declarado por el programador, y que tiene la propiedad de… …   Wikipedia Español

  • Algoritmo — Los diagramas de flujo sirven para representar algoritmos de manera gráfica. En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático persa Al… …   Wikipedia Español

  • Universal (metafísica) — Universal es la cualidad que hace referencia al Universo. Universum, Grabado Flammarion ,xilografía, publicada en París 1888. El Universo y lo universal se definen como conceptos respecto a diversos ámbitos …   Wikipedia Español

  • Wikipedia:Consultas/Consultas lingüísticas — Atajo WP:CLWP:CL INSTRUCCIONES Por favor lee detenidamente estas instrucciones …   Wikipedia Español

  • Wikipedia:Café (todos) — Atajos WP:CWP:C …   Wikipedia Español


Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.