5CCS2FC2: Foundations of Computing 代写案例
Question A
Construct a instance of SAT (i.e. a collection of propositional clauses) F with propo- sitional variables from {P,Q,R,S,T,X} such that when applying the DPLL algorithm to F :
-
(i) The algorithm terminates successfully with the following satisfying partial assignment: {P,Q,¬R,S,¬T}
(You may allow either X or ¬X as part of your assignment.)
-
(ii) The algorithm applies Unit Propagation at least once,
-
(iii) The algorithm applies Pure Literal Elimination at least once,
-
(iv) The algorithm branches and then backtracks at least once.
-
List the clauses from your constructed instance of SAT F meeting the above criteria (i)–(iv). Partial marks will be awarded for answers satisfying some but not all of the criteria [4 marks]
-
Demonstrate that your constructed instance of SAT F satisfies the criteria (i)–(iv) by applying the DPLL algorithm to F and recording the sequence of rules that are applied at each step. [4 marks]
★ A bonus mark is available for SAT instances that are judged to be interesting and original.
Question B
For the following question you will be require to construct your own language L with the following properties:
-
(i) L is not a regular langauge, i.e. it is not decided by any finite automaton,
-
(ii) L can be decided by a Turing Machine,
-
(iii) L is not an example of a non-regular language found in the course materials (Lecture slides/videos, LGTs, SGTs).
-
StateyourlanguageLsatisfyingthecriteria(i)–(iii)describedaboveandlistFIVE words that belong to L. [1 marks]
-
Prove that your language L is non-regular using proof by contradiction. [6 marks]
-
Construct a (deterministic or non-deterministic) Turing Machine M such that Language(M ) = L, i.e. M accepts all words w ∈ L and rejects all words w ∈/ L. [5 marks]
★ A bonus mark is available for languages and/or Turing Machines that are judged to be interesting and original.
Question C
Construct a recurrence relation T (n) of the form
(i) T(n)∈Θ(nlog2n),
(ii) T(n) ≥ 3nlog2(n), for all n ≥ 1
Tip: The Master Theorem may provide you with a good starting point but you may need to fine-tune you choice of a, b and f (n) to satisfy condition (ii).
-
State your recurrence relation T (n) that satisfying conditions (i)–(ii) above. [2 marks]
-
ListthefirstfivetermsT(2),T(3),T(4),T(5),andT(6)generatedbyyour recurrence relation T (n). [1 marks]
-
Prove by induction on n that your chosen recurrence relation T (n), satisfies the criterion (ii). i.e. that:
T(n) ≥ 3nlog2(n) for all n ≥ 1. Marks will be awarded for the precision, clarity, and correctness of
your proof. [7 marks]
★ A bonus mark is available for recurrence relations that are judged to be interesting and original.
咨询 Alpha 小助手，获取更多课业帮助