Diferencias

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

--- introalg:taller09_9 [2009/06/01 01:46] – 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 ======
+===== Problemas "de la vida real" =====
 ==== Los Amigos de Mis Amigos ====
@@ Línea 196: / Línea 198: @@
 Funciona como queríamos!
-Ahora, 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, 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 ====
-==== Resolvemos con generalizaciones los ejercicios anteriores ====
+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 ====
-==== Nueve 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 ====