domingo, 31 de octubre de 2010

PROLOG - Horario de Clase

Lenguajes de Programación - Semana 9 - PUNTOS EXTRA

Se plantea el siguiente acertijo:

”Un alumno de ITS, debido al nerviosismo del primer día de clase, ha anotado el nombre de sus profesores (Elisa, Fernando y Carlos), las asignaturas que se imparten (Lógica, Programación y Matemáticas) y el día de la semana de las distintas clases (lunes, miércoles y viernes), pero sólo
recuerda que:
- La clase de Programación, impartida por Elisa, es posterior a la de Lógica
- A Carlos no le gusta trabajar los lunes, día en el que no se imparte Lógica
Ayudale a relacionar cada profesor con su asignatura, así como el día de la semana que se imparte
(Sabemos que cada profesor imparte una única asignatura y que las clases se dan en días diferentes)”


Analicemos el problema mentalmente:

Tenemos 3 materias:

Lógica
Programación
Matemáticas


Tenemos 3 dias:

Lunes
Miércoles
Viernes


Tenemos 3 maestros:

Elisa
Carlos
Fernando


Con base a la redacción del problema tenemos las siguientes proposiciones:

Elisa da programación.
Carlos no trabaja el lunes.
El lunes no hay clase se Lógica.
Programación se imparte cualquier día posterior al Lunes.


Para acomodar los días en que se imparte cada materia sabemos solamente que los lunes no hay lógica, como programacón se da el día posterior a lógica entonces no puede impartirse el miércoles , y aunque necesitamos un día anterior ese día anterior no puede ser el lunes, entonces las materias se imparten en el siguiente orden:

Matemáticas los Lunes
Lógica los Miércoles
Programación los Viernes


Como Carlos no trabaja los lunes entonces solo le queda el miércoles para impartir clase porque Elisa le gan&ocute; los viernes, a Fernando no le qued&ocute; de otra mas que dar matemáticas. Entonces la respuesta al problema es:

Fernando da Matemáticas los Lunes
Carlos da Lógica los Miércoles
Elisa da Programación los Viernes


Analicemos el problema en PROLOG:

Primero convertimos cada una de las proposiciones en hechos:

materia(logica).
materia(programacion).
materia(matematicas).
maestro(elisa).
maestro(fernando).
maestro(carlos).
dia(lunes).
dia(miercoles).
dia(viernes).


Tendremos 3 formatos de respuesta diferentes:

imparte(X,Y) "Profesor X imparte la materia Y"
trabaja(X,Z) "Profesor X trabaja el día Z"
clase(Y, Z) "Hay clase Y el dia Z"

Tenemos la siguientes proposiciones predefinidas:

imparte(elisa, programacion). "Elisa imparte programacón"

Entonces para saber que maestro va el resto de las materias aplicaremos la siguiente regla:

imparte(X, Y) :- maestro(X), X\=elisa, materia(Y), imparte(elisa,YA), YA\=Y. "Sera verdad si hay un maestro X, a excepcion de Elisa; y existe una materia Y. Sacamos a Elisa de este conjunto porque ya sabemos que clase imparte, además recursivamente quitaremos el curso que imparte Elisa."

Sabemos tambien que Carlos ira cualquier día que no sea lunes, entonces:

trabaja(carlos, Z) :- dia(Z), Z\=lunes. " Carlos trabaja algún día Z, a excepción del Lunes"

La regla general queda:

trabaja(X, Z) :- maestro(X), X\=carlos, dia(Z), Z\=miercoles. "Sera verdad si hay un maestro X, quitando a Carlos, un dia Y. Quitamos a Carlos porque ya sabemos que lunes no va y los miercoles porque Carlos no va lunes y el viernes es de Elisa"

Tambien tenemos conocimento de que la clase de lógica no se da los lunes, entonces:

clase(logica, Z) :- dia(Z), Z\=lunes, Z\=viernes. "Sera verdad que logica se imparte el dia Z, si ese dia no es lunes o viernes; porque el lunes no aplica y el viernes tampoco puesto que sabemos hay una clase delante de ella"

