Black Jack

UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS
(Universidad del Perú, Decana de América)

FACULTAD DE CIENCIAS MATEMATICAS.
E.A.P. COMPUTACIÓN CIENTÍFICA
UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS
(Universidad del Perú, Decana de América)

FACULTAD DE CIENCIAS MATEMATICAS.
E.A.P. COMPUTACIÓN CIENTÍFICA


“EJERCICIOS APLICATIVOS DE INTELIGENCIA ARTIFICIAL”

CURSO : INTELIGENCIAARTIFICIAL
PROFESOR : OSCAR BENITO PACHECO
INTEGRANTES: TIRADO URIARTE, ABIMAEL
TORREZ MARTINEZ, IVAN
VILLAFUERTE MATURRANO, KATHERINE



LIMA-2012

COMPLEJIDAD DE PROBLEMAS ALGORÍTMICOS

I. Responda con T para Verdadero y F para falso para las siguientes afirmaciones.1.1- (T)
Porque se llama problemas computables a aquella abstracción de la realidad que tiene representación algorítmica y no computable a aquellos problemas que no se pueden representar mediante algoritmos.
Los algoritmos permiten encontrar soluciones a problemas computables donde estas soluciones deben ser de complejidad polinomicas (tratables) y de complejidad superior a lapolinómica (intratables).
1.2 (T)
De hecho existe una solución en tiempo P para todos los problemas de NP-completo.
1.3 (T)
Pues si un problema es intratable no se sabe si tiene solución polinómica o no por tanto es indecidible.
1.4 (T)
Porque puede representarse mediante algún algoritmo.
1.5 (T)
La pregunta ¿P = NP? es el más importante problema abierto en Computación teórica.
Preguntas comoésta motivan la introducción de los conceptos de hard (difícil)
1.6 (T)
Si un problema es intratable entonces solución de complejidad superior a la polinómica entonces  pueden ser resueltos por una máquina no determinista en tiempo polinómico lo que ahora seria un problema no computable.
1.7 (T)
Si existe un algoritmo el problema es computable entonces significaría que es tratable.
1.8 (T)
1.9(F)
A los problemas tratables se les conoce también como problemas P (de orden
polinomial). Asimismo a los problemas no tratables se les llama también
NP (de orden no determinístico polinomial).
1.10 (T)
Pues como ejemplo ponemos el problema del viajero.
II. Clasifique los siguientes problemas de acuerdo al tipo de respuesta.

3.1 MISIONEROS Y LOS CANÍBALES.
Tres misioneros ytres caníbales están en una de las márgenes de un río junto a un bote en la que sólo cabe 1 o 2 personas. Hay que encontrar la manera de pasarlos al otro lado del río pero teniendo cuidado que en ningún momento quede un grupo de misioneros junto con un grupo de caníbales, siendo la cantidad de misioneros menor a la de caníbales.

DEFINICION DEL PROBLEMA

Se debe considerar una secuenciaordenada de 3 números que representarán: la cantidad de misioneros, caníbales y en que orilla del río se encuentran.
Por lo tanto, el estado inicial será: 3, 3, 1.
El estado objetivo será: 0, 0, 0 en la orilla izquierda y 3, 3, 1 en la orilla derecha.

Operadores posibles:

Pueden ser que un bote:

No lleva ningún misionero y lleva un caníbal.
Lleva 2 misioneros y ningún caníbal.Lleva 2 caníbales y ningún misionero.
Lleva 1 caníbal y un misionero.
No lleva ningún caníbal y lleva un misionero.

Solo está permitido si hay igual o más misioneros que caníbales en una orilla o no hay misioneros que afectar en una orilla.
Se utilizará la búsqueda preferente por profundidad o depth search first.
En la búsqueda preferente por profundidad siempre se expande uno de losnodos que se encuentre en los más profundo de árbol, por lo tanto los nodos sucesores estarán a profundidades cada vez mayores.

DESARROLLO EN PROLOG:

/* Problema de los Caníbales y Misioneros usando búsqueda Depth First
Desarrollado en : Visual Prolog v. 5.1
(versión gratuita de Prolog (VIP.exe) bajada de : www.visual-prolog.com ).
Autor : Abimael Tirado Uriarte e Ivan Torrez Martinez...