« Examen Bloque II. Dic… « || Inicio || » Calificaciones Lógica… »

Ejercicios IA

Última modificación: 17 de Septiembre de 2021, y ha tenido 22321 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:
Inteligencia Colectiva:
Aprendizaje Automático:

NetLogo

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

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.

Posibles extensiones:

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.

2.- Propagación de mensajes entre individuos: En este modelo haremos uso únicamente de las tortugas. La idea es analizar cómo de rápido se difunde un mensaje entre una población móvil. Para simplificar, comenzaremos asignando un movimiento aleatorio a los agentes.

Prepara los agentes con alguna caracteristica que permita saber si tienen el mensaje o no (aquellos que no lo 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 mismo patch.
Proporciona un slider para determinar el número de agentes en el mundo.

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 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.
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 muerta (por "soledad" o "superpoblación").

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

Añade un slider %-rojo, para especificar el % de población que debe ser roja (el resto será verde). Hay dos posibles usos para esta variable:
- 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á esa, pero en cada ejecución puede haber pequeñas fluctuaciones.
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.
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 escenario.

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 procedimiento 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 (se debe considerar la 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, 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. Piensa en distintas formas de devolver ese camino: lista de nodos, lista de aristas, lista de nodos y aristas,...

13.- Repite los primeros ejercicios de esta sección poniendo como soporte un grafo en vez de patches (donde tenga sentido).

Colección Genérica de Problemas: Representación

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.
Cuando sea posible, realiza una implementación usando las librerías adecuadas de NetLogo.

Lista de Problemas

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 completamente cada una de las jarras, vacíar completamente 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 comerían a los misioneros. Además, la canoa siempre debe ser conducida por alguien (no puede cruzar el río sola).
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?
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$ (es decir, si están conectados por una arista del grafo), 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 vecinos están coloreados con colores distintos).
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 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.
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^2$, 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?
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 de $36$ y el producto de las cartas del segundo montón esté lo más cerca posible de $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. Se pueden pensar variantes con $n\times n$ huecos. por ejemplo, el 15-puzzle.
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. El más habitual es $N=3$.
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. El caso más común es el de $N=8$, el trablero de ajedrez estándar.
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:
Dados cuatro números naturales $n$, $m$, $r$ y $T$, encontrar una secuencia mínima de operaciones aritméticas básicas (suma, resta, multiplicación y división) que usando $n$ y $m$ únicamente y partiendo de $0$, obtenga como resultado $T$, con la restricción adicional de que ni $n$ ni $m$ se pueden usar más de $r$ veces. Por ejemplo, si $n = 2$, $m = 3$, $r = 3$ y $T = 28$, una posible solución (no necesariamente mínima) es $((((((0 + 3) × 3) × 2) − 3) × 2) − 2)$, ya que el resultado es $28$ y ni $2$ ni $3$ se han usado más de tres veces cada uno.
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úmero posible de ellas. Cada objeto tiene un peso asociado, $Peso(o_i)=p_i$, y las bolsas tienen un límite de peso máximo soportado, $B$.
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 $N$ ranas negras y $N$ verdes situadas encima de $2N+1$ nenúfares tal y como muestra la animación (en el caso particular de $N=3$). Comienza cada grupo de ranas en un extremo distinto de la fila de nenúfares. El objetivo consiste en intercambiar la posición de las ranas negras y verdes. 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 por encima de 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 ovejas. Cada oveja tiene un peso y se vende por un precio prefijado. El ganadero dispone de un camión que es capaz de cargar un peso máximo. Su problema es seleccionar una colección 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, cuya ejecución supone un coste ($c_{ij}$) que puede variar dependiendo del agente, $a_i$, y la tarea, $t_j$, asignada. Es necesario para desarrollar todas las tareas asignar un solo agente a cada tarea para que el coste total de la 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. Encuentra una asignación de tareas factible y de coste mínimo.
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 $N$ minutos de duración y queremos grabar el mayor tiempo posible de nuestra colección de $M$ canciones. Queremos saber qué pistas debemos grabar. Las duraciones en minutos de las canciones se dan en una lista $(d_1,\dots,d_{M})$. 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. 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_{M})$.
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 aparecer una vez”). En el problema del sudoku, 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. Es habitual que se den algunas casillas ya rellenas.
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: Reparte 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?
1. El noruego vive en la primera casa.
2. La casa de al lado del noruego es azul.
3. El de la tercera casa bebe leche.
4. El inglés vive en la casa roja.
5. El de la casa verde bebe café.
6. El de la casa amarilla fuma Ducados.
7. La casa blanca está después de la verde.
8. 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.
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:
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 "Muchahas".
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 cuero.
La orquesta de Boulika: Esta orquesta comprende 180 ejecutantes, ¿cuántos no tocan ninguno de estos 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.
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:
1. Relbou: "Jules Rateau es inocente, pero estoy seguro de que por lo menos uno de los otros es culpable".
2. Gremai: "Si Desiré Lafrange es culpable, no hay más que un cómplice, que está entre los demás".
3. Relbou: "Y si Michel Boileau es culpable, pienso que tiene dos cómplices entre los otros".
Puedes probar otros problemas de la colección: http://www.csplib.org/Problems/