clase(programacion, Z) :- dia(Z), Z\=lunes, clase(logica, ZA), ZA\=Z. "Sera verdad que programación se da un día Z, si ese día no es lunes; porque sabemos que hay una clase anterior a ella. Recursivamente quitamos el día en el que lógica puede impartirse"

La regla general queda:

clase(Y, Z) :- materia(Y), Y\=logica, Y\=programacion, clase(logica, ZA), clase(programacion, ZB), dia(Z), ZA\=Z, ZB\=Z. "Sera verdad si hay una materia Y que no sea lógica o programación, y cualquier día de la semana que no sean los días en que se imparte lógica y programación"

PROGRAMA COMPLETO

materia(logica).
materia(programacion).
materia(matematicas).
maestro(elisa).
maestro(fernando).
maestro(carlos).
dia(lunes).
dia(miercoles).
dia(viernes).
imparte(elisa, programacion).
imparte(X, Y) :- maestro(X), X\=elisa, materia(Y), imparte(elisa, YA), YA\=Y.
trabaja(carlos, Z) :- dia(Z), Z\=lunes.
trabaja(X, Z) :- maestro(X), X\=carlos, dia(Z), Z\=miercoles.
clase(programacion, Z) :- dia(Z), Z\=lunes, clase(logica, ZA), ZA\=Z.
clase(logica, Z) :- dia(Z), Z\=lunes, Z\=viernes.
clase(Y, Z) :- materia(Y), Y\=logica, Y\=programacion, clase(programacion, ZA), clase(logica, ZB), dia(Z), ZA\=Z, ZB\=Z.


Abrimos un archivo en emacs y lo llamaremos "horario.pro" (en terminal tecleamos: emacs -nw horario.pro ), tecleamos el código que les acabo de mostrar y guardamos todo.
Despues procedemos a abrir el interprete SWI-PROLOG:


Posteriormente cargamos el código que acabmos de guardar:


** OPCIONALMENTE PODEMOS TECLEAR LA OPCION listing. PARA VER LA CARGA DEL ARCHIVO, YO LA OMITO PORQUE LA IMAGEN ES MUY LARGA PARA ESTA ENTRADA.

Ahora evaluamos el problema, en este caso hay que concatenar todas nuestras preguntas para que se evalún juntas, si las ponemos separadas solo se nos mostraran todas las combinaciones de maestros, días y clases, pueden probarlo si quieren; asi evaluaremos toda la pregunta completa:

imparte(X,Y),trabaja(X,Z),clase(Y,Z).

Y este es el resultado:


Como ven, el resultado es el horario armado tal como la respuesta que obtuvimos analíticamente.

PD: La "a" al lado de la respuesta de Elisa la teclee yo, sirve para mostrar toda la lista de resultados sin tener que aplanar la tecla ";" para listar respuesta tras respuesta.

SALUDOS!!! ^_^

4 comentarios:

  1. juan carlos ya con este programa pude entender mejor lo que hicimos hace rato :) graciaas por ayudarme :)

    ResponderEliminar
  2. Hola Juan Carlos, muy bien explicado el problema. Me quedó una duda como pondrías en este caso que solo se imparte una materia por maestro y que no se puede repetir o no es necesario poner esto?

    Saludos

    ResponderEliminar
  3. El programa por si solo va deduciendo cual materia le corresponde a cada maestro, por ejemplo, a Elisa ya se le asigno que da programacion, entonces el programa solo buscara cual dia asignarle en la clasula "trabaja" y con la ayuda de la clausula "clase", juntas asignan que dia cada maestro puede trabajar y que clase se puede dar cada dia. Para evitar las repeticiones por eso se meten codigos recursivos, si te fijas en las reglas clase(Y,Z) utilizo 2 recursiones, esto comprueba que el dia que se asignara a una clase no se este utilizando ya; y en la regla imparte(X,Y) la utilizo para evitar asignar la clase de elisa que a otro profesor.

    ResponderEliminar