Source: http://www.cs.us.es/~fsancho/?e=159
Timestamp: 2019-04-19 22:34:03+00:00

Document:
Ejercicios IA - Fernando Sancho Caparrini
9. PSO: Optimización por enjambres de partículas (11553 vistas)
10. Entrenamiento de Redes Neuronales: mejorando el Gradiente Descendiente (10913 vistas)
« Examen Bloque II. Dic… « || Inicio || » Calificaciones Lógica… »
Ejercicios IA
Última modificación: 12 de Enero de 2019, y ha tenido 5230 vistas
Esta colección muestra un conjunto de ejercicios que pueden resolverse con las diversas técnicas estudiadas a lo largo del curso. Se recuerda que la sección de problemas genéricos pueden ser adaptados para ser resueltos por muchos de los métodos vistos, desde la simple representación del problema como espacio de estados, hasta los métodos más avanzados de PSO o Colonias de Hormigas. Una vez representados para ser resueltos por una técnica particular, se aconseja realizar la implementación correspondiente en NetLogo haciendo uso de las librerías proporcionadas en el curso.
El índice de las diversas colecciones de ejercicios es la siguiente:
Ejercicios de NetLogo
Colección Genérica de Problemas: Representación
IA Clásica:
Búsquedas Clásicas
Juegos con Adversario
Satisfacción de Restricciones (PSR)
Sistemas Dinámicos y Redes Complejas
Autómatas Celulares (AC)
Algoritmos de Hormigas (ACO)
Optimización por Sistemas de Partículas (PSO)
K-medias y KNN
Árboles de decisión (ID3)
Prepara el terreno asignando aleatoriamente patches con madera seca siguiendo una determinada 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 sus vecinos que tenga madera seca.
Añade un botón forever que ejecute el procedimiento anterior.
Añade fuerza y direccionalidad del viento (justifica la interpretación dada).
Añade diferencias en el terreno (proporción de seco, tiempo de quemado y de propagación,...).
Añade plots q muestren los resultados.
Prepara los agentes con alguna caracteristica que permita saber si tienen el mensaje o no (aquellos que no lo tenga no lo difundirán).
Proporciona un slider para determinar el número de agentes en el mundo.
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 agente, por ejemplo).
Proporciona una fuerza de impacto inicial al mensaje, de forma que a medida que lo oiga el agente más veces, esta fuerza de impacto decaiga y, superado un umbral, ya no lo transmita más.
3.- Juego de la vida (Conway): El juego de la vida es en realidad un juego de cero jugadores determinista, lo que quiere decir que su evolución está determinada por el estado inicial y no necesita ninguna interacción posterior.
El "tablero de juego" es una malla formada por cuadrados ("células") que se extiende por el infinito en todas las direcciones. Se consideran las 8 células vecinas de cada célula. Las células tienen dos estados: están "vivas" o "muertas" (o "encendidas" y "apagadas"). El estado de la malla evoluciona a lo largo de unidades de tiempo discretas (se podría decir que por turnos). El estado de todas las células se tiene en cuenta para calcular el estado de las mismas al turno siguiente. Todas las células se actualizan simultáneamente.
Añade un slider ProbMovimientoAleatorio. Modifica el comportamiento de los agentes para que con la probabilidad que indique ese slider se muevan, independientemente de que sean felices donde están o no. Si hay distintas opciones para esta extensión, selecciona una de ellas y justifica porqué se ha seleccionado.
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:
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
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. Aleatoriamente, los agentes se mueven por el mundo y, si se encuentran dos de ellos, se enfrentan de forma probabilística, es decir, cada cual "genera un número proporcional a su fuerza" y el que pierda muere. Gana el último agente que quede en pie.
Para comprobar que la realización de los siguientes ejericios es correcta se debe tener algún grafo creado en NetLogo, por ello se recomienda hacer todos en el mismo modelo y poder asi usar unos como base de los siguientes.
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 de aristas incidentes en él).
9.- Haz un procedimiento que reciba como dato un nodo, y etiquete el resto de nodos del grafo con la distancia a ese 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 componente conexa a la que pertenece. (Es decir, numera las componentes conexas, y etiqueta los nodos de cada componente con el 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 de "enlace preferencial": se van añadiendo nodos al grafo de forma que cada nodo nuevo se enlaza solo con uno de los presentes en ese momento, y la probabilidad de unirse a cada uno de los nodos existentes es directamente proporcional al grado de 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 del primero al segundo.
13.- Repetid los primeros ejercicios de esta sección poniendo como soporte un grafo en vez de patches (donde tenga sentido).
Para todos los problemas siguientes se pueden considerar las siguientes preguntas generales, además de las 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é tamaño tiene 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 espacio de estados.
Proporciona una función de coste que tenga sentido para medir la ejecución de la función de transición.
Proporciona una función heurística que sirva para medir la bondad de un estado respecto del objetivo buscado.
Según algunos de los métodos de resolución que se ven en el curso, puedes intentar los siguientes ejercicios para cada método:
Espacios de Búsqueda: 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
Problema del coloreado de Mapas: Fijado un grafo, \(G\), con un etiquetado dado y una función \(vecinos?(x,y)\) que indica si los nodos \(x\) e \(y\) son vecinos en \(G\). Determina (y en caso positivo, proporciona) si existe un coloreado válido de \(G\) haciendo uso de \(K\) colores. (Un coloreado es una asignación de colores a nodos, y es válido si nodos conectados están coloreados con colores distintos).
Un mono de \(30cm\) de altura, que no puede saltar se mete en una habitación en la que hay colgados unos plátanos a \(90cm\) de altura. Evidentemente, el mono quiere un plátano. Además, la habitación tiene \(2\) bloques apilables de \(30cm\) de alto que podrían soportar al mono.
Problema de las \(3\) Jarras: Se tienen \(3\) jarras de \(12\), \(8\) y \(3\) litros de capacidad y un grifo. Las operaciones que se pueden realizar con ellas son: llenar cada una de las jarras de agua, volcar el contenido de una en cualquier otra (hasta que una de las dos se vacía, o la otra se llena), o bien vaciar su contenido en el suelo. El objetivo es conseguir exactamente \(1\) litro en alguna de las jarras.
Formaliza la siguiente versión del puzzle Todos los dígitos del Rey: Dado el conjunto de dígitos \(0123456789\), inserta los símbolos de los operadores aritméticos (\(\times + - /,\)) y paréntesis entre ellos para que la expresión resultante se evalúe como 100. Por ejemplo: \[0+1+2+3+4+5+6+7+(8\times 9) =100\] ¿Puedes encontrar alguna otra solución?
Un cuadrado mágico consiste en una distribución de números en filas y columnas, formando un cuadrado, de forma que los números de cada fila, columna y diagonal suman lo mismo. Aunque es posible recrear diferentes tipos de cuadrados mágicos, tradicionalmente se forman con los números naturales desde el \(1\) hasta \(n\), donde \(n\) es el lado del cuadrado. Representa el problema de generación automática de cuadrados mágicos de tamaño \(n\) como un problema de espacio de estados. ¿Cuál sería su factor de ramificación y profundidad? A partir de un cuadrado vacío, representa un árbol de búsqueda que muestre la aplicación de operadores para \(n = 2\).
Tenemos \(10\) cartas numeradas del \(1\) al \(10\). Sepáralas en \(2\) montones de forma que la suma de las cartas del primer montón esté lo más cerca posible a \(36\) y el producto de las cartas del segundo montón esté lo más cerca posible a \(360\).
El problema del \(8\)-puzzle: es un puzle de deslizamiento que consiste en un conjunto de \(8\) piezas en un marco de tamaño \(3\times 3\), por lo que queda un hueco libre. El objetivo del puzle consiste en encontrar la sucesión de movimientos (moviendo piezas al hueco libre) que llevan la distribución inicial a una distribución ordenada prefijada.
Problema de las 2 Jarras: Se tienen dos jarras de agua, una de \(4\) litros y otra de \(3\) litros sin escala de medición. Se desea obtener \(2\) litros de agua en la jarra de \(4\) litros. Las operaciones válidas son: llenar cada una de las jarras, vacíar una de las jarras, pasar agua de una jarra a otra (hasta que la primera se vacía o la segunda se llena).
Misioneros y Caníbales: Hay \(3\) misioneros y \(3\) caníbales a la orilla de un río. Tienen una canoa con capacidad para dos personas como máximo. Se desea que los seis crucen el río, pero hay que considerar que no debe haber más caníbales que misioneros en ningún sitio porque entonces los caníbales se los comerían. Además, la canoa siempre debe ser conducida por alguien.
El Granjero: Un granjero va al mercado y compra un lobo, una oveja y una col. Para volver a su casa tiene que cruzar un río. El granjero dispone de una barca para cruzar a la otra orilla, pero en la barca solo caben él y una de sus compras.Si el lobo se queda solo con la oveja, se la come, si la oveja se queda sola con la col, se la come. El reto del granjero es cruzar el río con todas sus compras. ¿Cómo puede hacerlo?
Torres de Hanoi: Se tienen \(N\) discos de distinto tamaño apilados sobre una base \(A\) de manera que cada disco se encuentra sobre uno de mayor radio. Existen otras dos bases vacías \(B\) y \(C\). Haciendo uso únicamente de las 3 bases, el objetivo es llevar todos los discos de la base \(A\) hasta la base \(C\). Sólo se puede mover un disco a la vez, y cada disco puede descansar solamente en las bases o sobre otro disco de tamaño superior, pero no en el suelo.
Problema de las N reinas: Sitúar \(N\) reinas en un tablero de ajedrez de tamaño \(N\times N\) sin que se amenacen entre ellas. Una reina amenaza a otra si ambas están en la misma fila, columna o diagonal.
Criptoaritmética: Las letras representan dígitos. El objetivo es determinar el valor de cada una de las letras de tal manera que la operación sea correcta aritméticamente. Letras iguales - dígitos iguales, letras diferentes - dígitos diferentes. Ningún número inicia con cero. Por ejemplo:
Cruce del puente: Un grupo de \(5\) personas quiere cruzar un viejo y estrecho puente. Es una noche cerrada y se necesita llevar una linterna para cruzar, pero el grupo sólo dispone de una linterna, a la que le quedan \(5\) minutos de batería.Cada persona tarda en cruzar \(10\), \(30\), \(60\), \(80\) y \(120\) segundos, respectivamente. El puente sólo resiste un máximo de \(2\) personas cruzando a la vez, y cuando cruzan dos personas juntas caminan a la velocidad del más lento. No se puede lanzar la linterna de un extremo a otro del puente, así que cada vez que crucen dos personas, alguien tiene que volver a cruzar hacia atrás con la linterna a buscar a los compañeros que falten, y repetir este proceso hasta que hayan cruzado todos. ¿Cuál sería una solución válida?
Problema de las bolsas: Se pretende encontrar una manera de distribuir un conjunto de objetos, \(O=\{o_1,\dots,o_n\}\), en bolsas, usando el menor númer posible de bolsas. Cada objeto tiene un peso asociado, \(Peso(o_i)=p_i\), y las bolsas tienen un límite de peso soportado, \(B\).
Caminos en grafos: Considerando un grafo geométrico, diseña diversas estrategias para calcular el camino más corto entre dos nodos del grafo.
Suma nula: Dado un conjunto de enteros \(I=\{i_1,\dots,i_n\}\), el problema es encontrar un subconjunto \(S\subseteq I\) que sume \(0\).
El juego de las Ranas: Tenemos 3 ranas negras y 3 verdes situadas encima de 7 nenúfares tal y como muestra el diagrama, que podemos representar como: V V V O N N N, donde O es el nenufar vacío. El objetivo consiste en llegar a la configuración final N N N O V V V. Para ello, los movimientos permitidos son los siguientes: a) Una rana puede moverse a un nenúfar adyacente vacío, con coste 1. b) Una rana puede desplazarse a un nenúfar vacío saltando a una rana como máximo, con un coste igual a 2.
Juego de las Cifras (Cifras y Letras): Dados \(6\) números, y un objetivo \(O\), encontrar la combinación aritmética entre ellos que se aproxima lo más posible a \(O\).
Trabajaremos con números de 3 cifras (de \(100\) a \(999\)). Inicialmente, tenemos dos números prefijados, que denotaremos por \(S\) (Start) y \(G\) (Goal), y un conjunto de números que denotaremos por \(P\) (de Prohibidos). En cada turno, podemos transformar un número en otro añadiendo/sustrayendo 1 a uno de sus dígitos (por ejemplo, pasando de \(678\) a \(679\), o de \(234\) a \(134\)). El coste de cada movimiento es 1. Adicionalmente, tenemos estas restricciones: (a) No se permite añadir \(1\) a \(9\), ni sustraer \(1\) a \(0\). (b) No se permite convertir un número en un elemento de \(P\) (están prohibidos). (c) No se puede cambiar un mismo dígito 2 veces seguidas. Además de dar la representación general, resuelve el caso particular \(S = 567\), \(G = 777\) y \(P = \{666, 667\}\).
Un grupo de \(N\) personas de diferentes países se sienta en una mesa circular con \(N\) sillas. Cada persona sabe hablar dos idiomas (no necesariamente los mismos para todos). Se trata de encontrar una disposición para sentarse de manera que cada persona pueda comunicarse con sus dos vecinos en la mesa.
El Problema del Viajante: Dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad origen?
Un ayuntamiento tiene que adjudicar 10 proyectos de obra mediante concurso público. Se han presentado al concurso 5 empresas, dando presupuestos para cada uno de los diez proyectos. La adjudicación debe realizarse de manera que a cada empresa sólo se le concedan dos proyectos. Encuentra la adjudicación de menor precio.
Un ganadero tiene un rebaño de \(n\) ovejas. Cada oveja \(i\) tiene un peso \(p_i\) y la vende por un precio \(v_i\). Dispone de un camión que es capaz de cargar un peso total \(T\). Su problema es seleccionar una serie de ovejas para llevarlas al mercado de ganado en el camión, de manera que se maximice el precio total de las ovejas transportadas, sin superar el peso total soportado por el camión.
Usa algún método de optimización para conseguir un buen autómata celular 1D que resuelva de la mejor forma posible (cometerá errores) el problema de la mayoría. (Ayuda: usa la representación binaria de las reglas del autómata como conjunto de genes del individuo).
Problema de asignación de tareas: Hay un número de agentes (\(\{a_i: 1\leq i\leq n\}\)) y un número de tareas a realizar (\(\{t_j: 1\leq j \leq m\}\)). Cualquier agente puede ser asignado para desarrollar cualquier tarea, contrayendo algún coste (\(c_{ij}\)) que puede variar dependiendo del agente, \(i\), y la tarea, \(j\), asignados. Es necesario para desarrollar todas las tareas asignar un solo agente a cada tarea para que el coste total del asignación sea minimizado, aunque un mismo agente podría realizar más de una tarea, pero ha de tenerse en cuenta que la realización de la tarea \(t_j\) por el agente \(a_i\) conlleva el uso de una serie de recursos (\(r_{ij}\)) del agente, y éstos están acotados por una cantidad fija, \(b_i\), para cada agente.
Tenemos una lista que representa los pesos de una población (todos los pesos están entre 0 y 100). Queremos encontrar 3 números (0 < a1 < a2 < a3 < 100) que sirvan para dividir el conjunto anterior en 4 secciones: [0,a1), [a1,a2), [a2,a3),[a3,100), de forma que las sumas de los pesos que hay en cada sección sean lo más parecidas posibles. ¿Qué cambios harías para encontrar una división similar en \(K\) secciones?
Disponemos de un CD de 80 minutos de duración y queremos grabar el mayor tiempo posible de nuestra colección de 100 canciones. Queremos saber qué pistas debemos grabar. Las duraciones en minutos de las canciones se dan en una lista \((d_1,\dots,d_{100})\). Modifica la solución anterior para que, además, obtengamos un CD con el estilo más uniforme posible. El estilo de una canción viene dado por un código númerico de 0 a 9. Dos estilos son más parecidos si sus códigos son más cercanos. El estilo de las canciones de nuestra colección viene dado por una lista: \((e_1,\dots,e_{100})\).
Problema de Optimización de Tareas: Tenemos \(N\) tareas, \(\{T_1,\dots,T_N\}\), que se encargan de procesar datos. Podemos hacer uso de un procesador que NO tiene capacidad paralela.Cada tarea, \(T_i\), tarda un tiempo \(t_i\) en ejecutarse, y hasta que no termina una tarea, no puede lanzarse otra. Cada tarea solo se puede ejecutar 1 vez. Disponemos de un tiempo total, \(T\), para poder usar el procesador. Además, la ejecución de cada tarea, \(T_i\), consume \(D_i\) datos. Algunas tareas solo se pueden ejecutar si algunas otras se han ejecutado antes. Para saber cuáles, disponemos de una tabla que indica si una tarea necesita que otra tarea se haya ejecutado antes. Por ejemplo, la siguiente tabla indica que \(T_1\) necesita que \(T_2\) se haya ejecutado antes, \(T_2\) necesita que \(T_4\) se haya ejecutado antes, y \(T_3\) necesita que \(T_1\) se haya ejecutado antes:
\(T_1\) \(T_2\) \(T_3\) \(T_4\)
\(T_1\) \(0\) \(1\) \(0\) \(0\)
\(T_2\) \(0\) \(0\) \(0\) \(1\)
\(T_3\) \(1\) \(0\) \(0\) \(0\)
\(T_4\) \(0\) \(0\) \(0\) \(0\)
Objetivo: Obtén una secuencia de ejecuciones que consuma la máxima cantidad de datos en el tiempo total permitido.
Sudoku: Este problema se publicó en Nueva York en el año 1979 bajo el nombre de “Number Place” y se hizo popular en Japón con el nombre de sudoku (“Sudji wa dokushin ni kagiru”: “los números deben ser sencillos” o “los números deben aparecer una vez”). En el problema del sudoku (ver un ejemplo en la figura), hay que rellenar las casillas de un tablero de \(9 \times 9\) con números del \(1\) al \(9\), de forma que no se repita ningún número en la misma fila, columna, o subcuadro de 3 × 3 que componen el sudoku.
Problema de agrupamiento I: Agrupa \(N\) números en \(k\) grupos disjuntos minimizando la suma de las diferencias entre los grupos.
Problema de agrupamiento II: Dispón los \(N^2\) primeros números naturales en una matriz cuadrada \(N\times,N\) de tal manera que las sumas tanto por filas como por columnas coincidan.
Problema de emplazamiento de bloques rectangulares: Dado un conjunto de \(n\) bloques rectangulares de distintas anchuras y alturas, se trata de encontrar un emplazamiento (asignación de los centros de los bloques rectangulares a puntos de un espacio cartesiano bidimensional) de tal forma que no haya solapamientos entre los bloques rectangulares, y se minimice la función de coste \(f = A + \lambda C\), donde \(A\) es el área del rectángulo que engloba todos los bloques rectangulares, \(\lambda\) es una constante positiva y \(C\) un término de conectividad, \(C =\sum_{i=1}^{n-1}\sum_{j=i+1}^n w_{ij} d_{ij}\), siendo \(d_{ij}\) la distancia entre los centros de los bloques rectangulares y \(w_{ij}\) el coste relacionado al unir el bloque rectangular \(i\)-ésimo con el bloque rectangular \(j\)-ésimo.
Particionamientos de un grafo. Problema ”max-cut”. Problema ”min-cut”. Dado un grafo \(G = (V,E)\) sin ciclos, donde cada arista lleva asociado un peso entero positivo, se trata de encontrar una partición de \(V\) en dos conjuntos disjuntos, \(V_0\) y \(V_1\) de tal manera que la suma de los pesos de las aristas que tienen un extremo en \(V_0\) y el otro extremo en \(V_1\), sea máximo (problema max-cut) o mínimo (problema min-cut).
Problema del conjunto de vértices independientes. Dado un grafo \(G = (V,E)\), se trata de encontrar el denominado conjunto maximal de vértices independientes, es decir el conjunto \(VIM \subseteq V\) de mayor cardinalidad para el cual ninguna de sus aristas se encuentre en \(E\).
Problema del Salto del Caballo. Teniendo un tablero de \(N\times N\) casillas y un caballo de ajedrez colocado en una posición inicial cualquiera, consegir que el caballo pase por todas las casillas del tablero una, y sola una vez.
Problema del Dominó I. Las fichas del dominó se pueden representar por pares de números enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.
Problema del Dominó II. Toma el tablero de ajedrez y tapa con dos monedas los dos cuadros de dos esquinas opuestas. Ahora trata de cubrir todos los demás cuadros con 31 fichas de dominó, cada ficha ocupando dos cuadros contiguos del tablero. Intenta el mismo problema con distintos tamaños de tablero.
El Problema de los matrimonios estables: Una agencia matrimonial ofrece a sus clientes parejas estables. Para conseguirlo, cada cliente debe establecer sus preferencias respecto al resto por medio de una lista con sus favoritos por orden de preferencia, incluyendo todos aquellos en los que puede estar interesado y dejando fuera aquellos que no le interesan en absoluto. A partir de estas listas se deben confeccionar parejas estables. Se entiende por estable el que nadie tenga la tentación de divorciarse porque puede encontrar una 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 prefiere A por delante de C, entonces los emparejamientos anteriores no son estables.
¿De quién es esta cebra? Son cinco casas adosadas, de diferentes colores, habitadas por cinco hombres de diferentes nacionalidades. Cada uno posee un animal diferente, bebe una bebida diferente y fuman una marca de tabaco distinta. Sabiendo la siguiente información, ¿podrías decir quién bebe agua?, ¿de quién es la cebra?
La casa de al lado del noruego es azul.
El de la tercera casa bebe leche.
El de la casa verde bebe café.
El de la casa amarilla fuma Ducados.
La casa blanca está después de la verde.
El japonés fuma Habanos.
El que fuma Fortuna tiene un gato.
El que fuma Celtas bebe vino.
El vecino del que fuma Chester tiene un canario.
El vecino del que fuma Ducados tiene un caballo.
Comprando zapatos: Enriqueta, al volver del centro comercial, describe felizmente a su amiga Aurora los cuatro pares de zapatos que se ha comprado. A Aurora le encantan todos (las alpargatas de color crudo, los planos fucsia, las bambas moradas y unas sandalias de cuero preciosas), pero Enriqueta no puede recordar en qué tienda compró cada uno ("La granja del pie", "Tacones a Mogollón", "El palacio del zapato" o "Muchachas"). ¿Puedes echarles una mano y establecer el orden en el que Enriqueta compró cada par de zapatos, y dónde compró cada uno? Dispones de la siguiente información:
Enriqueta sabe que los planos fucsia los compró en "Tacones a Mogollón".
La tienda que visitó inmediatamente después de comprar sus bambas moradas no era "Muchahas".
En "La granja del pie" fue su segunda compra.
Dos paradas después de dejar el "Palacio del zapato", Enriqueta compró sus sandalias de cuero.
La orquesta de Boulika: Esta orquesta comprende 180 ejecutantes, ¿cuántos no tocan ninguno de estos instrumentos?
6 no tocan más que el violoncello.
24 tocan violocello y violín, pero no viola.
12 tocan violoncello y viola, pero no violín.
6 tocan violín y viola, pero no violoncello.
63 músicos tocan el violín, 54 el violoncelo y 36 la viola.
La perspicacia del inspector Lafrite: Lafrite está encargado de la investigación sobre un robo de cuadros en una galería de arte. Pidió a Relbou y Gremai, dos de sus asistentes, que le ayudaran en el asunto. Laminvestigación terminó con el arresto de cuatro personas: Jules Rateau, Desiré Lafrange, Michel Boileau y Felicie Ossy. Los interrogatorios los realizan los dos asistentes que vienen a dar su informe, a raíz del cual Lafrite dice: "Si considero que lo que me dicen es cierto, puedo afirmar la culpabilidad de una de las cuatro personas". ¿Puedes ayudar a los inspectores a encontrar a esa persona?. El informe es:
Relbou: "Jules Rateau es inocente, pero estoy seguro de que por lo menos uno de los otros es culpable".
Gremai: "Si Desiré Lafrange es culpable, no hay más que un cómplice, que está entre los demás".
Relbou: "Y si Michel Boileau es culpable, pienso que tiene dos cómplices entre los otros".
Basándose en el método de resolución general con BFS que se ha proporcionado, construue uno equivalente pero que haga uso de DFS (con límite de profundidad).
Adapta el algoritmo DFS de resolución general para que trabaje con agentes en vez de con listas, y aplícalo sobre algunos de los ejemplos.
Implementa el algoritmo de Profundidad iterada en NetLogo.
Escribe modelos de NetLogo que sean capaces de aplicar adecuadamente los algoritmos de búsqueda local vistos en el tema.
Aplica los métodos de resolución de este apartado para resolver algunos de los problemas de la Colección Genérica de Problemas.
Búsquedas con Adversarios
Implementa una estrategia ganadora completa en el juego del Nim en su versión más simple: se juega entre 2 jugadores, se tienen 9 cerillas, alternadamente cada jugador puede retirar 1, 2 o 3 cerillas, pierde el que retire la última cerilla.
Implementa una estrategia ganadora para el juego del Nim en su versión de montones: se juega entre 2 jugadores, se tienen \(N\) montones con cerillas, cada jugador alternadamente puede quitar todas las cerillas que quiera, pero solo de un montón, gana el jugador que se lleve la última cerilla.
Implementa un jugador del 3 en raya que haga uso de Minimax. Hazlo usando heurísticas sobre una profundidad máxima prefijada, y diseñando variantes que hagan uso de podas.
Implementa un jugador de conecta4 haciendo uso de Minimax con heurísticas y poda.
Dos jugadores, \(J_1\) y \(J_2\), se plantean competir sobre un circuito de ciudades con las siguientes reglas: (a) El recorrido del circuito se hace por tramos, partiendo de la ciudad marcada como Salida. (b) Los jugadores alternativamente eligen el tramo a recorrer entre aquellos que parten de la ciudad en la que se encuentran. Una vez elegido el tramo, ambos conductores lo recorren y se apunta los kilómetros del tramo el conductor que lo eligió. Es decir, si \(J_1\) empieza el recorrido y decide ir a B, se apuntará 30 kilómetros. A continuación el contrario debe elegir, partiendo de B, entre ir a C o a D, y se apuntará los kilómetros que separen ambas ciudades. (c) Un conductor no puede ir a una ciudad por la que ya haya pasado, por lo que la competición acaba cuando el jugador al que le toca moverse no puede hacerlo. (d) Gana el jugador que haya acumulado más kilómetros con los tramos recorridos. Se pide:
Recuerda que podéis usar la página Gateway to Logic para calcular formas normales conjuntivas (forma clausal) de las fórmulas que vayáis usando.
1.- Implementa el método DPLL en NetLogo utilizando una estructura de datos adecuada para almacenar las cláusulas y los conjuntos de claúsulas. El sistema trabajará suponiendo que ha recibido el conjunto de fórmulas ya en forma clausal.
2.- Implementa el método de Resolución en NetLogo utilizando una estructura de datos adecuada para almacenar las cláusulas y los conjuntos de claúsulas. El sistema trabajará suponiendo que ha recibido el conjunto de fórmulas ya en forma clausal.
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 \vee \neg q, \ p \vee q, \ \neg p \vee \neg q, \ \neg p \vee q\}\)
\(\{ \neg r, \ q, \ p \vee \neg q, \ \neg p \vee r \}\)
\(\{ p \vee q \vee r, \ \neg p \vee q,\ \neg q \vee r, \ \neg r, \ p \vee r \}\)
\(\{p, \ \neg p \vee q, \ r \}\)
7.- Demuestra, utilizando resolución o DPLL, la inconsistencia del conjunto de cláusulas
\(\{ \neg p \vee \neg q \vee r, \ \neg s \vee t, \ \neg t \vee p, \ s, \ \neg s \vee u, \ \neg u \vee q, \ \neg r \}\)
8.- Determina la inconsistencia del conjunto mediante resolución o DPLL:
\(\{ p \vee q, \ q \vee r, \ r \vee w, \ \neg r \vee \neg p, \ \neg w \vee \neg q, \ \neg q \vee \neg r \}\)
9.- Determina la inconsistencia del conjunto por resolución o DPLL:
\(\{ \neg A \vee \neg B \vee C, \ \neg A \vee \neg G \vee H, \ \neg A \vee \neg H \vee F, \ \neg G \vee B, \ G, \ A, \ \neg F \}\)
10.- Decide por el método de resolución o DPLL la verdad o falsedad de las siguientes afirmaciones:
\(\{p\rightarrow (q\rightarrow r), \ r\rightarrow q\}\models r\leftrightarrow q \)
\(\{p\rightarrow q,\ q\rightarrow (p\wedge q), p\rightarrow r\} \models q\rightarrow r\)
11.- Las guerras clon han comenzado. Durante el transcurso de una refriega, tres caballeros Jedi, Anakin, Obi Wan y Yoda, se encuentran con el conde Dooku. Utilizaremos el lenguaje proposicional A, O, Y para denotar que el correspondiente caballero participa en el combate, y G para denotar "los Jedi han ganado".
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 \(HJ(x, y)\) expresa “\(x\) es hijo/a de \(y\)”; \(HR(x, y)\): “\(x\) es hermano/a de \(y\); \(SB(x, y)\): “\(x\) es sobrino/a de \(y\)”; \(T(x, y)\): “\(x\) es tío/a de \(y\)”; \(PD(x, y)\): “\(x\) es padre de \(y\)”; \(MD(x, y)\): “\(x\) es madre de \(y\)”; y que tenemos las constantes Ana y Pedro.
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 entre \(x\) e \(y\) (o \(x\) si tienen la misma edad). \(H(x)\): “\(x\) es un hombre”; \(M(x)\): “\(x\) es una mujer”; \(PRG(x, y)\): “\(x\) es un progenitor de \(y\)”; \(HRO(x, y)\): “\(x\) es hermano de \(y\)”; \(HRA(x, y)\): “\(x\) es hermana de \(y\)”; \(CAS(x, y)\): “\(x\) está casado/a con \(y\)”; y que tenemos las constantes pepe, pepa y pepi.
4.- Introduciendo la notación apropiada, escribe las sentencias de los siguientes razonamientos como fórmulas de primer orden y decide si la conclusión es consecuencia lógica de las premisas, utilizando para ello formas clausales.
Todos los científicos están locos. No existen vegetarianos locos. Por tanto, no existen científicos vegetarianos.
Todos los hombres son animales. Algunos animales son carnívoros. Por tanto, algún hombre es carnívoro.
Todo barbero de esta ciudad afeita exactamente a los hombres que no se afeitan a si mismos. Por tanto, no 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 cualquier \(x\). Por 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) \vee P(a),\ \neg Q(w) \vee P(w),\ \neg Q(x) \vee \neg P(x)\}\)
\(\{Q(u) \vee P(a),\ \neg Q(w) \vee P(w),\ \neg Q(x) \vee \neg P(x),\ Q(y) \vee \neg P(y)\}\)
\(\{I(a),\ \neg R(x) \vee L(x),\ \neg D(y) \vee \neg L(y),\ D(a)\}\)
\(\{I(a),\ \neg R(x) \vee L(x),\ \neg D(y) \vee \neg L(y),\ D(a),\ \neg I(z) \vee R(z)\}\)
\(\{\neg P(x, y) \vee \neg P(y, z) \vee 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)),\neg M(x, y, z) \vee D(x, z),\neg P(x) \vee \neg M(y, z, u) \vee \neg D(x, u) \vee D(x, y),\neg D(a, b)\}\)
Modela este problema como un PSR: Cinco casas consecutivas tienen colores diferentes y son habitadas por hombres de diferentes nacionalidades. Cada uno tiene un animal diferente, una bebida preferida y fuma una 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 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 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
Representa mediante un PSR la siguiente información: “Juana, Pepa y Paloma nacieron y viven en ciudades diferentes (Málaga, Madrid y Valencia). Además, ninguna vive en la ciudad donde nació. Juana es más alta que la que vive en Madrid. Paloma es cuñada de la que vive en Valencia. La que vive en Madrid y la que nació en Málaga tienen nombres que comienzan por distinta letra. La que nació en Málaga y la que vive ahora en 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.
Realiza el tutorial completo que acompaña a la extensión anterior.
Control de alunizaje: Considera un caso similar al anterior pero en el que controlamos una nave que intenta tomar tierra en caida libre, teniendo motores que pueden compensar la aceleración de caida del planeta.
Control de la dirección de un vehículo: Disponemos de un circuito donde colocamos un vehículo que va a velocidad constante y que dispone de 2 sensores laterales que le indican la distancia a los bordes del circuito. Define un sistema difuso que pueda controlar el giro a izquierda y derecha del vehículo para que recorra el circuito sin salirse (y en el menor tiempo posible).
Búsqueda de localizaciones: Disponemos de un mapa en el que cada patch puede estar a una altura determinada y tener un uso (bosque, agua, urbanizable, urbanizado). Además, calculamos la inclinación de cada patch como el máximo de las inclinaciones (diferencia de alturas) que tiene con sus patches vecinos. Queremos encontrar un lugar donde construir nuestra nueva casa, así que define las variables difusas y las reglas necesarias para encontrar un lugar que:
¿Puedes encontrar en el modelo de Flocking algún valor crítico del número de individuos necesario para que se produzca un cambio en el comportamiento global?
Algunos individuos que actúen como cazadores, que persigan individuos de la manada, y de los que huyan estos últimos en caso de percibirlos suficientemente cerca.
Elementos estáticos distribuidos por el mundo (que se vayan regenerando) y que determinen algún peso de influencia en los movimientos de los individuos de la manada con el fin de pasar sobre ellos para comerlos.
Obstáculos que los individuos de la manada no puedan atravesar y tengan que girar para evitarlos.
Haciendo uso del modelo "Preferential Attachment" que viene en la biblioteca de ejemplos de NetLogo, construye un modelo que muestre en tiempo real la evolución de la distribución de grados del grafo que forma. A continuación, crea un procedimiento en el que se añadan aristas aleatoriamente entre nodos del grafo y mida cómo evoluciona la distribución de grados.
Haz un modelo en NetLogo que permita construir redes aleatorias a partir de: (a) Número de nodos y número de aristas. (b) Número de nodos y densidad de la red. ¿Puedes encontrar alguna relación entre ambos?
Define un procedimiento para poder calcular en NetLogo el diámetro de un grafo.
Define un procedimiento que, dado un grafo en NetLogo, haga lo siguiente: (a) Reciba como dato de entrada un nodo, que llamaremos \(A\), y un número, \(n\). (b) Aproxime la probabilidad de que un camino cualquiera de longitud \(n\) comenzando por otro nodo del grafo, pase por \(A\).
Escribe un procedimiento en NetLogo que, dado un grafo, se comporte de la siguiente forma:( a) Reciba como dato de entrada un nodo del grafo, que notaremos por \(A\). (b) Para cualquier otro nodo del grafo, aproxime la probabilidad de que un camino comenzando por \(A\) pase por él. Debe aproximar el cálculo del resto de nodos simultáneamente.
Idea una forma de modelar un autómata celular que tenga su soporte sobre un grafo. Piensa cómo podrías solventar el problema de que en un grafo, a pesar de que cada nodo tiene vecinos, igual que ocurre en una malla rectangular, no hay orientación predefinida en ellos para poder definir la función de transición de una forma sencilla.
Usa un autómata celular para simular el comportamiento de un crecimiento por difusión, como haría, por ejemplo, el crecimiento de un cristal. Usa si es necesario más de dos estados.
Haciendo uso del ejemplo que viene en la biblioteca de NetLogo de patches hexagonales, define autómatas celulares 2D que funcionen sobre este tipo de malla.
Construye un modelo que sea capaz de ejecutar autómatas celulares 3D haciendo uso de NetLogo3D.
Haciendo uso del modelo que trae NetLogo para experimentar sobre autómatas celulares 1D, intenta hacer un análisis manual para clasificar los 256 autómatas 1-dimensionales en las diversas clases de complejidad que se han visto en clase.
El problema de la Mayoría se define como sigue: Dada una configuración de un autómata celular de \(2\) estados con \(i+j\) celdas en total, de las cuales \(i\) están con estado \(0\), y \(j\) con estado \(1\), una solución correcta del problema debe establecer todas las celdas a \(0\), si \(i > j\), y a \(1\), si \(i < j\). En caso de que \(i = j\) puede dar cualquier de los dos resultados.
¿Cuántas posibles configuraciones iniciales hay con \(i + j\) estados verificando las condiciones expuestas anteriormente?
Intenta encontrar un autómata celular que resuelva el problema. Expón los experimentos que hagas, aunque no encuentres la solución.
Define procedimientos por recursión para generar algunos de los fractales clásicos que se han visto en la teoría.
Genera los procedimientos necesarios para poder definir fractales por medio de sistemas L (mira los documentos que hay en el tema acerca de este tipo de sistemas).
Define un modelo que aproxime fractales haciendo uso del método IFS.
Define un procedimiento que aproxime la dimensión fractal de una figura usando el método del conteo de cajas.
Haz uso de NetLogo3D para realizar fractales similares a los vistos en clase pero que hagan uso de 3 dimensiones.
Haz un modelo que sea capaz de representar el conjunto de Mandelbrot (o conjuntos de Julia). Añade funcionalidades para poder navegar por ellos de una forma cómoda.
Busca representaciones que te permitan obtener resultados similares a este que se muestra aquí.
Modifica el modelo de los tiburones y los peces para: (a) Incluir sexualidad en la población, (b) Evolución y reproducción en los tiburones. Recuerda poner alguna limitación en las características de las especies.
Implementa una solución al Problema del Viajante haciendo uso de Colonias de Hormigas pero en casos en los que el grafo subyacente a las ciudades no sea el grafo completo (es decir, no estén todas las posibles conexiones entre ciudades).
Busca posibles mejoras sobre el algoritmo de hormigas para resolver el problema de viajante.
Haz uso de algoritmos de hormigas para calcular caminos mínimos en grafos. Introduce variantes que no se basen en la distancia de la arista, sino en pesos que puedan tener.
Implementa el algoritmo de hormigas elitista, en el que de forma adicional se incrementa la feromona de la mejor solución encontrada hasta el momento.
Implementa el algoritmo de hormigas con ranking, en el que únicamente se añade feromona a las \(k\) mejores soluciones de cada vuelta, junto con la mejor solución encontrada hasta el momento.
Optimización por Enjambres de Partículas
El algoritmo PSO visto en clase usa una discretización de la función que se está optimizando por medio de los patches. Haz los cambios necesarios para que se pueda usar con funciones no discretizadas sin considerar los patches (esto es, si tenemos una función \(f(x,y)\), cada partícula no mira el valor que hay en el patch que tiene debajo, sino que directamente evalúa el valor de \(f\) en su posición).
Implementa un PSO en el que haya familias de partículas, de forma que no se guían por el mejor global obtenido del total, sino únicamente de la familia a la que pertenecen, y quizás haya partículas que puedan pertenecer a más de una familia.
Implementa un PSO en el que la comunicación entre partículas venga determinada por la posición que ocupan, es decir, que cada partícula solo puede saber los valores alcanzados por partículas que están dentro de un determinado radio.
Haz una implementación de PSO en el que la vecindad de cada partícula (es decir, el conjunto de partículas de las que puede obtener información) viene dado por un grafo prefijado a priori. Haz pruebas de cómo funciona el algoritmo para distintos tipos de grafos con el mismo número de nodos (por ejemplo, con grafos aleatorios en los que el número de aristas varía, o para grafos generados siguiendo el algoritmo de enlace preferencial).
Al igual que hemos optimizado el problema del tráfico 1D por medio de PSO, haz uso de otros modelos de NetLogo que puedas optimizar haciendo uso del mismo algoritmo.
Utiliza PSO para optimizar los parámetros de los que depende el algoritmo de Colonias de Hormigas para un caso concreto (por ejemplo, una instancia concreta del problema del viajante).
Puedes encontrar una gran colección de conjuntos de datos en la página UCI Machine Learning Repository, donde además de los datos puedes encontrar una explicación del contenido y problema que presentan.
Implementa el algoritmo de las K-medias sin tener en cuenta la librería. Aplica el algoritmo que has implementado sobre datos reales para ver los resultados que salen.
Busca un conjunto de datos bidimensionales en el que puedas aplicar el algoritmo de K-medias visto en clase. Aprovechando la librería dada en el repositorio, haz lo mismo con conjuntos de datos de dimensiones superiores y piensa alguna forma de representar las agrupaciones que se obtienen.
Utiliza el método de las K-medias para rebajar el número de colores que se usa en una imagen. Para ello:
Carga una imagen en los patches haciendo uso de la función de importación adecuada.
Aplica el algoritmo de K-medias al conjunto de colores, determinando a priori el número de colores finales que quieres usar (puedes hacer que sea una decisión del usuario por medio del interfaz).
Muestra la imagen resultante con los colores reasignados según el cluster al que pertenecen.
¿Se te ocurre alguna forma de restringir la paleta de colores original (no solo el número de colores)?
Añade al algoritmo de las K-medias alguna forma de medir la eficiencia según el número de clusters que se usa para poder decidir cuál es la agrupación más óptima con respecto a alguna medida que te inventes. Haciendo uso de esta medida, genera un programa que permita extraer una clusterización de los datos sin necesidad de explicitar el número de clusters que se buscan.
Implementa el algoritmo de los K vecinos más cercanos (KNN) visto en clase desde cero para dimensiones superiores. Busca un conjunto de datos que necesite más de 2 dimensiones en el que puedas aplicar el algoritmo KNN que has diseñado.
Implementa una modificación del algoritmo KNN en el que se pondere la importancia de los vecinos más cercanos en función de la distancia a la que se encuentren. Comienza haciéndolo para 2 dimensiones y amplíalo posteriormente para dimensiones mayores que 2.
Haz un estudio de cómo afecta el valor de \(K\) en el algoritmo KNN sobre conjuntos de datos concretos y en casos de multiclasificación, no solo binaria. No olvides reservar algunos datos para el test posterior, y representa la matriz de confusión asociada a los datos.
KNN Condensado: En el algoritmo KNN hay el problema de que requiere de mucha memoria y tiempo de ejecución porque hay que almacenar continuamente todos los datos que definen el espacio de ejemplos inicial. Sin embargo, es muy probable que muchas de las muestras iniciales no sean necesarias para clasificar las demás, ya que su información es redundante con las otras existentes. Para reducir este problema existe un preprocesamiento de los datos que se llama condensación, y que consiste en lo siquiente (observa que depende del orden dado a los datos y, además, tiene el problema de conservar los datos que introducen ruido al sistema): Dado un orden en los datos de entrada, para cada ejemplo se clasifica por medio de KNN haciendo uso únicamente de los datos anteriores; si la clasificación obtenida coincide con la real, ese ejemplo se elimina de los datos, si no, permanece.
Añade un procedimiento condensa a la librería vista en clase para producir este preprocesamiento de limpieza inicial y así reducir la carga computacional del algoritmo.
Regla de Reducción para KNN: es similar a la anterior, pero se comienza con el conjunto completo de datos, y se eliminan aquellos que no afectan a la clasificación del resto de datos de entrada (en contra de la condensación anterior, es capaz de eliminar las muestras que producen ruido, y guarda aquellas que son críticas para la clasificación.
Considera el siguiente conjunto de entrenamiento
Ej Atr1. Atr2. Atr3. Clasif
$E_1$ $1$ $1$ $0$ SI
$E_2$ $1$ $0$ $0$ SI
$E_3$ $1$ $0$ $1$ SI
$E_4$ $0$ $0$ $1$ NO
Aplica el algoritmo KNN con $k = 1$ para clasificar $P = (0'75, 0, 0)$ a partir del conjunto de entrenamiento anterior usando la distancia de Manhattan.
Considera el conjunto de entrenamiento anterior sin la columna de clasificación y tomando $m_1 = (1, 1, −1)$ y $m_2 = (0, −1, 1)$, aplica el algoritmo de k-medias para $k=2$ con $m_1$ y $m_2$ como centros iniciales hasta la primera modificación de los centros.
Considera los puntos $P_1 = (0, 48)$, $P_2 = (0, 78)$, $P_3 = (36, 126)$, $P_4 = (36, 0)$ y los centros $m_1 = (20, 63)$ y $m_2 = (36, 63)$. Se pide aplicar el algoritmo de k-medias usnado la distancia euclídea sobre los puntos $P_1, \dots, P_4$ tomando $m_1$ y $m_2$ como centros iniciales ($k = 2$) hasta la primera modificación de los centros.
Árboles de Decisión: ID3
Modifica el modelo ID3 para que trabaje con atributos continuos haciendo uso del algoritmo de las K-medias para decidir las agrupaciones que usará en los atributos continuos (es decir, primero se aplica el algoritmo de las K-medias al atributo, y se decide las agrupaciones que se considerarán para discretizarlo).
El algoritmo ID3 visto en clase solo construye el árbol. Amplía el modelo para que, posteriormente, se pueda usar como verdadera máquina de clasificación, de forma que reciba un dato de entrada y devuelva la clasificación obtenida.
Unos biólogos que exploraban la selva del Amazonas han descubierto una nueva especie de insectos, que bautizaron con el nombre de lepistos. Desgraciadamente, han desaparecido y la única información disponible de este insecto viene dada por el siguiente conjunto de ejemplos encontrados en un cuaderno de notas, en los que se clasifican una serie de muestras de individuos en función de ciertos parámetros como su color, el tener alas, su tamaño y su velocidad. Haciendo uso de la tabla, contesta a las siguiente cuestiones:
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
¿Cuál es la entropía del conjunto de ejemplos respecto a la clasificación de los mismos que realiza el atributo Lepisto?
¿Qué atributo proporciona mayor ganancia de información?
Aplicar (detallando cada uno de los pasos realizados) el algoritmo ID3 para encontrar, a partir de este conjunto de entrenamiento, un árbol que nos permita decidir si un determinado individuo es un lepisto o no.
Obtener un conjunto de reglas a partir del árbol obtenido en el apartado anterior.
Según las reglas obtenidas, ¿hay algún atributo que sea irrelevante para decidir si un individuo es un lepisto?
Una entidad bancaria concede un préstamo a un cliente en función de una serie de parámetros: su edad (puede ser joven, mediano o mayor), sus ingresos (altos, medios o bajos), un informe sobre su actividad financiera (que puede ser positivo o negativo) y, finalmente, si tiene otro préstamo a su cargo o no. La siguiente tabla presenta una serie de ejemplos en los que se especifica la concesión o no del préstamo en función de estos parámetros:
E1 joven altos negativo no no
E2 joven altos negativo si no
E3 mediano altos negativo no si
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” atributo que clasifica un conjunto de ejemplos es el de menor ganancia de información. En esta situación se pide:
En caso de ausencia de ruido, ¿obtendría el algoritmo modificado un árbol de decisión consistente con los ejemplos del conjunto de entrenamiento?, justifica la respuesta.
¿Qué sesgo tendría el algoritmo modificado?, justifica la respuesta.
Aplica (detallando cada uno de los pasos realizados) el algoritmo modificado para encontrar, a partir de este conjunto de entrenamiento, un árbol que nos permita decidir sobre la concesión de préstamos.
Aplica el algoritmo ID3 para construir un árbol de decisión consistente con los siguientes ejemplos, que nos ayude a decidir si comprar o no un CD nuevo. Considerar los siguientes ejemplos como conjunto de prueba y obtener la medida de rendimiento del árbol obtenido.
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
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
E15 Queen Sony rock 40 Virgin no
E16 Mozart Sony clásico 40 Mixup si
La siguiente tabla muestra ejemplos de plantas, indicando si sobrevivieron más de un año o no después de ser compradas, en función de su tamaño (grande, medio o pequeño), de su ambiente adecuado (interior o 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 encontrar un árbol de decisión consistente con el conjunto de entrenamiento \(\{E_1, \dots , E_{16}\}\) que permita decidir si una planta sobrevivirá más de un año o no después de ser comprada. Suponer que se elige para el nodo raíz el atributo tamaño , y continuar la ejecución del algoritmo a partir de ahí.
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:
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
Una empresa de material deportivo quiere hacer un estudio de mercado para encontrar las características principales de sus potenciales clientes. En una primera fase, las características a estudiar son las siguientes: la edad (joven o adulto), ser deportista profesional, el nivel de ingresos (altos, medios o bajos) y el sexo. Para ello, se realiza un cuestionario a 21 personas, obteniendo los resultados que se reflejan en la siguiente tabla:
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
Aplica el algoritmo ID3 para obtener un árbol de decisión que sirva para decidir si un cliente potencial está interesado o no en el producto que ofrece la empresa. Tomar como conjunto de entrenamiento los primeros 15 ejemplos de la tabla.
Tomando ahora como conjunto de prueba los ejemplos del 16 al 21 de la tabla, calcula el rendimiento del árbol de decisión obtenido en el apartado anterior. Usando ese conjunto de prueba, aplica un proceso de podado a posteriori sobre el árbol de decisión. Expresa mediante reglas el árbol obtenido tras la poda ¿Qué rendimiento tiene este árbol sobre el conjunto de prueba? ¿Y sobre el conjunto de entrenamiento?
Se han encontrado una gran cantidad de obras de arte realizadas por dos artistas A y B, pero sólo para un pequeño número de obras se ha podido asegurar cuál de los dos es el autor. La siguiente tabla muestra los datos de dichas obras, indicando el autor en función del tipo de obra (grabado, óleo o acuarela), del lugar donde se encontró la obra (España, Portugal o Francia), de su estilo (clásico o moderno), y de si tienen marco o no.
E1 grabado España clásico no B
E2 grabado España moderno no B
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
Aplica el algoritmo ID3 para encontrar un árbol de decisión consistente con el conjunto de entrenamiento \(\{E_1,\dots , E_{16}\}\) que permita decidir si una obra de arte fue realizada por A o por B.
Usa la siguiente tabla de ejemplos como conjunto de prueba para calcular el rendimiento del árbol de decisión obtenido en el apartado anterior
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
Prepara algunos ejemplos de clasificación para ser aplicados con los modelos SOM clasificadores proporcionados en las librerías de la asignatura.
Haz modificaciones del modelo SOM para que haga el entrenamiento sobre otras estructuras topológicas.
Haz uso de SOM para reducir el número de colores de una imagen. ¿De qué forma podrías usar SOM para hacer segmentación de imágenes (reconocer conjuntos de pixels que correspondan a los mismos objetos)?
Haz uso de SOM para entrenar el movimiento de un robot que evite obstáculos en su recorrido hacia un objetivo. Para ello, debes modelar en NetLogo al robot por medio de una tortuga que tiene sensores de distancia delante, sensor de dirección y se mueve a velocidad constante.
Haz uso de SOM 3D para aproximar varias superficies y volúmenes por medio del entrenamiento sobre nubes de puntos. Utiliza las aproximaciones obtenidas para dar mallas que amplíen o reduzcan la resolución inicial de un modelo.
Usa el modelo SOM-TSP (que se ha construido usando la librería SOM proporcionada en el repositorio) para comprobar los efectos de los distintos parámetros disponibles en la aproximación al ciclo mínimo proporcionado por SOM. ¿Crees que es suficiente el uso de SOM para asegurar que el ciclo obtenido es de longitud mínima?, ¿echas en falta algo? Comprueba también el resultado de cambiar la estructura subyacente en los nodos de aprendizaje.
Usa SOM-hexaClassifier para extraer un aprendizaje no supervisado de algunos conjuntos de datos pequeños disponibles en UCI Machine Learning Repository.
Crea, y entrena, estructuras de redes neuronales simples que calculen algunas funciones lógicas habituales (AND, OR, NOT, XOR,NAND,... y combinaciones de ellas).
Haz uso de redes neuronales adecuadas para aproximar el cáculo de algunas funciones reales: \(f(x)=x^2,\ f(x)=sin(x),\ f(x,y)=x sin(y)\), ...
Crea conjuntos artificiales de puntos 2D con una clasificación asignada (no tiene porqué ser binaria) y haz uso de diversas redes neuronales para aprender la clasificación y compara los resultados según las características topológicas de las redes neuronales utilizadas. Observa también las características de la frontera de separación entre las áreas de clasificación y la capacidad de las redes para separar correctamente distintas estruturas (lineales, con agujeros, mezclas al azar, etc.).
¿De qué forma podría usarse una red neuronal para hacer la función del algoritmo KNN?, ¿y para trabajar como K-medias?
Haz uso del modelo de reconocimiento que se ha visto en clase para entrenar a una red neuronal a reconocer algunos patrones específicos. Para ello tendrás que ser capaz de generar adecuadamente bolsas de ejemplos.
Una nariz electrónica analiza mediante sensores los vapores procedentes de determinadas sustancias y las clasifica a partir de la información cuantitativa obtenida. Supongamos que utilizamos 16 sensores para identificar cuatro tipos de vino tinto: Cabernet, Merlot, Syraz y Tempranillo. Describe en detalle cómo podríamos usar una red neuronal para abordar este problema: en qué consistiría un conjunto de entrenamiento y cómo se codificarían los ejemplos, la estructura de la red, el algoritmo de entrenamiento usado, y de qué manera se usaría la red una vez entrenada para identificar un nuevo vino tinto.
Supongamos que una empresa de TV por cable quiere diseñar un sistema automatizado para recomendar a sus clientes uno de sus cinco canales temáticos en función de sus preferencias, que se tratan de adivinar en función de una encuesta con 20 preguntas. ¿Cómo diseñarías el sistema usando una red neuronal? ¿Qué estructura tendría esta red neuronal? ¿Cómo entrenarías la red y cuál sería tu conjunto de entrenamiento? Una vez entrenada, ¿cómo usarías la red obtenida para recomendar un canal temático a un nuevo cliente?
Supongamos que queremos diseñar un sistema de anuncios personalizados para los usuarios de un portal web. En este portal web hay veinte secciones temáticas y la compañía maneja cuatro posibles perfiles publicitarios, cada uno de ellos apropiado a un usuario en función de los temas que más le interesan. Describe cómo se usaria una red neuronal para implementar este sistema: estructura de la misma, conjunto de entrenamiento, aprendizaje de los pesos, uso de la red una vez entrenada...
Supongamos que queremos diseñar un sistema automatizado para reconocer el estado de ánimo de la gente observando la expresión de su cara. Por simplificar las cosas, supongamos que consideramos cuatro tipos distintos de estados de ánimo: alegre, triste, enfadado y neutro. Suponiendo que nuestro sistema dispone de una cámara que es capaz de obtener imágenes digitalizadas de la cara de una persona ¿cómo diseñarías el sistema usando una red neuronal? ¿en qué consistiría el aprendizaje de esa red?
Idea un escenario en el que puedas entrenar una red neuronal haciendo uso de algoritmos genéticos. Es decir, cada individuo almacenará una variante de una misma red (solo cambian los pesos) que resuelve un problema en el espacio en el que se encuentra. en cada iteración se ponen todos los individuos a prueba para resolver el problema y se le asigna un fitness en función de lo buena que haya sido su red neuronal para ese objetivo. Se aplica el AG y se hace evolucionar la población completa. Al final de muchas iteraciones se espera que la población tenga individuos con redes muy aptas para la resolución del problema original.
Crea, y entrena adecuadamente, una red neuronal que pueda distinguir entre dos símbolos escritos: X y O.
Crea un modelo que sea capaz de leer algún formato de red neuronal que inventes (recuerda que debe contener, al menos, información acerca del número de capas, número de neuronas por capa, función de activación que usarán las neuronas, y todos los pesos de la red), con el que puedas cargar redes neuronales pre-entrenadas en otros ejercicios y ejecutarlas como máquinas de cálculo.
Disponemos de un robot con un brazo con 2 grados de libertad que se mueve en 2D tal y como muestra la figura. Ajustando los ángulos, \(\theta_1\), \(\theta_2\), el robot puede colocar su extremo en el punto \((x,y)\) del plano.
\[x=l_1 \cos \theta_1 + l_2 \cos (\theta_1+\theta_2)\]\[y=l_1 \sin \theta_1 + l_2 \sin (\theta_1+\theta_2)\]
Entrena una red neuronal multicapa con una capa oculta de 5 neuronas que sea capaz de aprender la cinemática inversa del robot, es decir, dadas las coordenadas del extremo, \((x, y)\), como entrada, la red debe devolver los correspondientes ángulos \((\theta_1,\theta_2)\) que le permiten alcanzar ese punto.
Si entrenas la red con 10 muestras de entrenamiento uniformemente distribuidos en el espacio,¿cuántas epochs se necesitan para que el entrenamiento de la red converja?, ¿cómo cambia este número cuando crece el tamaño del conjunto de entrenamiento? Haz pruebas experimentales.
Usa datos de validación para determinar cómo generaliza la red el aprendizaje. ¿Cómo afecta el tamaño de la capa oculta a la calidad de los resultados de la red? Haz pruebas experimentales para comprobar esta relación.
Imagina que tomamos un perceptrón simple y multiplicamos todos sus pesos (y bias) por una constante positiva, $c>0$. Demuestra que el comportamiento de la unidad no cambia. ¿Puedes decir lo mismo si en vez de trabajar con un perceptrón individual trabajamos con una red de perceptrones? ¿cómo afecta el uso de la función de activación a este hecho?
A partir de los distintos métodos vistos a lo largo del curso, piensa en métodos adicionales de entrenamiento de redes neuronales, destacando las ventajas e inconvenientes que podría tener cada uno de ellos.
Verifica que, en el caso de que $\sigma$ sea la función sigmoide, entonces $\sigma'(x)=\sigma(x)(1-\sigma(x))$.
1. Ejercicios de Lógica Proposicional (10363 vistas)
2. Ejercicios Lógica Difusa (8086 vistas)
3. Ejercicios de Lógica de Primer Orden (5613 vistas)
4. Ejercicios IA (5229 vistas)
5. Ejercicios de Algoritmos Genéticos (3664 vistas)
6. Ejercicios NetLogo I (2573 vistas)
7. Ejercicios Minimax (2489 vistas)
8. Ejercicios de Búsqueda no Informada (2171 vistas)
9. Ejercicios de Búsqueda Informada (1517 vistas)
10. Ejercicios NetLogo II (940 vistas)

References: resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución