----------------- Please distribute ----------------- EXPERT SYSTEMS: the exam 1984 There are three questions on each of the M.Sc. exams (at least, the AI ones). Answer two; you'll only get credit for the first two you answer (which is not necessarily the same as the first two you try!). Some (perhaps most) of the questions will come in several parts connected by some theme; do the bits you can, obviously. If you find yourself at sea, try to put down what you do know that you think relevant; you get marks for what you put down, if its relevant! Revision: the blue/white Xerox paper ("The Organization of Expert Systems: A Prescriptive Tutorial" by M.Stefik &c), lecture handouts and your own notes. If you want reassurance or further reading, then look at the expensive book ("Building Expert Systems", Hayes-Roth &c) and/or "Expert Systems in the Micro-electronic Age", Michie &c. Try AL/X and OPS5 just to get a taste of the practice, they make the course a little less academic - not obligatory, though. Some examples of bits of questions, to help you get the feel for the main event (my comments appear in {...} brackets): [1] Neither pure forward-chaining nor pure bacward-chaining is ideal for a diagnostic expert system that is expected to do much explaining. Explain why. {might be 40-50% of a question, and paired with some bookwork. Looking for some commonsense observations about the number and the apparent relevancy of questions and explanations that such expert systems might generate. Remember that exercise about (CHIHUAHUA FRED)? A simple example or two would help your answer, of the form 'Consider these rules - A, B imply C C implies D &c &c ... Suppose Z is the top-level, ultimate goal of the diagnosis. Then, if pure bacward-chaining is used, ... blether blether ...'} [2] Consider the famous water-pot problem: You have two water-pots, which hold X litres and Y litres. You want to get Z litres of water. There is a tap from which you can fill the pots. You can fill a pot, pour from one to the other, or empty a pot. Bloodbath Ltd. want a computer program to solve this sort of problem. What advice would you offer them about choice of search methods? Suppose they have to pay for the water - what advice would you then offer? Suppose they had to take account of the cost of hiring slaves, by the minute, to do the filling and pouring - what advice would you then offer? Remember, computer time is always at a premium. {this is essentially "tell me all you know about search methods", but within a context. It should start you recalling details about search methods that take account of path costs and node costs. Might be 75% - 100% of a question} [3] What are the disadvantages of (a) a MYCIN-like system (b) a PROSPECTOR-like system (c) a HEARSAY-II-like system, for expert systems work? {might be 50% of a question. Calls for a straightforward memory dump in (a) and (b). You'll realise that (c) was not covered in the lectures, but that's the point: you're being expected to do some commonsense reasoning. Comments might include 'computationally expensive', 'problem space must be apt for a blackboardish approach (i.e. multidimensional, with something like levels up which the work should progress)', 'thought must be given to limiting the searching' and so on. When in doubt, put down what you knwo that seems relevant} [4] Consider the following blocks-world situation: ----- ----- | D | | B | ----- ----- | A | | C | ----------------table The desired state is that D should be on top of C, which should be on top of B, which should be on top of A. There is one basic operator: (move X from Y to Z) which requires (cleartop X) and (cleartop Z) and adds (on X Z) and deletes (on X Y). Show how STRIPS might set about this problem. Show how WARPLAN might set about this problem. Show how NOAH might set about this problem. {could be 100% of a question, which should tell you that quite a lot of detail is required about what STRIPS etc do in planning. Start by stating the desired result: (on D C) and (on C B) and ... and take it from there. If you remember the salient details of these three planners, then common sense will take you a very long way} This being the first year for this M.Sc., there is no marking standard to live up to (or down to). I would guess that, in line with customary practice, a score of 50% will be a pass and a score of 75-80% will be heroic. Good luck. Contact me if you're getting worried... Peter, 031-667-1011 ext. 2557 PROLOG: the exam 1984 You won't be able to take the Prolog manual into the exam, the University are sticky about lettting people carry things in. However, if you find that you want to use or mention or discuss some Prolog predicate whose details you have forgotten, then you can just redefine it explicity, e.g. " ... using mumble(C), a predicate whose argument ought to be instantiated to an integer, and which outputs the character with that ASCII code, ..." (assuming you've forgotten about put(C)). I'll be at the exam. There are three questions on each of the M.Sc. exams (at least, the AI ones). Answer two; you'll only get credit for the first two you answer (which is not necessarily the same as the first two you try!). Some (perhaps most) of the questions will come in several parts connected by some theme; do the bits you can, obviously. If you find yourself at sea, try to put down what you do know that you think relevant; you get marks for what you put down, if its relevant! Revision: "Programming in Prolog" by Clocksin & Mellish, and the C-Prolog manual. You won't be expected to be a fluent programmer (that comes with the project, probably), but you will be expected to be able to read and understand fairly short programs - so spend a little while looking at the programs which got handed out, and try to sort out any bits you didn't understand. Some examples of bits of questions, to help you get the feel for the main event (my comments appear in {...} brackets): [1] Explain the 'cut' and why it is useful, giving examples. {would be 40-50% of a question. This is looking for a definition, plus some discussion e.g. comparing test :- a,!,b. | with | test :- a, b. test :- c. | | test :- not(a), c. and talk about control flow. If you've read the right bit in C&M this'll be easy. Mention efficiency if you can. You could reproduce some of the C&M protypical uses, e.g. 'cut' used to say 'this is the right choice', and 'cut, fail' used to say 'this is the wrong choice'} [2] Give an account, as though to someone halfway through a Prolog course, of the following program: vars(X,[X|L],L ) :- var(X), !. % var(_) succeeds if arg is a variable vars(T,L1, L2) :- T =.. [Func|Args], % =.. assembles a list of the functor vars2(A,L1,L2). % and arguments of a term T. vars2([T|Rest],L1,L2) :- vars(T,L1,L3), vars2(Rest,L3,L1). vars2([],L,L). {would be about 66% of a question. Say what it does (produces a list of the variables occuring in a given term), give an example or two to show you know what it does, talk learnedly about why the cut is there in the first clause for vars/3, and what vars2/3 does (it applies vars/3 to each element in a list of terms, collects up a list of all the variables) and about this being an example of difference lists} [3] Devise a definite clause grammar that will accept numerals between zero and ninety-nine, as expressed in English e.g. twenty one thirty nineteen fifty-four Explain how your grammar could be modified to produce the integer that corrsponds to an acceptable expression. {this would be around 60% of a question. A more involved example, e.g. up to 999, taking phrases such as 'two hundred and four', might form a whole question. Note the tricky optional use of a hyphen. The second bit is asking you to explain how to get extra arguments to do the work for you - see C&M's explanation about how extra arguments can be used to make singular/plural consistency in sentences. If you found this an easy example, then try a DCG for Roman numerals such as XLIV} [4] Justin Eidelburger, the notoriously lazy theoretician, wants to have a simple Prolog program for disproving simple theorems in propositional calculus. So far, he has lots of clauses of the form .... false(P equiv_to Q) :- false((P implies Q) and (Q implies P)). false(P implies Q) :- false(not P or Q). false(not not P) :- false(P). false(not (P or Q)) :- false(not P and not Q). .... Suggest declarations for the logical operators such as 'equiv_to', 'implies', 'not', 'and' and 'or', giving reasons for your choices. Suggest a simple mechanism to make it easy to input theorems and get them checked. {this might be 50-60% of a question. It's testing your knowledge of how operators work in Prolog. You wouldn't be expected to remember things like the declaration of standard operators, just how its done in general. Talk about questions of precedence and associativity. The question is a bit of a cheat, because it assumes you know a little about formal propositional calculus, i.e. how these things like 'or' and 'implies' are supposed to behave. The simple mechanism might be something like this: go :- read(Theorem), vet(Theorem). vet(quit). vet(Theorem) :- ( false(Theorem), write('Bad luck'),nl,! ; write('It aint false'),nl ), go. } This being the first year for this M.Sc., there is no marking standard to live up to (or down to). I would guess that, in line with customary practice, a score of 50% will be a pass and a score of 75-80% will be heroic. Good luck. Contact me if you're getting worried... Peter, 031-667-1011 ext. 2557