Búsqueda/Planificación Clásicas

Basándose en el método de resolución general con BFS que se ha proporcionado, construye 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.
Pon ejemplos de búsquedas en las que al aplicar el algoritmo voraz no encontremos una solución óptima.
Escribe modelos de NetLogo que sean capaces de aplicar adecuadamente los algoritmos de búsqueda local vistos en el tema.
Realiza en NetLogo un modelo para resolver de la forma más general que se te ocurra (haciendo uso de agentes) problemas de búsqueda por medio del algoritmo voraz.
Aplica los métodos de resolución de este apartado para resolver algunos de los problemas de la Colección Genérica de Problemas.
Representa el algoritmo de Resolución Proposicional como un Problema de Búsqueda, y haz una implementación efectiva de él usando las librerías de búsqueda proporcionadas en el curso.

Búsquedas con Adversarios

Consideramos el siguiente juego: dos contrincantes, A y B, manejan cada uno una ficha en un tablero como muestra la figura adjunta. Los dos jugadores mueven por turno, empezando por A. Cada jugador pueden mover su ficha a un espacio vacío adyacente a la posición que ocupen (en cualquier dirección). Si el adversario ocupa un espacio adyacente, entonces un jugador puede saltar sobre el adversario al siguiente espacio vacío, si existe. Por ejemplo, si A está sobre 3 y B está sobre 2, entonces A puede mover su ficha para ocupar el espacio 1. El juego termina cuando un jugador alcanza el extremo opuesto del tablero. Si A alcanza el espacio 5 en primer lugar, el valor de utilidad para A será $+\infty$, si B alcanza el espacio 1 en primer lugar, el valor de utilidad de A será $-\infty$.
- 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 posición de la figura anterior (empezando con el nodo raíz con etiqueta max de nivel 0, las hojas de nivel 6 también tendrán etiqueta max) y donde el primer movimiento lo hace A. Especifica los valores calculados para cada nodo y determina la mejor jugada para A.
Considera el árbol en figura siguiente de un juego de dos personas, donde los círculos son nodos max y los cuadrados son nodos min. Aplica el algoritmo minimax con poda alfa-beta, propaga los valores de evaluación hasta el nodo raíz, marca la mejor jugada para max, y marca todos los subárboles que se podan.
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:
- 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). Genera los sucesores de un nodo en orden alfabético, es decir, el primer sucesor del nodo Salida sería A y el segundo B.
- Define una función de evaluación adecuada para los nodos hoja, y propaga sus valores a través del árbol. ¿Qué jugada haría $J_1$?
- ¿Qué partes del árbol no se expandirían si se aplicara la poda?
Implementa un jugador automático para 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 un jugador automático 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.
Colección de juegos de Tablero. Para los siguientes juegos: 3 en raya, conecta4, Go Moku, Othello/Reversi, Damas, 4 en Línea, Mancala, Ranitas, 4 en Línea múltiple, Asimilación, Gran Avance, Quarto, 6 en raya, 9 hombres de Morris, Havannah, Isolation
- Dar una representación formal del juego: estados y movimientos del juego, explicitando estados y movimientos válidos, y cómo los movimientos cambian los estados. Esta representación debe ser dada en NetLogo.
- Hacer una implementación visual del juego para dos jugadores humanos. Esta implementación debe contemplar la representación formal dada en 1, y las restricciones impuestas por las reglas del juego. Además, debería estar preparada para los pasos siguientes.
- Hacer una implementación de un jugador automático por medio de MCTS / Minimax.
- Conectar el jugador automático a la implementación anterior.
Aplica los métodos de resolución de este apartado para resolver algunos de los problemas de la Colección Genérica de Problemas.

