Diferencias

Muestra las diferencias entre dos versiones de la página.

--- introalg:taller09_9 [2009/05/31 18:03] – creado laura
+++ introalg:taller09_9 [2018/08/10 03:03] (actual) – editor externo 127.0.0.1
@@ Línea 1: / Línea 1: @@
 ====== Resolviendo problemas complejos ======
-Empecemos con nuestro ejercicio estrella: recomendar amigos en una red social. En el día anterior especificamos el problema a alto nivel, es decir, distinguimos sus diferentes partes pero no entramos en detalle sobre cómo se podrían implementar cada una de estas partes. Repasemos qué era lo que tenía que hacer el programa:
+===== Problemas "de la vida real" =====
+==== Los Amigos de Mis Amigos ====
+Empecemos con nuestro ejercicio estrella: recomendar amigos en una red social. En el día anterior especificamos el problema a alto nivel, es decir, distinguimos sus diferentes partes pero no entramos en detalle sobre cómo se podrían implementar cada una de estas partes. Repasemos qué era lo que tenía que hacer el programa, y añadamos de paso un par de funcionalidades más ;-) :
   - obtener la lista de todos los amigos de los amigos de la persona a quien queremos recomendar nuevos amigos (llamémosle ''p''). Para eso necesitaremos la función ''losAmigosDeMisAmigos :: [Int] -> [(Int,String,[Int])] -> [Int]'', que se puede armar usando la función auxiliar ''listaDeAmigos :: Int -> [(Int,String,[Int])] -> [Int]''.
+  - quedarnos solamente con los amigos que son amigos por lo menos de dos amigos de ''p'', es decir, descartar los que son amigos solamente de uno de los amigos de ''p''.
+  - eliminar duplicados de esa lista. Fíjense que este paso no podemos hacerlo antes porque si no no podríamos detectar cuáles son los amigos que son amigos por lo menos de dos amigos de ''p''.
   - descartar de esa lista todos los que ya son amigos de ''p'', es decir, que ya están en la lista de amigos de ''p''. Para eso necesitaremos la función ''filtrarNoEstanEnLista :: [Int] -> [Int] -> [Int]''.
   - descartar de esa lista a ''p''.
-  - quedarnos solamente con los amigos que son amigos por lo menos de dos amigos de ''p'', es decir, descartar los que son amigos solamente de uno de los amigos de ''p''. Para eso necesitaremos el predicado ''existe2'', que se aplicará mediante un filtro.
+  - asignar el nombre a cada una de las personas que recomendamos, de las cuales de momento sólo conocemos su número identificador.
 La función principal ''recomendarNuevosAmigos'' se puede definir ahora como una combinación de todas estas funciones auxiliares, por ejemplo, de la siguiente manera:
 <code>
-recomendarNuevosAmigos (id,n,misamigos) directorio = filter existe2 ( filter (noEs id) ( filtrarNoEstanEnLista misamigos ( losAmigosDeMisAmigos misamigos directorio ) ) )
+recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [(String,Int)]
+recomendarNuevosAmigos (id,n,misamigos) directorio =
+  asignarNombre directorio (
+      filter (noEs id) (
+   	  filtrarNoEstanEnLista misamigos (
+	     eliminarDuplicados (
+	        filtrarExiste2 (
+		   losAmigosDeMisAmigos misamigos directorio
+                )
+             )
+         )
+      )
+   )
 </code>
