235-Ch5-离散数学英文版

1、Chapter 5: Induction and Recursion (Part 2),Elements of Discrete Structures,Recursively Defined Functions,Define a function f(n) recursively, n is an integer and n 0 : Basis Step: Specify the value of the function at n = 0 (or a special value): f(0) Recursive Step: For n 0, specify a rule for produc

2、ing the value of f(n+1) from f(n) Example: f(0) = 3 f(n+1) = 2f(n) + 3f(3) = 2f(2) + 3 = 2(2f(1) + 3) + 3 = 2(2(f(0) + 3) + 3) + 3 = 2(2(3 + 3) +3) + 3 = 45,Recursive Function Example,Recursive definition of factorial function f(n) = n! = n(n-1)(n-2)21 and f(0) = 0! = 1 Basis: f(0) = 1 Recursive: f(

3、n+1) = (n+1) f(n) f(5) = 5f(4) = 54f(3) = 543f(2) = 5432f(1) = 54321f(0) = 543211 = 120,Recursive Function Example,Give a recursive definition of: Solution: The first part of the definition is The second part is,Fibonacci Function,f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2) for n = 2, 3, 4, .,f(2) =

4、f(1) + f(0) = 1 + 0 = 1 f(3) = f(2) + f(1) = 1 + 1 = 2 f(4) = f(3) + f(2) = 2 + 1 = 3 f(5) = f(4) + f(3) = 3 + 2 = 5 f(6) = f(5) + f(4) = 5 + 3 = 8 We denote Fibonacci numbers as fn = f(n), n = 0, 1, 2, ,Fibonacci Numbers,Suppose a newly-born pair of rabbits, one male, one female, are put in a field

5、. Rabbits are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rabbits. Suppose that our rabbits never die and that the female always produces one new pair (one male, one female) every month,f1 = 1 f2 = f1 + f0 = 1 + 0 = 1 f3 = f2 + f1

6、= 1 + 1 = 2 f4 = f3 + f2 = 2 + 1 = 3 f5 = f4 + f3 = 3 + 2 = 5 f6 = f5 + f4 = 5 + 3 = 8,Fibonacci Example,Theorem: When n 3, fn n-2, = (1 + 5)/2 Proof by strong induction Basis step: For n = 3, f3 = 2 = (1 + 5)/2 (5 = 2.236)For n = 4, f4 = 3 2 = (3 + 5)/2 Why we need to prove n = 3 and n = 4?,Fibonac

7、ci Example,Inductive step: Assume fj j-2, for all j, 3 j k, k 4. We must show that fk+1 k-1. Note that fk+1 = fk + fk-1By induction assumption, fk k-2 and fk-1 k-3So, fk+1 = fk + fk-1 k-2 + k-3 We now only need to show that k-2 + k-3 = k-1 is a solution of x2 x 1 = 0, so 2 = + 1k-1 = 2 k-3 = ( + 1)

8、k-3 = k-2 + k-3,Recursively Defined Infinite Sets,Basis Step: Specify an initial collection of elements in the set Recursive Step: Provide rules for forming new elements in the set from those already known to be in the set Example: Basis Step: 3 S Recursive Step: if x S and y S then x + y S Then, S

9、= 3, 6, 9, 12, 15, 18, 21, ,Recursive Definition of Strings,Set of strings, denoted as *, over an alphabet or symbol set can be defined recursively by Basis: * ( is the empty string) Recursive: if w * and x , then wx * Example: = 0, 1. * contains the following: empty string 0, 1 00, 01, 10, 11 000,

10、001, 010, 011, 100, 101, 110, 111, ,String Concatenation,Definition: Two strings can be combined via the operation of concatenation(串联). Let be a set of symbols and * be the set of strings formed from the symbols in . We can define the concatenation of two strings, denoted by , as follows For any w

11、*, w = w, is the empty string If w1 * and w2 *, then the concatenation of w1 and w2 is w1 w2 or just w1 w2 If w1 = abra and w2 = cadabra, the concatenation w1 w2 = abracadabra,Length of String,Length of a string is defined as the number of symbols in the string Recursive definition of length of a st

12、ring Basis: l() = 0 Recursive: l(wx) = l(w) + 1, w * and x Let be the English letters. Find the length of “math”: l(math) = l(mat) + 1 = (l(ma) + 1) + 1 = (l(m) + 1) + 1) + 1 = (l() + 1) + 1) + 1) + 1 = (0 + 1) + 3 = 4,Balanced Parentheses,Example: Give a recursive definition of the set of balanced

13、parentheses P Solution: Basis Step: () P Recursive Step: If w P, then () w P, (w) P and w () P. Show that ()() is in P. Why is )() not in P?,Well-Formed Formulas(合适公式)Example,Well-Formed Formulas for compound propositions include T, F, propositional variables and operators (, , , , ) Recursive defin