Lógica Proposicional

Recuerda que puedes usar la página Gateway to Logic para calcular formas normales conjuntivas (forma clausal) 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 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.

3.- Implementa el método de Tablas de Verdad en NetLogo utilizando una estructura de datos adecuada para almacenar las fórmulas.

4.- Implementa los métodos de encadenamiento hacia adelante y encadenamiento hacia atrás en NetLogo 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 Tecnologías Informáticas de la Universidad de Sevilla.

2.- Determina, tras formalizar en un lenguaje proposicional, si los siguientes argumentos son lógicamente correctos:

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 temperatura permanece constante. En consecuencia, en caso de que llueva, la presión atmosférica no permanece constante.
Siempre que un número $x$ es divisible por $10$, acaba en $0$. El número $x$ no acaba en $0$. Luego, $x$ no es divisible 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 acaba en $0$. 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$ es negativo 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 considerablemente 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 empleado el fármaco A o se ha empleado el fármaco B. En consecuencia, podemos afirmar que si no hemos empleado el 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úsicos no podrían sobrevivir si los comerciantes no les contratasen para componer canciones para publicidad. Los comerciantes invierten en canciones publicitarias cuando tienen pérdidas. Por tanto, si llueve los músicos pueden sobrevivir.
Si el barco entra en el puerto, habrá una gran fiesta. El barco entra en el puerto sólo si necesita repostar combustible. El barco no necesita combustible a menos que venga de muy lejos. Es imposible que no necesite combustible si la comida ya se les ha terminado. Sabemos que, o bien se le ha terminado la comida, o bien necesita combustible. Por tanto: habrá una gran fiesta.
Si $f$ es diferenciable en $[a, b]$, es continua y acotada en $[a, b]$. Si $f$ no fuese acotada en $[a, b]$ no podrá ser 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. Llueve y tengo comida. Por lo tanto, no iré al restaurante.

3.- En un texto de Lewis Carroll, el tio Jorge y el tío Jaime discuten acerca de la barbería del pueblo, atendida por 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 estar para 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 afirma que sólo puede concluirse que Carlos y Alberto no pueden estar ausentes a la vez. ¿Cuál de los dos tiene razón?

4.- 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.

5.- 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 \}$

6.- 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 \}$

7.- 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 \}$

8.- 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 \}$

9.- 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$

10.- 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".

a. Formaliza las siguientes afirmaciones:

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

b. ¿Es cierto que $\{F_1, F_2, F_3\} \models G \rightarrow A \wedge O$? Razónese formalmente la respuesta.

11.- Describe el problema de las N reinas como un problema de satisfactibilidad proposicional.

12.- Describe el problema de Sudoku como un problema de satisfactibilidad proposicional.

13.- Describe el problema de coloreado de grafos como un problema de satisfactibilidad proposicional.

