Universidad Nacional Mayor de San Marcos Facultad de Ingeniera de Sistemas e Informtica EAP de Ing. De

Sistemas Inteligencia Artificial

Examen Parcial Semestre 2012 1 1.- Conceptos (6 puntos) Marque al lado derecho V para verdadero y F para Falso (+0.2 correcta, -0.05 incorrecta) 1. Ordenar un cubo mgico (esto es colocar el cubo de tal forma que cada cara del cubo tenga un solo color) es un problema de localizacin ( V ) 2. Es ms fcil demostrar un teorema con el menor nmero de pasos que simplemente demostrarlo. ( F ) 3. Si un problema de decisin es NP-difcil entonces su correspondiente problema de optimizacin puede ser tratable. ( F ) 4. En general los problemas de optimizacin con variables de decisin 0-1 son problemas de la clase NP-Difcil. ( F ) 5. Es recomendable usar sistemas inteligentes para resolver problemas considerados operacionales. ( V ) 6. La inteligencia es exclusividad de las maquinas hechas de protenas. ( F ) maquina puede llegar a mostrar inteligencia si esta no es percibida como tal en una conversacin con un agente humano. 7. El desarrollo de metodologas para desarrollar machine learning (maquinas que aprenden) corresponde al objetivo de la ciencia de la inteligencia artificial. ( V ) 8. Paradigma sub-simblico: redes neuronales artificiales, meta-heurstica, vida artificial. ( F ) 9. El desarrollo de compiladores para procesar lenguaje natural corresponde al rea de procesamiento de imgenes. ( F ) 10. El desarrollo de sistemas de crditos financieros (este es el sistema sugiere si se debe otorgar o rechazar una solicitud de crdito) basados en reglas de negocio corresponde al paradigma sub-simblico. ( F ) 11. Es adecuado usar tecnologa de inteligencia artificial para desarrollar sistemas de transacciones bancarias. ( F ) 12. Es adecuado usar los lenguajes de Inteligencia Artificial para implementar vida artificial. ( V ) 13. Es adecuado usar inteligencia artificial para hacer pronsticos de la demanda de productos farmacuticos. ( V ) 14. El sistema de produccin tiene por objetivo generar sucesores (nuevos estados) a partir de la aplicacin de las reglas (verificables) sobre un estado de entrada. ( V ) 15. El problema de bsqueda en un espacio de estado se puede resumir como encontrar desde el espacio de estado un camino (secuencia de reglas y/o estados) que inicie con el estado inicial y termine con el estado meta. ( V ) 16. Siempre se debe explicitar el estado meta. ( V ) 17. Toda regla que es 18. Es adecuado usar los mtodos de camino mnimo para resolver problemas de inteligencia artificial mediante bsqueda en un espacio de estados. ( V ) 19. Cuando el valor de la funcin evaluadora es constante para cualquier estado, entonces los mtodos de bsqueda informada tienen el mismo comportamiento de los llamados mtodos ciegos. ( V )

20. El mtodo de bsqueda de ramificacin con criterio FIFO es equivalente al mtodo de bsqueda en profundidad. ( F ) 21. Los mtodos de bsqueda en el peor de los casos pueden recorrer todo el espacio de estados; esto es, presentan complejidad no polinomial. ( F ) 22. Una funcin evaluadora asociada a los problemas de optimizacin es dada por la funcin objetivo a optimizar. ( V ) 23. El juego denominado pquer en el contexto de juegos inteligentes humano-maquina corresponde a los juegos por turno con informacin incompleta. ( V ) 24. La bsqueda en profundidad siempre es ms eficiente que la bsqueda en amplitud. ( F ) 25. El mtodo de bsqueda denominado Ascenso a la Colina siempre genera solucin ptima. ( F ) 26. En el mtodo de bsqueda no determinista es fundamental definir correctamente la funcin de evaluacin. ( V ) 27. Si h*(N) es el costo de la ruta optima desde N al nodo meta, se dice que una heurstica h es admisible si 0

Dada la funcin heurstica h(n) = p2 + p3 + p4 + p5 + dv donde p, vale 0 si la casilla i contiene la asignacin correcta respecto del estado final y vale 1 en caso contrario y dv es la distancia del blanco respecto a la posicin final (casilla 1). UNMSM - FISI Grupo 8 Por ejemplo, h(estado inicial) = 1 + 4 = 5 Responda: 2.1 Representar el problema como una bsqueda en el espacio de estados (describa: objetos, estado, estado inicial, estado meta, y el sistema de produccin). Observe que hay una regla para cada movimiento. (4 puntos) Solucion : Objetos: Monedas Vector Estado E( M[], pos, letra, costo) M[] = vector de monedas Pos = posicin final de la moneda. Letra = letra que se encuentra en esa posicin 0= vaco 1 = A 2= R Costo = costo que implica el movimiento de la moneda. Estado Inicial

Costo=0 Estado Meta

Reglas:

REGLA CONDICION MOVIMIENTO

Desplazar Derecha M[pos+1] =0 Pos0

E(M[],pos,letra,costo) M[pos]=0 M[pos-1]=letra Costo= costo+1

Girar A Pos>= 0 || pos= 0 || pos=0 Pos+2=0 Pos+2

El tramo B-C se encuentra obstruido, y los tiempos en minutos de recorrido del robot para los tramos son dados por: A-B: 14, B-H: 10, H-E: 7, E-F: 8, E-D: 11, D-C: 9, F-D: 5, F-G: 13, G-H: 10, G-J: 11, J-I: 5, I-K: 2, I-H: 13. Responda: Aplique el algoritmo A* o ramificacin y acotacin para determinar la mejor ruta que permita el rescate del minero herido. Indique para cada iteracin LE,P, y LV para A* o Cotas para Ramificacin y acotacin. Precise la funcin de evaluacin y el criterio usado. Primera Parte : De A hacia C

Nodo Peso

A 20

B 15

D 4

E 8

F 8

G 23

H 21

I 25

J 27

K 26

I LE P LV

1 A-20 A -

2 AB-29 B A

3 ABH-45 H A B

4 ABHI-62 ABHG-57 ABHE-39 E A B H

5 ABHEF -47 ABHED-46 D A B H E

6 ABHEDC-51 C A B H E D

7 ABHEDC A B H E D C

Segunda Parte de C hacia A o K F(X) = G(X) + |H1(X) -H2(X)|

Nodo Peso

B 4

C 20

D 22

E 15

F 18

G 10

H 7

I 5

J 8

K 5

I LE P LV

1 C-6 C -

2 CD-10 D C

3 CDE-5 CDF-24 E C D

4 CDEF-32 CDEH-28 CDF-24 F C D E

5 CDFG-45 CDEH-28 CDEF-32 H C D E F

6 CDEHB-40 CDEHI-41 CDEHG-41 CDFG-45 B C D E F H

7 CDEHBA-56 CDEHI-41 CDEHG-41 CDFG-45 I C D E F H B

8 CDEHIK-47 CDEHIJ- 49 CDEHBA-56 DEHG-41 CDFG-45 K C D E F H B I

9 CDEHIK-47 C D E F H B I K

Nodo Peso

B 5

C 7

D 26

E 23

F 20

G 22

H 6

I 5

J 4

K 5