• Author / Uploaded
• pepecr

Citation preview

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini Se

Fernando Sancho Caparrini Inicio

Docencia

Cursos

Buscar palabras usadas en entradas y páginas de este sitio Introduzca aquí la[s] palabra[s] a buscar:

Introduca términos de bús

TEMAS

Investigación

Proyectos

Publicaciones

Últimas Entradas

Por Temas

« Examen Bloque II. Dic… « || Inicio || » Calificacio

Ejercicios IA Última modificación: 30 de Noviembre de 2019, y ha te

Esta colección muestra un conjunto de ejercicios que pueden resolverse con las diversas técnicas estu largo del curso. Se recuerda que la sección de problemas genéricos pueden ser adaptados para ser resueltos p de los métodos vistos, desde la simple representación del problema como espacio de estados, hasta los m avanzados de PSO o Colonias de Hormigas. Una vez representados para ser resueltos por una técnica pa aconseja realizar la implementación correspondiente en NetLogo haciendo uso de las librerías proporcion curso.

agentes, algoritmos,

El índice de las diversas colecciones de ejercicios es la siguiente:

aprendizaje automático, busqueda, complejidad,

Ejercicios de NetLogo Colección Genérica de Problemas: Representación IA Clásica:

inteligencia artificial, investigación, lógica, machine learning,

matemáticas, modelado,

netlogo, opinión,

Lógicas:

simulacion, universidad(todas)

Lógica Proposicional - LP Lógica de Primer Orden - LPO Lógica Difusa - LD

LOS MÁS LEÍDO

Satisfacción de Restricciones - PSR Búsqueda/Planificación Clásicas Juegos con Adversario 1. Aprendizaje Supervisado y No Supervisado (39606 vistas) 2. Redes Neuronales: una visión superficial (27213 vistas) 3. Algoritmos de hormigas y el problema del viajante (25933 vistas) 4. Aprendizaje Inductivo: Árboles de Decisión (25536 vistas) 5. Introducción al Aprendizaje Automático (23792 vistas) 6. Introducción a la Lógica Difusa (22722 vistas) 7. Entrenamiento de Redes Neuronales: mejorando el Gradiente Descendiente (18451 vistas) 8. PSO: Optimización por enjambres de partículas (17474 vistas) 9. Una introducción a Prolog (17283 vistas) 10. Sistemas Complejos, Sistemas Dinámicos y Redes Complejas (16750 vistas)

Inteligencia Colectiva: Inteligencia Colectiva Sistemas Dinámicos y Redes Complejas Fractales Autómatas Celulares Algoritmos Genéticos - GA Algoritmos de Hormigas - ACO Optimización por Sistemas de Partículas - PSO Aprendizaje Automático: Clustering y KNN Árboles de decisión - ID3 Mapas Auto-organizados - SOM Redes Neuronales Artificiales - RNA

NetLogo 1.- Propagación de fuego por un tereno: En este modelo haremos uso únicamente de los patches analizar cómo influye la densidad de madera seca en el terreno para la propagación de un fuego que com foco puntual.

NETLOGO BOOK

Prepara el terreno asignando aleatoriamente patches con madera seca siguiendo una de probabilidad (que será dada por medio de un slider). Sitúa un fuego en el patch central (0,0). Crea un procedimiento de propagación de un paso: un patch con fuego se propaga a cualquiera de s que tenga madera seca. Añade un botón forever que ejecute el procedimiento anterior. Posibles extensiones: Añade fuerza y direccionalidad del viento (justifica la interpretación dada).

www.cs.us.es/~fsancho/?e=159

1/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

Añade diferencias en el terreno (proporción de seco, tiempo de quemado y de propagación,...). Añade plots q muestren los resultados. 2.- Propagación de mensajes entre individuos: En este modelo haremos uso únicamente de las t idea es analizar cómo de rápido se difunde un mensaje entre una población móvil. Para simplificar, com asignando un movimiento aleatorio a los agentes. Prepara los agentes con alguna caracteristica que permita saber si tienen el mensaje o no (aquellos tenga no lo difundirán). En cada paso, los agentes que tengan el mensaje se lo comunicarán a aquellos que estén en su mism Proporciona un slider para determinar el número de agentes en el mundo.

In english and spanish, the new book to learn NetLogo. 16 chapters going from the basics to advanced features. With exercises proposed in every chapter and full examples.

Posibles extensiones: Prueba con distintos modelos de movimiento (lineal, restringido a ciertas áreas,...). Representa de alguna forma el número de veces que los agentes reciben el mensaje (color del a ejemplo). Proporciona una fuerza de impacto inicial al mensaje, de forma que a medida que lo oiga el agente m esta fuerza de impacto decaiga y, superado un umbral, ya no lo transmita más.

ENLACES

Computación GMSC-UCE A.I.T. Programación NetLogo Elm Haskell Julia

3.- Juego de la vida (Conway): El juego de la vida es en realidad un juego de cero jugadores determin quiere decir que su evolución está determinada por el estado inicial y no necesita ninguna interacción poster El "tablero de juego" es una malla formada por cuadrados ("células") que se extiende por el infinito e direcciones. Se consideran las 8 células vecinas de cada célula. Las células tienen dos estados: están "vivas" o (o "encendidas" y "apagadas"). El estado de la malla evoluciona a lo largo de unidades de tiempo discretas decir que por turnos). El estado de todas las células se tiene en cuenta para calcular el estado de las mism siguiente. Todas las células se actualizan simultáneamente. Las transiciones dependen del número de células vecinas vivas: Una célula muerta con exactamente 3 células vecinas vivas "nace" (al turno siguiente estará viva). Una célula viva con 2 ó 3 células vecinas vivas sigue viva, en otro caso muere o permanece mu "soledad" o "superpoblación").

Machine Learning GIDTEC Datrik Intel. Cambrian Intel. Humanidades Digitales

4.- Para el modelo NetLogo/Social Science/Segregation model, se proponen las siguientes extensiones

CulturePlex BaroqueArt ExpoFinder

Añade un slider %-rojo, para especificar el % de población que debe ser roja (el resto será verde) posibles usos para esta variable:

Grupos de C.C.I.A. R.G.N.C. Lóg. Computacional Lóg. Matemática

Crear exctamente una proporción %-rojo de rojos. Crear cada agente con una proporción %-rojo de ser rojo, por lo que la media de rojos será en cada ejecución puede haber pequeñas fluctuaciones. Añade un slider ProbMovimientoAleatorio. Modifica el comportamiento de los agentes para q probabilidad que indique ese slider se muevan, independientemente de que sean felices donde está hay distintas opciones para esta extensión, selecciona una de ellas y justifica porqué se ha selecciona Añadie un slider para controlar la distancia a la que puede moverse un agente. Añade alguna variale local que controle cómo se mueven los agentes:

CONTACTO Dpto. Ciencias de la Computación e Inteligencia Artificial, Universidad de Sevilla . Dirección:E.T.S.I.I. Av. Reina Mercedes, s/n. 41012, Sevilla

solo a las celdas aceptables a la celda libre más cercana a la celda aceptable más cercana a la celda libre más lejana a la celda aceptale más lejana

Tfno: (+ 34) 954556979, Fax: (+34) 954556599 Despacho: H1.48 e-mail: fsancho en us(.)es

Añade alguna medida de segregación inventada por ti y represéntala en un plot. 5.- Juego del más fuerte: Tenemos una familia de agentes con una variable que indica su fuerza. Alea los agentes se mueven por el mundo y, si se encuentran dos de ellos, se enfrentan de forma probabilística, es cual "genera un número proporcional a su fuerza" y el que pierda muere. Gana el último agente que quede en Posbles extensiones: El que gane cada batalla pierde los puntos que sacase su contrincante. Los jugadores se recuperan poco a poco mientras no se enfrentan a otros. Introducir características de lucha (fuerza, habilidad, ...) y definir un juego adecuado con ese escena Para comprobar que la realización de los siguientes ejericios es correcta se debe tener algún grafo NetLogo, por ello se recomienda hacer todos en el mismo modelo y poder asi usar unos como base de los sigu www.cs.us.es/~fsancho/?e=159

2/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

6.- Haz un procedimiento que genere el grafo completo de grado n . 7.- Haz un procediiento que genere un grafo aleatorio de n nodos y m aristas. 8.- Dado un grafo, crea un procedimiento que etiquete cada nodo con el grado que tiene (número incidentes en él). 9.- Haz un procedimiento que reciba como dato un nodo, y etiquete el resto de nodos del grafo con la dis nodo (distancia en el grafo, es decir, el número mínimo de pasos para llegar de uno al otro). 10.- Haz un procedimiento que etiquete cada nodo con un identificador que corresponda con la compone a la que pertenece. (Es decir, numera las componentes conexas, y etiqueta los nodos de cada compon número de la componente a la que pertenecen). 11.- Estudia el modelo "Preferential Attachament", que genera un grafo de tamaño n siguiendo la ley preferencial": se van añadiendo nodos al grafo de forma que cada nodo nuevo se enlaza solo con uno de los p ese momento, y la probabilidad de unirse a cada uno de los nodos existentes es directamente proporcional esos nodos. Es decir, siguiendo la ley: "cuanto más tienes, más consigues". 12.- Haz un procedimiento que reciba como entrada dos nodos, y devuelva, si lo hay, el camino que va de segundo. 13.- Repetid los primeros ejercicios de esta sección poniendo como soporte un grafo en vez de patches (d sentido).

Colección Genérica de Problemas: Representación Para todos los problemas siguientes se pueden considerar las siguientes preguntas generales, ade preguntas particulares que se proporcionan junto con los enunciados de los mismos: Da una representación de los posibles estados, y describe el espacio completo de estados. ¿Qué tam este espacio? Indica un espacio inicial válido. Proporciona una función para saber si un estado es final o no (comprobación de objetivo). Proporciona una función de transición válida para resolver el problema como una búsqueda en el estados. Proporciona una función de coste que tenga sentido para medir la ejecución de la función de transic Proporciona una función heurística que sirva para medir la bondad de un estado respecto de buscado. Según algunos de los métodos de resolución que se ven en el curso, puedes intentar los siguientes ejer cada método: Espacios de Estados: del 1 al 40 BFS: del 1 al 26, del 29 al 30, el 33, 35, 36, 38, 40 A*: del 3 al 8, del 11 al 26, el 29, 31, 33, 35, 36, 38, 40 Templado Simulado: el 1, 5, 6, 12, 13, del 15 al 18, del 20 al 40 Algoritmos Genéticos: el 1, 4, 5, 6, 12, 13, 15, 16, 17, 18, del 20 al 40 PSO: el 28, 32, 34 ACO: el 1, 3, 7, 11, 12, 16, 17, 18, 22, 23, 24, 27, 30, 37, 38, 40 Satisfacción de Restricciones: el 5, 12, 13, 31, 33, 36, del 40 al 44 Lógica: del 41 al 44

