103年 - 103 國立嘉義大學_碩士班(甲組)招生考試試題_資訊管理學系：計算機概論#146091

(a) Please draw the heuristic search tree for solving the famous 8 puzzle problem. The puzzle is contained in a tray that can be thought of as a grid of nine squares. The tray contains only eight tiles, which means that one of the grids is always empty. The tiles are numbered from 1 to 8. The rule of the game is that a tile can be slid into an empty slot. The initial and goal states of an 8-puzzle are shown as the follows. Please draw the heuristic search tree for solving the puzzle.
Initial stateGoal state

(b) Use a truth table to find whether the following argument is valid.
{P → Q, Q → R} |− (P → R)

(a) List and define three kinds of identification witness in entity authentication.

(b) Define a certification authority (CA) and its relation to public-key cryptography.

(a) The input data to a program is made up of a combination of three integers in the range of 1000 to 1999 (inclusive). Find the number of exhaustive tests to test all combinations of these numbers.

(b) A random number generator creates a number between 0 and 0.999. How can this random number generator be used to do random testing for the system described in (a).

(a) Write a recursive algorithm in pseudocodeto find the combination of n objects taken k at a time using the following definition.\[ c(n, k) = \begin{cases} 1 & \text{if } k = 0 \text{ or } n \\ c(n-1, k) + c(n-1, k-1) & \text{if } n > k \ge 1 \end{cases} \]

(b) Using the above definition, find C(10,3) and C(2,7).

(a) Sending a frame to the next node.

(b) Sending a packet from the source to the destination.

(c) Delivery of a long message from the source computer to the destination computer.

(d) Logging in to a remote computer.