New Semester Started Get 50% OFF Study Help! --h --m --s Claim Now

Question Answers

Textbooks

Find textbooks, questions and answers

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Study Help
Tutors
AI Study Planner NEW
Sell Books

Search
Sign In
Register

study help
computer science
artificial intelligence modern

Artificial Intelligence A Modern Approach 3rd edition Stuart Russell, Peter Norvig - Solutions

Equation (8.4) on page 306 defines the conditions under which a square is breezy. Here we consider two other ways to describe this aspect of the wumpus world.a. We can write diagnostic rules leading from observed effects to hidden causes. For finding pits, the obvious diagnostic rules say that if a
Rewrite the first two Peano axioms in Section 8.3.3 as a single axiom that defines NatNum(x) so as to exclude the possibility of natural numbers except for those generated by the successor function.
Complete the following exercises about logical senntences:a. Translate into good, natural English (no xs or ys!): ∀ x, y, l SpeaksLanguage(x, l) ∧ SpeaksLanguage(y, l) ⇒ Understands (x, y) ∧ Understands(y, x).b. Explain why this sentence is entailed by the sentence ∀ x, y, l
Consider a vocabulary with the following symbols:Occupation(p, o): Predicate. Person p has occupation o.Customer (p1, p2): Predicate. Person p1 is a customer of person p2.Boss(p1, p2): Predicate. Person p1 is a boss of person p2.Doctor , Surgeon, Lawyer , Actor : Constants denoting
This exercise uses the function MapColor and predicates In(x, y), Borders(x, y), and Country(x), whose arguments are geographical regions, along with constant symbols for various regions. In each of the following we give an English sentence and a number of candidate logical expressions. For each of
Does the fact ¬Spouse(George, Laura) follow from the facts Jim ≠ George and Spouse (Jim, Laura)? If so, give a proof; if not, supply additional axioms as needed. What happens if we use Spouse as a unary function symbol instead of a binary predicate?
Consider a version of the semantics for first-order logic in which models with empty domains are allowed. Give at least two examples of sentences that are valid according to the standard semantics but not according to the new semantics. Discuss which outcome makes more intuitive sense for your
Consider the family of generalized tic-tac-toe games, defined as follows. Each particular game is specified by a set S of squares and a collection W of winning positions. Each winning position is a subset of S. For example, in standard tic-tac-toe, S is a set of 9 squares and W is a collection of 8
Describe how the minimax and alpha–beta algorithms change for two-player, nonzero- sum games in which each player has a distinct utility function and both utility functions are known to both players. If there are no constraints on the two terminal utilities, is it possible for any node to be
Prove that alpha–beta pruning takes time O(2m/2) with optimal move ordering, where m is the maximum depth of the game tree.
This question considers pruning in games with chance nodes. Figure 5.19 shows the complete game tree for a trivial game. Assume that the leaf nodes are to be evaluated in left-to-right order, and that before a leaf node is evaluated, we know nothing about its value€”the range of possible
Consider the following procedure for choosing moves in games with chance nodes:Generate some dice-roll sequences (say, 50) down to a suitable depth (say, 8).With known dice rolls, the game tree becomes deterministic. For each dice-roll sequence, solve the resulting deterministic game tree using
In the following, a "max" tree consists only of max nodes, whereas an "expectimax" tree consists of a max node at the root with alternating layers of chance and max nodes. At chance nodes, all outcome probabilities are nonzero. The goal is to find the value of the root with a bounded-depth search.
Which of the following are true and which are false? Give brief explanations.a. In a fully observable, turn-taking, zero-sum game between two perfectly rational players, it does not help the first player to know what strategy the second player is using—that is, what move the second player will
Consider the problem of placing k knights on an n×n chessboard such that no two knights are attacking each other, where k is given and k ≤ n2.a. Choose a CSP formulation. In your formulation, what are the variables?b. What are the possible values of each variable?c. What sets of variables are
Consider the following logic puzzle: In five houses, each with a different color, live five persons of different nationalities, each of whom prefers a different brand of candy, a different drink, and a different pet. Given the following facts, the questions to answer are “Where does the zebra
The TREE-CSP-SOLVER (Figure 6.10) makes arcs consistent starting at the leaves and working backwards towards the root. Why does it do that? What would happen if it went in the opposite direction?Figure 6.10 E (F) A )-(B )-(C (D B D (a)
We introduced Sudoku as a CSP to be solved by search over partial assignments because that is the way people generally undertake solving Sudoku problems. It is also possible, of course, to attack these problems with local search over complete assignments. How well would a local solver using the
Define in your own words the terms constraint, backtracking search, arc consistency, back jumping, min-conflicts, and cycle cutset.
Which of the following are correct?a. False ⊨ True.b. True ⊨ False.c. (A ∧ B) ⊨ (A ⇔ B).d. A ⇔ B ⊨ A ∨ B.e. A ⇔ B ⊨ ¬A ∨ B.f. (A ∧ B) ⇒ C ⊨ (A ⇒ C) ∨ (B ⇒ C).g. (C ∨ (¬A ∧ ¬B)) ≡ ((A ⇒ C) ∧ (B ⇒ C)).h. (A ∨ B) ∧ (¬C ∨¬D ∨ E) |= (A ∨ B).i.
Prove each of the following assertions:a. α is valid if and only if True ⊨ α.b. For any α, False ⊨ α.c. α ⊨ β if and only if the sentence (α ⇒ β) is valid.d. α ≡ β if and only if the sentence (α ⇔ β) is valid.e. α ⊨ β if and only if the sentence (α ∧ ¬β) is
Prove, or find a counterexample to, each of the following assertions:a. If α ⊨ γ or β |= γ (or both) then (α ∧ β) ⊨ γb. If α ⊨ (β ∧ γ) then α ⊨ β and α ⊨ γ.c. If α ⊨ (β ∨ γ) then α ⊨ β or α ⊨ γ (or both).
Use resolution to prove the sentence ¬ A ∧¬ B from the clauses in Exercise 7.20.
According to some political pundits, a person who is radical (R) is electable (E) if he/she is conservative (C), but otherwise is not electable.a. Which of the following are correct representations of this assertion?(i) (R ∧ E) ⇐⇒ C(ii) R ⇒ (E ⇐⇒ C)(iii) R ⇒ ((C ⇒ E) ∨ ¬ E)b.
This question considers representing satisfiability (SAT) problems as CSPs.a. Draw the constraint graph corresponding to the SAT problem (¬ X1 ∨ X2) ∧ (¬ X2 ∨ X3) ∧ . . . ∧ (¬ Xn−1 ∨ Xn)for the particular case n = 5.b. How many solutions are there for this general SAT problem as a
Explain why every nonempty propositional clause, by itself, is satisfiable. Prove rigorously that every set of five 3-SAT clauses is satisfiable, provided that each clause mentions exactly three distinct variables. What is the smallest set of such clauses that is unsatisfiable? Construct such a set.
A propositional 2-CNF expression is a conjunction of clauses, each containing exactly 2 literals, e.g.,(A ∨ B) ∧ (¬ A ∨ C) ∧ (¬ B ∨ D) ∧ (¬ C ∨ G) ∧ (¬ D ∨ G).a. Prove using resolution that the above sentence entails G.b. Two clauses are semantically distinct if they are not
Consider the following sentence:[(Food ⇒ Party) ∨ (Drinks ⇒ Party)] ⇒ [(Food ∧ Drinks) ⇒ Party] .a. Determine, using enumeration, whether this sentence is valid, satisfiable (but not valid), or unsatisfiable.b. Convert the left-hand and right-hand sides of the main implication into CNF,
A sentence is in disjunctive normal form (DNF) if it is the disjunction of conjunctions NORMAL FORM of literals. For example, the sentence (A ∧ B ∧ ￢C) ∨ (￢A ∧ C) ∨ (B ∧￢C) is in DNF.a. Any propositional logic sentence is logically equivalent to the assertion that some possible
Convert the following set of sentences to clausal form.S1: A ⇔ (B ∨ E).S2: E ⇒ D.S3: C ∧ F ⇒ ¬B.S4: E ⇒ B.S5: B ⇒ F.S6: B ⇒ CGive a trace of the execution of DPLL on the conjunction of these clauses.
Is a randomly generated 4-CNF sentence with n symbols and m clauses more or less likely to be solvable than a randomly generated 3-CNF sentence with n symbols and m clauses? Explain.
Trace the behavior of DPLL on the knowledge base in Figure 7.16 when trying to prove Q, and compare this behavior with that of the forward-chaining algorithm.Figure 7.16 LAM = P P ВЛL 3D M ΑΛΡ L АЛВ — L B (a) (b)
Write a successor-state axiom for the Locked predicate, which applies to doors, assuming the only actions available are Lock and Unlock.
Section 7.7.1 provides some of the successor-state axioms required for the wumpus world. Write down axioms for all remaining fluent symbols.
Modify the HYBRID-WUMPUS-AGENT to use the 1-CNF logical state estimation method described on page 271. We noted on that page that such an agent will not be able to acquire, maintain, and use more complex beliefs such as the disjunction P3,1 ∨ P2,2. Suggest a method for overcoming this problem by
Which of the following are valid (necessarily true) sentences?a. (∃x x = x) ⇒ (∀ y ∃z y = z).b. ∀x P(x) ∨¬P(x).c. ∀ x Smart(x) ∨ (x = x).
Are reflex actions (such as flinching from a hot stove) rational? Are they intelligent?
The neural structure of the sea slug Aplysia has been widely studied (first by Nobel Laureate Eric Kandel) because it has only about 20,000 neurons, most of them large and easily manipulated. Assuming that the cycle time for an Aplysia neuron is roughly the same as for a human neuron, how does the
To what extent are the following computer systems instances of artificial intelligence:• Supermarket bar code scanners.• Web search engines.• Voice-activated telephone menus.• Internet routing algorithms that respond dynamically to the state of the network.
Many of the computational models of cognitive activities that have been proposed involve quite complex mathematical operations, such as convolving an image with a Gaussian or finding a minimum of the entropy function. Most humans (and certainly all animals) never learn this kind of mathematics at
Is AI a science, or is it engineering? Or neither or both? Explain.
“Surely animals cannot be intelligent—they can do only what their genes tell them.” Is the latter statement true, and does it imply the former?
Examine the AI literature to discover whether the following tasks can currently be solved by computers:a. Playing a decent game of table tennis (Ping-Pong).b. Driving in the center of Cairo, Egypt.c. Driving in Victorville, California.d. Buying a week’s worth of groceries at the market.e. Buying
Various subfields of AI have held contests by defining a standard task and inviting researchers to do their best. Examples include the DARPA Grand Challenge for robotic cars, The International Planning Competition, the Robocup robotic soccer league, the TREC information retrieval event, and
Suppose that the performance measure is concerned with just the first T time steps of the environment and ignores everything thereafter. Show that a rational agent’s action may depend not just on the state of the environment but also on the time step it has reached.
Let us examine the rationality of various vacuum-cleaner agent functions.a. Show that the simple vacuum-cleaner agent function described in Figure 2.3 is indeed rational under the assumptions listed on page 38.b. Describe a rational agent function for the case in which each movement costs one
For each of the following assertions, say whether it is true or false and support your answer with examples or counterexamples where appropriate.a. An agent that senses only partial information about the state cannot be perfectly rational.b. There exist task environments in which no pure reflex
This exercise explores the differences between agent functions and agent programs.a. Can there be more than one agent program that implements a given agent function? Give an example, or show why one is not possible.b. Are there agent functions that cannot be implemented by any agent program?c.
Write pseudocode agent programs for the goal-based and utility-based agents. The following exercises all concern the implementation of environments and agents for the vacuum-cleaner world.
Your goal is to navigate a robot out of a maze. The robot starts in the center of the maze facing north. You can turn the robot to face north, east, south, or west. You can direct the robot to move forward a certain distance, although it will stop before hitting a wall.a. Formulate this problem.
Suppose two friends live in different cities on a map, such as the Romania map shown in Figure 3.2. On every turn, we can simultaneously move each friend to a neighboring city on the map. The amount of time needed to move from city i to neighbor j is equal to the road distance d(i, j) between the
Consider the n-queens problem using the “efficient” incremental formulation given on page 72. Explain why the state space has at least 3√n! states and estimate the largest n for which exhaustive exploration is feasible.
Give a complete problem formulation for each of the following. Choose a formulation that is precise enough to be implemented.a. Using only four colors, you have to color a planar map in such a way that no two adjacent regions have the same color.b. A 3-foot-tall monkey is in a room where some
On page 68, we said that we would not consider problems with negative path costs. In this exercise, we explore this decision in more depth.a. Suppose that actions can have arbitrarily large negative costs; explain why this possibility would force any optimal algorithm to explore the entire state
Consider the problem of finding the shortest path between two points on a plane that has convex polygonal obstacles as shown in Figure 3.31. This is an idealization of the problem that a robot has to solve to navigate in a crowded environment.a. Suppose the state space consists of all positions (x,
The missionaries and cannibals problem is usually stated as follows. Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place
Define in your own words the following terms: state, state space, search tree, search node, goal, action, transition model, and branching factor.
What’s the difference between a world state, a state description, and a search node? Why is this distinction useful?
An action such as Go(Sibiu) really consists of a long sequence of finer-grained actions: turn on the car, release the brake, accelerate forward, etc. Having composite actions of this kind reduces the number of steps in a solution sequence, thereby reducing the search time. Suppose we take this to
Which of the following are true and which are false? Explain your answers. a. Depth-first search always expands at least as many nodes as A∗ search with an admissible heuristic.b. h(n) = 0 is an admissible heuristic for the 8-puzzle.c. A∗ is of no use in robotics because percepts, states,
Prove that GRAPH-SEARCH satisfies the graph separation property illustrated in Figure 3.9. Begin by showing that the property holds at the start, then show that if it holds before an iteration of the algorithm, it holds afterwards. Describe a search algorithm that violates the property.Figure 3.9.
Consider a state space where the start state is number 1 and each state k has two successors: numbers 2k and 2k + 1.a. Draw the portion of the state space for states 1 to 15.b. Suppose the goal state is 11. List the order in which nodes will be visited for breadth first search, depth-limited search
A basic wooden railway set contains the pieces shown in Figure 3.32. The task is to connect these pieces into a railway that has no overlapping tracks and no loose ends where a train could run off onto the floor.a. Suppose that the pieces fit together exactly with no slack. Give a precise
we mentioned iterative lengthening search, an iterative analog of uniform cost search. The idea is to use increasing limits on path cost. If a node is generated whose path cost exceeds the current limit, it is immediately discarded. For each new iteration, the limit is set to the lowest path cost
Prove each of the following statements, or give a counter example:a. Breadth-first search is a special case of uniform-cost search.b. Depth-first search is a special case of best-first tree search.c. Uniform-cost search is a special case of A∗ search.
Trace the operation of A∗ search applied to the problem of getting to Bucharest from Lugoj using the straight-line distance heuristic. That is, show the sequence of nodes that the algorithm will consider and the f, g, and h score for each node.
The heuristic path algorithm (Pohl, HEURISTIC PATH 1977) is a best-first search in which the evaluation function is f(n) = (2 − w)g(n) + wh(n). For what values of w is this complete? For what values is it optimal, assuming that h is admissible? What kind of search does this perform for w = 0, w =
Consider the unbounded version of the regular 2D grid shown in Figure 3.9. The start state is at the origin, (0,0), and the goal state is at (x, y).a. What is the branching factor b in this state space?b. How many distinct states are there at depth k (for k > 0)?c. What is the maximum number of
n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n × n grid. The vehicles must be moved to the top row but in reverse order; so the vehicle i that starts in (i, 1) must end up in (n−i+1, n). On each time step, every one of the n vehicles can move one square up, down,
The traveling salesperson problem (TSP) can be solved with the minimum-spanning tree (MST) heuristic, which estimates the cost of completing a tour, given that a partial tour has already been constructed. The MST cost of a set of cities is the smallest sum of the link costs of any tree that
The AND-OR-GRAPH-SEARCH algorithm in Figure 4.11 checks for repeated states only on the path from the root to the current state. Suppose that, in addition, the algorithm were to store every visited state and check against that list. (See BREADTH-FIRST-SEARCH in Figure 3.11 for an example.)
Explain precisely how to modify the AND-OR-GRAPH-SEARCH algorithm to generate a cyclic plan if no acyclic plan exists. You will need to deal with three issues: labeling the plan steps so that a cyclic plan can point back to an earlier part of the plan, modifying OR-SEARCH so that it continues to
In Section 4.4.1 we introduced belief states to solve sensorless search problems. A sequence of actions solves a sensorless problem if it maps every physical state in the initial belief state b to a goal state. Suppose the agent knows hˆ—(s), the true optimal cost of solving the physical
This exercise explores subset–superset relations between belief states in sensor less or partially observable environments.a. Prove that if an action sequence is a solution for a belief state b, it is also a solution for any subset of b. Can anything be said about supersets of b?b. Explain in
It was assumed that a given action would have the same cost when executed in any physical state within a given belief state. (This leads to a belief-state search problem with well-defined step costs.) Now consider what happens when the assumption does not hold. Does the notion of optimality still
Consider the sensorless version of the erratic vacuum world. Draw the belief-state space reachable from the initial belief state {1, 2, 3, 4, 5, 6, 7, 8}, and explain why the problem is unsolvable.
Like DFS, online DFS is incomplete for reversible state spaces with infinite paths. For example, suppose that states are points on the infinite two-dimensional grid and actions are unit vectors (1, 0), (0, 1), (−1, 0), (0, −1), tried in that order. Show that online DFS starting at (0, 0) will

Showing 300 - 400 of 377

1
2
3
4

Step by Step Answers

Services

Sitemap
Fun
Definitions
Become Tutor
Used Textbooks
Study Help Categories
Recent Questions
Expert Questions
Campus Wear
Sell Your Books

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship
Online Quiz
Give Feedback, Get Rewards

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Student Discount
Campus Ambassador

Secure Payment

Download Our App

© 2026 SolutionInn. All Rights Reserved