14.- En una isla habitan dos tribus de nativos, A y B. Todos los miembros de la tribu A siempre dicen la verdad, mientras que todos los de la tribu B siempre mienten. Llegamos a esta isla y le preguntamos a un nativo si allí hay oro, a lo que nos responde: “Hay oro en la isla si y sólo si yo siempre digo la verdad ”. ¿Hay oro en la isla? ¿Podemos determinar a qué tribu pertenece el nativo que nos respondió?

15.- Tres niños, Manolito, Juanito y Jesuli, son sorprendidos después de haberse roto el cristal de una ventana cerca de donde estaban jugando. Al preguntarles si alguno de ellos lo había roto, respondieron lo siguiente:

Manolito: “Juanito lo hizo, Jesuli es inocente”.
Juanito: “Si Manolito lo rompió, entonces Jesuli es inocente”.
Jesuli: “Yo no lo hice, pero uno de los otros dos sí lo rompió”.

¿Son consistentes las afirmaciones anteriores? Si se comprueba que ninguno de los niños rompió el cristal, ¿quiénes han mentido? Si se asume que todos dicen la verdad, ¿quién rompió el cristal?

16.- En un texto de Lewis Carroll, el tío Jorge y el tío Jaime discuten acerca de la barbería del pueblo, atendida por 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 estar para atender el establecimiento.
Si Alberto no está, tampoco estará Benito.

17.- Ash, Misty y Brock han organizado una batalla entre sus Pokemon. Se conocen los siguientes datos al respecto:

a) Uno, y sólo uno, de los siguientes Pokemon fue el vencedor: Pikachu, Bulbasaur, Togepi, Starmie, Vulpix y Onix.
b) Ash ganó la batalla si el Pokemon vencedor fue Pikachu o Bulbasaur.
c) Si o bien Togepi o bien Starmie fue el vencedor, Misty ganó la batalla.
d) Brock ganó la batalla si el vencedor fue Onix o Vulpix.
e) Si Onix fue derrotado, Starmie también.
f ) Bulbasaur fue derrotado.
g) Si Pikachu fue derrotado, entonces Ash no ganó la batalla.
h) Brock no ganó la batalla si Bulbasaur fue derrotado.
i) Si Vulpix fue derrotado, Togepi y Onix también corrieron la misma suerte.

Utiliza el algoritmo DPLL para probar que Ash fue el ganador.

18.- Tenemos 10 piezas de dominó distintas entre sí y cuyos lados están marcados con puntos del 0 al 3. Queremos colocar 6 piezas en fila de modo que (como es habitual en el juego del dominó) los lados de cualesquiera piezas adyacentes estén marcados con el mismo número de puntos. Para cada $i$ : $1 \leq i \leq 6$, y cada par $(j,k)$ de números $0 \leq j \leq 3$, $0 \leq k \leq 3$ consideramos una variable proposicional $P_{i,(j,k)}$ para expresar que la $i$-ésima ficha de la fila es la que tiene $j$ puntos en su lado izquierdo y $k$ puntos en su lado derecho. Por ejemplo, $P_{1,(2,3)}$ expresa que la primera ficha de la fila es la que tiene $2$ puntos en su lado izquierdo y $3$ en el derecho. Utilizando estas variables, proporciona un conjunto de fórmulas proposicionales, $S$, que describan las restricciones que deben cumplir las $6$ piezas dispuestas en fila. Obtén utilizando dicho conjunto de fórmulas proposicionales una disposición de $6$ piezas en fila.

19.- (El misterio del asesinato de la Mansión Dreadsbury) Alguien en la Mansión Dreadsbury ha matado a la tía Agatha. Los únicos habitantes de la mansión son Agatha, el mayordomo y Charles. Sabemos que un asesino siempre odia a su víctima y no es más rico que ella. Charles no odia a nadie a quien odie Agatha y Agatha odia a todo el mundo, salvo al mayordomo. Por su parte, el mayordomo odia a cualquiera que no sea más rico que Agatha. Además el mayordomo odia a todo aquel al que odia Agata, pero nadie odia a todo el mundo. ¿Quién mató a la tía Agatha?

