Code: C–20 / T-21                                                      Subject: ARTIFICAL INTELLIGENCE &

                                                                                                                   NEURAL NETWORKS    

Time: 3 Hours                                                                                                     Max. Marks: 100

NOTE: There are 9 Questions in all.

· Question 1 is compulsory and carries 20 marks.

· Out of the remaining EIGHT Questions answer any FIVE Questions. Each question carries 16 marks.

· Any required data not explicitly given, may be suitably assumed and stated.

Q.1       Give a True/False answer for each of the following:                                               (2x10)

a. When a heuristic function overestimates, A* algorithm gives an optimal solution.

b. Cryptarithmatic problem cannot be solved as a constraint satisfaction problem.

c. Expert System Shell = Expert System + Knowledge

             d.   ! in prolog is used for reducing the search space.

             e.   Neural Network cannot be used as learning component in an Expert System.

             f.    Search in game playing programs proceeds backwards from the goal state to the current position rather than forward from the current position to the goal state.

             g.   Composition of substitutions is always commutative.

             h.   Goal stack planning is non-linear planning.

             i.    An α-cut of a fuzzy set A is a crisp set consisting of those elements of A which belong to the fuzzy set with degree at least α.

             j.    Centroid or centre of mean, centre of sums and mean of maximum are some methods used for fuzzification.

Answer any FIVE Questions out of EIGHT Questions.

Each question carries 16 marks.

Q.2     a.   When would best-first search be worse than simple breadth-first search?

b. What do you understand by underestimation and overestimation of a heuristic function? Under what conditions A* gives optimal solution.

c. Distinguish between linear and non-linear planning.

d. Find the probability of the event A when it is known that some event B has occurred. From experiments, it has been determined that P (B|A) = 0.84,    P (A) = 0.2 and P (B) = 0.34.                         (4x4)

Q.3           Consider the famous game of tic-tac-toe. For this game                                          

(i) Draw the first three levels of the state space search tree.

(ii) Apply the Two-Ply minimax on the tic-tac-toe search tree.

(iii) Define a heuristic function.

(iv) Show how the alpha-beta pruning can be used for this tree.           (4x4)

Q.4           Consider the following piece of knowledge:

· Mary, Micky and John are members of Rotary club.

· Every Rotary club member who is not a swimmer is a mountain climber.

· Mountain climbers do not like rains.

· Anyone who does not like water is not a swimmer.

· Micky dislikes whatever Mary likes and likes whatever Mary dislikes.

· Mary likes rain and water.

(i) Represent this knowledge as predicate statements.

(ii) Show that a query “Is there a member of Rotary club who is not a mountain climber but a swimmer” using resolution method.                                             (6+10)

Q.5     a.   You are explaining the problem of searching for a move in chess to your friend. Your friend notices that the algorithm needs to find the maximum of some function (i.e., the move that is best for you) and suggests that one should simply differentiate the function, set the result to zero, and solve. Explain why this will not work.                                                            (8)

             b.   Develop all syntactically valid parses of the sentence “Jack slept on the table on the roof”. Define standard grammatical formalism and use it.         (8)

  Q.6     a. What is rote learning? Would it be reasonable to apply rote-learning procedure to chess? Why (not)?                                                                    (8)

b. Solve the following cryptarithmatic problem.

  TWO

                   +TWO

                   --------

FOUR

                  --------                                                                                                               (8)

Q.7     a.   What is an Expert System? How do you distinguish between a knowledge based system and an expert system?                                                                                                           (10)

b.   Describe the various conflict resolution strategies in Rule Based Expert Systems.                 (6)

Q.8     a.   Write a Prolog program to find the sum of first n natural numbers.                       (4)

b.   Write a Prolog program for obtaining a list after deleting all occurrence of a particular element from a given list.                                                      (4)

c. Explain (with the help of examples) how and when

(i) ! (cut)

(ii) fail

                  are used in Prolog to change the backtracking sequencing.                                   (8)

Q.9     a.   What are the main differences between scripts and frame structures?                   (4)

b.   What do you mean by inheritance? Explain various types of inheritance present in frame based systems.                                                                 (6)

c.   Define some good heuristic functions for each of the following problems:

(i) Chess

(ii) Travelling Salesman                                                                               (2)

 d.  Why is it important that an expert system be able to explain the why and    

      how questions related to a problem solving session?                                             (4)