Lista de Problemas 1. Problema del coloreado de Mapas: Fijado un grafo,

G

, con un etiquetado dado y un

que indica si los nodos x e y son vecinos en G . Determina (y en caso positivo, propo existe un coloreado válido de G haciendo uso de K colores. (Un coloreado es una asignación de vecinos?(x, y)

nodos, y es válido si nodos conectados están coloreados con colores distintos). 2. Un mono de 30cm de altura, que no puede saltar se mete en una habitación en la que hay colg plátanos a 90cm de altura. Evidentemente, el mono quiere un plátano. Además, la habitación tiene apilables de 30cm de alto que podrían soportar al mono. 3. Problema de las 3 Jarras: Se tienen 3 jarras de 12, 8 y 3 litros de capacidad y un grifo. Las op que se pueden realizar con ellas son: llenar cada una de las jarras de agua, volcar el contenido cualquier otra (hasta que una de las dos se vacía, o la otra se llena), o bien vaciar su contenido en e objetivo es conseguir exactamente 1 litro en alguna de las jarras. www.cs.us.es/~fsancho/?e=159

3/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

4. Formaliza la siguiente versión del puzzle Todos los dígitos del Rey: Dado el conjunto 0123456789, inserta los símbolos de los operadores aritméticos (× + −/,) y paréntesis entre ellos p expresión resultante se evalúe como 100. Por ejemplo: 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + (8 × 9) = 100

¿Puedes encontrar alguna otra solución?

5.

Un cuadrado mágico consiste en una distribución de números en filas y formando un cuadrado, de forma que los números de cada fila, columna y diagonal suman lo mism es posible recrear diferentes tipos de cuadrados mágicos, tradicionalmente se forman con los naturales desde el 1 hasta n , donde n es el lado del cuadrado. Representa el problema de g 2

automática de cuadrados mágicos de tamaño n como un problema de espacio de estados. ¿Cuál serí de ramificación y profundidad? 6. Tenemos 10 cartas numeradas del

1

al

. Sepáralas en

10

2

montones de forma que la suma de las

primer montón esté lo más cerca posible a 36 y el producto de las cartas del segundo montón esté lo posible a 360 .

7. conjunto de

8

El problema del 8-puzzle: es un puzle de deslizamiento que consis piezas en un marco de tamaño 3 × 3 , por lo que queda un hueco libre. El objetivo

consiste en encontrar la sucesión de movimientos (moviendo piezas al hueco libre) que llevan la di inicial a una distribución ordenada prefijada. 8. Problema de las 2 Jarras: Se tienen dos jarras de agua, una de

4

litros y otra de

3

litros sin

medición. Se desea obtener 2 litros de agua en la jarra de 4 litros. Las operaciones válidas son: llena de las jarras, vacíar una de las jarras, pasar agua de una jarra a otra (hasta que la primera se vacía o l se llena). 9. Misioneros y Caníbales: Hay

3

misioneros y

3

caníbales a la orilla de un río. Tienen una

capacidad para dos personas como máximo. Se desea que los seis crucen el río, pero hay que cons no debe haber más caníbales que misioneros en ningún sitio porque entonces los caníbales se los Además, la canoa siempre debe ser conducida por alguien. 10. El Granjero: Un granjero va al mercado y compra un lobo, una oveja y una col. Para volver a su que cruzar un río. El granjero dispone de una barca para cruzar a la otra orilla, pero en la barca solo una de sus compras.Si el lobo se queda solo con la oveja, se la come, si la oveja se queda sola con l come. El reto del granjero es cruzar el río con todas sus compras. ¿Cómo puede hacerlo?

11.

Torres de Hanoi: Se tienen N discos de distinto tamaño apilados sobre de manera que cada disco se encuentra sobre uno de mayor radio. Existen otras dos bases vací Haciendo uso únicamente de las 3 bases, el objetivo es llevar todos los discos de la base A hasta A

Sólo se puede mover un disco a la vez, y cada disco puede descansar solamente en las bases o sobre de tamaño superior, pero no en el suelo.

12.

Problema de las N reinas: Sitúar N reinas en un tablero de ajedrez de tamañ sin que se amenacen entre ellas. Una reina amenaza a otra si ambas están en la misma fila, c

diagonal. 13. Criptoaritmética: Las letras representan dígitos. El objetivo es determinar el valor de cada una de de tal manera que la operación sea correcta aritméticamente. Letras iguales - dígitos iguales, letras

www.cs.us.es/~fsancho/?e=159

4/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

- dígitos diferentes. Ningún número inicia con cero. Por ejemplo:

14. Dados cuatro números naturales

n

,

m

,

r

y

T

, encontrar una secuencia mínima de operaciones a

básicas (suma, resta, multiplicación y división) que usando n y m únicamente y partiendo de 0, obte resultado T , con la restricción adicional de que ni n ni m se pueden usar más de r veces. Por e n = 2

,

,

m = 3

r = 3

y

, una posible solución (no necesariamente mín , ya que el resultado es 28 y ni 2 ni 3 se han usado más de

T = 28

((((((0 + 3) × 3) × 2) − 3) × 2) − 2)

cada uno. 15. Cruce del puente: Un grupo de 5 personas quiere cruzar un viejo y estrecho puente. Es una noche se necesita llevar una linterna para cruzar, pero el grupo sólo dispone de una linterna, a la que le minutos de batería.Cada persona tarda en cruzar 10, 30, 60, 80 y 120 segundos, respectivamente. sólo resiste un máximo de 2 personas cruzando a la vez, y cuando cruzan dos personas juntas cam velocidad del más lento. No se puede lanzar la linterna de un extremo a otro del puente, así que cad crucen dos personas, alguien tiene que volver a cruzar hacia atrás con la linterna a buscar a los co que falten, y repetir este proceso hasta que hayan cruzado todos. ¿Cuál sería una solución válida? 16. Problema de las bolsas: Se pretende encontrar una manera de distribuir un conjunto d , en bolsas, usando el menor númer posible de bolsas. Cada objeto tiene un peso , y las bolsas tienen un límite de peso soportado, B.

O = {o 1 , … , o n } P eso(o i ) = pi

17. Caminos en grafos: Considerando un grafo geométrico, diseña diversas estrategias para calcular más corto entre dos nodos del grafo. 18. Suma nula: Dado un conjunto de enteros I

= {i1 , … , in }

, el problema es encontrar un subconju

que sume 0.

19. 2N + 1

El juego de las Ranas: Tenemos N ranas negras y N verdes situadas e nenúfares tal y como muestra la animación (en el caso particular de N = 3). Comienza cad

ranas en un extremos distinto de la fila de nenúfares. El objetivo consiste en intercambiar la posic ranas negras y verdes. Para ello, los movimientos permitidos son los siguientes: a) Una rana puede un nenúfar adyacente vacío, con coste 1. b) Una rana puede desplazarse a un nenúfar vacío salta rana como máximo, con un coste igual a 2. 20. Juego de las Cifras (Cifras y Letras): Dados 6 números, y un objetivo aritmética entre ellos que se aproxima lo más posible a O. 21. Trabajaremos con números de 3 cifras (de

100

a

999

O

, encontrar la com

). Inicialmente, tenemos dos números prefij

denotaremos por S (Start) y G (Goal), y un conjunto de números que denotaremos por P (de Prohi cada turno, podemos transformar un número en otro añadiendo/sustrayendo 1 a uno de sus dí ejemplo, pasando de 678 a 679 , o de 234 a 134 ). El coste de cada movimiento es 1. Adicionalmente estas restricciones: (a) No se permite añadir 1 a 9, ni sustraer 1 a 0. (b) No se permite convertir un n un elemento de P (están prohibidos). (c) No se puede cambiar un mismo dígito 2 veces seguidas. A dar la representación general, resuelve el caso particular S = 567, G = 777 y P = {666, 667} . 22. Un grupo de N personas de diferentes países se sienta en una mesa circular con N sillas. Cada per hablar dos idiomas (no necesariamente los mismos para todos). Se trata de encontrar una dispos sentarse de manera que cada persona pueda comunicarse con sus dos vecinos en la mesa. 23. El Problema del Viajante: Dada una lista de ciudades y las distancias entre cada par de ellas, ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad origen? 24. Un ayuntamiento tiene que adjudicar 10 proyectos de obra mediante concurso público. Se han pre concurso 5 empresas, dando presupuestos para cada uno de los diez proyectos. La adjudica realizarse de manera que a cada empresa sólo se le concedan dos proyectos. Encuentra la adjud menor precio. 25. Un ganadero tiene un rebaño de ovejas. Cada oveja tiene un peso y se vende por un precio pr ganadero dispone de un camión que es capaz de cargar un peso máximo. Su problema es selecc colección de ovejas para llevarlas al mercado de ganado en el camión, de manera que se maximic total de las ovejas transportadas, sin superar el peso total soportado por el camión. www.cs.us.es/~fsancho/?e=159

5/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

26. Usa algún método de optimización para conseguir un buen autómata celular 1D que resuelva de forma posible (cometerá errores) el problema de la mayoría. (Ayuda: usa la representación bina reglas del autómata como conjunto de genes del individuo). 27. Problema de asignación de tareas: Hay un número de agentes ({a

i

: 1 ≤ i ≤ n}

) y un n

tareas a realizar ({t : 1 ≤ j ≤ m} ). Cualquier agente puede ser asignado para desarrollar cualqu contrayendo algún coste (c ) que puede variar dependiendo del agente, i, y la tarea, j, asig j

ij

necesario para desarrollar todas las tareas asignar un solo agente a cada tarea para que el cost asignación sea minimizado, aunque un mismo agente podría realizar más de una tarea, pero ha de cuenta que la realización de la tarea

por el agente

tj

ai

conlleva el uso de una serie de recurso

agente, y éstos están acotados por una cantidad fija, b , para cada agente. 28. Tenemos una lista que representa los pesos de una población (todos los pesos están entre 0 y 100). i

encontrar 3 números (0 < a1 < a2 < a3 < 100) que sirvan para dividir el conjunto anterior en 4 [0,a1), [a1,a2), [a2,a3),[a3,100), de forma que las sumas de los pesos que hay en cada sección se parecidas posibles. ¿Qué cambios harías para encontrar una división similar en K secciones? 29. Disponemos de un CD de 80 minutos de duración y queremos grabar el mayor tiempo posible d colección de 100 canciones. Queremos saber qué pistas debemos grabar. Las duraciones en minu canciones se dan en una lista (d , … , d ). Modifica la solución anterior para que, además, obten CD con el estilo más uniforme posible. El estilo de una canción viene dado por un código númerico 1

100

Dos estilos son más parecidos si sus códigos son más cercanos. El estilo de las canciones de nuestra viene dado por una lista: (e , … , e ). 30. Problema de Optimización de Tareas: Tenemos N tareas, {T , … , T }, que se encargan d 1

100

1

N

