发表于 |

Welcome to AI Fundamental course at UCAS

Thank you for your interest in our materials developed for AI Fundamental course (2017) at University of Chinese Academy of Sciences. At this web site, you will find the following:

  • Some lecture slides (mainly for the third part of this course)
  • Detailed analysis on some key questions, which are not well addressed in the course book. These questions are usually used as the homework for the students in the course.
阅读全文 »

发表于 |

We provide a formal proof on

  • The graph separation property in graph search
  • The optimality on uniform-cost search

Please check the following pdf.
(Thanks to Qinlin Zhu.)

发表于 |

We provide a formal proof on the following properties

  • If a heuristic is consistent, it must be admissible. We also give an example heuristic which is admissible, but not consistent.
  • A* of graph search is NOT optimal with admissible heuristic.

For the second property, the course book only says that “A* of graph search is optimal with consistent heuristic”. Some students are wondering whether the conclusion that

A* of graph search is optimal with admissible heuristic

is true or not (see the page). Here, we show this conclusion is wrong. The key point is that the frontier set in graph search include both the visited and unvisited nodes.

Please check the following pdf.
(Thanks to Xingcheng Ruan.)

发表于 |

We provide a formal proof on the correctness of NegaScout, which cannot be found in other places of Web.

We also find that we can also perform the scout step even for the first child of a node. It means that the constraint on the “first action” (see Line 6 of the algorithm in the pdf) is NOT necessary. It is only necessary when $\alpha = -\infty $.

Please check the following pdf.
(Thanks to Rongqing Wang.)

发表于 |

陆钟万先生编写的《面向计算机科学的数理逻辑》是数理逻辑方面的经典教材。
本次作业，利用课本讲授的包含11条推演规则的命题逻辑系统，以形式推演的方式证明了课本中的

  • 定理2.6.4
  • 定理2.6.9

详细的证明请见 pdf.
(Thanks to Rongqing Wang.)

向陆钟万先生致敬！

发表于 |

We give the detailed answer to Exercise 7.17 in the book of AIMA.

7.17 A propositional 2-CNF expression is a conjunction of clauses, each containing exactly 2 literals, e.g.,
$$(A \lor B) \land (\lnot A \lor C) \land (\lnot B \lor D) \land (\lnot C \lor G) \land (\lnot D \lor G)$$

a. Prove using resolution that the above sentence entails G.
b. Two clauses are semantically distinct if they are not logically equivalent. How many semantically distinct 2-CNF clauses can be constructed from n proposition symbols?
c. Using your answer to (b), prove that propositional resolution always terminates in time polynomial in n given a 2-CNF sentence containing no more than n distinct symbols.
d. Explain why your argument in (c) does not apply to 3-CNF.

详细的证明请见 pdf.
(Thanks to Lv Feng.)

发表于 |

Foreword

This assignment should be finished with Prolog.

Question I

Given a set, list all its elements.
给出一个集合，列出其所有元素 

1
2
3
4
5
/* using MS Windows GUN prolog（gprolog）
query ：mymember(X,[1,2,3,4,5]). */
mymember(X,[_|Y]):- mymember(X,Y).
mymember(X,[X|_]).

(Thanks to Shiyu Wu)

Question II

Given a set, list all its subsets.
给出一个集合，列出其所有子集 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* gprolog
Supposing the subset is in order.
EXAMPLE:
| ?- subset([2,3],[1,2,3]).
true ? 
yes 
| ?- subset(X,[1,2,3]).
X = [1,2,3] ? ;
X = [1,2] ? ;
X = [1,3] ? ;
X = [1] ? ;
X = [2,3] ? ;
X = [2] ? ;
X = [3] ? ;
X = [] ? ;
*/
subset([],[]).
subset([A|B],[A|C]):- subset(B,C).
subset(A,[_|B]):- subset(A,B).

(Thanks to Pan Shi)

匿名变量 _
prolog中，变量由大写字母或下划线 _ 开头。
匿名变量 _ 不会绑定为任何值，所以也不要求它所出现的位置的值必须相同。

列表表达 |
Prolog提供了把表头项目以及除去表头项目后剩下的列表分离的方法。
其次，Prolog强大的递归功能可以方便地访问除去表头项目后的列表。
如：

1
[X | Y]

使用此列表可以与任意的列表匹配，匹配成功后，X绑定为列表的第一个项目的值，
我们称之为表头（head）。而Y则绑定为剩下的列表，我们称之为表尾（tail)，举例说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
?- [H|T] = [apple, broccoli, refrigerator].
H = apple 
T = [broccoli, refrigerator] 
?- [H|T] = [a, b, c, d, e].
H = a
T = [b, c, d, e] 
?- [H|T] = [apples, bananas].
H = apples 
T = [bananas]
?- [H|T] = [a, [b,c,d]]. /* 这个例子中的第一层列表有两个项目。*/
H = a 
T = [[b, c, d]] 
?- [H|T] = [apples]. /*列表中只有一个项目的情况 */
H = apples
T = []
0%