20.- (El problema de los números de Langford) Tenemos dos conjuntos de 4 bolas cada uno, numeradas del 1 al 4. Se trata de colocar las 8 bolas formando una sucesión en la que las bolas con número 1 estén separadas por una bola, las que tienen número 2 por dos bolas, las que tiene número 3 por tres bolas, y las que tienen número 4 por cuatro bolas.

21.– (El cuadrante de las enfermeras) Se trata de organizar la asignación de las jornadas de trabajo semanales de 5 enfermeras de modo que se satisfagan las siguientes restricciones:

Cada enfermera debe tener un día de descanso cada cuatro días y no puede trabajar tres noches seguidas.
Debe haber un mínimo de 2 enfermeras en el turno de noche y 2 en el turno de día.

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 Tecnologías 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 $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)\}$

Lógica Difusa

Usando la extensión de NetLogo para trabajar con Lógica Difusa, crea modelos que generen modelos difusos para los siguientes problemas:

El problema de la propina: crea un modelo de lógica difusa para el siguiente sistema de reglas.
1. Si el servicio es pobre, la propina es baja.
2. Si el servicio es bueno, la propina es media.
3. Si el servicio es excelente, la propia es generosa.
4. Si la comida está rancia, la propina es baja.
5. Si la comida está deliciosa, la propina es generosa.
Realiza el tutorial completo que acompaña a la extensión anterior.
Control de velocidad de un automóvil: el sistema de control de un vehículo no tripulado viene caracterizado por 3 variables: velocidad (muy lenta, lenta, media, rápida, muy rápida), aceleración (decelerando, constante, acelerando) y distancia al objetivo (muy cerca, cerca, lejos). El sistema automático puede inyectar más o menos gasolina al vehículo para que se aproxime al destino de forma eficaz sin frenos. Teniendo en cuenta reglas del tipo "Si está lejos y a velocidad lenta, acelera", construye un modelo difuso que controle lo mejor posible el vehículo para que se aproxime lo más posible al punto de destino (que puede ser variable).
Control de alunizaje: Considera un caso similar al anterior pero en el que controlamos una nave que intenta tomar tierra en caída libre, teniendo motores que pueden compensar la aceleración de caída al 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. Para ello define las variables difusas y las reglas necesarias para encontrar un lugar que:
1. Sea urbanizable.
2. Esté cerca de agua y de bosque, pero no mucho de otras zonas urbanizadas.
3. Tenga una altura media.
4. No esté muy inclinado.

