-----------------
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