datos. Podemos hacer uso de un procesador que NO tiene capacidad paralela.Cada tarea, T , tarda t en ejecutarse, y hasta que no termina una tarea, no puede lanzarse otra. Cada tarea solo se puede vez. Disponemos de un tiempo total, T , para poder usar el procesador. Además, la ejecución de cada consume D datos. Algunas tareas solo se pueden ejecutar si algunas otras se han ejecutado antes. P i

i

i

cuáles, disponemos de una tabla que indica si una tarea necesita que otra tarea se haya ejecutado ejemplo, la siguiente tabla indica que T necesita que T se haya ejecutado antes, T necesita que T ejecutado antes, y T necesita que T se haya ejecutado antes: 1

3

2

2

1

T1

T2

T3

T4

T1

0

1

0

0

T2

0

0

0

1

T3

1

0

0

0

T4

0

0

0

0

Objetivo: Obtén una secuencia de ejecuciones que consuma la máxima cantidad de datos en el tie permitido. 31. Sudoku: Este problema se publicó en Nueva York en el año 1979 bajo el nombre de “Number Place popular en Japón con el nombre de sudoku (“Sudji wa dokushin ni kagiru”: “los números deben apa vez”). En el problema del sudoku, hay que rellenar las casillas de un tablero de 9 × 9 con números de forma que no se repita ningún número en la misma fila, columna, o subcuadro de 3 × 3 que com sudoku. Es habitual que se den algunas casillas ya rellenas. 32. Problema de agrupamiento I: Agrupa N números en k grupos disjuntos minimizando la su diferencias entre los grupos. 33. Problema de agrupamiento II: Reparte los N primeros números naturales en una matriz N ×, N de tal manera que las sumas tanto por filas como por columnas coincidan. 34. Problema de emplazamiento de bloques rectangulares: Dado un conjunto de n 2

rectangulares de distintas anchuras y alturas, se trata de encontrar un emplazamiento (asignac centros de los bloques rectangulares a puntos de un espacio cartesiano bidimensional) de tal form haya solapamientos entre los bloques rectangulares, y se minimice la función de coste f = A + λC es el área del rectángulo que engloba todos los bloques rectangulares, λ es una constante positiv término de conectividad,

n−1

C = ∑

i=1

n

∑

j=i+1

wij dij

, siendo

dij

la distancia entre los centros de lo

rectangulares y w el coste relacionado al unir el bloque rectangular i-ésimo con el bloque re j-ésimo. 35. Particionamientos de un grafo. Problema ”max-cut”. Problema ”min-cut”. Dado G = (V , E ) sin ciclos, donde cada arista lleva asociado un peso entero positivo, se trata de enco ij

partición de V en dos conjuntos disjuntos, V y V de tal manera que la suma de los pesos de las a 0

www.cs.us.es/~fsancho/?e=159

1

6/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

tienen un extremo en

V0

y el otro extremo en

V1

, sea máximo (problema max-cut) o mínimo (p

min-cut). 36. Problema del conjunto de vértices independientes. Dado un grafo G = (V , E ), se trata de el denominado conjunto maximal de vértices independientes, es decir el conjunto V I M ⊆ V cardinalidad para el cual ninguna de sus aristas se encuentre en E . 37. Problema del Salto del Caballo. Teniendo un tablero de N × N casillas y un caballo de ajedre en una posición inicial cualquiera, consegir que el caballo pase por todas las casillas del tablero una, vez. 38. Problema del Dominó I. Las fichas del dominó se pueden representar por pares de números e problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segund de cada ficha coincida con el primero de la siguiente. 39. Problema del Dominó II. Toma el tablero de ajedrez y tapa con dos monedas los dos cuadr esquinas opuestas. Ahora trata de cubrir todos los demás cuadros con 31 fichas de dominó, c ocupando dos cuadros contiguos del tablero. Intenta el mismo problema con distintos tamaños de ta 40. El Problema de los matrimonios estables: Una agencia matrimonial ofrece a sus client estables. Para conseguirlo, cada cliente debe establecer sus preferencias respecto al resto por med lista con sus favoritos por orden de preferencia, incluyendo todos aquellos en los que puede estar in dejando fuera aquellos que no le interesan en absoluto. A partir de estas listas se deben confeccion estables. Se entiende por estable el que nadie tenga la tentación de divorciarse porque puede enco pareja mejor que la actual: Si A está emparejado con B y C con D, pero a A le gusta más D que B, y D por delante de C, entonces los emparejamientos anteriores no son estables. 41. ¿De quién es esta cebra? Son cinco casas adosadas, de diferentes colores, habitadas por cinco h diferentes nacionalidades. Cada uno posee un animal diferente, bebe una bebida diferente y fuman u de tabaco distinta. Sabiendo la siguiente información, ¿podrías decir quién bebe agua?, ¿de quién es 1. 2. 3. 4.

El noruego vive en la primera casa. La casa de al lado del noruego es azul. El de la tercera casa bebe leche. El inglés vive en la casa roja.

5. 6. 7. 8.

El de la casa verde bebe café. El de la casa amarilla fuma Ducados. La casa blanca está después de la verde. El español tiene un perro.