Satisfacción de Restricciones

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 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
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?
Seis amigos y sus respectivas esposas, se hospedan en el mismo hotel; y todos ellos salen todos los días, asistiendo a reuniones de distinto volumen y composición. Para asegurar la variedad en estas salidas, han acordado establecer las siguientes reglas: “Si Antonio está con su mujer, es decir en la misma reunión que su mujer, y David con la suya, y Luis con la señora de Pedro, Enrique debe estar con la señora de Ramón. Si Antonio está con su mujer y Pedro con la suya, y David con la señora de Enrique, Ramón no debe estar con la señora de Luis. Si Enrique y Ramón y sus mujeres están todos en la misma reunión, y Antonio no está con la señora de David, Luis no debe estar con la señora de Pedro. Si Antonio está con su mujer y Ramón con la suya, y David no está con la señora de Enrique, Luis debe estar con la señora de Pedro. Si Luis está con su mujer y Pedro con la suya y Enrique con la señora de Ramón, Antonio no debe estar con la señora de David. Si David y Enrique y sus mujeres están todos en la misma reunión, y Luis no está con la señora de Pedro, Ramón debe estar con la señora de Luis”. Modelar dicho problema como un PSR y obtener las posibles combinaciones de reuniones para cada amigo. ¿Es posible que todos los días haya al menos un matrimonio cuyos miembros no estén juntos en la misma reunión? (problema original de Lewis Carroll, en su obra Lógica Simbólica).
Cinco amigos, Bernardo, Casimir, Luis, Carlos y Marcial, se encuentran cada día en el restaurante. Tienen estas reglas, que observan cada vez que comen:“Bernardo toma sal si y solamente si Casimir toma solo sal o solo mostaza. Bernardo toma mostaza si y solamente si, o bien Luis no toma sal ni mostaza, o bien Marcial toma ambas. Casimir toma sal si y solamente si, o Bernardo toma solamente uno de los dos condimentos, o bien Marcial no toma ninguno de ellos. Toma mostaza si y solamente si Luis o Carlos toman dos condimentos. Luis toma sal si y solamente si o bien Bernardo no toma ningún condimento, o bien Casimir toma ambos. Luis toma mostaza si y solamente si Carlos o Marcial no toman ni sal ni mostaza. Carlos toma sal si y solamente si Bernardo o Luis no toman ni sal ni mostaza. Toma mostaza si y solamente si Casimir o Marcial no toman ni sal, ni mostaza. Marcial toma sal si y solamente si Bernardo o Carlos toman los dos condimentos. Marcial toma mostaza si y solamente si Casimir o Luis toman solo un condimento”. Modelar el PSR correspondiente. El problema consiste en descubrir si estas reglas son compatibles y, en caso de que lo sean, cuales son las combinaciones posibles (problema original de Lewis Carroll, en su obra Lógica Simbólica).
Representar 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?
Henry Dudeney (1847-1930) era un ingenioso inventor de problemas matemáticos. Entre sus aportaciones se encuentra un puzzle con cierta complejidad de resolución. Se trata de un heptágono donde en cada arista hay que colocar tres números: uno en cada vértice y otro en el centro de la arista. Hay que colocar los números del 1 al 14 alrededor de las aristas del heptágono de manera que el número de la arista y los dos vértices extremos sumen lo mismo, para todas las aristas. Modelar el PSR correspondiente.
Obtener, según diversas heurísticas, la mejor ordenación para el coloreado de los siguientes mapas:
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

Modifica el modelo de Hormigas que se ha visto en el tema para hacer que el usuario pueda decidir el número de fuentes de comida y se coloquen aleatoriamente en el mundo.
¿Puedes encontrar en el modelo de hormigas algún valor crítico del número de hormigas necesario para que se produzca un cambio en el comportamiento global de la colonia?
En el modelo de Hormigas se usa un truco para volver al nido, pero las hormigas de verdad usan otros sistemas. Investiga acerca de ello e intenta implementar en el modelo alguna idea que pueda funcionar.
Usando el modelo de Hormigas, crea otro modelo similar en el que haya 2 hormigueros que compitan por las mismas fuentes de comida. Piensa en acciones que pueden tomar las hormigas de un nido al encontrar feromonas u hormigas del otro nido.
¿Puedes encontrar en el modelo de termitas algún valor crítico del número de individuos para que se produzca un cambio en el comportamiento global de la colonia?
Amplía el modelo de las Termitas permitiendo que haya distintos tipos de madera que las termitas deben agrupar por tipos.
En el modelo de las luciérnagas, ¿cómo afecta el número de individuos (densidad) al comportamiento global?, ¿existe algún valor de densidad que pueda considerarse crítico (hay un cambio de comportamiento si hay más o menos de ese valor de densidad)?
En el modelo de las luciérnagas, ¿podrías pensar en otras estrategias de sincronización, o de mejoras en las que hay implementadas?
¿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?
En el modelo de Flocking introduce variantes como:
- Existencia de familias (tipos) de individuos que determinen sus características (radio y ángulo de visión, mínima separación, etc)
- 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.

Sistemas Dinámicos y Redes Complejas

