Exam

TDDA23 - Artificial Intelligence and Lisp

22 August, 2006

Auxiliary items. English dictionary.

Jour:  Erik Sandewall, mobile phone 0708 - 28 14 08.

Directions: Solutions should be precise, concise, and to
the point. It is possible, and strongly recommended, to
write the solutions for each of the problems or problem 
parts (a, b, c) in at most ten lines. Long and verbose
solutions are almost always a waste of time.

Each solution to a problem shall be on a separate sheet
of paper, with your name and the problem number on it
in the upper RIGHT corner, not in the upper left corner.
(The a, b, and c parts of a problem can be on the same 
paper, however). Write only on one side of the paper. 
Answers can be written in Swedish or English.

Points:  Full and correct solutions to all problems
gives 20 points. The number of points for each problem
is specified below. The requirement for passing the
exam is 9 points.


1.  Define a Lisp function (numberof a s) that takes an
    atom (i.e. symbol, string, or number) and an
    S-expression  as arguments, and counts the number of
    times that a occurs in s. For example, the value of
       (numberof  4  '((3 1 4) 2 (3 (6 4 2) 4)))
    shall be the integer 3.

    The definition must be written as a recursive function,
    and constructs using side-effects may not be used. 
    It must allow s to contain an arbitrary mix of symbols,
    strings, and numbers. It must also allow substructures 
    that are dotted pairs, for example (4 . 6).

    The solution must be fully correct Lisp code. Solutions
    that are incorrect with respect to the Lisp syntax or 
    semantics will be given 0 points.

    This problems gives (3 p).


2.  Assume that a correct definition of the function 
    numberof (from problem 1) exists already, and
    consider the following definition:

       (defun num (j) '(lamba (s)(numberof j s)))

    and the following expression to be evaluated:

       (funcall (num 4) '((3 1 4) 2 (3 (6 4 2) 4)))

    a)  What is the result of evaluating this expression?
        Explain why the result is obtained. (2 p).

    b)  Is there a better way of writing the definition
        of num, for example for obtaining a more appropriate
        result, or for avoiding errors in some situations?
        (1 p).


3.  a)  Give a precise definition of the classical planning 
        problem. (2 p).

    b)  An intelligent robot may be required to achieve
        several goals at the same time, for example if
        it has several users and each one of them wants
        some task to be done by the robot. Suggest some
        way of defining that situation in terms of the
        classical planning problem. (2 p).


4.  The Yale Shooting Example (YSE) is a concrete example
    that illustrates a type of problems for reasoning
    about actions that causes some reasoning methods to 
    obtain the wrong set of models. What is the 
    characteristic property of the YSE that leads to this 
    anomaly? (Describe it in 2-3 sentences). Also, describe
    a model that is incorrectly obtained by some wellknown
    reasoning mehod. (3 p).


5.  The course has introduced "second-order predicate logic"
    and "modal logic". Is it possible to have a combination
    that contains both the constructs of second-order
    predicate logic and of modal logic? If no, explain why.
    If yes, give an example of an expression in the
    combined logic, and discuss whether the combination
    could be of any use. (3 p).


6.  a)  Describe the standard architecture for natural
        language dialog systems, using a dataflow diagram
        and a brief explanation of each module in the
        dataflow. (2 p).
    b)  What is meant by 'anaphora' and how are they
        handled in the standard architecture? (1 p).
    c)  What is meant by 'turntaking' and how is it
        handled in the standard architecture? (1 p).