Problema computacional

En ciència computacional teòrica, un problema computacional o problema abstracte és una relació entre un conjunt de instàncies i un conjunt de solucions. Un problema abstracte permet establir formalment la relació desijada entre cada instància del problema i la seua corresponent solució. Una solució algorítmica a un problema abstracte consistix d'un algoritme que per cada instància del problema calcula a lo manco una solució corresponent –en cas d'haver-la– o expedix un certificat de que no existix solució alguna. Un problema abstracte es convertix en un problema concret quan les instàncies i solucions estan codificades en forma de llenguages formals.

Els problemes abstractes solen definir-se en dos parts: en la primera es descriu al conjunt d'instàncies i en la segona es descriu la solució esperada per a cada instància. Per eixemple, el problema d'ordenació d'número entero se sol definir com seguix:

Instància: Una successió finita d'número entero

(a_{1}, a_{2}, \dots, a_{n})

Solució: Una permutació

(a_{1}^{'}, a_{2}^{'}, \dots, a_{n}^{'})

de la successió d'entrada tal que

a_{1}^{'} \leq a_{2}^{'} \leq \dots \leq a_{n}^{'}

Ací tant el conjunt d'instàncies i el de solucions és el mateix, puix es tracta del conjunt de totes les successions finitas d'número entero. La relació que hi ha entre ells assigna a cada successió $(a_{1}, a_{2}, \dots, a_{n})$ l'única permutació $(a_{1}^{'}, a_{2}^{'}, \dots, a_{n}^{'})$ tal que $a_{1}^{'} \leq a_{2}^{'} \leq \dots \leq a_{n}^{'}$ . Per eixemple, $(6, 9, 4, 5)$ té com a solució a $(4, 5, 6, 9)$ . Una solució algorítmica al problema d'ordenament és l'ordenament de bombeta perque este algoritme produïx una solució com a eixida cada volta que se li suministra una instància com a entrada.

Tipos de problemes computacionals

Artícul principal → Problema de decisió.

En un problema de decisió cada instància té associada exactament una solució "sí" o "no". Els problemes de decisió queden completament determinats pel conjunt

Y

d'instàncies que tenen associada la solució "sí". Per eixemple, el problema de decidir si una gràfica té o no un cicle Hamiltoniano queda completament determinat el seu conjunt de solucions "sí":

$H A M = {G ∣ G es una gráfica hamiltoniana}$

En esta representació el problema equival a preguntar si una instància

i

pertany o no al conjunt

H A M

. En general, els problemes de decisió sempre equivalen a decidir la proposició

i \in Y

a on

Y

és el conjunt d'instàncies en solució "sí". Una solució algorítmica per a un problema de decisió és un algoritme que calcula la funció característica de

Y

o equivalent:

$χ_{Y} (i) = {\begin{matrix} 1 & si i \in Y \\ 0 & si i \notin Y \end{matrix}$

En els problemes de busca la relació entre el conjunt d'instàncies i el de solucions queda determinat per un predicat llògic $P (i, s)$ que determina si $s$ és una solució de $i$ . Donada una instància $i$ el problema consistix en trobar, si és que existix, una solució $s$ de $i$ . És dir, buscar l'element $s$ que faça verdadera la proposició $\exists s \in S . P (i, s)$ . Quan es fixa el valor de $i$ i la solució és única, es diu que és un problema matemàtic. Per eixemple, el problema de factorización d'un número entero $n$ consistix en trobar un factor no trivial de $n$ ; és dir, número entero $m$ diferent d'1 i de $n$ tal que $m$ dividixca exactament a $n$ . En símbols

$\exists m \in 𝐙 . m \neq 1 \land m \neq n \land \frac{n}{m} \in 𝐙$

Esta fòrmula simplement està preguntant l'existència d'un factor no trivial de $n$ . Una solució algorítmica a un problema de busca ve dador per un algoritme $f$ tal que $P (i, f (i))$ és verdadera sempre i quan existixca solució per a $i$ , és dir, $f$ sempre calcula una solució si és que esta existix. En el cas del problema de la factorización de sancers es conta en l'algoritme de la divisió per tentativa.

Artícul principal → Optimisació (matemàtica).

En un problema d'optimisació no solament es busca una solució, sino que es busca "la millor" de totes. Cada problema d'optimisació pot concebre's com un problema de busca i una funció $g$ , comunament coneguda com a funció objectiu, que determina la calitat de les solucions. El problema d'optimisació (que a la seua volta és de busca) consistix en trobar la solució maximizar o minimise el valor de $g$ . Per eixemple, el problema del viajante no solament exigix determinar si una gràfica té o no un cicle hamiltoniano, sino que ademés pregunta quin és el cicle hamiltoniano més curt. En este cas el problema de busca subjacent és trobar un cicle hamiltoniano qualsevol i la funció objectiu medix la distància recorreguda per eixe cicle.

Referències

Gómez Navas Lozano, Ricardo Iván, Gómez Navas Chapa Leonardo, Introducció a les Ciències Socials, McGraw Hill, China, 2011

Este artícul conté una traducció derivada de «Problema computacional» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.