-Ahora lo que tenemos que hacer es desarrollar cada una de las partes que hemos especificado, por separado.
+Fíjense que si escribimos la función indentada, podremos comentar las partes que todavía no hayamos desarrollado y probar solamente las que ya hemos desarrollado, pero teniendo en todo momento a la vista la estructura de alto nivel del programa. Fíjense que en algunos casos, si comentamos algunas partes de la función, puede cambiar la signatura de tipos.
-Y cómo sería este mismo problema en prolog? Vamos a tratar de aplicar la misma aproximación: primero vemos el problema a alto nivel, nos damos cuenta de cuáles son las diferentes partes del problema y cómo están relacionadas entre ellas, y después pasamos a desarrollar cada una de estas partes independientemente.
+Ahora lo que tenemos que hacer es desarrollar cada una de las partes que hemos especificado, por separado. Vamos a ver que muchas de estas partes son filtros, pero con algunas diferencias con los filtros estándares, lo que hace difícil que podamos usar la generalización //filter//.
+En primer lugar, vamos a desarrollar la subfunción (o //subrutina//) para crear una lista con todas las personas que son amigas de mis amigos. Como está especificado en la definición de alto nivel de la función principal, esta subfunción va a trabajar con la lista de los identificadores de mis amigos y el directorio de todas las personas que hay en la red social, y va a devolver una lista con los identificadores de los amigos de mis amigos. La signatura de tipos sería como sigue:
+<code>
+losAmigosDeMisAmigos :: [Int] -> [(Int,String,[Int])] -> [Int]
+</code>
+Y la función se podría definir como sigue:
+<code>
+losAmigosDeMisAmigos [] _ = []
+losAmigosDeMisAmigos (a:amigos) directorio = ( listaAmigos a directorio ) ++ losAmigosDeMisAmigos amigos directorio
+</code>
+Fíjense que estamos usando una función auxiliar, es decir, otra subrutina: ''listaAmigos''. Esta función encuentra la lista de los amigos de una persona en el directorio, por lo tanto, toma como argumentos el identificador de la persona y el directorio, y devuelve una lista con los identificadores de los amigos de esta persona. Se podría definir como sigue:
+<code>
+listaAmigos :: Int -> [(Int,String,[Int])] -> [Int]
+listaAmigos _ [] = []
+listaAmigos a ((id,n,amigos):xs) | id == a   = amigos
+                                 | otherwise = listaAmigos a xs
+</code>
+Fíjense que esta función tiene una estructura semejante a un filtro pero con dos diferencias: el predicado que se evalúa trabaja con subpartes de la cabeza de la lista. Ademá, en el caso positivo se corta la recursividad, ya que una vez encontrada la lista de amigos de la persona no necesitamos seguir buscando.
+Ahora que ya tenemos esto, podemos probar una parte de la función principal, comentando el resto y cambiando la signatura de tipos:
+<code>
+--recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [(String,Int)]
+recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [Int]
+recomendarNuevosAmigos (id,n,misamigos) directorio =
+--  asignarNombre directorio (
+--      filter (noEs id) (
+--   	  filtrarNoEstanEnLista misamigos (
+--	     eliminarDuplicados (
+--	        filtrarExiste2 (
+		   losAmigosDeMisAmigos misamigos directorio
+--                )
+--             )
+--         )
+--      )
+--   )
+</code>
+Ahora esta función nos devolverá la lista de todos los amigos de mis amigos. Por ejemplo:
+<code>
+Main> recomendarNuevosAmigos (2,"b",[1,3]) [(1,"a",[2,3,4]),(2,"b",[1]),(3,"c",[1,2,4]),(4,"d",[2,3])]
+[2,3,4,1,2,4]
+</code>
+También podríamos comentar toda la función principal, y probar solamente las subrutinas, para comprobar que hacen lo que esperamos que hagan:
+<code>
+Main> listaAmigos 3 [(1,"a",[2,3,4]),(2,"b",[1]),(3,"c",[1,2,4]),(4,"d",[2,3])]
+[1,2,4]
+</code>
+<code>
+Main> losAmigosDeMisAmigos [3,4] [(1,"a",[2,3,4]),(2,"b",[1]),(3,"c",[1,2,4]),(4,"d",[2,3])]
+[1,2,4,2,3]
+</code>
+Sigamos ahora con otra parte de la función principal. Vamos a definir la subrutina que nos permite quedarnos únicamente con las personas que aparecen **por lo menos** dos veces en la lista de amigos de mis amigos. Como definimos en la función principal, esta función toma el directorio y la lista de amigos de mis amigos resultante de la subrutina que recién acabamos de definir, y nos devuelve una lista que contiene solamente los identificadores de las personas que ocurren por lo menos dos veces en la lista. Por lo tanto, es muy parecido a un filtro, pero con una diferencia: el predicado que se evalúa toma dos argumentos. Por esta razón no podemos usar la generalización //filter//.
+<code>
+filtrarExiste2 :: [Int] -> [Int]
+filtrarExiste2 [] = []
+filtrarExiste2 (x:xs) | existe2 x (x:xs) = x : filtrarExiste2 xs
+                      | otherwise        =     filtrarExiste2 xs
+</code>
+Vemos que para definir ''filtrarExiste2'' necesitamos definir el predicado ''existe2'', que a su vez necesita del predicado ''existe1'', tal como los definimos acá:
+<code>
+existe2 :: Int -> [Int] -> Bool
+existe2 a [] = False
+existe2 a (x:xs) | a == x     = existe1 a xs
+                         | otherwise = existe2 a xs
+existe1 :: Int -> [Int] -> Bool
+existe1 a xs = elem a xs
+</code>
+Ahora que ya tenemos definida esta parte de la función, vamos a probarla. Podemos descomentar la parte de la función principal que usa esta subfunción:
+<code>
+--recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [(String,Int)]
+recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [Int]
+recomendarNuevosAmigos (id,n,misamigos) directorio =
+--  asignarNombre directorio (
+--      filter (noEs id) (
+--   	  filtrarNoEstanEnLista misamigos (
+--	     eliminarDuplicados (
+	        filtrarExiste2 (
+		   losAmigosDeMisAmigos misamigos directorio
+                )
+--             )
+--         )
+--      )
+--   )
+</code>
+Y probamos la función principal:
+<code>
+recomendarNuevosAmigos (2,"b",[1,3]) [(1,"a",[2,3,4]),(2,"b",[1]),(3,"c",[1,2,4]),(4,"d",[2,3])]
+[2,4]
+</code>
+También podemos probar las subfuncines por separado:
+<code>
+Main> existe1 3 [1,2,3]
+True
+Main> existe2 3 [1,2,3]
+False
+Main> existe2 3 [1,2,3,3]
+True
+Main> filtrarExiste2 [1,2,3,3]
+[3]
+</code>
+Seguimos desarrollando otra subfunción: la que elimina los elementos duplicados. También se trata de un filtro, ya que solamente se queda con un elemento si hay más de uno igual, pero como el predicado que se aplica es complejo, tampoco podemos usar la generalización //filter//. Veamos cómo sería:
+<code>
+eliminarDuplicados :: [Int] -> [Int]
+eliminarDuplicados [] = []
+eliminarDuplicados (x:xs) | elem x xs =     eliminarDuplicados xs
+                          | otherwise = x : eliminarDuplicados xs
+</code>
+Probamos la subfunción y vemos que funciona bien:
+<code>
+Main> eliminarDuplicados [1,2,3,1,3,4,5,5]
+[2,1,3,4,5]
+</code>
+La siguiente subfunción que queremos desarrollar es la que filtra las personas de la lista de posibles recomendaciones que ya están en la lista de mis propios amigos. De vuelta se trata de un filtro algo más complejo:
+<code>
+filtrarNoEstanEnLista :: [Int] -> [Int] -> [Int]
+filtrarNoEstanEnLista [] xs = xs
+filtrarNoEstanEnLista xs [] = []
+filtrarNoEstanEnLista (x:xs) ys = filtrarNoEstanEnLista xs (filter (/=x) ys)
+</code>
+Ahora queremos filtrar a una persona especial: yo mismo! esto podríamos hacerlo incorporándome a la lista de mis propios amigos, o también mediante un filtro simple, esta vez sí! Lo vemos así en la función principal: ''filter (noEs id) LISTARECOMENDADOS''. Sólo tenemos que definir el predicado ''noEs'':
+<code>
+noEs :: Int -> Int -> Bool
+noEs a b = a /= b
+</code>
+Ahora ya tenemos una lista con los identificadores de las personas que queremos recomendar como posibles amigos a alguien. Se trata de personas que son amigos de por lo menos dos de sus amigos pero de las cuales todavía no es amigo él mismo.
+Finalmente, sólo nos queda una cuestión estética. Hasta el momento hemos estado trabajando con los identificadores de las personas, pero la información final que vamos a querer mostrarle a nuestro usuario será no solamente el identificador, sino también el nombre, porque resulta mucho más agradable para una persona. Los identificadores son útiles para las máquinas, pero no para las personas. Por esta razón vamos a querer asociar a cada uno de los identificadores de las personas que queremos recomendar a su nombre. Para ello vamos a consultar la información del directorio una vez más, junto con la lista de identificadores de personas recomendadas, de la siguiente forma:
+<code>
+asignarNombre :: [(Int,String,[Int])] -> [Int] -> [(String,Int)]
+asignarNombre _ [] = []
+asignarNombre directorio (x:xs) = ( (encuentraNombre x directorio), x ) : asignarNombre  directorio xs
+</code>
+La función auxiliar ''encuentraNombre'' se definiría así:
+<code>
+encuentraNombre :: Int -> [(Int,String,[Int])] -> String
+encuentraNombre x [] = "el usario no se encuentra en el directorio"
+encuentraNombre x ((id,nombre,amigos):xs) | id == x   = nombre
+                                          | otherwise = encuentraNombre x xs
+</code>
+Ahora sí, podemos cambiar la signatura de tipos de la función principal según la habíamos pensado inicialmente:
+<code>
+recomendarNuevosAmigos :: (Int,String,[Int]) -> [(Int,String,[Int])] -> [(String,Int)]
+</code>
+Descomentar todas las líneas y probarla:
+<code>
+recomendarNuevosAmigos (2,"b",[1,3]) [(1,"a",[2,3,4]),(2,"b",[1]),(3,"c",[1,2,4]),(4,"d",[2,3])]
+[("d",4)]
+</code>
+Funciona como queríamos!
+Ahora, cómo sería este mismo problema en prolog? Mucho pero mucho más sencillo que en haskell. Veamos:
+<code>
+recomendar(X,NuevoAmigo) :-
+  amigo(X,Amigo1), amigo(X,Amigo2), not(Amigo1 = Amigo2),
+  amigo(Amigo1,NuevoAmigo), amigo(Amigo2,NuevoAmigo),
+  not(amigo(X,NuevoAmigo)), not(X = NuevoAmigo).
+amigo(pedro,maría).
+amigo(pedro,juan).
+amigo(maría,pedro).
+amigo(maría,clara).
+amigo(maría,romina).
+amigo(juan,pedro).
+amigo(juan,clara).
+amigo(clara,maría).
+amigo(clara,juan).
+amigo(romina,maría).
+</code>
+Quizás pueden empezar a reconsiderar sus opiniones sobre prolog ;)
+==== Cálculos numéricos de bases de datos ====
+Habíamos propuesto en el día anterior una función que calcule el porcentaje de estudiantes que aprobó o promocionó la materia, definiendo una función ''porcentajeEstudiantes :: (Int -> Bool -> Bool) -> [(String,Int,Int,Int,Bool,Bool)] -> Int''. El primer argumento es un predicado que determina si una media de teórico práctico y una media de taller promociona, aprueba o desaprueba. El segundo argumento es la lista de estudiantes, representados como seis-uplas con su nombre, la nota de cada uno de los tres parciales y dos booleanos que representan la aprobación o desaprobación de cada uno de los parcialitos de taller. El resultado es el porcentaje de estudiantes que aprobaron o promocionaron la materia, dependiendo del predicado que pongamos como primer argumento.
+Como en el caso anterior, definimos una función principal y varias funciones auxiliares o subrutinas:
+<code>
+porcentajeEstudiantes :: (Int -> Bool -> Bool) -> [(String,Int,Int,Int,Bool,Bool)] -> Int
+porcentajeEstudiantes test estudiantes =
+		      div
+		      	   ( 100 * ( length ( filter (estudiantePositivo test) estudiantes ) ) )
+			   ( length estudiantes )
+aprueba, promociona :: Int -> Bool -> Bool
+aprueba n _ = n > 4
+promociona n p = n > 7 && p
+estudiantePositivo :: (Int -> Bool -> Bool) -> (String,Int,Int,Int,Bool,Bool) -> Bool
+estudiantePositivo test (nombre,p1,p2,p3,t1,t2) = test ( div (p1+p2+p3) 3 ) ( t1 || t2 )
+</code>
+Probamos la función:
+<code>
+Main> porcentajeEstudiantes aprueba [("a",8,9,8,True,True),("b",1,1,1,False,False),("c",5,6,4,True,False)]
+
+Main> porcentajeEstudiantes promociona [("a",8,9,8,True,True),("b",1,1,1,False,False),("c",5,6,4,True,False)]
+
+</code>
 ==== Central de turnos ====
