Midterm Review: Examples
October 23, 2020
Midterm Review: Examples October 23, 2020 1 / 9
Matching lists
Copyright By PowCoder代写 加微信 powcoder
Find if the following lists match or not. Provide transformations. [K,L|[M|N]] and[cps|[mth|[phy]]]
[K, L | [ M | N ] ] = [K, L, M | N]
[ cps | [mth | [phy] ] ] = [ cps | [mth, phy] ]
[ cps | [ mth, phy] ] = [ cps, mth, phy]
[K,L,M | N ]=
[cps,mth,phy | [ ] ] if K=cps, L=mth, M=phy, N=[ ]
Canthelists[X, c, b | [c | X ] ] and[[p,q] | [c,b,c | [p,q,r] ]] match or not?
[X, c, b | [c | X ] ] = [X, c, b, c | X ]
[[p,q] | [c,b,c | [p,q,r] ] ] = [[p,q], c,b,c | [p,q,r] ]
[ X, c, b, c | X ] =?=
[[p,q], c,b,c | [p,q,r] ] if X=[p,q] and X=[p,q,r] at the same time, but this is impossible. So, the given lists do not match.
Midterm Review: Examples October 23, 2020 3 / 9
Queries to a KB
Assume that you are given a collection of atomic statements about products available for purchase, manufacturers and prices, using the following predicates:
inStore(ItemID,ProductType,Quantity) – Quantity of a ProductType (it can be
a phone, a laptop, a tablet, etc) with an unique ItemID (it can be any unique item identifier) is available in the store, where Quantity is the number of
the copies of a product that are available in the store.
manufacturer(ItemID,Company,Year) – ItemID has been manufactured by Company in Year.
Formulate the following query in Prolog using these predicates: Find the most popular product available in a store, i.e., the product with the largest quantity.
?- inStore(ItemID,Product,Q),
not ( inStore(ItemID2,Product2,Q2), Q2 > Q )
Find the Apple manufactured product with the largest quantity available in a store.
?- inStore(ID,P,Q), manufacturer(ID,apple,Year),
not ( inStore(ID2,P2,Q2), manufacturer(ID2,apple,Y2), Q2 > Q)
Notice the standard pattern in queries of this kind. Questions ?
Midterm Review: Examples October 23, 2020 2 / 9
Typical errors in recursion
The predicate length(List,N) is true if N is the number of elements in List. Recall what is the recursive program that implements this predicate ?
length([ ],0).
length([ H | T ], N) :- length(T, Interm), N is Interm + 1.
There are several typical errors that students make when writing a recursive rule in the programs of this type.
length([ H | T ], N) :- N is X + 1, length(T, X).
Error: the output X must be computed first from a recursive call, before it an be used
to compute the number of elements N of the given list.
length([ H | T ], N) :- length(T, X), N = X + 1.
Error: to compute addition of X and 1, we must use is since equality “=” only unifies
strings on the left and on the right sides, but it does not compute a sum of X and 1.
length([ H | T ], N) :- N = length(T) + 1.
Error: the predciate length(L,X) can be only true or false, but it does not have a
numerical value, since predciates are not functions.
Midterm Review: Examples October 23, 2020 4 / 9
Arithmetics with addition and multiplication
For simplicity, let us focus on arithmetic expressions with addition and multiplication only. Use the term sum(X , Y ) to represent the sum of X and Y . Use the term prod(X,Y) to represent the product of X and Y.
Last simplification: use one variable only. But any constants are fine.
Example: sum(prod (2, X ), prod (4, 5)) means expression ((2 ∗ X ) + (4 ∗ 5)) Example: prod (sum(X , 7), prod (0, sum(X , 1))) means ((X + 7) ∗ (0 ∗ (X + 1)))
Task: write a program that evaluates our simplified arithmetical expressions for a given number N. The predicate evalPS(E,N,V) is true if V is a value of an arithmetical expression E, when its single variable takes value N. Do case analysis.
evalPS(X,N,Val):- var(X), number(N), Val is N. /*base case: variable*/ evalPS(X,N,Val):- number(X), Val is X. /*base case: constant*/
Both var(X) and number(X) are library predicates. How to write recursive rules? evalPS(sum(L,R),N, Value) :- evalPS(L,N,V1), evalPS(R,N,V2),
Value is V1+V2.
evalPS(prod(L,R),N, Value) :- evalPS(L,N,V1), evalPS(R,N,V2),
Value is V1 * V2.
Warning: only the first answer is correct, need “!” to cut backtracking. Example:
?- evalPS( sum( prod(A,5), prod(A,4)), 2,Val). returns Val=18
Midterm Review: Examples October 23, 2020 6 / 9
Arithmetic abstract syntax trees
Next week we start talking about grammars and parsing in application to English. However, these notions are fundamental for all programming languages. Take a course on the theory of compilation to learn more.
Here, we consider only a simple example: a syntax tree for arithmetical expressions. The binary syntax tree for (3 · a + 5 · (b + a))/(c − (a − (b · c))) is the following (ignore parentheses for simplicity):
Lesson to learn: arithmetic expressions can be represented uniquely as binary trees.
Midterm Review: Examples October 23, 2020 5 / 9
Recursion with arithmetics
Example: compute recursively the sum of a simple series Nk = 1 k = 1 + 2 + 3 + 4 + . . . + N .
Let predicate seriesSum(N, S) be true if S is the sum of the first N terms from this given series. To write a recursive program, do case analysis.
seriesSum(1,1). /* base case */
seriesSum(N,S) :- N > 1, M is N-1,
seriesSum(M,X), /*compute the previous sum recursively*/
S is X + N. /*addthelastterm*/ Let the predicate sumSquares(N, S) be true if S is the sum of the first N squares:
Nk = 1 k 2 = 1 2 + 2 2 + 3 2 + 4 2 + . . . + N 2 .
sumSquares(1,1). /* base case */ sumSquares(N,S) :- N > 1, M is N-1,
sumSquares(M,X), /*compute the previous sum recursively*/ S is X + N∧2. /*addthelastterm*/
Midterm Review: Examples October 23, 2020 7 / 9
Newton-Raphson algorithm
“Newton’s method, also known as the Newton–Raphson method, named after and , is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-valued function.”
(Wikipedia, see animation at https://en.wikipedia.org/wiki/Newton’s_method)
1 Choose an initial guess x0 of the point where the given function f(x)=0.
2 Draw the tangent of the graph of f at the point (x0, f (x0)). Let the point (x1, 0) be the intersection of the x-axis and the tangent. The equation of the tangent line at x0 is y = f′(x0)(x − x0) + f(x0). The x-intercept is the solution x1 of the equation
0=f′(x )(x −x )+f(x ),orx =x − f(x0) ,wheref′ isthederivativeoff. 0 1 0 0 1 0 f′(x0)
3 Repeat the process of successive approximations as x = x − f (xn ) , where n+1 n f′(xn)
f′(xn) is the derivative of f at the point xn. Stop when f(xn) is close to 0.
Example: computing square roots of numbers. Note that computing a square root of a given number N requires finding X such that X 2 − N = 0 Since the derivative of function f(X) = (X2 − N) is simply expression 2 ∗ X, the main recursive formula becomes
xn+1=xn−((xn)2−N) =xn−xn + N =0.5∗(xn+N/xn). 2∗xn 2 2∗xn
The algorithm is well explained at
https://www.math.ubc.ca/ pwalls/math-python/roots-optimization/newton/
Midterm Review: Examples October 23, 2020 8 / 9
Newton’s method for square roots in Prolog
xn+1 = 0.5 ∗ (xn + N/xn).
Only the first answer must be correct. Use the library predicates number(N), checks if N is a number, and abs(X , Y ) that computes Y as the absolute value of the number X .
The predicate nr(N,Appr1,Appr2,E,Result) implements Newton-Raphson algorithm. It is true for a given number N, if Appr1,Appr2 are two successive approximations, E is a precision that determines termination, and Result is √N.
epsilon(E) :- E is 1/1000000.
mySQRT(N,Res):- not number(N), Res=”First argument must be a number”. mySQRT(N,Res) :- Next is N/2, epsilon(EPS), /*choose N/2 as x0 */
nr(N, N, Next, EPS,Res).
/* Check if the algorithm terminates: if the last approximation squared is close to N*/
nr(N,Appr1,Appr2,E,Result) :- Diff is (Appr2)∧2 – N, abs(Diff,Val), Val < E, Result is Appr2.
/* If termination condition is false, then use the recurrence above and continue */
nr(N,Appr1,Appr2,E,Res) :- NewAppr is 0.5* (Appr1 + N/Appr1),
nr(N, Appr2, NewAppr, E,Res).
?- mySQRT(65536, X).
X = 256.00000000000648
?- mySQRT(256, X).
X = 16.000000000000341
Midterm Review: Examples
?- mySQRT(16, X).
X = 4.0000000000000044
October 23, 2020
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com