Ciencias de la Computación FAMAF

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
===== Parcial 1 (recuperatorio) =====

=== ejercicio 1 (prolog, no recursivo) ===

  * Dada la siguiente base de conocimiento en prolog, que especifica tres ingredientes necesarios para cocinar un platillo y los que tengo en la casa, crear las reglas necesarias para saber si podremos cocinar un platillo.
<code>
ingredientes(tortilla,huevos,aceite,papa).
ingredientes(pizza,prepizza,salsa,queso).
ingredientes(ensalada,lechuga,tomate,aceitunas).
tengo(huevos).
tengo(aceite).
tengo(papa).
</code>

  Ejemplo: ''puedoCocinar(tortilla). true. puedoCocinar(pizza). false.''

== solución ==
<code>
puedoCocinar(X) :- 
   ingredientes(X,A,B,C) ,
   tengo(A) , tengo(B) , tengo(C).
</code>

=== ejercicio 2 (haskell, no recursivo) ===

  * Definir la función ''sumaPar :: (Int,Int) -> Bool'', que, dado un par de enteros, devuelve true si la suma de ambos es par. 

  Ejemplo: ''sumaPar (2,5) = false.''

== solución ==
<code>
sumaPar :: (Int,Int) -> Bool
sumaPar (x,y) = mod (x+y) 2 == 0
</code>

=== ejercicio 3 (recursivo) ===

  * Definir la función ''sumaMayoresQueN :: Int -> [Int] -> Int'', que, dado un entero ''n'' y una lista de enteros, devuelve la suma de todos los elementos de la lista mayores que ''n''.

  Ejemplo: ''sumaMayoresQueN 3 [3,5,2,4] = 9''.

== solución ==
<code>
sumaMayoresQueN :: Int -> [Int] -> Int
sumaMayoresQueN n [] = 0
sumaMayoresQueN n (x:xs) | x > n     = x + sumaMayoresQueN n xs
                         | otherwise = sumaMayoresQueN n xs
</code>

===== Parcial 2 =====

=== ejercicio 1 (usando generalizaciones) ===

  * Usando ''map'', ''filter'' y ''foldr'', definir la función ''porCientoMayorQue :: Int -> Int -> [Int] -> Int'', que dado un número ''n'', otro número ''m'' y una lista de enteros, devuelve la suma de todos los porcentajes mayores que ''n''. **Ayuda:** definir una función auxiliar ''PorCiento :: Int -> Int -> Int'' que use la función ''div'' que devuelve la división entera de dos enteros.

  Ejemplo: porCientoMayorQue 10 50 [22,4,30,10] = 26.

== solución ==
<code>
porCientoMayorQue :: Int -> Int -> [Int] -> Int
porCientoMayorQue n m xs = foldr (+) 0 ( filter (>n) ( map (porCiento m) xs ) )
</code>

=== resolviendo problemas "de la vida real" ===

  * Definir la parte del sistema de préstamos de una biblioteca que determina si un usuario puede tomar prestado un libro o, si ya está prestado, reservarlo, cumpliendo las siguientes condiciones:
      * un usuario puede tener en préstamo un máximo de seis libros simultáneamente
      * un usuario puede tener un máximo de tres reservas
      * un libro se puede prestar si no está en préstamo ni está reservado por otro usuario

Para plantear el problema, deben definir dos funciones (o predicados) con la siguiente semántica:
<code>
puedeTomarPrestado -> usuario -> libro -> Bool
puedeReservar -> usuario -> libro -> Bool
</code>

Para plantear el problema en haskell, deben definir las dos funciones principales y la estructura de funciones auxiliares, incluyendo sus signaturas de tipos. Fíjense que eso incluye también definir las estructuras de datos que representarán los libros, los usuarios y cómo se registran los préstamos.

Para plantear el problema en prolog, deben definir los hechos y las reglas. Fíjense que eso incluye definir los predicados para libros, usuarios y préstamos.

Deben plantear el problema en los dos lenguajes, y resolverlo completamente en uno de los dos.

== solución ==

En este problema se pueden plantear muy distintas soluciones, ya que el problema es bien complejo y se puede ver de muchas formas.

Una posible solución en prolog:
<code>
%% definimos los usuarios como un predicado con tres argumentos: 
  %% el nombre del usuario (o su identificador si el nombre no alcanza para hacerlos únicos)
  %% el número de libros que tiene en préstamo
  %% el número de libros que tiene reservado
