**IAIC 2024-25** Lista de Ejercicios # Representación, Búsqueda y Optimización ## Lógica !!!alg:Ej. 1. Para cada una de las siguientes fórmulas, determina todas sus subfórmulas, todos sus modelos e indica si son satisfactibles, insatisfactibles o tautologías: * $p → (q → r ∧ q)$ * $q → (p ∧ ¬p) → r$ * $(p ↔ q) ∧ (p → ¬q) ∧ p$ * $(p ∧ r) ∨ (¬p ∧ q) → ¬q$ !!!alg:Ej. 2. Decide cuáles de las siguientes afirmaciones son verdaderas: * $\{p ∨ q\} \models p → r$ * $\{p → q,\ q → p ∧ r\} \models p → (p → q) → r$ * $\{p ∧ ¬p\} \models r → r ∨ q$ * $\{p ∧ q ∧ r\} \models r → ¬p$ !!!alg:Ej. 3. Formaliza los siguientes argumentos y decide si son correctos o no: * Si la tormenta continúa o anochece, nos quedaremos a cenar o a dormir; si nos quedamos a cenar o a dormir no iremos mañana al concierto; pero sí iremos mañana al concierto. Así pues, la tormenta no continúa. * Si un triángulo tiene tres ángulos, un cuadrado tiene cuatro ángulos rectos. Un triángulo tiene tres ángulos y su suma vale dos ángulos rectos. Si los rombos tienen cuatro ángulos rectos, los cuadrados no tienen cuatro ángulos rectos. Por tanto, los rombos no tienen cuatro ángulos rectos. * Si la gorila es atractiva, el gorila sonreirá abiertamente o será infeliz. Si no es feliz, no procreará en cautividad. Por consiguiente, si la gorila es atractiva, entonces, si el gorila no sonríe abiertamente, no procreará en cautividad. * Si Elvira opina que hay que hacer lo posible para ser feliz, abandonará a su amante o se dedicará a su profesión. Si se dedica a su profesión, no dejará a su marido. En conclusión, si Elvira opina que hay que hacer lo posible para ser feliz, entonces, dejará a su marido aunque no abandone a su amante. * Si los astrónomos observan un nuevo planeta con atmósfera fuera de nuestro sistema solar, la Tierra no será el único planeta habitable en el Universo. O la Tierra no es el único planeta habitable o hay sistemas inexplorados. Por tanto, o los astrónomos no observan un nuevo planeta con atmósfera, fuera de nuestro sistema solar, o la Tierra es el único planeta habitable en el Universo. * Si no es cierto que se puede ser rico y dichoso a la vez, entonces la vida está llena de frustraciones y no es un camino de rosas. Si se es feliz, no se puede tener todo. Por consiguiente, la vida está llena de frustraciones. !!!alg:Ej. 4. Decide la corrección del siguiente argumento. Se sabe que: * 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 consiguiente, se concluye que el animal es una cebra. !!!alg:Ej. 5. En una isla hay dos tribus, la de los veraces (siempre dicen la verdad) y la de los mentirosos (qsiempre mienten). Un viajero se encuentra con tres isleños A, B y C. Cada uno le dice una frase: * A dice “B y C son veraces syss C es veraz”. * B dice “Si A y C son veraces, entonces B y C son veraces y A es mentiroso”. * C dice “B es mentiroso syss A o B es veraz”. Decide a qué tribu pertenecen A, B y C. !!!alg:Ej. 6. 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ó? !!!alg:Ej. 7. Tres niños, Manolito, Juanito y Paquito, 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, Paquito es inocente”. * Juanito: “Si Manolito lo rompió, entonces Paquito es inocente”. * Paquito: “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? !!!alg:Ej. 8. Sea $S = \{p → q,\ ¬s ∧ r → q,\ ¬q,\ q ↔ r ∧ s\}$. Obtén todos los modelos de $S$ por medio de DPLL. !!!alg:Ej. 9. Sea $S$ el siguiente conjunto de fórmulas proposicionales: $$\{p ∨ q → m,\ m ∧ (s ∨ r) → u,\ u ∧ w → j,\ u ∧ r → v,\ p ∧ s ∧ r → v,\ ¬v\}$$ Decide, usando el algoritmo DPLL, si $S$ es consistente. Y en caso de que lo sea, explicita el modelo que se encuentra al aplicar el algoritmo. !!!alg:Ej. 10. Formaliza los siguientes argumentos en Lógica de Primer Orden (si es necesario, con igualdad): 1. Existe una persona en la Feria tal que si dicha persona paga, entonces todas las personas pagan. 2. Sócrates es un hombre. Los hombres son mortales. Luego, Sócrates es mortal. 3. Hay estudiantes inteligentes y hay estudiantes trabajadores. Por tanto, hay estudiantes inteligentes y trabajadores. 4. Todos los participantes son vencedores. Hay como máximo un vencedor. Hay como máximo un participante. Por lo tanto, hay exactamente un participante. 5. Juan teme a María. Pedro es temido por Juan. Luego, alguien teme a María y a Pedro. 6. Los hermanos tienen el mismo padre. Juan es hermano de Luis. Jorge es padre de Luis. Por tanto, Jorge es padre de Juan. 7. Los aficionados al fútbol aplauden a cualquier futbolista extranjero. Juanito no aplaude a futbolistas extranjeros. Por tanto, si hay algún futbolista extranjero nacionalizado español, Juanito no es aficionado al fútbol. 8. Toda persona pobre tiene un padre rico. Por tanto, existe una persona rica con abuelo rico. 9. Todo lo existente tiene una causa. Luego hay una causa de todo lo existente. 10. Todos los robots obedecen a los amigos del programador jefe. Alvaro es amigo del programador jefe, pero Benito no le obedece. Por tanto, Benito no es un robot. 11. Supongamos conocidos los siguientes hechos acerca del número de aprobados de dos asignaturas A y B: * Si todos los alumnos aprueban la asignatura A, entonces todos aprueban B. * Si algún delegado de la clase aprueba A y B, entonces todos los alumnos aprueban A. * Si nadie aprueba B, entonces ningún delegado aprueba A. * Si Manuel no aprueba B, entonces nadie aprueba B. * Por tanto, si Manuel es un delegado y aprueba la asignatura A, entonces todos los alumnos aprueban las asignaturas A y B. 12. Carlos afeita a todos los habitantes de Sevilla que no se afeitan a sí mismo y sólo a ellos. Carlos es un habitante de Sevilla Por consiguiente, Carlos no afeita a nadie. !!!alg:Ej. 11. Haciendo una adecuada conversión de Primer Orden en Proposicional para poder hacer uso de DPLL, intenta determinar la consistencia de los siguientes conjuntos de clausulas: * $\{Q(u)∨P(a), ¬Q(w)∨P(w), ¬Q(x)∨¬P(x)\}$ * $\{Q(u)∨P(a), ¬Q(w)∨P(w), ¬Q(x)∨¬P(x), Q(y)∨¬P(y)\}$ * $\{I(a), ¬R(x)∨L(x), ¬D(y)∨¬L(y), D(a)\}$ * $\{I(a), ¬R(x)∨L(x), ¬D(y)∨¬L(y), D(a), ¬I(z)∨R(z)\}$ * $\{¬P(x,y)∨¬P(y,z)∨P(x,z), P(a,x), P(x,b), P(x,f(x))\}$ ## Representación !!!alg:Ej. 1: **Criptoaritmética** En general, un problema de criptoaritmética establece una relación aritmética entre palabras que codifican números. El objetivo es asignar valores (dígitos entre $0$ y $9$) a las letras que forman esas palabras de forma que se verifiquen las relaciones aritméticas expresadas, con la restricción de que letras distintas tienen asignaciones distintas, y ninguna de las cifras empieza por $0$. Por ejemplo: `send + more = money` !!!alg:Ej. 2: **Problema del coloreado de Mapas** El problema original consiste en ver el número de colores que deben usarse para colorear los países de un mapa con el objetivo de diferenciarlos adecuadamente:  Nosotros lo traducimos a un problema de grafos equivalente (y que generaliza el problema fundamental que hay detrás): 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). !!!alg:Ej. 3: **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, vaciar completamente una de las jarras, pasar agua de una jarra a otra (hasta que la primera se vacía o la segunda se llena). !!!alg:Ej. 4: **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*). Es un problema ampliamente conocido, así que lo describimos muy brevemente. Una rejilla de $9×9$ en la que se deben colocar números entre $1$ y $9$ con la condición de que: 1. En cada fila no se repiten números. 2. En cada columna no se repiten números. 3. En cada submatriz de tamaño $3×3$ no se repiten números (estas submatrices dividen la rejilla completa en $9$ espacios disjuntos del mismo tamaño). 4. A veces, se dan algunos valores fijos en la rejilla inicial que hay que respetar. !!!alg:Ej. 5: **Puzzle de las Esquinas** Este rompecabezas pide que se coloquen los dígitos del $1$ al $8$ en los bordes del cuadrado (tal y como se indica en la figura siguiente, un dígito en cada celda) de modo que el número de cada celda lateral sea igual a la suma de los números de las esquinas contiguas. ~~~~none .----+----+----. | NO | N | NE | +----+----+----+ | O | | E | +----+----+----+ | SO | S | SE | '----+----+----' ~~~~ !!!alg:Ej. 6: **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. Se debe recordar que dos reinas se amenazan entre sí 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, y fue propuesto por el ajedrecista alemán Max Bezzel en 1848. Edsger Dijkstra usó este problema (en su versión general) en 1972 para ilustrar el poder de la llamada programación estructurada. Publicó una descripción muy detallada del desarrollo del algoritmo de backtracking DFS. !!!alg:Ej. 7: **Clases en la E.T.S.I.I** Alicia, al volver de la escuela, describe las cuatro asignaturas (`IA`, `SI`, `MD` y `PD`) a las que ha asistido a su amigo Juan. A Juan le interesan las cuatro asignaturas, pero ella no recuerda exactamente en qué aula fue cada una ni el orden, solo recuerda haber visitado la `A1.16`, `H1.12`, `I1.32`, y la `F0.10`, y alguna informaciónn adicional. Identifica dónde se imparte cada asignatura y en qué orden.: 1. Alicia acudió a la la `H1.12` para `SI`. 2. Después de haber acudido a `MD` no fue la `F0.10`. 3. La segunda clase la recibió en la `A1.16`. 4. Dos clases después de salir de la `I1.32`, acudió a `PD`. !!!alg:Ej. 8: **Monjes y puertas** Hay una habitación con cuatro puertas (denotadas por A, B, C y D) y ocho monjes. Una o más de las puertas pueden ser de salida. Cada monje puede mentir o no. Los monjes hacen las siguientes afirmaciones: * Monje 1: La puerta A es de salida. * Monje 2: Al menos una de las puertas B y C es de salida. * Monje 3: El monje 1 y el monje 2 dicen la verdad. * Monje 4: Las puertas A y B son ambas salidas. * Monje 5: Las puertas A y C son ambas salidas. * Monje 6: O el monje 4 o el monje 5 dicen la verdad. * Monje 7: Si el Monje 3 dice la verdad, también lo hace el Monje 6. * Monje 8: Si el monje 7 y el monje 8 dicen la verdad, el monje 1 también. ¿Qué puerta/s son salidas? ¿Puedes determinar quién dice la verdad y quién miente? ¿Y si añadimos la información de que solo una de las puertas es la salida? !!!alg:Ej. 9: **Noticias** El Daily Galaxy envió a sus cuatro mejores reporteros (Carlos, Jaime, Luis y Pedro), a diferentes lugares (Granada, Cádiz, Sevilla, y Córdoba), para cubrir cuatro noticias de última hora: nacimiento de un bebé de 100Kg, lanzamiento de un dirigible hecho de globos infantiles, inauguración de un rascacielos de 3Km de altura, y la aparición de una ballena varada de color rosa. El editor del periódico intenta recordar dónde se encuentra cada uno de los reporteros y qué noticia ha cubierto, pero solo tiene la siguiente información parcial confirmada: 1. El bebé no nació ni en Córdoba ni en Cádiz. 2. Jaime no fue a Sevilla. 3. El lanzamiento del dirigible y la inauguración del rascacielos fueron cubiertos, en algún orden, por Luis y el reportero que fue enviado a Sevilla. 4. Córdoba no fue el lugar de la ballena varada ni de la inauguración del rascacielos. 5. Granada es el lugar al que fue Carlos o el lugar donde varó la ballena, o ambos. !!!alg:Ej. 10: **Arquero** Teniendo en cuenta que una diana tiene las puntuaciones 16, 17, 23, 24, 39, 40 en sus diferentes círculos, y que el arquero puede tirar tantas flechas como quiera. ¿Cuál sería la mejor distribución de tiros para quedarse lo más cerca posible de 100? !!!alg:Ej. 11: **Monedas** ¿Cuál es el número mínimo de monedas que permite pagar exactamente cualquier cantidad inferior a 1 euro? Recordemos que existen seis moneda de céntimos de euro, de denominación 1, 2, 5, 10, 20, 50. !!!alg:Ej. 12: **Tomografía Discreta** Una matriz que contiene $0s$ y $1s$ se escanea vertical y horizontalmente, dando el número total de $1s$ en cada fila y columna. El problema consiste en reconstruir el contenido de la matriz a partir de esta información. Por ejemplo: ~~~~none 0 7 1 6 3 4 5 2 7 0 0 8 ■ ■ ■ ■ ■ ■ ■ ■ 2 ■ ■ 6 ■ ■ ■ ■ ■ ■ 4 ■ ■ ■ ■ 5 ■ ■ ■ ■ ■ 3 ■ ■ ■ 7 ■ ■ ■ ■ ■ ■ ■ 0 ~~~~ !!!alg:Ej. 13: **Fill-a-Pix** Un puzzle Fill-a-Pix consiste en una cuadrícula que contiene pistas en varios lugares. El objetivo es revelar una imagen oculta pintando los cuadrados alrededor de cada pista de modo que el número de cuadrados pintados, incluido el cuadrado con la pista, coincida con el valor de la pista. * [Reglas de Fill-a-pix](http://www.conceptispuzzles.com/index.aspx?uri=puzzle/fill-a-pix/rules) * [Historia de Fill-a-pix](http://www.conceptispuzzles.com/index.aspx?uri=puzzle/fill-a-pix/history) !!!alg:Ej. 14: **Diferencia mínima** A partir de los dígitos ($0$ a $9$) construimos 2 números, $X$ e $Y$, cada uno de $5$ dígitos, y sin repetirse ninguno entre ellos (es decir, vistos como conjuntos, $X$ e $Y$ forman una partición de $0:9$). ¿Cuál es la diferencia mínima que se puede conseguir? !!!alg:Ej. 15: **Sucesiones Mágicas** Una sucesión mágica de longitud $n$ es una sucesión de enteros $x_0, \dots, x_{n-1}$ entre $0$ y $n-1$, tal que para todo $0 ≤ i ≤ n-1$, el número $i$ aparece exactamente $x_i$ veces en la sucesión. Por ejemplo, $6,2,1,0,0,0,1,0,0,0$ es una sucesión mágica, ya que el $0$ aparece $6$ veces en ella, el $1$ aparece $2$ veces, el $2$ aparece $1$ vez, etc. Construye sucesiones mágicas por medio de CSP. !!!alg:Ej. 16: **Buscaminas** Un campo minado viene dado por una matriz numérica que indica cuántas minas son adyacentes a cada posición (si hay un número, no puede haber una mina). En la representación siguiente: * los ■ representan que ese dato es desconocido (pudiendo haber, o no, una mina en esa posición), * los □ representan espacios sin mina, * los * representan minas, * las posiciones con números indican el número de minas que le rodean (no hay minas en ellos). El objetivo consiste en decubrir dónde están todas las minas de un campo minado de entrada. Por ejemplo: ~~~~none ■ ■ 2 ■ 3 ■ * □ 2 □ 3 * 2 ■ ■ ■ ■ ■ 2 * □ * * □ ■ ■ 2 4 ■ 3 ==> □ □ 2 4 * 3 1 ■ 3 4 ■ ■ 1 □ 3 4 * □ ■ ■ ■ ■ ■ 3 □ * * * □ 3 ■ 3 ■ 3 ■ ■ * 3 □ 3 * * ~~~~ !!!alg:Ej. 17: **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. !!!alg:Ej. 18: **Humanos y zombies:** Hay \(3\) humanos y \(3\) zombies a la orilla de un río que desean cruzar a la otra orilla. Tienen una canoa con capacidad para dos personas como máximo, y si intentan cruzar más, se hundirá y morirán los ocupantes. Hay que considerar que no debe haber más zombies que humanos en ningún sitio porque entonces los zombies se comerían a los humanos. Además, la canoa siempre debe ser conducida por alguien (no puede cruzar el río sola). ¿Cuál es una buena sucesión de movimientos para que al final consigan cruzar todos? !!!alg:Ej. 19: **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? !!!alg:Ej. 20: **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? !!!alg:Ej. 21: **Cuadrado Mágico** 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. !!!alg:Ej. 22: **Montones de Cartas** 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\). !!!alg:Ej. 23: **\(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. !!!alg:Ej. 24: **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\). Solo 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$. !!!alg:Ej. 25. 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. !!!alg:Ej. 26: **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 solo 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 solo 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? !!!alg:Ej. 27: **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\). !!!alg:Ej. 28: **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\). !!!alg:Ej. 29: **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: * Una rana puede moverse a un nenúfar adyacente vacío, con coste 1. * 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. !!!alg:Ej. 30: **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\). !!!alg:Ej. 31. 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\}\). !!!alg:Ej. 32. 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. !!!alg:Ej. 33: **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? !!!alg:Ej. 34. 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 solo se le concedan dos proyectos. Encuentra la adjudicación de menor precio. !!!alg:Ej. 35. 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. !!!alg:Ej. 36. Tenemos un tablero de $3{\times}3$ casillas como el de la figura, donde en cada esquina tenemos caballos de ajedrez ($2$ caballos negros y $2$ blancos). Haciendo los movimientos del caballo válidos en el ajedrez, deseamos intercambiar los caballos negros con los blancos. !!!alg:Ej. 37: **Problema de asignación de tareas:** Disponemos de un conjunto de agentes ($A=\{a_i: 1\leq i\leq n\}$) y un número de tareas a realizar ($T=\{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 estos están acotados por una cantidad fija, \(b_i\), para cada agente. Encuentra una asignación de tareas factible y de coste mínimo. !!!alg:Ej. 38. 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? !!!alg:Ej. 39. 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 numérico. 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})\). !!!alg:Ej. 40: **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 y que funciona bajo las siguientes condiciones: * 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\) | Obtén una secuencia de ejecuciones que consuma la máxima cantidad de datos en el tiempo total permitido. !!!alg:Ej. 41: **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. !!!alg:Ej. 42: **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. !!!alg:Ej. 43: **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**). !!!alg:Ej. 44: **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\). !!!alg:Ej. 45: **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. !!!alg:Ej. 46: **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. !!!alg:Ej. 47: **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. !!!alg:Ej. 48: **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. !!!alg:Ej. 49: **¿De quién es esta cebra?** En el vecindario hay cinco casas adosadas, de diferentes colores, habitadas por cinco personas de diferentes nacionalidades. Cada una posee un animal diferente, bebe una bebida diferente y fuma una marca de tabaco distinta. Sabiendo la siguiente información, ¿podrías determinar las características completas del vecindario y decirnos a quién pertenece la cebra que se está comiendo las flores? 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. !!!alg:Ej. 50: **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 zapatos planos de color fucsia, las bambas moradas, y unas sandalias de cuero preciosas), pero Enriqueta no puede recordar en qué tienda compró cada uno, aunque recuerda las tiendas en que compró: *La granja del pie*, *Tacones a Mogollón*, *El palacio del zapato* o *Zapatos Asesinos*. ¿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 *Zapatos Asesinos*. 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. !!!alg:Ej. 51: **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. La investigació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 extraen las siguientes conclusiones tras interrogar a los sospechosos: 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*. A raíz de lo 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? !!!alg:Ej. 52. Puedes probar otros problemas de la colección: [http://www.csplib.org/Problems/](http://www.csplib.org/Problems/) ## Búsqueda !!!alg:Ej. 1. El grafo que se muestra abajo determina un problema de búsqueda. Cada nodo representa un estado; los arcos modelan la aplicación de operadores. Supongamos que A es el estado inicial y que K y E son estados finales.  * Desarrolla el árbol de búsqueda que genera la búsqueda en anchura, sin filtrar estados repetidos. ¿Cuál de los nodos finales se encuentra primero? * Indica el orden en que se expanden los nodos. * Explicita el estado de la lista abierta en cada paso del algoritmo. !!!alg:Ej. 2. El grafo que se muestra a continuación representa un esquema de un mapa de carreteras (concretamente, de Rumanía). Los nodos están etiquetados con el nombre de ciudades, y los arcos con la distancia por carretera entre dichas ciudades. La función $h^*$ que se muestra al lado indica la distancia aérea entre cualquier ciudad y la ciudad de B, que es nuestro destino. Disponemos de un coche eléctrico que permite recorrer 320km sin recargar. Sólo puede recargar en ciudades con estación de recarga pública, los cuales se indican en el mapa por los cuadrados rellenos (ciudades D, F, O, y V). Inicialmente nos encuentramos en la ciudad A con la batería completamente cargada, y deseamos llegar a B por la ruta más corta posible (y sin quedarnos tirados por el camino con la batería vacía). Conocemos la red de carreteras, la posición de las estaciones de recarga, y las características del vehículo, por lo que en cada momento sabemos a qué ciudades vecinas podemos llegar dado el estado de carga de su batería. Aplica la búsqueda A* para resolver el problema.  * Representa el problema como espacio de estados. * Desarrolla el árbol de búsqueda que genera el algoritmo $A^*$. Indica el orden en el que se expanden los nodos, los valores de $g$, $h^*$ , y $f^*$ de cada nodo del árbol de búsqueda, así como el estado de la lista abierta en cada paso del algoritmo. * Resuelve el mismo problema pero sin suponer ninguna restricción respecto a la distancia máxiam que puede recorrer el coche sin repostar. * ¿Es $h^*$ (distancia área entre ciudades) optimista? Justifica la respuesta. !!!alg: Ej. 3. Aplica de forma detallada el **algoritmo $A^*$** sobre el grafo de estados siguiente para encontrar un camino de peso mínimo de $A$ a $H$ (en cada arista se muestra su peso, y en la tabla se muestra la heurística desde cada nodo hasta $H$).  Para cada paso del algoritmo indica el conjunto de nodos explorados con sus costes y heurísticas, cuáles están abiertos, cerrados, el nodo seleccionado para el siguiente paso, y los caminos parciales que se consideran. !!!alg:Ej. 4. La figura siguiente muestra el espacio de estados de un cierto problema, donde $a$ es el estado inicial, $z$ el estado final, y las aristas representan las transiciones válidas. Bajo cada nodo se muestra su valor de heurística, $h$, y en cada arista se muestra su coste.  1. ¿Es $h$ admisible? Razona la respuesta. 2. Modifica alguno de los costes de las aristas mostrados en la figura para que $h$ no sea admisible, y explica por qué es así. 3. Cambia $h$ en alguno de los nodos para que la nueva heurística no sea admisible, y explica por qué es así. 4. Aplica de forma detallada el **algoritmo $A^*$** usando los datos de la figura. Indica por pasos el conjunto de nodos explorados explicitando costes totales y heurísticas, cuáles están abiertos, cerrados, y el nodo seleccionado para el siguiente paso. ¿Qué camino sale?, ¿en qué cambia con las modificaciones que has propuesto en los apartados anteriores? !!!alg:Ej. 5. Aplica de forma detallada el **algoritmo $A^*$** sobre el grafo de estados de la imagen para encontrar un camino de peso mínimo de $a$ a $z$ (bajo cada nodo se muestra una estimación del camino hasta $z$; en cada arista se muestra su peso).  Indica en cada paso el conjunto de nodos explorados con sus costes y heurísticas, cuáles están abiertos, cerrados, y el nodo seleccionado para el siguiente paso. !!!alg:Ej. 6. Dada la siguiente red $2D$ regular e infinita, donde el estado inicial es $(0, 0)$, el estado final puede ser cualquier punto $(x, y)∈ \mathbb{Z}\times \mathbb{Z}$, y el movimiento entre estados directamente conectados tiene coste 1:  ¿Cuáles de las siguientes funciones heurísticas son optimistas? (las definimos para un estado genérico $(u,v)$) 1. $h^∗ ((u, v)) = |u - x| + |v - y|$ 2. $h^∗ ((u, v)) = |u - x| * |v - y|$ 3. $h^∗ ((u, v)) = 2 * min(|u - x|, |v - y|)$ 4. $h^∗ ((u, v)) = |u| + |x| + |v| + |y|$ 5. $h^∗ ((u, v)) = \sqrt{(|u - x|^2 + |v - y|^2)}$ !!!alg:Ej. 7. En el espacio de estados que se muestra con el grafo siguiente:  Considerando que $A$ es el estado inicial y $G$ es el objetivo. Los costes de cada arista (que pueden ser atravesadas en ambas direcciones) se muestran en el grafo. * Demuestra que la heurística $h_1$ es consistente pero la heurística $h_2$ no lo es. * Para cada uno de los algoritmos de la siguiente tabla, marca cuál (si lo hay) de los caminos señalados podría devolver. Ten en cuenta que para algunas estrategias de búsqueda el camino específico devuelto podría depender del comportamiento de desempate. En tales casos, asegúrate de marcar todos los caminos que podrían ser devueltos bajo algún esquema de desempate. |Algoritmo | A-B-D-G | A-C-D-G | A-B-C-D-F-G| |:--------:|---------|---------|------------| |BFS | | | | |DFS | | | | |$A^*(h_1)$| | | | |$A^*(h_2)$| | | | * Supongamos que estamos completando la nueva función heurística $h_3$ que se muestra a continuación, donde todos los valores son fijos excepto $h_3(B)$. |Nodo | A | B | C | D | E | F | G | |:---:|---|---|---|---|---|---|---| |$h_3$|$10$| ? |$9$|$7$|$1.5$|$4.5$|$0$| Para cada una de las siguientes condiciones, escribe el conjunto de valores posibles para $h_3(B)$: 1. ¿Qué valores de $h_3(B)$ hacen que $h_3$ sea admisible? 2. ¿Qué valores de $h_3(B)$ hacen que $h_3$ sea consistente? 3. ¿Qué valores de $h_3(B)$ harán que la búsqueda $A^*$ del grafo expanda el nodo $A$, luego el nodo $C$, luego el nodo $B$, y luego el nodo $D$ en ese orden? !!!alg:Ej. 8. Para cada una de las siguientes estrategias de búsqueda para el Espacio de Estados representado por el grafo adjunto, calcula el orden en el que se expanden los estados y el camino devuelto por la búsqueda. En todos los casos, los empates se resuelven de manera que los estados con un orden alfabético anterior se expanden primero. El estado inicial y el estado objetivo son $S$ y $G$, respectivamente.  Resuelve el problema por: * BFS. * DFS. * Búsqueda $A^*$ con la heurística $h$. !!!alg:Ej. 9. El grafo de la figura siguiente muestra el espacio de estados de un hipotético problema de búsqueda. Los estados se indican con letras, y el coste de cada acción se indica en la arista correspondiente. Obsérvese que las acciones no son reversibles, ya que el grafo es dirigido. La tabla que aparece junto al espacio de estados muestra el valor de una función heurística admisible, considerando $G$ como objetivo (comprueba que esta heurística nunca sobreestima el mínimo coste del camino desde cualquier estado hasta $G$).  Considerando $S$ como estado inicial, resuelve el problema de búsqueda anterior utilizando: * BFS. * DFS. * $A^*$ con la heurística anterior. Al dar el árbol de búsqueda debe indicarse: - el orden de expansión de cada nodo (por ejemplo, numerando los nodos expandidos según el orden de su expansión), - la acción correspondiente a cada arista del árbol, - el estado, - el coste del camino, y - el valor de la heurística de cada nodo. !!!alg:Ej. 10. $A^∗$ es un algoritmo que se usa profusamente en los sistemas de navegación (por ejemplo, para ayudar a la conducción de vehículos), pero habitualmente la búsqueda se orienta por medio de una heurística de mínima distancia, cuando no siempre es lo deseable. Por ejemplo: promocionar rutas turísticas/paisajísticas, facilitar trayectos en los que se producen giros más sencillos, compensar los tiempos de tráfico denso en determinadas zonas, sistemas de transporte multimodal, etc. Idea y diseña situaciones en las que tenga sentido el uso de heurísticas distintas (o de combinación de heurísticas) en sistemas de recomendación de rutas o en sistemas de navegación automática. !!!alg:Ej. 11. Considera el árbol 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. !!!alg:Ej. 12. Dos conductores, el agente y su contrario, se plantean competir sobre un circuito de ciudades con las siguientes reglas: * El recorrido del circuito se hace por tramos, partiendo de la ciudad marcada como Salida. * 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ó, sin importar quién llega antes a la ciudad de destino. Es decir, si el agente empieza el recorrido y decide ir a B, el agente se apuntará 30 kilómetros. A continuación el contrario debe elegir, partiendo de B, entre ir a C o a D. * Un conductor no puede ir a una ciudad en la que haya estado antes, por lo que la competición acaba cuando el conductor al que le toca moverse no puede ir a ninguna ciudad no visitada anteriormente. * Gana el conductor que haya acumulado más kilómetros con los tramos recorridos.  * Define una representación eficiente para los estados del juego. * Desarrolla el árbol de búsqueda Minimax con un máximo de dos jugadas para cada jugador (desde el punto de vista del que empieza primero). 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 propague sus valores a través del árbol. ¿Qué jugada haría el agente tuyo? * ¿Qué partes del árbol del apartado anterior no se expandirían si se aplicara la poda? !!!alg:Ej. 13. Aplica el algoritmo de **Templado Simulado** para resolver el siguiente problema: Dado un grafo $G=(V,E)$ con pesos positivos en las aristas, encontrar una partición de $V$ en tres conjuntos, $V_1$, $V_2$ y $V_3$, de tal manera que la suma de los pesos de las aristas que conectan $V_1$ y $V_2$, y la suma de los pesos de las aristas que conectan $V_1$ y $V_3$, sea lo más parecida posible. !!!alg:Ej. 14. Implementa jugadores automáticos para los siguientes juegos de tablero haciendo uso de MCTS. Para cada uno de ellos: 1. Da 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. 2. Haz 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. 3. Haz una implementación de un jugador automático por medio de MCTS. 4. Conecta el jugador automático a la implementación anterior. Juegos propuestos: * 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. * 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. * El juego del **3 en raya**. * **Colección de juegos de Tablero**: [conecta4](https://es.wikipedia.org/wiki/Conecta_4), [Go Moku](http://www.ludoteka.com/go-moku.html), [Othello/Reversi](https://brainking.com/es/GameRules?tp=9), [Damas](https://brainking.com/es/GameRules?tp=7), [4 en Línea](https://brainking.com/es/GameRules?tp=13), [Mancala](https://brainking.com/es/GameRules?tp=103), [Ranitas](https://brainking.com/es/GameRules?tp=54), [4 en Línea múltiple](https://brainking.com/es/GameRules?tp=16), [Asimilación](https://brainking.com/es/GameRules?tp=89), [Gran Avance](https://brainking.com/es/GameRules?tp=84), [6 en raya](http://www.ludoteka.com/6-en-raya.html), [9 hombres de Morris](http://www.ludoteka.com/morris.html), [Havannah](http://www.ludoteka.com/havannah.html), [Isolation]("https://en.wikipedia.org/wiki/Isolation_(board_game)"). !!!alg:Ej. 15. Implementa jugadores automáticos para los siguientes juegos de tablero haciendo uso de MCTS para el juego del **Quarto** en su versión simplificada: Es un juego que se desarrolla en un tablero cuadrado dividido en 16 casillas (4X4) en el que se enfrentan 2 jugadores. Además se utilizan 16 piezas que combinan las siguientes características dando como resultado de esta combinación todas las variaciones posibles: Tamaño (grande/pequeño), Color (rojo/azul), Forma (cuadrado/círculo), Agujero (pieza con agujero/no). El objetivo del juego para cada jugador es intentar terminar por turno una fila de cuatro piezas que tengan en común al menos una de las características descritas (cuatro grandes, cuatro pequeñas, cuatro azules, cuatro rojas, cuatro redondas, cuatro cuadradas, cuatro con agujero o cuatro sin agujero). Las filas pueden ser horizontales, verticales o diagonales. El ganador es el jugador que consigue colocar la cuarta pieza de una de las filas en el tablero en primer lugar. El juego se desarrolla añadiendo piezas al tablero en turnos alternos de cada uno de los dos contrincantes. En cada uno de sus turnos cada jugador añade una nueva pieza a una casilla del tablero. La pieza añadida al tablero ya no se moverá a lo largo de la partida. Aquí buscamos una versión simplificada, en la que en cada turno el jugador correspondiente decide qué pieza coloca (de entre las piezas libres) y dónde. Si se colocan las 16 piezas en el tablero sin que ninguno de los dos jugadores consiga el objetivo, la partida termina en empate. En la versión original del juego, el jugador que incorpora una pieza decide en qué casilla se incorpora, pero no qué pieza se incorpora, ya que el adversario hace la elección concreta de la pieza. Por tanto, el turno de cada jugador consta de dos decisiones: 1. Colocar la pieza indicada por el adversario en el tablero en el turno anterior; 2. Indicar al adversario la pieza que deberá colocar en su siguiente movimiento. Al principio de la partida, el jugador que tiene el primer turno sólo indica al adversario la pieza que va a colocar en el tablero. ## Optimización !!!alg:Ej. 1. Aplica el algoritmo de **Optimización por Enjambre de Partículas** (**PSO**) para resolver el problema de empaquetamiento de esferas: El objetivo es encontrar la disposición más óptima de $N$ esferas sólidas del mismo tamaño ($radio = 1$) de forma que se puedan meter todas juntas en una caja rectangular del menor volumen posible. Debe tenerse presente que las esferas, a lo sumo, se pueden tocar, pero son sólidas, no pueden cortarse. !!!alg:Ej. 2. Explica cómo usarías un algoritmo de optimización para obtener el polinomio de grado $4$ que mejor aproxima a una función dada. Es decir, concretamente: Dada $f : [0, 1] → \mathbb{R}$, calcula el polinomio $p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4$ que mejor aproxima a la función $f$ en el intervalo $[0, 1]$. Ten en cuenta las siguientes ayudas: 1. Vamos a suponer que los coeficientes de $p(x)$ pueden tomar valores en $[−1, 1]$. 2. La distancia entre $f$ y $p$ se puede calcular como $d(f, p) =\int_0^1 |f(x)−p(x)|dx$, y supondremos que tenemos procedimientos para calcular esta integral. 3. Una forma alternativa de calcular la distancia sería por medio de un muestreo en un conjunto de puntos del dominio. # Aprendizaje Automático ## DataFrames !!!alg:Ej. 1. Crea un Dataframe que tenga el siguiente contenido por columnas: $$X:[78,85,96,80,86],\ Y:[84,94,89,83,86],\ Z:[86,97,96,72,83]$$ !!!alg:Ej. 2. Crea un Dataframe que almacena la siguiente tabla de datos de forma adecuada, y muestra la descripción de la misma (`?` indica un valor faltante) : ~~~~ exam_data = { Nombre: ['Anastasia', 'Dima', 'Katherine', 'James', 'Emily', 'Michael', 'Matthew', 'Laura', 'Kevin', 'Jonas'], Nota1: [12.5, 9, 16.5, ?, 9, 20, 14.5, ?, 8, 19], Nota2: [2.5, 3, 19, ?, 3, 10, 1.5, 4, 16, 9], Intentos: [1, 3, 2, 3, 2, 3, 1, 1, 2, 1], Trabajo: ['yes', 'no', 'yes', ?, 'no', 'yes', 'yes', ?, 'no', 'yes'] Etiquetas: ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'] } ~~~~ 1. Genera un dataframe derivado que solo contenga las columnas `Nombre` y las `Notas`. 2. Añade una columna con la nota media (decide qué debe hacerse con los datos faltantes). 3. Crea un dataframe con la misma estructura, pero que contenga solo aquellos alumnos que han superado la puntuación de `10` y hayan presentado el trabajo. 4. Crea un dataframe con la misma estructura, pero que contenga únicamente las filas con algún dato faltante. 5. Repite todo lo anterior, pero asignando un valor `0` a las notas faltantes, y `no` a los trabajos faltantes. 6. Calcula la puntuación media de la clase, y el número total, máximo y mínimo de intentos realizados en el curso. 7. Exporta todos los dataframes generados a ficheros CSV. !!!alg:Ej. 3. A partir del siguiente fichero CSV: ~~~~ ID Name Age Gender Salary Target 1,Sara,25,Female,50000,0 2,Ophrah,30,Male,60000,1 3,Torben,22,Male,70000,0 4,Masaharu,35,Male,80000,1 5,Kaya,?,Female,55000,0 6,Abaddon,29,Male,?,1 ~~~~ 1. Carga el CSV (tras haberlo guardado en un fichero) en un dataframe. 2. Muestra las filas con valores faltantes. 3. Sustituye los valores faltantes por la media del grupo. 4. Convierte las variables categóricas en numéricas. 5. Convierte las categóricas en una codificación one-hot. 6. Normaliza los datos numéricos usando el escala min-max. 7. Normaliza los datos numéricos usando $N(0,1)$. 8. Divide el dataset en conjuntos de Training y Testing. 9. Graba los datasets procesados en ficheros CSV. !!!alg:Ej. 4. Vamos a usar el dataset `MASS/Crabs` (puedes encontrar información sobre su estructura [aquí](https://vincentarelbundock.github.io/Rdatasets/doc/MASS/crabs.html)) que se encuentra en el repositorio RDatasets: 1. Carga el dataset en un dataframe adecuado. 2. Extrae una descripción del contenido del dataset. 3. Normaliza las variables numéricas usando una escala min-max. 4. Convierte las variables categóricas en numéricas. 7. Normaliza los datos numéricos usando $N(0,1)$. 8. Divide el dataset en conjuntos de Training y Testing. 9. Graba los datasets procesados en ficheros CSV. !!!alg:Ej. 5. Explora los datasets presentes en RDatasets y practica con algunos de ellos tareas similares a las que se han hecho en los ejercicios anteriores. ## Redes Neuronales !!!alg:Ej. 1. Usa el dataset [`MASS/Crabs`](../../Practicas/datasets/crabs.csv) para: 1. Predecir el sexo del individuo a partir del resto de datos. 2. Predecir el tipo y sexo a partir del resto de datos. 3. Predecir alguna variable numérica a partir del resto de datos. !!!alg:Ej. 2. Usa el dataset [`Datastes/iris`](../../Practicas/datasets/iris.csv) para: 1. Modifica la columna `Specie` para convertirla en una codificación one-hot. 2. Predide la especie a partir de las dimensiones del individuo. !!!alg:Ej. 3. Crea redes Neuronales y datasets adecuados para: 1. 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. 2. 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. 3. Calcular las funciones lógicas habituales: AND, OR, NOT, XOR. !!!alg:Ej. 4. Explora los datasets presentes en [Datasets](#Datasets) y practica con algunos de ellos tareas similares a las que se han hecho en los ejercicios anteriores. !!!alg:Ej. 5. Detalla algún procedimiento por el que podrías usar Templado Simulado (o PSO) para entrenar una red nueronal. !!!alg:Ej. 6. Imagina que tomamos una neurona 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? !!!alg:Ej. 7. Verifica que, en el caso de que $\sigma$ sea la función sigmoide, entonces $$\sigma'(x)=\sigma(x)(1-\sigma(x))$$ ## Clustering !!!alg:Ej. 1. Utiliza algún algoritmo de Clustering para rebajar adecuadamente el número de colores que se usa en una imagen. Para ello, ten en cuenta que una imagen es un conjunto de pixels (en forma de matriz), cada uno con un color RGB. ¿Se te ocurre alguna forma de restringir la paleta de colores original (no solo el número de colores)? !!!alg:Ej. 2. Idea un sistema en el que un algoritmo de clustering podría usarse para agrupar imágenes por similaridad en su contenido. !!!alg:Ej. 3. Idea un sistema en el que un algoritmo de clustering podría usarse para agrupar textos cortos por similaridad en su contenido. !!!alg:Ej. 4. Considera el siguiente conjunto de entrenamiento 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. | Ej | Atr1. | Atr2. | Atr3. | |-------|-------|-------|-------| | $E_1$ | $1$ | $1$ | $0$ | | $E_2$ | $1$ | $0$ | $0$ | | $E_3$ | $1$ | $0$ | $1$ | | $E_4$ | $0$ | $0$ | $1$ | $\quad$ !!!alg:Ej. 5. 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. !!!alg:Ej. 6. 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 !!!alg:Ej. 1. Modifica el modelo ID3 para que trabaje con atributos continuos haciendo uso de algún algoritmo de clustering para decidir las agrupaciones que usará en los atributos continuos (es decir, primero se aplica el algoritmo de clustering al atributo, y se decide las agrupaciones que se considerarán para discretizarlo). !!!alg:Ej. 2. 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 | 1. ¿Cuál es la entropía del conjunto de ejemplos respecto a la clasificación de los mismos que realiza el atributo Lepisto? 2. ¿Qué atributo proporciona mayor ganancia de información? 3. Aplicar (detallando cada uno de los pasos realizados) el algoritmo ID3 para encontrar, a partir de este conjunto de entrenamiento, un árbol que nos permita decidir si un determinado individuo es un lepisto o no. 4. Obtener un conjunto de reglas a partir del árbol obtenido en el apartado anterior. 5. Según las reglas obtenidas, ¿hay algún atributo que sea irrelevante para decidir si un individuo es un lepisto? !!!alg:Ej. 3. 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: 1. 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. 2. ¿Qué sesgo tendría el algoritmo modificado?, justifica la respuesta. 3. 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. !!!alg:Ej. 4. Aplica el algoritmo ID3 para construir un árbol de decisión consistente con los ejemplos de la primer tabla que nos ayude a decidir si comprar o no un CD nuevo. Haz uso de los ejemplos de la segunda tabla para obtener una 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 | $\quad$ !!!alg:Ej. 5. 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 | $\quad$ !!!alg:Ej. 6. 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 | 1. 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. 2. 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? !!!alg:Ej. 7. Se han encontrado una gran cantidad de obras de arte realizadas por dos artistas A y B, pero solo 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 | 1. 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. 2. 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 | $\quad$ ## KNN !!!alg:Ej. 1. Implementa el algoritmo de los **K vecinos más cercanos** (KNN) visto en clase. Implementa la versión ponderada y también alguna versión que pueda usarse para problemas de regresión. !!!alg:Ej. 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. !!!alg:Ej. 3: **KNN Condensado** En el algoritmo KNN existe el problema de que requiere de mucha memoria y tiempo de ejecución porque hay que almacenar permanentemente todos los datos que forman 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 otras existentes. Para reducir este problema existe un preprocesamiento de los datos que se llama **condensación**, y que consiste en lo siguiente (observa que depende del orden dado a los datos y, además, tiene el problema de conservar los datos que introducen ruido al sistema): Se comienza dando un orden en los datos de entrada; posteriormente, y siguiendo el orden anterior, cada ejemplo $x_n$ se clasifica por medio de KNN haciendo uso únicamente de los datos anteriores según el orden anterior (es decir, usando $x_1,\dots,x_{n-1}$); si la clasificación obtenida coincide con la real, ese ejemplo se elimina de los datos, si no, permanece. Para que tenga sentido, $x_1,\dots, x_K$ se añaden inicialmente. !!!alg:Ej. 4: **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). ## Datasets Cada dataset se resume de forma similar, para facilitar su comparación y navegación para que puedas practicar tanto las técnicas específicas de preparación de datos como los métodos de modelización posteriores. En concreto, junto a los propios ficheros de datos, de cada dataset daremos: * **Nombre**: Cómo referirse al dataset. * **Tipo de problema**: regresión/clasificación. * **Entradas y salidas**: Características y objetivo. * **Rendimiento**: Rendimiento de referencia para la comparación con un algoritmo básico y con el mejor rendimiento conocido (si se conoce). * **Enlaces**: Para descagar los ficheros asociados. * **Referencia**: Para saber más... Además de los datasets que se ofrecen aquí, pueden visitarse sitios como: * [UC Irvine Machine Learning Repository](https://archive.ics.uci.edu/) * [Google Dataset Search](https://datasetsearch.research.google.com/) * [Wikipedia ML datasets](https://en.wikipedia.org/wiki/List_of_datasets_for_machine-learning_research) * [RDatasets](https://vincentarelbundock.github.io/Rdatasets/articles/data.html) * [OpenML](https://www.openml.org/) ### MNIST El dataset de dígitos tiene como objetivo predecir el dígito a partir de una imagen $28\times 28$ del mismo. Se trata de un problema de clasificación multiclase. Se proporcionan dos ficheros CSV, uno de entrenamiento (con $60.000$ muestras), y otro de test (con $10.000$ muestras). Son grandes, así que se proporcionan en versión ZIP. El número de observaciones de cada clase está equilibrado. La primera columna contiene la salida real, mientras que el resto de columnas contienen una versión aplanada de la matriz de pixels. [Descarga Test](../../Practicas/datasets/mnist_test.zip)
[Descarga Train](../../Practicas/datasets/mnist_train.zip) ### Calidad del Vino El dataset sobre calidad del vino tiene como objetivo en predecir la calidad de los vinos blancos en una escala a partir de medidas químicas de cada vino. Se trata de un problema de clasificación multiclase, aunque también podría plantearse como un problema de regresión. El número de observaciones de cada clase no está equilibrado. Hay $4.898$ observaciones con $11$ variables de entrada y una variable de salida. Los nombres de las variables son los siguientes: `Acidez fija`, `Acidez volátil`, `Ácido cítrico`, `Azúcar residual`, `Cloruros`, `Dióxido de azufre libre`, `Dióxido de azufre total`, `Densidad`, `pH`, `Sulfatos`, `Alcohol`, `Calidad` (puntuación de $0$ a $10$). El rendimiento de referencia de la predicción del valor medio es un RMSE de aproximadamente $0,148$ puntos de calidad. [Descarga](http://archive.ics.uci.edu/ml/machine-learning-databases/wine-quality/winequality-white.csv) ### Pima Indians Diabetes Dataset El dataset sobre diabetes de los indios Pima tiene como objetivo predecir la aparición de diabetes en un plazo de 5 años entre los indios Pima a partir de datos médicos. Se trata de un problema de clasificación binaria (2 clases). El número de observaciones para cada clase no está equilibrado. Hay $768$ observaciones con $8$ variables de entrada y $1$ variable de salida. Los valores faltantes se codifican con valores cero. Los nombres de las variables son los siguientes: `Número de embarazos`, `Concentración plasmática de glucosa a las 2 horas de una prueba oral de tolerancia a la glucosa`, `Presión arterial diastólica` (mm Hg), `Espesor del pliegue cutáneo del tríceps` (mm), `Insulina sérica en 2 horas` (mu U/ml), `Índice de masa corporal` (peso en kg/(altura en m)^2), `Función pedigrí de la diabetes`, `Edad` (años), `Variable de clase` ($0$ ó $1$). El rendimiento de referencia de la predicción de la clase más prevalente es una precisión de clasificación de aproximadamente el 65%. Los mejores resultados alcanzan una precisión de clasificación de aproximadamente el 77%. [Descarga](https://raw.githubusercontent.com/jbrownlee/Datasets/master/pima-indians-diabetes.csv) ### Sonar El dataset del sonar tiene como objetivo predecir si un objeto es una mina o una roca en función de la intensidad de los retornos del sonar en distintos ángulos. Se trata de un problema de clasificación binaria (2 clases). El número de observaciones para cada clase no está equilibrado. Hay $208$ observaciones con $60$ variables de entrada y $1$ variable de salida. Los nombres de las variables son los siguientes: `Retornos del sonar en diferentes ángulos`, ..., `Clase` (`M` para mina y `R` para roca) El rendimiento de referencia de la predicción de la clase más frecuente es una precisión de clasificación de aproximadamente el 53%. Los mejores resultados alcanzan una precisión de clasificación de aproximadamente el 88%. [Decarga](https://archive.ics.uci.edu/ml/machine-learning-databases/undocumented/connectionist-bench/sonar/sonar.all-data) ### Iris El dataset de flores de iris tiene como objetivo predecir la especie de flor a partir de mediciones de flores de iris. Se trata de un problema de clasificación multiclase. El número de observaciones para cada clase está equilibrado. Hay $150$ observaciones con $4$ variables de entrada y $1$ variable de salida. Los nombres de las variables son los siguientes (todas las medidas en cm): `Longitud del sépalo`, `Anchura del sépalo`, `Longitud de los pétalos`, `Anchura de los pétalos`, `Clase` (setosa, versicolor, virginica). El rendimiento de referencia de la predicción de la clase más prevalente es una precisión de clasificación de aproximadamente el 26%. [Descarga](../../Practicas/datasets/iris.csv) ### Abalón El dataset sobre el abalón (el molusco más caro del mundo, también llamado oreja de mar) tiene como objetivo predecir la edad del abalón a partir de medidas objetivas de los individuos. Se trata de un problema de clasificación multiclase, pero también puede plantearse como una regresión. El número de observaciones de cada clase no está equilibrado. Hay $4.177$ observaciones con $8$ variables de entrada y $1$ variable de salida. Los nombres de las variables son los siguientes: `Sexo` (`M`, `F`, `I`), `Longitud`, `Diámetro`, `Altura`, `Peso entero`, `Peso sin cáscara`, `Peso de las vísceras`, `Peso con cáscara`, `Anillos`. El rendimiento de referencia de la predicción de la clase más prevalente es una precisión de clasificación de aproximadamente el 16%. El rendimiento de referencia de la predicción del valor medio es un RMSE de aproximadamente 3,2 anillos. [Descarga](http://archive.ics.uci.edu/ml/machine-learning-databases/abalone/abalone.data) ### Semillas de trigo El dataset tiene como objetivo la predicción de especies a partir de medidas de semillas de distintas variedades de trigo. Se trata de un problema de clasificación multiclase (3 clases). El número de observaciones de cada clase está equilibrado. Hay $210$ observaciones con $7$ variables de entrada y $1$ variable de salida. Los nombres de las variables son los siguientes: `Superficie`, `Perímetro`, `Compacidad`, `Longitud del grano`, `Anchura del núcleo`, `Coeficiente de asimetría`, `Longitud del surco del grano`, `Clase` (1, 2, 3). El rendimiento de referencia de la predicción de la clase más frecuente es una precisión de clasificación de aproximadamente el 28%. [Descarga](http://archive.ics.uci.edu/ml/machine-learning-databases/00236/seeds_dataset.txt) ### Boston House Price El dataset tiene como objetivo predecir el precio de una casa en miles de dólares a partir de datos sobre la casa y su vecindario. Se trata de un problema de regresión. Hay $506$ observaciones con $13$ variables de entrada y $1$ variable de salida. Los nombres de las variables son los siguientes: * `CRIM`: tasa de delincuencia per cápita por ciudad. * `ZN`: proporción de suelo residencial zonificado para lotes de más de 25.000 pies cuadrados. * `INDUS`: proporción de acres comerciales no minoristas por ciudad. * `CHAS`: variable ficticia Charles River (= 1 si la zona linda con el río; 0 en caso contrario). * `NOX`: concentración de óxidos nítricos (partes por 10 millones). * `RM`: número medio de habitaciones por vivienda. * `AGE`: proporción de unidades ocupadas por sus propietarios construidas antes de 1940. * `DIS`: distancias ponderadas a cinco centros de empleo de Boston. * `RAD`: índice de accesibilidad a las autopistas radiales. * `TAX`: tipo del impuesto sobre bienes inmuebles por cada 10.000 dólares. * `PTRATIO`: ratio alumnos-profesor por ciudad. * `B`: 1000(Bk - 0,63)^2 donde Bk es la proporción de negros por ciudad. * `LSTAT`: % más bajo de la población. * `MEDV`: valor medio de las viviendas ocupadas por sus propietarios en miles de dólares. El rendimiento de referencia de la predicción del valor medio es un RMSE de aproximadamente 9,21 mil dólares. [Descarga](https://raw.githubusercontent.com/jbrownlee/Datasets/master/housing.data) ### Varios Algunos datasets adicionales que pueden utilizarse, por ejemplo, para clasificación con ID3, son: [Examen](../../Practicas/datasets/Examen.csv)
[Golf](../../Practicas/datasets/Golf.csv)
[Lentes de contacto](../../Practicas/datasets/Lentes.csv)
[Presión Arterial](../../Practicas/datasets/Presion.csv)
[Rutina Deportiva](../../Practicas/datasets/Rutina.csv)
[Coches](../../Practicas/datasets/cars.csv)
[Crédito](../../Practicas/datasets/credit.csv)
[Golf (con atributos numéricos)](../../Practicas/datasets/GolfNum.csv)
[Obesidad](../../Practicas/datasets/Obesity.csv)
[Calidad vino](../../Practicas/datasets/wine.csv) Algunos datasets para clusterización: [Blobs](../../Practicas/datasets/blob.csv)
[Sonar](../../Practicas/datasets/sonar.csv)