Department of Computer Science
CPS 721: An Introduction to Artificial Intelligence Sample Midterm Test #1
NOT FOR DISTRIBUTION
Copyright By PowCoder代写 加微信 powcoder
(C) COPYRIGHT:
THIS EXAM CANNNOT BE SHARED WITHOUT EXPLICIT PERMISSION
Do not turn this page over until you are asked to do so.
Time: 1 hour and 40min.
Total marks: 20
Keep your Ryerson photo ID card on your desk.
Closed Book: aids are not allowed, all electronic devices must be turned off, use of scrap paper is not allowed.
Do not detach the pages of this test. Please print your answers legibly. Good luck!
Last name:
First Name:
Student #:
Section #:
1 (2 points). Assume that you are given a simple collection of atomic statements about bookstores, using the following predicates:
hasBook(Bookstore,Author,Title,ListPrice) – the Bookstore sells a book with the Title written by the Author for the ListPrice,
lives(Person,City) – the Person lives in the City,
shipping(Bookstore,City,Cost) – the shipping cost from the Bookstore to the City is the Cost. Formulate the following queries (not rules!) in Prolog using these predicates:
• What bookstore sells for the total price less than 20 to customers from more than one city?
• What book written by Robertson Davies is available from one bookstore only?
2 (2 points). For each of the following pairs of Prolog lists, state which pairs can be made identical, and which cannot. Write a brief proof: it is not acceptable to give an answer without any explanations. You lose marks if you do not explain properly. As an explanation, provide equivalent transformations between lists. For those pairs that mention variables, and that can be made identical, give the values of their variables that make the two lists the same. Print legibly.
(a) [X | [Y | Z]] and [[a,b,c], k, l, m, n].
(b) [cps109,mth110 | [X | []]] and [P | [Q,[pcs110] | S]].
3 (2 points). The predicate rangeTenForty(List1,List2) is true if each element of List2 is a number n in the range 10 ≤ n ≤ 40 taken from the given list of numbers List1. Assume that all numbers in List1 are distinct. For example, a query
?- rangeTenForty([400, 13, 20, 50], X). returns the answer X = [13, 20], a query
?- rangeTenForty([100, 5, 77], X). returns the answer X = [], but a query
?- rangeTenForty([12,25,2004], [12,2004]). must return the answer no.
Write a recursive program that implements this predicate. If you would like to use another predicate in your implementation, you must implement it as well. You can assume that in any query the first argument will be a given list (input to your program), and the second argument will be either a variable representing the result that has to be computed or a list of elements representing the result to be verified.
4 (3 points). Let L1 and L2 be given sorted lists of numbers. The predicate merge(L1,L2,Result,N) is true if the list Result is a sorted list of elements from the lists L1, L2 and N is the total number of elements in Result. Note that the number of elements in L1 and L2 can be different and the list Result may have repetitions. For example, a query
?- merge([5, 30], [10,100], Result,N). returns the answers Result = [5, 10, 30, 100] and N = 4, a query ?-merge([9,10,77],[9,25],Result,N). returnstheanswersResult=[9,9,10,25,77]andN=5,but ?- merge([1,2],[2,30],[1,2,30],5). must return the answer no.
Write a recursive program that implements this predicate. You can assume that in any query the first and the second argument will be (possibly empty) lists of numbers (input to your program), the third argument will be either a variable representing the resulting list that has to be computed or a list of numbers representing the result to be verified. Similarly, the fourth argument can be a variable in queries and your program must compute the correct value to answer queries. Note that if you would like to use other predicates in your implementation, you must implement them as well.
5 (3 points). Consider a database about families represented so that each family is described by one atomic statement using the predicate family(Husband,Wife,ListOfChildren). Each atomic statement about a family has three arguments: husband, wife and children. As the number of children varies from family to family the children are represented by a list that is capable of accommodating any number of elements. To better structure data about husbands, wives and children, each person (including every child) is represented by a term of four arguments: person(FirstName,Surname,Date,Job). The job argument can be either unemployed or it can specify a company or an organization. The date argument is a term date(Day,Month,Year) with three arguments representing date of birth of a person. Assume that a database is comprised of a sequence of facts that use the predicate family with arguments represented by the terms mentioned above. The arguments of all terms are constants (names of people, names of organizations, days, months, years). We would like to retrieve certain information from the database. Formulate the following queries in Prolog using the predicate family and terms given to you. You can use other helping predicates, but if you do, you must implement them too.
1. (1 point). Find surnames of families without children such that both wife and husband work for the same employer, they were born on the same date, but have different ages.
2. (2 points). Using atomic statements from the family database define the new predicate rela- tives(X,Y) that is true if X and Y have a common ancestor.
6 (5 points). Consider the following constraint satisfaction problem. At a recent Jane’s child’s birthday party there were four mothers and their children aged 1, 2, 3 and 4. Each mother has one child only. You are given the following clues:
• Brian is not the oldest child.
• Sarah had Anne just over a year ago. • Laura’s child will be 3 next birthday. • Daniel is older than Charlie.
• Teresa’s child is the oldest.
• Charlie is older than Laura’s child.
You have to write a Prolog program that computes solution of this problem and finds whose child is whose and relevant ages of children. Do not attempt to solve any part of this puzzle yourself: it is your program that should solve it. To write a Prolog program that solves this puzzle, you have to do the following:
(1) (1 point) introduce variables representing names of four distinct mothers (Teresa, Sarah, Laura, Jane) and variables representing names of their four distinct children (Anne, Brian, Charlie, Daniel, not respectively); introduce also one predicate that provides a correspondence between each variable and one of the possible values (which are digits 1, 2, 3, 4);
(2) (3 points) write an efficient Prolog program that uses “smart interleaving of generate and test” technique; in other words, express given constraints in a way that reduces the number of guesses;
(3) (1 point) show a solution of the puzzle that your program will find; e.g., you can write the first solution that will be computed by the program.
Note that if you would like to use other predicates in your implementation, you must implement them as well.
7 (3 points). Many applications require representing temporal knowledge, i.e., rules and facts about time and time intervals. For instance, let the predicate before(A,B) mean that time interval A precedes time interval B, the predicate during(A,B) hold if time interval A is strictly inside time interval B and the predicate starts(A,B) mean that time interval A is inside time interval B and starts together with B. Pictorially, the predicates before(A,B), during(A,B), starts(A,B) are represented as follows:
———–time——->
BBBBBBBBBB
before(A,B) is true during(A,B) is true
starts(A,B) is true
Now suppose that you are planning a set of five meetings and have the following information in your KB about their corresponding intervals:
before(m2,m3).
before(m3,m4).
starts(m1,m2).
during(m5,m3).
The knowledge base (KB) includes also the following set of rules that govern relations between arbitrary time intervals A, B, C:
before(A,C) :- during(A,B), /* A missing rule from part before(A,C) :- before(A,B), during(A,B) :- starts(A,B). during(A,C) :- starts(A,B),
before(B,C).
(b) should be here; do not use it in part (a) */ before(B,C).
during(B,C).
(a)(1 point). Show the evaluation tree, including backtracking, that corresponds to Prolog’s eval- uation for the following query:
?- before(m1,m4).
You have to mention every step of the back-chaining procedure. Use the symbol x to show branches that fail and dashed lines to show backtracking.
(b) (2 points). Now suppose that you want to prove the fact before(m1,m5). Unfortunately, attempt- ing to prove this fact from the above KB using the back-chaining procedure leads to failure. What single rule we can add to the KB that will allow us to prove this fact? Again, show the evaluation tree similar to the previous case.
(1st query)
(2nd query)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com