Mathematics for Computer Science
6.4. Strong Induction vs. Induction vs. Well Ordering 153 the student was infected at the previous step (since beaver flu last ...
Chapter 6 Induction154 Here’s a bogus proof of a very important true fact, every integer greater than 1 is aproduct of a unique ...
6.4. Strong Induction vs. Induction vs. Well Ordering 155 Homework Problems Problem 6.23. A group ofn 1 people can be divided i ...
Chapter 6 Induction156 False Claim.Every Fibonacci number is even. Bogus proof.Let all the variablesn;m;kmentioned below be nonn ...
6.4. Strong Induction vs. Induction vs. Well Ordering 157 statesWWDN^3 start stateWWD.a;b;1/ (wherea > b > 0) transitionsW ...
...
7 Recursive Data Types Recursive data typesplay a central role in programming, and induction is really all about them. Recursive ...
Chapter 7 Recursive Data Types160 Definition 7.1.1.LetAbe a nonempty set called analphabet, whose elements are referred to ascha ...
7.1. Recursive Definitions and Structural Induction 161 Definition 7.1.3.Theconcatenationstof the stringss;t 2 Ais defined rec ...
Chapter 7 Recursive Data Types162 We must show thatP.s/holds: jstjDjha;ritj Djha;rtij (concat def, constructor case) D 1 Cjr ...
7.2. Strings of Matched Brackets 163 We’ll need the following lemma in the next section: Lemma 7.1.6. #c.st/D#c.s/C#c.t/: The e ...
Chapter 7 Recursive Data Types164 Expression Parsing During the early development of computer science in the 1950’s and 60’s, cr ...
7.2. Strings of Matched Brackets 165 Now, [] [ ]D[ ] [ ] 2 RecMatch (lettingsD;tD[ ]) [ [ ] ]D[ [ ] ] 2 RecMatch (lettingsD[ ...
Chapter 7 Recursive Data Types166 Definition 7.2.2.Define the set, AmbRecMatchf];[grecursively as follows: Base case: 2 Amb ...
7.3. Recursive Functions on Nonnegative Integers 167 7.3.1 Some Standard Recursive Functions onN The Factorial function. This fu ...
Chapter 7 Recursive Data Types168 f 2 .n/WWD ( 0; ifnD0; f 2 .nC1/ otherwise: (7.3) This “definition” has a base case, but still ...
7.4. Arithmetic Expressions 169 “linear” but with a slow growing coefficient nearly equal to the inverse Ackermann function. Thi ...
Chapter 7 Recursive Data Types170 [ef] 2 Aexp. The expression[ef] is called aproduct. The Aexp’seandf are called thecomponent ...
7.4. Arithmetic Expressions 171 For example, here’s how the recursive definition of eval would arrive at the value of 3 Cx^2 whe ...
Chapter 7 Recursive Data Types172 Here’s how the recursive definition of the substitution function would find the result of subs ...
«
4
5
6
7
8
9
10
11
12
13
»
Free download pdf
