CSE 352 Spring 2003 Stony Brook |
Artificial Intelligence
Annie Liu Assignment 5 |
Handout A5 Mar. 11, 2003 Due Mar. 25 |
Programming with Logical Relations and Rules
Your task is to solve a number of problems using logical relations and rules and implement them using XSB, a well-known tabled Prolog implementation that happens to be developed at Stony Brook. :-) You can download XSB from xsb.sourceforge.net. Remember that programming assignments are to be done in pairs; if you didn't have a partner for previous assignments, you are encouraged to have one this time.
You should write down your code before you sit at the terminal. All your code should be put in one file and be well-commented or clearly self-explanatory. You should also provide code for testing your programs as automatically as possible and include instructions for demo/testing.
Submission
Submit a printout of the following items in class on the due date, preferably printed 2 pages per sheet.
Grading
This homework is worth 5% of the course grade. Exceptionally well-thought-out and well-written homeworks will receive appropriate extra credit. Partial solutions get partial credit, but if you only manage to write some of the components, you should test each of them and hand in the results of the test.
Problems
Given a graph, the transitive closure of its set of edges is the set of pairs (n1,n2) such that there is a path from n1 to n2 following the edges. We can use binary relation edge for the set of edges, and define relation path as follows.
path(X,Y) :- edge(X,Y). path(X,Y) :- path(X,Z), edge(Z,Y).Then, the query ?- path(X,Y) will return the transitive closure.
Suppose that, in addition to the graph, we are given a set of nodes as sources. You can use a unary relation for the given set of source nodes. You are asked to define, in two ways as described below, a unary relation reach such that reach(X) is true if and only if X is reachable from a source node following zero or more edges.
(a) Define the relation using path.
(b) Define the relation without using path.
Note that both programs can get into infinite loop and have repeated computations of the same goal, if run using naive backtracking, as described in lecture and in textbook. However, if you specify
:- table path/2. :- table reach/1.in XSB (the numbers 2 and 1 indicate the number of arguments of the relations), both will terminate and be very efficient.
Our "Solarlet" course database has relation course relating four items: a name, a lecturer, a time, and a place, where time is composed of a day, a starting time, and a finish time. That is, the relation is of the form course(Course,Lecturer,Time,Place), where Time is a compound object of the form time(Day,Start,Finish).
We can use rules to define particular relations of interest, such as lecturer, duration, teaches, and occupied below.
lecturer(Lecturer,Course) :- course(Course,Lecturer,Time,Place). duration(Course,Length) :- course(Course,Lecturer,time(Day,Start,Finish),Place), Length is Finish-Start. teaches(Lecturer,Day) :- course(Course,Lecturer,time(Day,Start,Finish),Place). occupied(Place,Day,Time) :- course(Course,Lecturer,time(Day,Start,Finish),Place), Start<=Time, Time<=Finish.
(a) Add rules defining the relations location(Course,
Building), busy(Lecturer,Time), and
cannot_meet(Lecturer1,Lecturer2).
(b) Possibly using relations from (1), define the relation
schedule_conflict(Time,Place,Course1,Course2).
Exercise 9.14 of textbook. This is for programming permutation sort and insertion sort. You are not required to write a quick sort, but if you do, you get upto 20% bonus for this assignment.
Exercise 9.15 of textbook. This is for algebraic simplification as well as symbolic differentiation as we did in Assignment 2. This kind of symbolic manipulation is much easier in Prolog.