%% dejamos para otra regla la actualización de esos números 
 % cuando alguien toma prestado o reserva un libro

usuario(pepe,6,3).
usuario(maría,5,2).
usuario(carla,6,1).
usuario(esteban,0,0).
usuario(marisol,3,3).

%% definimos los libros como un predicado con tres argumentos:
  %% el título del libro (o su identificador si el nombre no alcanza para hacerlos únicos)
  %% si está prestado o no
  %% si está reservado o no
libro("la isla del tesoro",pres,nores).
libro("el lazarillo de tormes",nopres,nores).
libro("los hombres que no amaban a las mujeres",pres,res).
libro("la chica que soñaba con una cerilla y un bidón de gasolina",nopres,res).

%% después de los hechos, definimos las reglas
puedeTomarPrestado(Usuario,Libro) :-
  usuario(Usuario,Prestados,_),
  libro(Libro,nopres,nores),
  Prestados < 6.

puedeReservar(Usuario,_) :-
  usuario(Usuario,_,Reservados),
  Reservados < 3.
</code>

Una posible solución en haskell:
<code>
puedeTomarPrestado :: (String,Int,Int) -> (String,Bool,Bool) -> Bool
puedeTomarPrestado (_,lp,_) (_,p,r) = lp < 6 && not(p) && not(r)

puedeReservar :: (String,Int,Int) -> (String,Bool,Bool) -> Bool
puedeReservar (_,_,lr) _ = lr < 3
</code>

=== ejercicio extra (para ayudar a aprobar) ===

**Bonus Track:** Definir la función ''tieneSegmentoOrdenado :: Int -> [Int] -> Bool'', que dado un entero ''n'' y una lista de enteros, determina si la lista tiene un segmento de longitud mayor o igual a ''n'' cuyos elementos están ordenados de menor a mayor.

  Ejemplo: tieneSegmentoOrdenado 3 [5,1,4,11,3,2] = true.
  	   tieneSegmentoOrdenado 4 [5,1,4,11,3,2] = false.

== solución ==

Hemos planteado una posible solución que va recorriendo la lista y va contando cuántos elementos encuentra que estén ordenados de menor a mayor. Cuando el número de elementos ordenados alcanza el número de elementos que pedimos que tenga el segmento, la función termina y devuelve ''True''. Cuando encuentra un elemento que es menor al elemento anterior, deja de contar, es decir, pone el contador en ''1''. Cuando llega a la lista vacía devuelve ''False''. 

La función principal es ''tieneSegmentoOrdenado'', que lo único que hace es añadir el argumento contador y pasarle todos los argumentos a la función ''cuantosOrdenados''. La función ''cuantosOrdenados'' va comprobando en cada momento si hemos alcanzado la longitud de segmento que estábamos buscando, con la guarda ''c >= n''. Fíjense que si la longitud que buscamos es 0 o 1, nos va a devolver ''True'' sin hacer ningún llamado a la función recursiva. Si no, llama a la función recursiva para que recorra la lista y vaya contando la longitud de los segmentos ordenados que encuentra. 

La función recursiva es ''cuentaOrdenado'', que va recorriendo la lista. Si encuentra una lista vacía o una lista con un solo elemento, devuelve ''False'', porque llegó al final de la lista sin poder encontrar el segmento que buscaba. Para listas de por lo menos dos elementos, los compara y si el primero es menor que el segundo, entonces suma uno al contador y llama a la función ''cuantosOrdenados'', que comprueba si el segmento que vamos encontrando ya es de la longitud que se pedía en el argumento. Si es así, la función termina con ''True'', si no, vuelve a llamar a ''cuentaOrdenado''. Si el primer elemento es mayor que el segundo, entonces el contador vuelve a su estado inicial, 1, es decir, empieza a contar de nuevo.

<code>
tieneSegmentoOrdenado :: Int -> [Int] -> Bool
tieneSegmentoOrdenado n xs = cuantosOrdenados 1 n xs

cuantosOrdenados :: Int -> Int -> [Int] -> Bool
cuantosOrdenados c n xs | c >= n    = True
                        | otherwise = cuentaOrdenado c n xs

cuentaOrdenado :: Int -> Int -> [Int] -> Bool
cuentaOrdenado c n [] = False
cuentaOrdenado c n [x] = False
cuentaOrdenado c n (x:y:xs) | x <= y    = cuantosOrdenados (c+1) n (y:xs)
                            | otherwise = cuentaOrdenado 1 n (y:xs)
</code>