+Veamos ahora otro problema. Queremos realizar un sistema de ayuda a una central de turnos. Este sistema dirá si se le puede asignar un turno a un paciente con un determinado médico para un determinado día, siguiendo las siguientes premisas:
+  - el paciente no tiene ningún turno asignado para el mismo día a la misma hora.
+  - el paciente no tiene ningún turno asignado con ningún especialista de la misma especialidad para la que pide turno.
+  - el médico para el que pide turno no tiene turno asignado con ningún otro paciente para el mismo día a la misma hora.
+Este tipo de problema se define muy bien en prolog, **con una sola regla** que expresa exactamente lo que acabamos de decir acá arriba. Traten de expresar esa regla, y vean qué turnos se pueden asignar y qué turnos no se pueden asignar si tenemos los siguientes turnos ya asignados y las siguientes especialidades (esta sería nuestra base de conocimiento):
+<code>
+turno(celia,rivas,(6,30,8)).
+turno(celia,zilvetti,(7,14,11)).
+turno(tomás,rivas,(7,11,10)).
+turno(tomás,pérez,(8,11,10)).
+turno(tomás,schuster,(9,11,10)).
+turno(lidia,zilvetti,(7,14,10)).
+turno(lidia,schuster,(9,11,11)).
+turno(esteban,rivas,(7,1,9)).
+especialidad(rivas,oftalmologia).
+especialidad(smith,oftalmologia).
+especialidad(zilvetti,ginecología).
+especialidad(román,ginecología).
+especialidad(pérez,endocrinología).
+especialidad(schuster,clínico).
+</code>
+La regla que podríamos hacer sería algo más o menos así:
+<code>
+valido(Paciente,Medico,(Mes,Dia,Hora)) :-
+  not((turno(Paciente,OtroMedico,_) ,
+       especialidad(OtroMedico,X) , especialidad(Medico,X))) ,
+  not(turno(Paciente,_,(Mes,Dia,Hora))),
+  not(turno(_,Medico,(Mes,Dia,Hora))).
+</code>
+==== Otros problemas "de la vida real" para resolver ====
+  * Comprobar si podemos cocinar un determinado platillo dados los ingredientes necesarios para el platillo y los ingredientes que tenemos en la heladera. Se puede ampliar con los utensilios, las técnicas, e implicaciones entre ellos (p.ej., si tenemos que usar la técnica "montar a punto de nieve" necesitamos el utensilio "batidora").
+  * Crear un sistema de alertas que cuando se produce un insumo, chequea en la base de datos cuánta reserva queda de ese insumo y, si la reserva está por debajo de un mínimo, devuelve un mensaje diciendo que hay que comprar más de ese insumo.
+  * Hacer un programa **no muy largo** que, dado un animal, nos diga si es ovíparo o vivíparo, si vive en la tierra, en el agua o en el aire, si come carne o vegetales, etc. Tratar excepciones como "delfín" (mamífero marino), "nutria" (mamífero de agua dulce) o "guppi" (pez vivíparo).
+===== Problemas clásicos de programación recursiva =====
+==== Máximo Común Divisor ====
+Definir en haskell y en prolog una función que nos dé el máximo común divisor (mcd) de dos números. Aprovechen el hecho de que se trata de lenguajes declarativos y traten de definir el mcd como **lo que es**: el mayor número por el que la division entera de cualquiera de los dos números devuelve 0 como resto.
+Fíjense que puede haber suerte y que uno de los dos números sea ya el mcd, ese sería un caso base. Tenemos entonces dos casos base: que el primer número sea el mcd, o que lo sea el segundo. Si no es ninguno de esos casos, tenemos el caso recursivo...
+==== N Reinas ====
+En el problema de las n reinas tenemos que encontrar una forma de colocar n reinas en un tablero de n x n sin que se estén amenazando (por ejemplo, ocho reinas en un tablero de ajedrez).
+==== Misioneros y Caníbales ====
+En el problema de los misioneros y los caníbales, tenemos tres misioneros y tres caníbales que tienen que cruzar un río usando un bote que sólo puede transportar hasta dos personas. En ningún momento pueden quedar más caníbales que misioneros en ningún lado del río, porque en ese caso los caníbales se comerían a los misioneros. Además, el bote no puede cruzar el río sin personas a bordo.
+==== Resolvemos con generalizaciones los ejercicios de clases anteriores ====