Mathematics for Computer Science
5.4. State Machines 133 0 1 2 3 0 1 2 x y goal ‹‹ Figure 5.9 Can the Robot get to.1;0/? ...
Chapter 5 Induction134 . ̇1/C. ̇1/, that is, by 0, 2, or -2. Of course, adding 0, 2 or -2 to an even number gives an even number ...
5.4. State Machines 135 ifqandrare consecutive states in the sequence, thenq!r. A state is calledreachableif it appears in som ...
Chapter 5 Induction136 Robert W. Floyd The Invariant Principle was formulated by Robert W. Floyd at Carnegie Tech in 1967. (Carn ...
5.4. State Machines 137 5.4.4 The Die Hard Example The movieDie Hard 3: With a Vengeanceincludes an amusing example of a state m ...
Chapter 5 Induction138 such that 0 b5;0l 3. (We can prove that the reachable values ofband lwill be nonnegative integers, bu ...
5.4. State Machines 139 To prove thatPis a preserved invariant of Die-Hard-Once-and-For-All machine, we assumeP.q/holds for some ...
Chapter 5 Induction140 fewer multiplications by using a technique calledFast Exponentiation. The regis- ter machine program belo ...
5.4. State Machines 141 Ifzis even, then we have thatxtDx^2 ;ytDy;ztDz=2. Therefore,zt 2 N and ytxtztDy.x^2 /z=2 Dyx^2 z=2 Dyxz ...
Chapter 5 Induction142 5.4.6 Derived Variables The preceding termination proof involved finding a nonnegative integer-valued mea ...
5.4. State Machines 143 Theorem 5.4.7 generalizes straightforwardly to derived variables taking values in a well ordered set (Se ...
Chapter 5 Induction144 Figure 5.10 Gehry’s new tile. Now it’s easy to check that if.x;y/!.x^0 ;y^0 /is a legitimate robot move, ...
5.4. State Machines 145 Figure 5.11 The induction hypothesis for the false theorem. Inductive step: Assume thatP.n/is true for s ...
Chapter 5 Induction146 Identify the induction hypothesisP.n/. Establish the base case. Prove thatP.n/)P.nC1/. Conclude thatP.n/ ...
5.4. State Machines 147 False Theorem.For alln 0 , 2 C 3 C 4 CCnD n.nC1/ 2 Proof. We use induction. LetP.n/be the propositio ...
Chapter 5 Induction148 AnnC 1 -bit adderadds twonC 1 -bit binary numbers. More precisely, an nC 1 -bit adder takes two lengthnC ...
5.4. State Machines 149 Problem 5.10. The Math for Computer Science mascot, Theory Hippotamus, made a startling discovery while ...
Chapter 5 Induction150 Prove the Distributive Law of intersection over the union ofnsets by induction: A\ [n iD 1 BiD [n iD 1 .A ...
5.4. State Machines 151 Exam Problems Problem 5.13. Prove by induction: Xn iD 0 i^3 D n.nC1/ 2 2 ; 8 n0: (5.17) using the e ...
Chapter 5 Induction152 (j) 9 n: 9 m > n:ŒP.2n/AND NOT.P.2m//ç (k)Œ 9 n:P.n/çIMPLIES 8 n: 9 m > n:P.m/ (l) NOT.P.0//IMPLIES ...
«
3
4
5
6
7
8
9
10
11
12
»
Free download pdf
