|
Back to practice exercises.
1: Background Reading
2: Learning Goals
- Define/read/write/trace/debug the BottomUp proof procedure
- Define/read/write/trace/debug the TopDown proof procedure
- Define/read/write/trace/debug the TopDown proof procedure as a search problem
- Represent simple domains in Datalog
- Apply TopDown proof procedure in Datalog
3: Directed Questions
- If KB is a knowledge base and g is a conjunction of atoms, what is meant by KB |- g? [solution]
- Given a proof procedure, a knowledge base KB and a conjunction of atoms g, what is
meant by KB |= g? [solution]
- Define what it means for a proof procedure to be sound. [solution]
- Define what it means for a proof procedure to be complete. [solution]
- What is the key idea of the bottom-up proof procedure? [solution]
- How do you know when you have completed a successful derivation using the bottom-up
proof procedure? [solution]
- How can the bottom-up proof procedure show that there is no successful derivation? [solution]
- What is the key idea of the top-down proof procedure? [solution]
- How do you know when you have completed a successful derivation using the top-down
proof procedure? [solution]
- Give an example of an admissible heuristic for top-down search. [solution]
4: Exercise: Datalog
A university has asked you to write a program to help them determine whether or not to accept
students who have applied for admission. There are 3 basic pathways for a student to be accepted.
If a student is returning to the university after a time away and is in good academic standing
with no outstanding fees, they are accepted. Students who submit a complete application and
are qualified are also accepted. Students are qualified if they have high SAT scores as well as
good high-school transcripts. The university also has a legacy program, wherein children of
former graduates are qualified (though these student must still submit a complete application).
For brevity, let's only talk about 3 individuals: Sam is a former graduate and Chris is his son.
Chris has good high-school transcripts and he submitted a complete application. Laura is a
returning student in good academic standing.
- Give the knowledge base representing this problem, using unary predicates accepted,
returning, goodStanding, clearBalance, appComplete, qualified, legacyStudent,
highSAT, goodHS, and graduate, as well as the binary predicate child. The university
admissions officials should be able to provide queries such as accepted(chris) and get a
true or false answer. [solution]
- Load your KB in the deduction tool, and run the top-down derivation of the query accepted(chris) applied to your KB. [solution]
- Now run the query accepted(laura) and examine one of the failing top-down derivations of the query. [solution]
5: Learning Goals Revisited
- Define/read/write/trace/debug the BottomUp proof procedure
- Define/read/write/trace/debug the TopDown proof procedure
- Define/read/write/trace/debug the TopDown proof procedure as a search problem
- Represent simple domains in Datalog
- Apply TopDown proof procedure in Datalog
|