14、ition of well-formed formulas: Basis: T, F and any propositional variable x are well-formed formulas Recursive: if A and B are well-formed formulas, then A, A B, A B, A B and A B are also well-formed formulas,Well-Formed Formulas Example,Examples. Are the following well-formed formulas? (From defini

15、tion, start with the variable of single-operand operator ) (A ( ( B) (C) (D) ( (A B) C) (A ( B) (D) (A B) C,Full Binary Tree (满二叉树)Example,Basis Step: any single node is a binary tree Inductive Step: : If T1 and T2 are full binary trees, then the following tree T is also a full binary tree: pick a n

16、ew root node and attach it to the root of T1 as a left subtree and to the root of T2 as a right subtree (T1 and T2 can be the same). Denoted T = T1T2,So, what is a full binary tree?,Basis: the empty set is an extended binary tree Inductive: : If T1 and T2 are extended binary trees, then the followin

17、g tree T is also an extended binary tree: pick a new root node and attach it to the root of T1 as a left subtree and to the root of T2 as a right subtree (T1 and T2 can be the same). Denoted T = T1T2,Extended Binary Tree Example,T0,T1,T2,T3,T4,T1,T1,T1,T0,T1,T0,T0,T5,T6,T7,T8,T9,T13,T0,Structural In

18、duction,Applying Structural Induction for recursively defined sets Basis Step: Show that the result is true for all elements specified in the basis step of the recursive definition Recursive (or inductive) Step: Show that, if the result is true for the old elements used in constructing new elements,

19、 then it is also true for the new elements,Induction Example,Show that the set S recursively defined as “3 S and if x S and y S then x + y S”, is the set of all positive integers that are multiples of 3 Proof: let A be the set of all positive integers that are multiples of 3, A = 3n | n = 1, 2, . We

20、 need to prove A S and S A, which proves S = A A S: (Simple Induction on n) when n = 1, 3 S. Assume when n = k, 3k S. For n = k+1, we need to show that 3(k+1) S. 3(k+1) = 3k + 3, by induction assumption 3k S. Also from induction basis, 3 S. By recursive definition of S (let x = 3k and y = 3), 3(k+1)

21、 = 3k + 3 S,Structural Induction Example,Proof (continued): S A : (Structural Induction) we need to show that any element in S is a multiple of 3 ( A)Basis step: 3 is in S and 3 is a multiple of 3Recursive step: assume the elements (x and y) used to build new elements are true (multiples of 3). Show

22、 that the newly built elements (x + y) is also true (multiple of 3). We know by previous knowledge that if 3 | x and 3 | y, then 3 | (x + y). So, x + y A,Structural Induction Example,Use structural induction to show that l(xy) = l(x) + l(y) l(w) = length of string w and x, y, w * over symbol set Bas

23、is step: (Induction on length of y). When length of y = 0, y = . l(x) = l(x) = l(x) + 0 = l(x) + l() Recursive step: assume l(xy) = l(x) + l(y), when length of y = k. We need to prove, when the length of ya is k + 1, a , l(xya) = l(x) + l(ya) By definition of length, l(xya) = l(xy) + 1 = l(x) + l(y)

24、 + 1 (by induction assumption) = l(x) + l(ya) (by definition of length),Binary Tree Example,Recursive Definition of the height of a full binary tree T, denoted h(T):Basis: The height of the full binary tree of only a root is zero: h(T) = 0Recursive: If T1 and T2 are full binary trees, then the full

25、binary tree formed from them, T = T1T2, has height h(T) = 1 + max(h(T1), h(T2),Binary Tree Example,Recursive Definition of the number of nodes in a binary tree T, denoted n(T):Basis: The number of nodes of the full binary tree of only a root: n(T) = 1Recursive: If T1 and T2 are binary trees, then th

26、e number of nodes for the full binary tree T = T1T2 isn(T) = 1 + n(T1) + n(T2),Binary Tree Example,Theorem: If T is a full binary tree T, then n(T) 2h(T)+1 1 (i) Proof by structural InductionBasis: for a full binary tree of only a root, n(T) = 1 and h(T) = 0. So, 1 = n(T) 2h(T)+1 1 = 21 1 = 1Inducti

27、ve: Assume for full binary tree T1, n(T1) 2h(T1)+1 1 (ii) and for full binary tree T2 , n(T2) 2h(T2)+1 1 (iii)we need to show that if T = T1T2 , then (i) holds,Binary Tree Example,Proof (continued)n(T) = 1 + n(T1) + n(T2) (recursive definition) 1 + (2h(T1)+1 1) + (2h(T2)+1 1) (ii) and (iii) = 2h(T1)

28、+1 + 2h(T2)+1 1 2max(2h(T1)+1, 2h(T2)+1 ) 1 = 22max(h(T1)+1, h(T2)+1) 1 (max(2x, 2y) =2max(x, y) = 22max(h(T1), h(T2)+1 1 = 22h(T) 1(recursive definition of h(T) = 2h(T)+1 1,n(T2) = 3, h(T2) = 1, verify that n(T2) 2h(T2)+1 1 n(T3) = 5, h(T3) = 2, verify that n(T3) 2h(T3)+1 1 n(T5) = 7, h(T5) = 2, ve

29、rify that n(T5) 2h(T5)+1 1,Binary Tree Example,Recursive Algorithms,Definition:An algorithm is called recursive if It solves a problem by reducing it to an instance of the same problem with smaller input This reduction must lead to the basis step for which the solution is known,Factorial Recursive A

30、lgorithm,Computing n! based on the recursive definition(i) 0! = 1 and (ii) n! = n (n1)! for n 0 procedure factorial(n: nonnegative integer) if n 1 then factorial(n) := 1 Basis Step else factorial(n) := n factorial(n - 1) How is factorial(6) calculated?,Power Recursive Algorithm,Computing an based on

31、 the recursive definition(i) a0 = 1 and (ii) an = a an-1 for n 0 procedure power(a: nonzero real number, n: nonnegative integer) if n = 0 then power(a, n) := 1 else power(a, n) := a power(a, n 1) How is 24 is computed in power?,Sum Recursive Algorithm,We use recursive algorithm to compute the sum of

32、 n numbers a1, a2, , an. Example of sum(a1, a2, a3: 3) = ,procedure sum(a1, , an: list, n: positive Integer) if n = 1 then sum(a1, , an, n) = a1 else sum(a1, , an, n) = an + sum(a1, , an, n-1),GCD Recursive Algorithm,Computing gcd(a,b) based on (i) Basis step: gcd(a,0) = a when a 0, and (ii) Recursi

33、ve step: gcd(a, b) = gcd(b, a mod b) for b 0 procedure gcd(a, b: nonnegative integers with a b) if b = 0 then gcd(a, b) := a else gcd(a, b) := gcd(b, a mod b) Example: Compute gcd(44, 24),Binary Search Recursive Algorithm,Binary search in a sorted list of n elements can be reduced to a comparison wi

34、th the middle elements and a binary search of one of the two smaller lists with (n+1)/2 elements,procedure binary-search(i, j, x) Data in a1, , an in ascending order m := (i + j)/2 if x = am then return mm is the location for x else if (x am and j m) then binary-search (m+1, j, x) else return 0Not f

35、ound! Output is the location of the term equal to x, or 0 if not found ,Example: a=(2, 3, 5, 6, 8), binary-search(1, 5, 8) = = 5,First split list successively into pairs so the result is a balanced binary tree (upper half) Sorting is done by successively merging the pairs of lists in ascending order

36、 (bottom half),Merge Sort(归并排序) Algorithm,Split,Merge,Recursive Algorithm for Merge Sort,Procedure mergesort uses a subroutine merge (on the next slide) to merge two lists into a sorted one in ascending order,procedure ms(L = a1, , an) ms for mergesort, omitting n if n 1 then return L else m := n/2

37、L1 := a1, , am L2 := am+1, , an L := merge( ms(L1), ms(L2) ),Example: ms(8, 2, 3, 6, 1) = ,Merging Example,L,L1,L2,Merging Two Lists,procedure merge(L1, L2: sorted lists in nondecreasing order) L := empty list while L1 and L2 are both nonempty Remove smaller of first element of L1 and L2 from the li

38、st it is in and add it to the end of L. if removal of this element makes one list empty then Remove all elements from the remaining list and append them to L return L L is the merged list with elements in nondecreasing order,Time Complexity of Merge,Let m, 2 m n, be the total number of numbers in th

39、e two lists to be merged. n is the number of numbers to be sorted by mergesort Every comparison results in one element being removed from one of the two lists There will be at most m 1 comparisons (the last one does not need a comparison) This leads to O(m) time complexity,Time Complexity of Merge S

40、ort,Let n be the number of numbers to be sorted and is a power of 2 (n = 2k, for some positive integer k. So, k = log2(n) This makes the tree a complete binary tree (worst case). When the height is k, there are n (= 2k) leaves In merging the lists, the first step is to compare and sort the numbers a

41、t the leaves: n/2 comparisons The last step is compare and sort two lists right under the root: n 1 comparisons,Time Complexity of Merge Sort,Time complexity of the recursive merge sort algorithm is kO(n) = O(kn) = O(nlog2n),height=k: n/2 = O(n)Comparisons,Each height from 2 to k-1:n/2 Comparisons n

42、-1Also O(n),height=1: n 1 = O(n)Comparisons,height=k-1: 3(n/4) = O(n)Comparisons,11,7,8,5,9,1,3,4,12,16,6,10,14,2,15,13,7 11,5 8,1 9,3 4,12 16,6 10,2 14,13 15,5 7 8 11,1 3 4 9,6 10 12 16,2 13 14 15,1 3 4 5 7 8 9 11,2 6 10 12 13 14 15 16,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,Time Complexity of Merge Sort,Total number of comparisons is Time complexity of the recursive merge sort algorithm is O(nlog2n),(Same as in the textbook),Recursion versus Iteration,Rec