The list of topics includes an estimate of %-weight assigned to each topic.
· (about 10%) Formulate queries in Prolog (as in A1, Part 1 and in midterm). Note you have to write queries, not the rules. The queries are conjunctions of predicates that can be negated. Negation can be applied not only to a single predicate, but to a conjunction of predicates as well, e.g.,
· ?- predicate(X,Y), not ( predicate1(X), predicate2(Y), X > Y ).
The latter is a common query pattern in Prolog that allows to retrieve from the data base an unique element characterized by super-lative adjectives such as the oldest, the largest, the cheapest, and so on.
Copyright By PowCoder代写加微信 assignmentchef
· (about 8%) Structures in Prolog: how to use terms inside predicates, recursive programs with terms. For example, a family database (with terms for a person and date of birth), a binary tree example, or using the term next(H,T) to represent a list [H | T]. You can read the handout about binary trees as terms (posted on D2L) that includes an exercise. Read also similar exercises in the midterm review PDF files, your personal notes, and/or quizzes.
· (about 15%) Recursive programs (possibly with arithmetics), recursion over lists and over terms (A1 and A2, Parts 2 and 3, and the sample midterm questions). Read all handouts posted in Documents folder on D2L. Use case analysis: for each case you have to write a separate rule. Usually, you check a condition, and if it is true, do what is required, and then, sometimes, make a recursive call. Make sure you understand clearly which arguments in the given predicate provide input to your program, and which arguments are used to return the results. You have to understand how to write programs for predicates “append(L1,L2,L3)” and “member(Element,List)”. However, the actual test questions about recursion will likely not need “append” and “member”, and it is possible that programs must be written without these predicates. E.g., we can easily write recursive programs for “length(L,N)”, “sum(List,S)” and for “replaceOne(X,Y,L1,L2)”, “replaceAll(X,Y,L1,L2)” without using “append” and “member”. In D2L cps721 course shell, read handouts related to the 2nd assignment that we discussed in class (“city reachable from Toronto”, “blocks world”).
You have to know the following topics:
· – arithmetics in Prolog
· – using case analysis when developing a recursive program
· – order of predicates in rules (is it important or not?)
· – order of rules in a program (what happens if one changes the order of rules)
· – negated predicates in recursive rules
· – recursive programs with terms (structures) inside predicates
· (about 12%) Constraints (A3 and a midterm question about a CSP). Read slides from the class. Read also your lecture notes: we discussed in class the standard techniques. You have to know 2 approaches to solving problems with constraints: “pure generate and test” technique and “interleaving of generate and test”. Note how dependency graph helps to choose an efficient order of constraints. Start solving this kind of exercises with writing facts that characterize all elements in the given finite domain. This can be done by writing a few atomic statements using a given predicate. The same predicate should be used throughout your program to retrieve values for variables (i.e., to “generate” values for variables). Next, think how many variables you need. This is always stated informally in English in the problem: number of the variables depend on how many unknowns you have. Then, write the single Prolog rule implementing the predicate solve(List). In this rule, implement all of the constraints. If you decide to use any helping predicates, then implement them.
· (about 15-20%) Natural Language Understanding (NLU)
· main concepts, levels of analysis, applications;
· grammars;
· parsing of noun phrases and simple sentences: you should be able to draw a successful parsing tree given a grammar and a sentence or a noun phrase (parsing trees are different from a query evaluation trees since in the parsing tree you need neither branches that fail, nor backtracking);
· implementation of NLU systems (Assignment 4): there is no need to memorize the parser, but you are expected to understand how it works.
You can read examples of parsing in your lecture and lab notes on NLU.
· (about 5%) General questions (short essay can be expected). You can read also handouts and lecture notes. Pay attention to what has been discussed in the 1st and 2nd weeks of classes (in September).
· (about 20-25%) Problem solving and planning (A5):
· – properties of the general problem solver: what happens during the 1st stage (when the recursive rule for the predicate “reachable(S,L)” is applied) and what happens during the 2nd stage (when the program is searching for a sequence of legal moves).
· – the predicate legal_move(S2,M,S1): why is it useful (hint: it serves two different purposes)
· – predicates max_length(List,N) and reverse(List1,List2): what they do
· – situations and fluents approach: main advantages and main differences from the state-based approach
· – precondition axioms (how to write them)
· – successor state axioms (SSA): how to write them. There are 2 main types of successor state axioms. Each positive effect axiom is saying when the fluent becomes true after doing an action. There is a separate rule for each action that makes fluent true. As for negative effect rules, recall that when you write a SSA saying that the fluent truth value is preserved, you have to say the fluent remains true unless none of the actions that make it false was the last action that was executed, i.e, you have to write a conjunction of the form (not A=act1, not A=act2, ) on the RHS of the rule.
· – complexity of planning, what kind of search strategies we can use to save time on search
· – depth-first search (DFS) and breadth-first search (BFS)
· – declarative heuristics and how the predicate “useless” helps to save time on search.
Read your lecture notes (e.g., tiles on a grid example), your quiz, assignment 5 and the examples of precondition and successor state axioms discussed in class and during the tutorial. In total, more than 5 different examples have been discussed.
· (about 12-15%) Bayesian Networks
· – basic probability theory: axioms of probability, conditional probability, joint probability, chain product rule, marginal probability, discrete random variables, joint probability distributions of discrete random variables, independence, conditional independence of a random variable from other variables, what computational advantage is provided by independence: examples.
· Bayesian Network: definition, conditional probability tables, main properties.
· Why Bayesian networks are useful and popular
· How to use Bayesian networks to compute joint probability
· How to use joint probability distribution to answer queries about conditional probabilities (recall: marginalization).
· Examples of Bayesian Networks.
Read your lecture notes (we discussed a few examples in class), your lab notes, and handouts on Bayesian Networks posted in the Documents folder on D2L.
程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.