Haz un modelo en NetLogo que permita visualizar el campo de vectores asociado a una ecuación diferencial de 2 variables.
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 en NetLogo que permita calcular el coeficiente de clustering de los nodos de un grafo. A continuación aplícalo sobre un grafo cualquiera para calcular su distribución de clustering.
Idea algún método de generación dinámica de redes, y mide las características de las redes resultantes: densidad, distribución de grados, distribución de clustering, etc.
Define un procedimiento que, dada una red en NetLogo, reciba como dato de entrada 2 nodos suyos y devuelva la distancia que hay 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.

Autómatas Celulares

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.

Fractales

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.

Algoritmos Genéticos

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.
Vamos a usar Algoritmos Genéticos para calcular óptimos de funciones de varias variables, usando lo que se llaman Algoritmos Genéticos Continuos. Vamos a explicarlo para funciones de $2$ variables, $f(x,y)$. En este caso, un gen será un par formado por dos valores $(x,y)$. Dados $2$ individuos de la población, $(x_1,y_1)$ y $(x_2,y_2)$, para cada $\alpha\in [0,1]$ se pueden calcular los dos descendientes siguientes por medio de un cruzamiento continuo: $(\alpha x_1 + (1-\alpha)x_2, \alpha y_1 + (1-\alpha)y_2)$ y $((1-\alpha) x_1 + \alpha x_2, (1-\alpha) y_1 + \alpha y_2)$. La mutación se consigue de forma análoga al caso de genes discretos, modificando ligeramente alguna de sus dos componentes. Tras esto, se puede aplicar el mismo algoritmo que el visto en clase para optimizar cualquier función de $2$ (o $n$) variables. Aplícalo para optimizar funciones reales.
Aplica los métodos de resolución de este apartado para resolver algunos de los problemas de la Colección Genérica de Problemas.

Algoritmos de Hormigas

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.
Aplica los métodos de resolución de este apartado para resolver algunos de los problemas de la Colección Genérica de Problemas.

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íen 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).
Aplica los métodos de resolución de este apartado para resolver algunos de los problemas de la Colección Genérica de Problemas.

Aprendizaje Automático

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.

Clustering y KNN

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 conjuntos de datos bidimensionales en los que puedas aplicar los algoritmos de Clustering vistos en clase. Aprovechando las implementaciones dadas, haz lo mismo con conjuntos de datos de dimensiones superiores y piensa alguna forma de representar las agrupaciones que se obtienen.
Utiliza algún algoritmo de Clustering para rebajar el número de colores que se usa en una imagen. Para ello:
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úmero de colores finales que quieres usar (puedes hacer que sea una decisión del usuario por medio del 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 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
1. 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.
2. 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. Prueba con otros algoritmos de Clustering.
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 algún algoritmo de Clusetring usando 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.

Haciendo uso de la siguiente matriz de distancias entre los puntos del dataset:

	A	B	C	D	E	F	G
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	0
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 distancias habituales.

Árboles de Decisión: ID3

Busca conjuntos de datos sobre los que puedas aplicar el algoritmo ID3 visto en clase.
Modifica el modelo ID3 para que pueda incluir alguna versión sencilla de trabajar con atributos continuos.
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:

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

¿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:

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
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.

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
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í.

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

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:

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

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.

Ejemplo	Tipo	Lugar	Estilo	Marco	Autor
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

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

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.
Usando NetLogo3D, haz las modificaciones necesarias para que pueda implementarse SOM en un entorno de patches 3D.
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.

Redes Neuronales

Crea una red Neuronal que, con el entrenamiento adecuado, sea capaz de calcular la función binaria de la mayoría: recibe una entrada de $n$ bits, y devuelve $1$ si hay mayoría de $1's$ y $0$ en caso contrario.
Crea una red Neuronal que, con el entrenamiento adecuado, sea capaz de calcular la función binaria de la paridad: recibe una entrada de $n$ bits, y devuelve $1$ si hay una cantidad par de $1's$ y $0$ en caso contrario.
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)\]
1. 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.
2. 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.
3. 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))$.