Class notes
Problem Solving and Search summary
- Course
- Institution
- Book
This document summarizes all lectures given during the Problem Solving and Search course at the UvA. With this summary I completed this course with an 8.
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
1 review
By: iyoasennay • 1 year ago
Seller
Follow
camilleniessink1
Reviews received
Content preview
PROBLEM SOLVING AND SEARCHLecture 1
Imperative (programs as recipes)
function sum(list : List) : Nat
i = 0
while (i < list.lenght)
sum = sum + list[i]
i++
return sum
Functional (programs as functions e.g. Haskell)
sum [] = 0
sum (x : xs) = x + sum xs
Declarative (programs as ‘problems’ e.g. Prolog)
sum([], 0).
sum([Head | Tail, Result):-
sum(Tail, S),
Result is Head + S.
● Imperative programming: specify how to compute
● Declarative programming: specify what to compute
The origins of Prolog (PROgrammation en LOGique):
● Invented in the 1970s by Alain Colmerauer and a team of researchers in France – using
a natural language like French to reason and communicate directly with a computer
● Originally intended for natural language processing – clear and concise programs
● Prolog and Lisp are the two main AI programming languages today
● There are different interpreters, we will use SWI-Prolog
bigger(elephant, horse).
bigger(horse, donkey).
bigger(donkey, dog).
bigger(donkey, monkey).
,?- bigger(donkey, dog).
true
?- bigger(monkey, elephant).
false
?- bigger(elephant, monkey).
false
bigger(X, Y) :- bigger(X, Z), bigger(Z, Y).
?- bigger(elephant, monkey).
true
?- bigger(X, donkey).
X = horse ;
X = elephant ;
false
?- bigger(donkey, X), bigger (X, monkey).
X = dog
?- bigger(donkey, X), bigger(Y, monkey).
X = dog
Prolog terms are either:
● Variables
● Atomic terms: numbers and atoms
● Compound terms
Variables start with a capital letter or the underscore: X, Elephant, _G177, MyVariable, _
Anonymous variable: _
Atoms start with a lowercase letter or are enclosed in single quotes: elephant, xYZ, a_123,
‘Hello?’
Compound terms consist of a functor (an atom) and a number of arguments (terms) enclosed in
brackets: bigger(horse, X)
f(g(Alpha, _), 7)
‘female’(dog)
Ground terms are terms without variables
Facts are compound terms (or atoms), followed by a full stop
, Facts are used to define something as being unconditionally true
bigger(elephant, horse).
parent(john, mary).
Rules consist of a head and a body separated by ‘:-’
The head of a rule (a compound term or an atom) is true if all goals in the body (each a
compound term or an atom) can be proved to be true
grandfather(X, Y) :-
father(X, Z),
parent(Z, Y).
Facts and rules are used to define predicates
Facts and rules are also called clauses
A program is a list of clauses
● Compose your programs in a text editor
A query consists of one or several compound terms (or atoms), separated by commas and
followed by a full stop
● Type your queries in the Prolog prompt and expect a response
● ?- bigger(horse, X), bigger(X, dog).
X = donkey
true
Built-in predicates:
● Compiling a program file:
?- consult(‘big-animals.pl’).
true
● Writing something (a term) on the screen:
?- write (‘Hello!’), nl, write(‘Goodbye!’)
Hello!
Goodbye!
true
Two terms match if they are identical or can be made identical by substituting their variables
with suitable ground terms
We can explicitly ask Prolog whether two given terms match by using the built-in
equality-predicate:
?- born(mary, yorkshire) = born(mary, X).
X = yorkshire
true
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller camilleniessink1. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $9.62. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
53022 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now