9. El ucraniano bebe té. 10. El japonés fuma Habanos. 11. El que fuma Fortuna tiene un gato. 12. El que fuma Celtas bebe vino. 13. El vecino del que fuma Chester tiene un canario. 14. El vecino del que fuma Ducados tiene un caballo. 42. Comprando zapatos: Enriqueta, al volver del centro comercial, describe felizmente a su amiga A cuatro pares de zapatos que se ha comprado. A Aurora le encantan todos (las alpargatas de color planos fucsia, las bambas moradas y unas sandalias de cuero preciosas), pero Enriqueta no puede re qué tienda compró cada uno ("La granja del pie", "Tacones a Mogollón", "El palacio del "Muchachas"). ¿Puedes echarles una mano y establecer el orden en el que Enriqueta compró ca zapatos, y dónde compró cada uno? Dispones de la siguiente información: 1. Enriqueta sabe que los planos fucsia los compró en "Tacones a Mogollón". 2. La tienda que visitó inmediatamente después de comprar sus bambas moradas no era "Muc 3. En "La granja del pie" fue su segunda compra. 4. Dos paradas después de dejar el "Palacio del zapato", Enriqueta compró sus sandalias de cu 43. La orquesta de Boulika: Esta orquesta comprende 180 ejecutantes, ¿cuántos no tocan ningun instrumentos? 1. 6 no tocan más que el violoncello. 2. 24 tocan violocello y violín, pero no viola. 3. 12 tocan violoncello y viola, pero no violín. 4. 6 tocan violín y viola, pero no violoncello. 5. 63 músicos tocan el violín, 54 el violoncelo y 36 la viola. www.cs.us.es/~fsancho/?e=159

7/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

44. La perspicacia del inspector Lafrite: Lafrite está encargado de la investigación sobre un robo d en una galería de arte. Pidió a Relbou y Gremai, dos de sus asistentes, que le ayudaran en Laminvestigación terminó con el arresto de cuatro personas: Jules Rateau, Desiré Lafrange, Michel Felicie Ossy. Los interrogatorios los realizan los dos asistentes que vienen a dar su informe, a ra Lafrite dice: "Si considero que lo que me dicen es cierto, puedo afirmar la culpabilidad de una de personas". ¿Puedes ayudar a los inspectores a encontrar a esa persona?. El informe es: 1. Relbou: "Jules Rateau es inocente, pero estoy seguro de que por lo menos uno de los culpable". 2. Gremai: "Si Desiré Lafrange es culpable, no hay más que un cómplice, que está entre los dem 3. Relbou: "Y si Michel Boileau es culpable, pienso que tiene dos cómplices entre los otros". 45. Puedes probar otros problemas de la colección: http://www.csplib.org/Problems/

Búsqueda/Planificación Clásicas 1. Basándose en el método de resolución general con BFS que se ha proporcionado, construue uno e pero que haga uso de DFS (con límite de profundidad). 2. Adapta el algoritmo DFS de resolución general para que trabaje con agentes en vez de con listas, sobre algunos de los ejemplos. 3. Implementa el algoritmo de Profundidad iterada en NetLogo. 4. Pon ejemplos de búsquedas en las que al aplicar el algoritmo voraz no encontremos una solución óp 5. Escribe modelos de NetLogo que sean capaces de aplicar adecuadamente los algoritmos de búsq vistos en el tema. 6. Realiza en NetLogo un modelo para resolver de la forma más general que se te ocurra (hacien agentes) problemas de búsqueda por medio del algoritmo voraz. 7. Aplica los métodos de resolución de este apartado para resolver algunos de los problemas de la Genérica de Problemas.

Búsquedas con Adversarios 1. Implementa una estrategia ganadora completa en el juego del Nim en su versión más simple: se j 2 jugadores, se tienen 9 cerillas, alternadamente cada jugador puede retirar 1, 2 o 3 cerillas, pie retire la última cerilla. 2. Implementa una estrategia ganadora para el juego del Nim en su versión de montones: se jue jugadores, se tienen N montones con cerillas, cada jugador alternadamente puede quitar todas las c quiera, pero solo de un montón, gana el jugador que se lleve la última cerilla. 3. A partir del modelo que se proporciona en el temario, introduce los cambios necesarios para implementar la poda alfa-beta. 4. Implementa un jugador del 3 en raya que haga uso de Minimax. Hazlo usando heurísticas profundidad máxima prefijada, y diseñando variantes que hagan uso de podas. 5. Implementa un jugador del 3 en raya que haga uso de MCTS. 6. Implementa un jugador de conecta4 haciendo uso de Minimax con heurísticas y poda. 7. Implementa un jugador de conecta4 haciendo uso de MCTS. 8. Implementa un jugador de Quarto haciendo uso de Minimax usando heurísticas sobre una pr máxima prefijada y con podas. 9. Implementa un jugador de Quarto haciendo uso de MCTS. 10. Implementa un jugador de Go Moku haciendo uso de Minimax usando heurísticas sobre una pr máxima prefijada y con podas. 11. Implementa un jugador de Go Moku haciendo uso de MCTS. 12. Implementa un jugador de 6 en raya haciendo uso de Minimax usando heurísticas sobre una pr máxima prefijada y con podas. 13. Implementa un jugador de 6 en raya haciendo uso de MCTS. 14. Implementa un jugador de 9 hombres de Morris profundidad máxima prefijada y con podas. 15. Implementa un jugador de 9 hombres de Morris

haciendo uso de Minimax usando heurísticas haciendo uso de MCTS.

16. Implementa un jugador de Havannah haciendo uso de Minimax usando heurísticas s profundidad máxima prefijada y con podas. 17. Implementa un jugador de Havannah haciendo uso de MCTS.

www.cs.us.es/~fsancho/?e=159

8/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

18. Aplica los métodos de resolución de este apartado para resolver algunos de los problemas de la Genérica de Problemas.

19.

Consideramos el siguiente juego: dos contrincantes, A y B, manejan cad ficha en un tablero como muestra la figura adjunta. Los dos jugadores mueven por turno, empezan Cada jugador pueden mover su ficha a un espacio vacío adyacente a la posición que ocupen (en dirección). Si el adversario ocupa un espacio adyacente, entonces un jugador puede saltar sobre el al siguiente espacio vacío, si existe. Por ejemplo, si A está sobre 3 y B está sobre 2, entonces A puede ficha para ocupar el espacio 1. El juego termina cuando un jugador alcanza el extremo opuesto del A alcanza el espacio 5 en primer lugar, el valor de utilidad para A será +∞ , si B alcanza el espacio 1 lugar, el valor de utilidad de A será −∞ . Define una función de evaluación e(s) para un estado s cualquiera. Aplica el algoritmo Minimax con límite de profundidad hasta el nivel 6, empezando con la de la figura anterior (empezando con el nodo raíz con etiqueta max de nivel 0, las hojas d también tendrán etiqueta max) y donde el primer movimiento lo hace A. Especifica lo calculados para cada nodo y determina la mejor jugada para A.

20. Considera el árbol en figura siguiente de un juego de dos personas, donde los círculos son nodos cuadrados son nodos min. Aplica el algoritmo minimax con poda alfa-beta, propaga los valores de e hasta el nodo raíz, marca la mejor jugada para max, y marca todos los subárboles que se podan.

21. Dos jugadores, J y J , se plantean competir sobre un circuito de ciudades con las siguientes reg recorrido del circuito se hace por tramos, partiendo de la ciudad marcada como Salida. (b) Los alternativamente eligen el tramo a recorrer entre aquellos que parten de la ciudad en la que se en 1

2

Una vez elegido el tramo, ambos conductores lo recorren y se apunta los kilómetros del tramo el que lo eligió. Es decir, si J empieza el recorrido y decide ir a B, se apuntará 30 kilómetros. A conti contrario debe elegir, partiendo de B, entre ir a C o a D, y se apuntará los kilómetros que separ ciudades. (c) Un conductor no puede ir a una ciudad por la que ya haya pasado, por lo que la co 1

acaba cuando el jugador al que le toca moverse no puede hacerlo. (d) Gana el jugador que haya a más kilómetros con los tramos recorridos. Se pide: Da una representación eficiente para los estados del juego. Desarrolla el árbol de búsqueda Minimax hasta nivel 4 (dos jugadas para cada jugador). G sucesores de un nodo en orden alfabético, es decir, el primer sucesor del nodo Salida ser segundo B. Define una función de evaluación adecuada para los nodos hoja, y propaga sus valores a t árbol. ¿Qué jugada haría J ? 1

¿Qué partes del árbol no se expandirían si se aplicara la poda?

www.cs.us.es/~fsancho/?e=159

9/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

Lógica Proposicional Recuerda que podéis usar la página Gateway to Logic

para calcular formas normales conjuntivas (for

de las fórmulas que vayáis usando.

Ejercicios de implementación 1.- Implementa el método DPLL en NetLogo utilizando una estructura de datos adecuada para alm cláusulas y los conjuntos de claúsulas. El sistema trabajará suponiendo que ha recibido el conjunto de fórm forma clausal. 2.- Implementa el método de Resolución en NetLogo utilizando una estructura de datos adecuada para las cláusulas y los conjuntos de claúsulas. El sistema trabajará suponiendo que ha recibido el conjunto de f en forma clausal. 3.- Implementa el método de Tablas de Verdad en NetLogo utilizando una estructura de datos ade almacenar las fórmulas. 4.- Implementa los métodos de encadenamiento hacia adelante y encadenamiento hacia atrás utilizando una estructura de datos adecuada para representar las reglas de disparo y los hechos.

Ejercicios teóricos 1.- Accede desde aquí a los ejercicios que se proponen en el curso de Lógica Informática del grado de T Informáticas de la Universidad de Sevilla. 2.- Determina, tras formalizar en un lenguaje proposicional, si los siguientes argumentos son lógicamente Si Juan es comunista, entonces Juan es ateo. Juan es ateo. Por tanto, Juan es comunista. Cuando tanto la temperatura como la presión atmosférica permanecen contantes, no llueve. La tem permanece constante. En consecuencia, en caso de que llueva, la presión atmosférica no permanece Siempre que un número x es divisible por 10, acaba en 0. El número x no acaba en 0. Luego, x no e por 10. Para que un número x sea divisible por 5, es necesario que el número acabe en 0. El número x no a Luego, x no es divisible por 5. El número y es negativo si x es positivo. Cuando z es negativo, y también lo es. Por tanto, y e siempre que o bien x sea positivo o bien z sea negativo. En cierto experimento, cuando hemos empleado un fármaco A, el paciente ha mejorado consider en el caso, y sólo en el caso, en que no se haya empleado también un fármaco B. Además, o se ha em fármaco A o se ha empleado el fármaco B. En consecuencia, podemos afirmar que si no hemos em fármaco B, el paciente ha mejorado considerablemente. Si llueve las calles están vacías. Si las calles están vacías, los comercios obtienen pérdidas. Los m podrían sobrevivir si los comerciantes no les contratasen para componer canciones para public comerciantes invierten en canciones publicitarias cuando tienen pérdidas. Por tanto, si llueve lo pueden sobrevivir. Si el barco entra en el puerto, habrá una gran fiesta. El barco entra en el puerto sólo si necesit combustible. El barco no necesita combustible a menos que venga de muy lejos. Es imposible que n combustible si la comida ya se les ha terminado. Sabemos que, o bien se le ha terminado la comi necesita combustible. Por tanto: habrá una gran fiesta. www.cs.us.es/~fsancho/?e=159

10/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

Si

f

es diferenciable en

[a, b]

, es continua y acotada en

[a, b]

. Si

f

no fuese acotada en

[a, b]

no

diferenciable en [a, b] . Por tanto: si f es discontinua y acotada en [a, b] no es diferenciable en [a, b] . Si llueve no iré al mercado. Si no iré al mercado, o bien no tendré comida o bien iré al restaurante tengo comida. Por lo tanto, no iré al restaurante. 3.- Ash, Misty y Brock han organizado una batalla entre sus Pokemon. Se conocen los siguientes datos al r Uno, y sólo uno, de los siguientes Pokemon fue el vencedor: Pikachu, Bulbasaur, Togepi, Starmie Onix. Ash ganó la batalla si el Pokemon vencedor fue Pikachu o Bulbasaur. Si o bien Togepi o bien Starmie fue el vencedor, Misty ganó la batalla. Brock ganó la batalla si el vencedor fue Onix o Vulpix. Si Onix fue derrotado, Starmie también. Bulbasaur fue derrotado. Si Pikachu fue derrotado, entonces Ash no ganó la batalla. Brock no ganó la batalla si Bulbasaur fue derrotado. Si Vulpix fue derrotado, Togepi y Onix también corrieron la misma suerte. Probad que Ash fue el ganador. 4.- En un texto de Lewis Carroll, el tio Jorge y el tío Jaime discuten acerca de la barbería del pueblo, at tres barberos: Alberto, Benito y Carlos. Los dos tíos aceptan las siguientes premisas: Si Carlos no está en la barbería, entonces ocurrirá que si tampoco está Alberto, Benito tendrá que atender el establecimiento. Si Alberto no está, tampoco estará Benito. El tío Jorge concluye de todo esto que Carlos no puede estar ausente, mientras que el tío Jaime afirm puede concluirse que Carlos y Alberto no pueden estar ausentes a la vez. ¿Cuál de los dos tiene razón? 5.- Demuestra, mediante encadenamiento hacia adelante, la corrección del siguiente argumento. Los animales con pelo o que dan leche son mamíferos. Los mamíferos que tienen pezuñas o que rumian son ungulados. Los ungulados de cuello largo son jirafas. Los ungulados con rayas negras son cebras. Se observa un animal que tiene pelos, pezuñas y rayas negras. Por tanto, el animal es una cebra. 6.- Usando resolución o DPLL, determina la consistencia de los conjuntos de cláusulas: {p ∨ ¬q,  p ∨ q,  ¬p ∨ ¬q,  ¬p ∨ q} {¬r,  q,  p ∨ ¬q,  ¬p ∨ r} {p ∨ q ∨ r,  ¬p ∨ q,  ¬q ∨ r,  ¬r,  p ∨ r} {p,  ¬p ∨ q,  r}

7.- Demuestra, utilizando resolución o DPLL, la inconsistencia del conjunto de cláusulas {¬p ∨ ¬q ∨ r,  ¬s ∨ t,  ¬t ∨ p,  s,  ¬s ∨ u,  ¬u ∨ q,  ¬r}

8.- Determina la inconsistencia del conjunto mediante resolución o DPLL: {p ∨ q,  q ∨ r,  r ∨ w,  ¬r ∨ ¬p,  ¬w ∨ ¬q,  ¬q ∨ ¬r}

9.- Determina la inconsistencia del conjunto por resolución o DPLL: {¬A ∨ ¬B ∨ C ,  ¬A ∨ ¬G ∨ H ,  ¬A ∨ ¬H ∨ F ,  ¬G ∨ B,  G,  A,  ¬F }

10.- Decide por el método de resolución o DPLL la verdad o falsedad de las siguientes afirmaciones: {p → (q → r),  r → q} ⊨ r ↔ q {p → q,  q → (p ∧ q), p → r} ⊨ q → r

11.- Las guerras clon han comenzado. Durante el transcurso de una refriega, tres caballeros Jedi, Anakin, Yoda, se encuentran con el conde Dooku. Utilizaremos el lenguaje proposicional A, O, Y para deno correspondiente caballero participa en el combate, y G para denotar "los Jedi han ganado". a. Formaliza las siguientes afirmaciones: F1 F2 F3 F4

www.cs.us.es/~fsancho/?e=159

: Para derrotar al conde Dooku deben participar al menos dos caballeros Jedi. : El Conde Dooku gana cuando sólo participa un caballero. : Si el Conde Dooku pierde entonces Anakin ha participado en el combate. : Si el Conde Dooku pierde, entonces no han participado los tres caballeros. 11/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

b. ¿Es cierto que {F

1,

F2 , F3 } ⊨ G → A ∧ O

? Razónese formalmente la respuesta.

12.- Describe el problema de las N reinas como un problema de satisfactibilidad proposicional. 13.- Describe el problema de Sudoku como un problema de satisfactibilidad proposicional. 14.- Describe el problema de coloreado de grafos como un problema de satisfactibilidad proposicional.

Lógica de Primer Orden 1.- Accede desde aquí a los ejercicios que se proponen en el curso de Lógica Informática del grado de T Informáticas de la Universidad de Sevilla. 2.– Escribe fórmulas del lenguaje LRP0 que expresen las siguientes afirmaciones: Todo el que tiene un padre tiene una madre. Todo hermano de un tío de Pedro es tío de Pedro o es su padre. Todo el mundo tiene abuela. Pedro y Ana son primos. Todo hijo de un hermano de Pedro es su sobrino. Si dos personas tienen una abuela en común entonces son primos o bien son hermanos. No todo el mundo tiene hijos. Supóngase que H J (x, y) expresa “x es hijo/a de y”; H R(x, y): “x es hermano/a de y; S B(x, y): “x es so ”; T (x, y): “x es tío/a de y”; P D(x, y) : “x es padre de y”; M D(x, y): “x es madre de y”; y que tenemos las Ana y Pedro. y

3.- Escribe fórmulas de LPO que expresen las siguientes afirmaciones: Pepi es hija de Pepe y Pepa. Un abuelo siempre es de mayor edad que cualquiera de sus nietos. Pepe tiene exactamente 2 hijos. Pepe tiene al menos un cuñado. La suegra de Pepa es la madre de Pepe. Pepi tiene una prima y un primo. Todo hijo de Pepi es nieto de Pepe. Pepa es la abuela materna de toda hija de Pepi. Supóngase que: pd(x) es el padre de x, md(x) es la madre de x, pm(x, y) es la persona de mayor edad en x si tienen la misma edad). H (x) : “x es un hombre”; M (x) : “x es una mujer”; P RG(x, y): “x es un proge H RO(x, y) : “x es hermano de y”; H RA(x, y) : “x es hermana de y”; C AS (x, y): “x está casado/a con tenemos las constantes pepe, pepa y pepi. 4.- Introduciendo la notación apropiada, escribe las sentencias de los siguientes razonamientos como f primer orden y decide si la conclusión es consecuencia lógica de las premisas, utilizando para ello formas cla Todos los científicos están locos. No existen vegetarianos locos. Por tanto, no existen científicos veg Todos los hombres son animales. Algunos animales son carnívoros. Por tanto, algún hombre es carn Todo barbero de esta ciudad afeita exactamente a los hombres que no se afeitan a si mismos. Por existen barberos en esta ciudad. Para cualesquiera x e y, si x > y e y > z, entonces x > z. Además, x > x es falso para cualqu tanto, para cualesquiera x e y, si x > y , entonces no es posible que y > x . 5.- Determina la consistencia de los siguientes conjuntos de clausulas: {Q(u) ∨ P (a),  ¬Q(w) ∨ P (w),  ¬Q(x) ∨ ¬P (x)} {Q(u) ∨ P (a),  ¬Q(w) ∨ P (w),  ¬Q(x) ∨ ¬P (x),  Q(y) ∨ ¬P (y)} {I (a),  ¬R(x) ∨ L(x),  ¬D(y) ∨ ¬L(y),  D(a)} {I (a),  ¬R(x) ∨ L(x),  ¬D(y) ∨ ¬L(y),  D(a),  ¬I (z) ∨ R(z)} {¬P (x, y) ∨ ¬P (y, z) ∨ P (x, z),  P (a, x),  P (x, b),  P (x, f (x))} {M (a, s(c), s(b)), P (a), M (x, x, s(x)), ¬M (x, y, z) ∨ D(x, z), ¬P (x) ∨ ¬M (y, z, u) ∨ ¬D(x, u)

6.- Describe el problema de las N reinas como un problema de satisfactibilidad de Primer Orden. 7.- Describe el problema de Sudoku como un problema de satisfactibilidad de Primer Orden. 8.- Describe el problema de coloreado de grafos como un problema de satisfactibilidad de Primer Orden.

www.cs.us.es/~fsancho/?e=159

12/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

Lógica Difusa Usando la extensión de NetLogo los siguientes problemas:

para trabajar con Lógica Difusa, crea modelos que generen modelos d

1. El problema de la propina: crea un modelo de lógica difusa para el siguiente sistema de reglas. 1. 2. 3. 4. 5.

Si el servicio es pobre, la propina es baja. Si el servicio es bueno, la propina es media. Si el servicio es excelente, la propia es generosa. Si la comida está rancia, la propina es baja. Si la comida está deliciosa, la propina es generosa.

2. Realiza el tutorial completo que acompaña a la extensión anterior. 3. Control de velocidad de un automóvil: el sistema de control de un vehículo no tripul caracterizado por 3 variables: velocidad (muy lenta, lenta, media, rápida, muy rápida), a (decelerando, constante, acelerando) y distancia al objetivo (muy cerca, cerca, lejos). El sistema a puede inyectar más o menos gasolina al vehículo para que se aproxime al destino de forma eficaz Teniendo en cuenta reglas del tipo "Si está lejos y a velocidad lenta, acelera", construye un modelo controle lo mejor posible el vehículo para que se aproxime lo más posible al punto de destino (que variable). 4. Control de alunizaje: Considera un caso similar al anterior pero en el que controlamos una intenta tomar tierra en caída libre, teniendo motores que pueden compensar la aceleración d planeta. 5. Control de la dirección de un vehículo: Disponemos de un circuito donde colocamos un vehíc a velocidad constante y que dispone de 2 sensores laterales que le indican la distancia a los bordes d Define un sistema difuso que pueda controlar el giro a izquierda y derecha del vehículo para que circuito sin salirse (y en el menor tiempo posible). 6. Búsqueda de localizaciones: Disponemos de un mapa en el que cada patch puede estar a u determinada y tener un uso (bosque, agua, urbanizable, urbanizado). Además, calculamos la incli cada patch como el máximo de las inclinaciones (diferencia de alturas) que tiene con sus patche Queremos encontrar un lugar donde construir nuestra nueva casa. Para ello define las variables di reglas necesarias para encontrar un lugar que: 1. 2. 3. 4.

Sea urbanizable. Esté cerca de agua y de bosque, pero no mucho de otras zonas urbanizadas. Tenga una altura media. No esté muy inclinado.

Satisfacción de Restricciones 1. Modela este problema como un PSR: Cinco casas consecutivas tienen colores diferentes y son hab hombres de diferentes nacionalidades. Cada uno tiene un animal diferente, una bebida preferida y marca determinada. Además, se sabe que: El noruego vive en la primera casa La casa de al lado del noruego es azul El habitante de la tercera casa bebe leche El inglés vive en la casa roja El habitante de la casa verde bebe café El habitante de la casa amarilla fuma Kools La casa blanca se encuentra justo después de la verde El español tiene un perro El ucraniano bebe té El japonés fuma Cravens El fumador de Old Golds tiene un caracol El fumador de Gitanes bebe vino El vecino del fumador de Chesterfields tiene un reno El vecino del fumador de Kools tiene un caballo 2. Representa mediante un PSR la siguiente información: “Juana, Pepa y Paloma nacieron y viven en diferentes (Málaga, Madrid y Valencia). Además, ninguna vive en la ciudad donde nació. Juana e que la que vive en Madrid. Paloma es cuñada de la que vive en Valencia. La que vive en Madrid y la www.cs.us.es/~fsancho/?e=159

13/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

en Málaga tienen nombres que comienzan por distinta letra. La que nació en Málaga y la que vive 3. 4. 5. 6.

Valencia tienen nombres que comienzan por la misma letra”. ¿Dónde nació y vive cada una? Representa el Sudoku como un PSR. Representa el problema de las N reinas como un PSR. Representa algunos de los problemas genéricos (los adecuados) como un PSR. Puedes probar con otros problemas de la colección: http://www.csplib.org/Problems/

Inteligencia Colectiva 1. Modifica el modelo de Hormigas que se ha visto en el tema para hacer que el usuario pueda decidir de fuentes de comida y se coloquen aleatoriamente en el mundo. 2. ¿Puedes encontrar en el modelo de hormigas algún valor crítico del número de hormigas necesario se produzca un cambio en el comportamiento global de la colonia? 3. En el modelo de Hormigas se usa un truco para volver al nido, pero las hormigas de verdad u sistemas. Investiga acerca de ello e intenta implementar en el modelo alguna idea que pueda funcion 4. Usando el modelo de Hormigas, crea otro modelo similar en el que haya 2 hormigueros que compit mismas fuentes de comida. Piensa en acciones que pueden tomar las hormigas de un nido al feromonas u hormigas del otro nido. 5. ¿Puedes encontrar en el modelo de termitas algún valor crítico del número de individuos pa produzca un cambio en el comportamiento global de la colonia? 6. Amplía el modelo de las Termitas permitiendo que haya distintos tipos de madera que las term agrupar por tipos. 7. En el modelo de las luciérnagas, ¿cómo afecta el número de individuos (densidad) al compo global?, ¿existe algún valor de densidad que pueda considerarse crítico (hay un cambio de comport hay más o menos de ese valor de densidad)? 8. En el modelo de las luciérnagas, ¿podrías pensar en otras estrategias de sincronización, o de mejo que hay implementadas? 9. ¿Puedes encontrar en el modelo de Flocking algún valor crítico del número de individuos necesario se produzca un cambio en el comportamiento global? 10. En el modelo de Flocking introduce variantes como: Existencia de familias (tipos) de individuos que determinen sus características (radio y á visión, mínima separación, etc) Algunos individuos que actúen como cazadores, que persigan individuos de la manada, y d huyan estos últimos en caso de percibirlos suficientemente cerca. Elementos estáticos distribuidos por el mundo (que se vayan regenerando) y que determin peso de influencia en los movimientos de los individuos de la manada con el fin de pasar so para comerlos. Obstáculos que los individuos de la manada no puedan atravesar y tengan que girar para ev

Sistemas Dinámicos y Redes Complejas 1. Haz un modelo en NetLogo que permita visualizar el campo de vectores asociado a una ecuación d de 2 variables. 2. Haciendo uso del modelo "Preferential Attachment" que viene en la biblioteca de ejemplos de construye un modelo que muestre en tiempo real la evolución de la distribución de grados del forma. A continuación, crea un procedimiento en el que se añadan aristas aleatoriamente entre grafo y mida cómo evoluciona la distribución de grados. 3. Haz un modelo en NetLogo que permita construir redes aleatorias a partir de: (a) Número de nodos de aristas. (b) Número de nodos y densidad de la red. ¿Puedes encontrar alguna relación entre ambo 4. Define un procedimiento en NetLogo que permita calcular el coeficiente de clustering de los no grafo. A continuación aplícalo sobre un grafo cualquiera para calcular su distribución de clustering. 5. Idea algún método de generación dinámica de redes, y mide las características de las redes re densidad, distribución de grados, distribución de clustering, etc. 6. Define un procedimiento que, dada una red en NetLogo, reciba como dato de entrada 2 nodo devuelva la distancia que hay entre ambos. 7. Define un procedimiento para poder calcular en NetLogo el diámetro de un grafo. 8. Define un procedimiento que, dado un grafo en NetLogo, haga lo siguiente: (a) Reciba como dato d un nodo, que llamaremos A, y un número, n . (b) Aproxime la probabilidad de que un camino cua www.cs.us.es/~fsancho/?e=159

14/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

longitud n comenzando por otro nodo del grafo, pase por A. 9. Escribe un procedimiento en NetLogo que, dado un grafo, se comporte de la siguiente forma:( a) Re dato de entrada un nodo del grafo, que notaremos por A. (b) Para cualquier otro nodo del grafo, ap probabilidad de que un camino comenzando por A pase por él. Debe aproximar el cálculo del resto simultáneamente.

Autómatas Celulares 1. Idea una forma de modelar un autómata celular que tenga su soporte sobre un grafo. Piensa cóm solventar el problema de que en un grafo, a pesar de que cada nodo tiene vecinos, igual que ocur malla rectangular, no hay orientación predefinida en ellos para poder definir la función de transici forma sencilla. 2. Usa un autómata celular para simular el comportamiento de un crecimiento por difusión, como ejemplo, el crecimiento de un cristal. Usa si es necesario más de dos estados. 3. Haciendo uso del ejemplo que viene en la biblioteca de NetLogo de patches hexagonales, define celulares 2D que funcionen sobre este tipo de malla. 4. Construye un modelo que sea capaz de ejecutar autómatas celulares 3D haciendo uso de NetLogo3D 5. Haciendo uso del modelo que trae NetLogo para experimentar sobre autómatas celulares 1D, intent análisis manual para clasificar los 256 autómatas 1-dimensionales en las diversas clases de complejid han visto en clase. 6. El problema de la Mayoría se define como sigue: Dada una configuración de un autómata celular de con i + j celdas en total, de las cuales i están con estado 0, y j con estado 1, una solución co problema debe establecer todas las celdas a 0, si i > j , y a 1, si i < j . En caso de que i = j cualquier de los dos resultados. ¿Cuántas posibles configuraciones iniciales hay con i + j estados verificando las condiciones anteriormente? Intenta encontrar un autómata celular que resuelva el problema. Expón los experimentos que haga no encuentres la solución.

Fractales 1. Define procedimientos por recursión para generar algunos de los fractales clásicos que se han v teoría. 2. Genera los procedimientos necesarios para poder definir fractales por medio de sistemas L documentos que hay en el tema acerca de este tipo de sistemas). 3. Define un modelo que aproxime fractales haciendo uso del método IFS. 4. Define un procedimiento que aproxime la dimensión fractal de una figura usando el método del cajas. 5. Haz uso de NetLogo3D para realizar fractales similares a los vistos en clase pero que hagan dimensiones. 6. Haz un modelo que sea capaz de representar el conjunto de Mandelbrot (o conjuntos de Juli funcionalidades para poder navegar por ellos de una forma cómoda.

Algoritmos Genéticos 1. Busca representaciones que te permitan obtener resultados similares a este que se muestra aquí . 2. Modifica el modelo de los tiburones y los peces para: (a) Incluir sexualidad en la población, (b) E reproducción en los tiburones. Recuerda poner alguna limitación en las características de las especie 3. Vamos a usar Algoritmos Genéticos para calcular óptimos de funciones de varias variables, usando llaman Algoritmos Genéticos Continuos. Vamos a explicarlo para funciones de 2 variables, f este caso, un gen será un par formado por dos valores (x, y). Dados 2 individuos de la población, (x , y ), para cada α ∈ [0, 1] se pueden calcular los dos descendientes siguientes por med cruzamiento continuo: (αx + (1 − α)x , αy + (1 − α)y ) y ((1 − α)x + αx , (1 − α)y + mutación se consigue de forma análoga al caso de genes discretos, modificando ligeramente alguna componentes. Tras esto, se puede aplicar el mismo algoritmo que el visto en clase para optimizar función de 2 (o n ) variables. Aplícalo para optimizar funciones reales. 4. Aplica los métodos de resolución de este apartado para resolver algunos de los problemas de la 2

2

1

2

1

2

1

2

1

Genérica de Problemas.

www.cs.us.es/~fsancho/?e=159

15/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

Algoritmos de Hormigas 1. Implementa una solución al Problema del Viajante haciendo uso de Colonias de Hormigas per en los que el grafo subyacente a las ciudades no sea el grafo completo (es decir, no estén todas la conexiones entre ciudades). 2. Busca posibles mejoras sobre el algoritmo de hormigas para resolver el problema de viajante. 3. Haz uso de algoritmos de hormigas para calcular caminos mínimos en grafos. Introduce varian se basen en la distancia de la arista, sino en pesos que puedan tener. 4. Implementa el algoritmo de hormigas elitista, en el que de forma adicional se incrementa la de la mejor solución encontrada hasta el momento. 5. Implementa el algoritmo de hormigas con ranking, en el que únicamente se añade feromo mejores soluciones de cada vuelta, junto con la mejor solución encontrada hasta el momento. 6. Aplica los métodos de resolución de este apartado para resolver algunos de los problemas de la Genérica de Problemas.

Optimización por Enjambres de Partículas 1. El algoritmo PSO visto en clase usa una discretización de la función que se está optimizando por me patches. Haz los cambios necesarios para que se pueda usar con funciones no discretizadas sin con patches (esto es, si tenemos una función f (x, y), cada partícula no mira el valor que hay en el patch debajo, sino que directamente evalúa el valor de f en su posición). 2. Implementa un PSO en el que haya familias de partículas, de forma que no se guían por el me obtenido del total, sino únicamente de la familia a la que pertenecen, y quizás haya partículas qu pertenecer a más de una familia. 3. Implementa un PSO en el que la comunicación entre partículas venga determinada por la pos ocupan, es decir, que cada partícula solo puede saber los valores alcanzados por partículas que están un determinado radio. 4. Haz una implementación de PSO en el que la vecindad de cada partícula (es decir, el conjunto de de las que puede obtener información) viene dado por un grafo prefijado a priori. Haz pruebas funciona el algoritmo para distintos tipos de grafos con el mismo número de nodos (por ejemplo, aleatorios en los que el número de aristas varía, o para grafos generados siguiendo el algoritmo preferencial). 5. Al igual que hemos optimizado el problema del tráfico 1D por medio de PSO, haz uso de otros m NetLogo que puedas optimizar haciendo uso del mismo algoritmo. 6. Utiliza PSO para optimizar los parámetros de los que depende el algoritmo de Colonias de Hormig caso concreto (por ejemplo, una instancia concreta del problema del viajante). 7. Aplica los métodos de resolución de este apartado para resolver algunos de los problemas de la Genérica de Problemas.

Aprendizaje Automático Puedes encontrar una gran colección de conjuntos de datos en la página UCI Machine Learning Reposito además de los datos puedes encontrar una explicación del contenido y problema que presentan.

Clustering y KNN 1. Implementa el algoritmo de las K-medias sin tener en cuenta la librería. Aplica el algoritm implementado sobre datos reales para ver los resultados que salen. 2. Busca un conjunto de datos bidimensionales en el que puedas aplicar los algoritmos de Clusterin clase. Aprovechando la librería dada en el repositorio, haz lo mismo con conjuntos de datos de dim superiores y piensa alguna forma de representar las agrupaciones que se obtienen. 3. Utiliza algún algoritmo de Clustering para rebajar el número de colores que se usa en una imagen 1. Carga una imagen en los patches haciendo uso de la función de importación adecuada. 2. Aplica el algoritmo de Clustering al conjunto de colores, determinando a priori el nú colores finales que quieres usar (puedes hacer que sea una decisión del usuario por m interfaz). 3. Muestra la imagen resultante con los colores reasignados según el cluster al que pertenecen 4. ¿Se te ocurre alguna forma de restringir la paleta de colores original (no solo el número de c 4. Añade al algoritmo de las K-medias alguna forma de medir la eficiencia según el número de clust usa para poder decidir cuál es la agrupación más óptima con respecto a alguna medida que te www.cs.us.es/~fsancho/?e=159

16/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

Haciendo uso de esta medida, genera un programa que permita extraer una clusterización de los necesidad de explicitar el número de clusters que se buscan. 5. Implementa el algoritmo de los K vecinos más cercanos (KNN) visto en clase desde dimensiones superiores. Busca un conjunto de datos que necesite más de 2 dimensiones en el q aplicar el algoritmo KNN que has diseñado. 6. Implementa una modificación del algoritmo KNN en el que se pondere la importancia de los ve cercanos en función de la distancia a la que se encuentren. Comienza haciéndolo para 2 dime amplíalo posteriormente para dimensiones mayores que 2. 7. Haz un estudio de cómo afecta el valor de K en el algoritmo KNN sobre conjuntos de datos conc casos de multiclasificación, no solo binaria. No olvides reservar algunos datos para el test po representa la matriz de confusión asociada a los datos. 8. KNN Condensado: En el algoritmo KNN hay el problema de que requiere de mucha memoria y ejecución porque hay que almacenar continuamente todos los datos que definen el espacio de ejemp Sin embargo, es muy probable que muchas de las muestras iniciales no sean necesarias para cla demás, ya que su información es redundante con las otras existentes. Para reducir este problema preprocesamiento de los datos que se llama condensación, y que consiste en lo siquiente (ob depende del orden dado a los datos y, además, tiene el problema de conservar los datos que introdu al sistema): Dado un orden en los datos de entrada, para cada ejemplo se clasifica por medio haciendo uso únicamente de los datos anteriores; si la clasificación obtenida coincide con la real, es se elimina de los datos, si no, permanece. Añade un procedimiento condensa a la librería vista en clase para producir este preprocesam limpieza inicial y así reducir la carga computacional del algoritmo. 9. Regla de Reducción para KNN: es similar a la anterior, pero se comienza con el conjunto co datos, y se eliminan aquellos que no afectan a la clasificación del resto de datos de entrada (en co condensación anterior, es capaz de eliminar las muestras que producen ruido, y guarda aquella críticas para la clasificación. 10. Considera el siguiente conjunto de entrenamiento Ej

Atr1.

Atr2.

Atr3.

Clasif

E1

1

1

0

SI

E2

1

0

0

SI

E3

1

0

1

SI

E4

0

0

1

NO

1. Aplica el algoritmo KNN con k = 1 para clasificar P = (0 75, 0, 0) a partir del con entrenamiento anterior usando la distancia de Manhattan. 2. Considera el conjunto de entrenamiento anterior sin la columna de clasificación y m = (1, 1, −1) y m = (0, −1, 1) , aplica el algoritmo de k-medias para k = 2 con m y m centros iniciales hasta la primera modificación de los centros. Prueba con otros algor Clustering. ′

1

2

1

11. Considera los puntos P = (0, 48) , P = (0, 78) , P = (36, 126) , P = (36, 0) y los centros m = y m = (36, 63). Se pide aplicar algún algoritmo de Clusetring usando la distancia euclídea sobre P , … , P tomando m y m como centros iniciales (k = 2 ) hasta la primera modificación de los ce 12. Haciendo uso de la siguiente matriz de distancias entre los puntos del dataset: 1

2

3

4

1

2

1

4

A

www.cs.us.es/~fsancho/?e=159

1

B

C

2

D

E

A

0

B

2'15

0

C

0'7

1'53

0

D

1'07

1'14

0'43

0

E

0'85

1'38

0'21

0'29

0

F

1'16

1'01

0'55

0'22

0'41

F

G

0 17/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

G

1'56

2'83

1'86

2'04

2'02

2'05

0

Aplica el método AGNES para obtener la jerarquía de clusters asociados usando alguna de las habituales.

Árboles de Decisión: ID3 1. Busca conjuntos de datos sobre los que puedas aplicar el algoritmo ID3 visto en clase. 2. Modifica el modelo ID3 para que pueda incluir alguna versión sencilla de trabajar con atributos con 3. Modifica el modelo ID3 para que trabaje con atributos continuos haciendo uso del algoritmo medias para decidir las agrupaciones que usará en los atributos continuos (es decir, primero se algoritmo de las K-medias al atributo, y se decide las agrupaciones que se considerarán para discreti 4. El algoritmo ID3 visto en clase solo construye el árbol. Amplía el modelo para que, posteriormente usar como verdadera máquina de clasificación, de forma que reciba un dato de entrada y d clasificación obtenida. 5. Unos biólogos que exploraban la selva del Amazonas han descubierto una nueva especie de ins bautizaron con el nombre de lepistos. Desgraciadamente, han desaparecido y la única información de este insecto viene dada por el siguiente conjunto de ejemplos encontrados en un cuaderno de no que se clasifican una serie de muestras de individuos en función de ciertos parámetros como su colo alas, su tamaño y su velocidad. Haciendo uso de la tabla, contesta a las siguiente cuestiones: EJEMPLO

COLOR

ALAS

TAMAÑO

VELOCIDAD

LEPISTO

E1

negro

sí

pequeño

alta

sí

E2

amarillo

no

grande

media

no

E3

amarillo

no

grande

baja

no

E4

blanco

sí

medio

alta

sí

E5

negro

no

medio

alta

no

E6

rojo

sí

pequeño

alta

sí

E7

rojo

sí

pequeño

baja

no

E8

negro

no

medio

media

no

E9

negro

sí

pequeño

media

no

E10

amarillo

sí

grande

media

no

1. ¿Cuál es la entropía del conjunto de ejemplos respecto a la clasificación de los mismos que atributo Lepisto? 2. ¿Qué atributo proporciona mayor ganancia de información? 3. Aplicar (detallando cada uno de los pasos realizados) el algoritmo ID3 para encontrar, a este conjunto de entrenamiento, un árbol que nos permita decidir si un determinado individ lepisto o no. 4. Obtener un conjunto de reglas a partir del árbol obtenido en el apartado anterior. 5. Según las reglas obtenidas, ¿hay algún atributo que sea irrelevante para decidir si un ind un lepisto? 6. Una entidad bancaria concede un préstamo a un cliente en función de una serie de parámetros (puede ser joven, mediano o mayor), sus ingresos (altos, medios o bajos), un informe sobre su financiera (que puede ser positivo o negativo) y, finalmente, si tiene otro préstamo a su cargo siguiente tabla presenta una serie de ejemplos en los que se especifica la concesión o no del pré función de estos parámetros:

www.cs.us.es/~fsancho/?e=159

Ejemplo

Edad

Ingresos

Informe

Otro prestamo

Conceder

E1

joven

altos

negativo

no

no

E2

joven

altos

negativo

si

no

E3

mediano

altos

negativo

no

si 18/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

Ejemplo

Edad

Ingresos

Informe

Otro prestamo

Conceder

E4

mayor

medios

negativo

no

si

E5

mayor

bajos

positivo

no

si

E6

mayor

bajos

positivo

si

no

E7

mediano

bajos

positivo

si

si

E8

joven

medios

negativo

no

no

E9

joven

bajos

positivo

si

si

E10

mayor

medios

positivo

no

si

E11

joven

medios

positivo

si

si

E12

mediano

medios

negativo

si

si

E13

mediano

altos

positivo

no

si

E14

mayor

medios

negativo

si

no

Supongamos que modificamos el algoritmo ID3 de manera que el criterio para obtener el “mejor” at clasifica un conjunto de ejemplos es el de menor ganancia de información. En esta situación se pide: 1. En caso de ausencia de ruido, ¿obtendría el algoritmo modificado un árbol de decisión co con los ejemplos del conjunto de entrenamiento?, justifica la respuesta. 2. ¿Qué sesgo tendría el algoritmo modificado?, justifica la respuesta. 3. Aplica (detallando cada uno de los pasos realizados) el algoritmo modificado para enc partir de este conjunto de entrenamiento, un árbol que nos permita decidir sobre la conc préstamos. 7. Aplica el algoritmo ID3 para construir un árbol de decisión consistente con los siguientes ejemplo ayude a decidir si comprar o no un CD nuevo. Considerar los siguientes ejemplos como conjunto d obtener la medida de rendimiento del árbol obtenido.

www.cs.us.es/~fsancho/?e=159

Ejemplo

Cantante

Discográfica

Género

Precio

Tienda

Comprar

E1

Queen

Emi

rock

30

Mixup

si

E2

Mozart

Emi

clásico

40

Virgin

no

E3

Anastacia

Corazón

soul

20

Virgin

si

E4

Queen

Sony

rock

20

Virgin

si

E5

Anastacia

Corazón

soul

30

Mixup

si

E6

Queen

Sony

rock

30

Virgin

si

E7

Wagner

Sony

clásico

30

Mixup

no

E8

Anastacia

Corazón

soul

30

Virgin

no

E9

Queen

Emi

rock

40

Virgin

no

E10

Mozart

Sony

clásico

40

Mixup

si

Ejemplo

Cantante

Discográfica

Género

Precio

Tienda

Comprar

E11

Queen

Emi

rock

30

Virgin

si

E12

Anastacia

Corazón

soul

20

Virgin

no

E13

Queen

Sony

rock

20

Virgin

no

E14

Anastacia

Corazón

soul

30

Virgin

no 19/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

Ejemplo

Cantante

Discográfica

Género

Precio

Tienda

Comprar

E15

Queen

Sony

rock

40

Virgin

no

E16

Mozart

Sony

clásico

40

Mixup

si

8. La siguiente tabla muestra ejemplos de plantas, indicando si sobrevivieron más de un año o no desp compradas, en función de su tamaño (grande, medio o pequeño), de su ambiente adecuado ( exterior), de si tienen flores y de la estación en la que se compró. Usa la siguiente tabla para aplicar (detallando cada uno de los pasos realizados) el algoritmo ID3 y un árbol de decisión consistente con el conjunto de entrenamiento {E , … , E } que permita dec 1

16

planta sobrevivirá más de un año o no después de ser comprada. Suponer que se elige para el no atributo tamaño , y continuar la ejecución del algoritmo a partir de ahí. Ejemplo

Tamaño

Flores

Ambiente

Estación

Sobrevive

E1

grande

si

interior

verano

no

E2

grande

si

interior

verano

no

E3

grande

si

exterior

primavera

no

E4

grande

si

exterior

invierno

no

E5

grande

no

interior

otoño

no

E6

grande

no

exterior

primavera

no

E7

medio

si

interior

verano

si

E8

medio

si

interior

verano

si

E9

medio

no

interior

primavera

si

E10

medio

no

exterior

otoño

no

E11

medio

no

exterior

verano

no

E12

pequeño

si

interior

invierno

no

E13

pequeño

si

exterior

verano

si

E14

pequeño

no

interior

primavera

no

E15

pequeño

no

interior

verano

si

E16

pequeño

no

exterior

otoño

no

Usa la siguiente tabla para medir el rendimiento del árbol obtenido: Ejemplo

Tamaño

Flores

Ambiente

Estación

Sobrevive

E17

grande

no

exterior

verano

no

E18

medio

no

interior

otoño

si

E19

medio

no

exterior

primavera

no

E20

medio

si

exterior

verano

no

E21

pequeño

si

interior

verano

no

E22

pequeño

si

interior

invierno

no

E23

pequeño

no

interior

verano

no

E24

pequeño

no

exterior

otoño

no

9. Una empresa de material deportivo quiere hacer un estudio de mercado para encontrar las cara principales de sus potenciales clientes. En una primera fase, las características a estudiar son las sig www.cs.us.es/~fsancho/?e=159

20/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

edad (joven o adulto), ser deportista profesional, el nivel de ingresos (altos, medios o bajos) y el ello, se realiza un cuestionario a 21 personas, obteniendo los resultados que se reflejan en la siguient Ejemplo

Edad

Profesional

Ingresos

Sexo

Interesado

E1

joven

si

bajos

hombre

si

E2

joven

si

altos

hombre

si

E3

joven

no

altos

mujer

no

E4

joven

si

bajos

mujer

si

E5

joven

no

medios

mujer

no

E6

adulto

si

altos

hombre

no

E7

adulto

no

altos

mujer

no

E8

adulto

si

altos

mujer

no

E9

adulto

no

medios

mujer

no

E10

adulto

si

bajos

mujer

no

E11

adulto

no

medios

mujer

no

E12

adulto

si

medios

hombre

no

E13

adulto

no

altos

hombre

si

E14

joven

si

altos

mujer

si

E15

joven

si

medios

hombre

si

E16

adulto

no

medios

hombre

no

E17

adulto

no

bajos

hombre

no

E18

joven

no

medios

hombre

no

E19

joven

no

bajos

mujer

no

E20

adulto

si

medios

mujer

no

E21

joven

si

medios

mujer

si

1. Aplica el algoritmo ID3 para obtener un árbol de decisión que sirva para decidir si u potencial está interesado o no en el producto que ofrece la empresa. Tomar como con entrenamiento los primeros 15 ejemplos de la tabla. 2. Tomando ahora como conjunto de prueba los ejemplos del 16 al 21 de la tabla, c rendimiento del árbol de decisión obtenido en el apartado anterior. Usando ese conjunto de aplica un proceso de podado a posteriori sobre el árbol de decisión. Expresa mediante regla obtenido tras la poda ¿Qué rendimiento tiene este árbol sobre el conjunto de prueba? ¿Y conjunto de entrenamiento? 10. Se han encontrado una gran cantidad de obras de arte realizadas por dos artistas A y B, pero sól pequeño número de obras se ha podido asegurar cuál de los dos es el autor. La siguiente tabla m datos de dichas obras, indicando el autor en función del tipo de obra (grabado, óleo o acuarela) donde se encontró la obra (España, Portugal o Francia), de su estilo (clásico o moderno), y de si tien o no.

www.cs.us.es/~fsancho/?e=159

Ejemplo

Tipo

Lugar

Estilo

Marco

Autor

E1

grabado

España

clásico

no

B

E2

grabado

España

moderno

no

B

21/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

Ejemplo

Tipo

Lugar

Estilo

Marco

Autor

E3

grabado

Portugal

moderno

no

B

E4

grabado

Francia

clásico

si

B

E5

grabado

Francia

moderno

no

B

E6

grabado

Francia

moderno

si

B

E7

óleo

España

clásico

si

A

E8

óleo

España

clásico

no

A

E9

óleo

Francia

moderno

no

A

E10

óleo

Portugal

moderno

si

B

E11

óleo

España

moderno

si

B

E12

acuarela

Francia

clásico

no

B

E13

acuarela

España

clásico

si

A

E14

acuarela

Francia

moderno

no

B

E15

acuarela

España

moderno

no

A

E16

acuarela

Portugal

moderno

si

B

1. Aplica el algoritmo ID3 para encontrar un árbol de decisión consistente con el con entrenamiento {E , … , E } que permita decidir si una obra de arte fue realizada por A o p 2. Usa la siguiente tabla de ejemplos como conjunto de prueba para calcular el rendimiento de decisión obtenido en el apartado anterior 1

16

Ejemplo

Tipo

Lugar

Estilo

Marco

Autor

E17

grabado

España

moderno

si

A

E18

óleo

Portugal

moderno

no

A

E19

óleo

Francia

moderno

si

B

E20

óleo

España

moderno

no

A

E21

acuarela

España

clásico

no

A

E22

acuarela

Francia

clásico

si

B

E23

acuarela

España

moderno

si

A

E24

acuarela

Portugal

clásico

si

B

Mapas Auto-organizados: SOM 1. Prepara algunos ejemplos de clasificación para ser aplicados con los modelos SOM clas proporcionados en las librerías de la asignatura. 2. Haz modificaciones del modelo SOM para que haga el entrenamiento sobre otras estructuras topoló 3. Usando NetLogo3D, haz las modificaciones necesarias para que pueda implementarse SOM en u de patches 3D. 4. Haz uso de SOM para reducir el número de colores de una imagen. ¿De qué forma podrías usar S hacer segmentación de imágenes (reconocer conjuntos de pixels que correspondan a los mismos obj 5. Haz uso de SOM para entrenar el movimiento de un robot que evite obstáculos en su recorrido objetivo. Para ello, debes modelar en NetLogo al robot por medio de una tortuga que tiene se distancia delante, sensor de dirección y se mueve a velocidad constante. 6. Haz uso de SOM 3D para aproximar varias superficies y volúmenes por medio del entrenamie nubes de puntos. Utiliza las aproximaciones obtenidas para dar mallas que amplíen o reduzcan la www.cs.us.es/~fsancho/?e=159

22/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

inicial de un modelo. 7. Usa el modelo SOM-TSP (que se ha construido usando la librería SOM proporcionada en el reposit comprobar los efectos de los distintos parámetros disponibles en la aproximación al ciclo proporcionado por SOM. ¿Crees que es suficiente el uso de SOM para asegurar que el ciclo obten longitud mínima?, ¿echas en falta algo? Comprueba también el resultado de cambiar la estructura s en los nodos de aprendizaje. 8. Usa SOM-hexaClassifier para extraer un aprendizaje no supervisado de algunos conjuntos pequeños disponibles en UCI Machine Learning Repository .

Redes Neuronales 1. Crea una red Neuronal que, con el entrenamiento adecuado, sea capaz de calcular la función bin mayoría: recibe una entrada de n bits, y devuelve 1 si hay mayoría de 1 s y 0 en caso contrario. 2. Crea una red Neuronal que, con el entrenamiento adecuado, sea capaz de calcular la función bin paridad: recibe una entrada de n bits, y devuelve 1 si hay una cantidad par de 1 s y 0 en caso contrar 3. Crea, y entrena, estructuras de redes neuronales simples que calculen algunas funciones lógicas (AND, OR, NOT, XOR,NAND,... y combinaciones de ellas). 4. Haz uso de redes neuronales adecuadas para aproximar el cáculo de algunas funcion f (x) = x ,  f (x) = sin(x),  f (x, y) = xsin(y) , ... 5. Crea conjuntos artificiales de puntos 2D con una clasificación asignada (no tiene porqué ser bina uso de diversas redes neuronales para aprender la clasificación y compara los resultados características topológicas de las redes neuronales utilizadas. Observa también las característ frontera de separación entre las áreas de clasificación y la capacidad de las redes para separar corr distintas estruturas (lineales, con agujeros, mezclas al azar, etc.). ′

′

2

6. ¿De qué forma podría usarse una red neuronal para hacer la función del algoritmo KNN?, ¿y par como K-medias? 7. Haz uso del modelo de reconocimiento que se ha visto en clase para entrenar a una red ne reconocer algunos patrones específicos. Para ello tendrás que ser capaz de generar adecuadamente ejemplos. 8. Una nariz electrónica analiza mediante sensores los vapores procedentes de determinadas sustan clasifica a partir de la información cuantitativa obtenida. Supongamos que utilizamos 16 sens identificar cuatro tipos de vino tinto: Cabernet, Merlot, Syraz y Tempranillo. Describe en det podríamos usar una red neuronal para abordar este problema: en qué consistiría un co entrenamiento y cómo se codificarían los ejemplos, la estructura de la red, el algoritmo de entre usado, y de qué manera se usaría la red una vez entrenada para identificar un nuevo vino tinto. 9. Supongamos que una empresa de TV por cable quiere diseñar un sistema automatizado para reco sus clientes uno de sus cinco canales temáticos en función de sus preferencias, que se tratan de a función de una encuesta con 20 preguntas. ¿Cómo diseñarías el sistema usando una red neuron estructura tendría esta red neuronal? ¿Cómo entrenarías la red y cuál sería tu conjunto de entren Una vez entrenada, ¿cómo usarías la red obtenida para recomendar un canal temático a un nuevo cli 10. Supongamos que queremos diseñar un sistema de anuncios personalizados para los usuarios de web. En este portal web hay veinte secciones temáticas y la compañía maneja cuatro posible publicitarios, cada uno de ellos apropiado a un usuario en función de los temas que más le interesan cómo se usaria una red neuronal para implementar este sistema: estructura de la misma, co entrenamiento, aprendizaje de los pesos, uso de la red una vez entrenada... 11. Supongamos que queremos diseñar un sistema automatizado para reconocer el estado de ánimo d observando la expresión de su cara. Por simplificar las cosas, supongamos que consideramos cu distintos de estados de ánimo: alegre, triste, enfadado y neutro. Suponiendo que nuestro sistema d una cámara que es capaz de obtener imágenes digitalizadas de la cara de una persona ¿cómo dis sistema usando una red neuronal? ¿en qué consistiría el aprendizaje de esa red? 12. Idea un escenario en el que puedas entrenar una red neuronal haciendo uso de algoritmos gen decir, cada individuo almacenará una variante de una misma red (solo cambian los pesos) que re problema en el espacio en el que se encuentra. en cada iteración se ponen todos los individuos a pr resolver el problema y se le asigna un fitness en función de lo buena que haya sido su red neurona objetivo. Se aplica el AG y se hace evolucionar la población completa. Al final de muchas iteraciones que la población tenga individuos con redes muy aptas para la resolución del problema original. 13. Crea, y entrena adecuadamente, una red neuronal que pueda distinguir entre dos símbolos escrito 14. Crea un modelo que sea capaz de leer algún formato de red neuronal que inventes (recuerda contener, al menos, información acerca del número de capas, número de neuronas por capa, f www.cs.us.es/~fsancho/?e=159

23/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini

activación que usarán las neuronas, y todos los pesos de la red), con el que puedas cargar redes n pre-entrenadas en otros ejercicios y ejecutarlas como máquinas de cálculo.

15.

Disponemos de un robot con un brazo con 2 grados de libertad que se mu tal y como muestra la figura. Ajustando los ángulos, θ , θ , el robot puede colocar su extremo en (x, y) del plano. 1

2

x = l1 cos θ1 + l2 cos(θ1 + θ2 )

y = l1 sin θ1 + l2 sin(θ1 + θ2 )

1. Entrena una red neuronal multicapa con una capa oculta de 5 neuronas que sea aprender la cinemática inversa del robot, es decir, dadas las coordenadas del extremo, (x, entrada, la red debe devolver los correspondientes ángulos (θ , θ ) que le permiten alca punto. 2. Si entrenas la red con 10 muestras de entrenamiento uniformemente distribuidos en el ¿cuántas epochs se necesitan para que el entrenamiento de la red converja?, ¿cómo cam número cuando crece el tamaño del conjunto de entrenamiento? Haz pruebas experimentale 3. Usa datos de validación para determinar cómo generaliza la red el aprendizaje. ¿Cómo tamaño de la capa oculta a la calidad de los resultados de la red? Haz pruebas experiment comprobar esta relación. 1

2

16. Imagina que tomamos un perceptrón simple y multiplicamos todos sus pesos (y bias) por una positiva, c > 0. Demuestra que el comportamiento de la unidad no cambia. ¿Puedes decir lo mism de trabajar con un perceptrón individual trabajamos con una red de perceptrones? ¿cómo afecta el función de activación a este hecho? 17. A partir de los distintos métodos vistos a lo largo del curso, piensa en métodos adicionales de entre de redes neuronales, destacando las ventajas e inconvenientes que podría tener cada uno de ellos 18. Verifica que, en el caso de que σ sea la función sigmoide, entonces σ (x) = σ(x)(1 − σ(x)) . ′

TAMBIÉN TE PUEDE INTER 1. Ejercicios IA (9029 vistas) 2. Instalación Python+Keras+Tensorflow (3925 vista 3. Elm: Introducción (2314 vistas) 4. Curso MOOC de NetLogo en Difundi (939 vistas) 5. Calificaciones LITI 2017-2018 (627 vistas) 6. Elm: Señales (588 vistas) 7. Calificaciones IAIC 2017-2018 (551 vistas) 8. Propuestas de Trabajos de Investigación/Desarrol 9. IAIC 19-20: Grupos de Prácticas (514 vistas) 10. Conceptos Matemáticos y Terminología para la Funcional (499 vistas)

www.cs.us.es/~fsancho/?e=159

24/25

25/4/2020

Ejercicios IA - Fernando Sancho Caparrini 0 Comentarios  Recomendar

🔒 Política de privacidad de Disqus

Añade un comentario si lo deseas... t Tweet

1 

Ordenar por

f Compartir

Sé el primero en comentar... INICIAR SESIÓN CON

O REGISTRARSE CON DISQUS ?

Nombre

Sé el primero en comentar.

✉ Suscríbete d Añade Disqus a tu sitio webAñade Disqus Añadir

⚠ Do Not Sell My Data

« Examen Bloque II. Dic… « || Inicio || » Calificacio

Magazine Theme for PivotX

www.cs.us.es/~fsancho/?e=159

by Windmill Web Work

in 2009, released under the Simple Public License

.

25/25