Ch离散数学英文实用.pptx

《Ch离散数学英文实用.pptx》由会员分享，可在线阅读，更多相关《Ch离散数学英文实用.pptx（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Recursively Defined FunctionsDefine 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 producing 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、(2(f(0)+3)+3)+3=2(2(3+3)+3)+3=45第1页/共44页Recursive Function ExampleRecursive definition of factorial function f(n)=n!=n(n-1)(n-2)21 and f(0)=0!=1Basis:f(0)=1Recursive:f(n+1)=(n+1)f(n)f(5)=5f(4)=54f(3)=543f(2)=5432f(1)=54321f(0)=543211=120第2页/共44页Recursive Function ExampleGive a recursive definition o

3、f:Solution:The first part of the definition isThe second part is第3页/共44页Fibonacci Functionf(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2)for n=2,3,4,.f(2)=f(1)+f(0)=1+0=1f(3)=f(2)+f(1)=1+1=2f(4)=f(3)+f(2)=2+1=3f(5)=f(4)+f(3)=3+2=5f(6)=f(5)+f(4)=5+3=8We denote Fibonacci numbers as fn=f(n),n=0,1,2,第4页/共44页Fibonacci

4、NumbersSuppose a newly-born pair of rabbits,one male,one female,are put in a field.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(

5、one male,one female)every month f1=1f2=f1+f0=1+0=1f3=f2+f1=1+1=2f4=f3+f2=2+1=3f5=f4+f3=3+2=5f6=f5+f4=5+3=8第5页/共44页Fibonacci ExampleTheorem:When n 3,fn n-2,=(1+5)/2Proof by strong inductionBasis step:For n=3,f3=2 =(1+5)/2(5=2.236)For n=4,f4=3 2=(3+5)/2Why we need to prove n=3 and n=4?第6页/共44页Fibonacc

6、i ExampleInductive 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)k-3=k-2+k-3第7页/共44页Recursively Define

7、d Infinite SetsBasis Step:Specify an initial collection of elements in the setRecursive Step:Provide rules for forming new elements in the set from those already known to be in the setExample:Basis Step:3 SRecursive Step:if x S and y S then x+y SThen,S=3,6,9,12,15,18,21,第8页/共44页Recursive Definition

8、of StringsSet of strings,denoted as *,over an alphabet or symbol set can be defined recursively byBasis:*(is the empty string)Recursive:if w *and x ,then wx *Example:=0,1.*contains the following:empty string 0,100,01,10,11000,001,010,011,100,101,110,111,第9页/共44页String ConcatenationDefinition:Two str

9、ings 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 followsForanyw *,w =w,is the empty stringIfw1 *and w2 *,then the concatenation of w1and w2 is w1 w2 or

10、 just w1w2If w1=abra and w2=cadabra,the concatenation w1w2=abracadabra第10页/共44页Length of StringLength of a string is defined as the number of symbols in the stringRecursive definition of length of a stringBasis:l()=0Recursive:l(wx)=l(w)+1,w *and x Let be the English letters.Find the length of“math”:

11、l(math)=l(mat)+1=(l(ma)+1)+1=(l(m)+1)+1)+1=(l()+1)+1)+1)+1=(0+1)+3=4第11页/共44页Balanced Parentheses Example:Give a recursive definition of the set of balanced parentheses P Solution:Basis Step:()PRecursive Step:If w P,then ()w P,(w)P and w()P.Show that()()is in P.Why is)()not in P?第12页/共44页Well-Formed

12、 Formulas(合适公式)ExampleWell-Formed Formulas for compound propositions include T,F,propositional variables and operators(,)Recursive definition of well-formed formulas:Basis:T,F and any propositional variable x are well-formed formulasRecursive:if A and B are well-formed formulas,then A,A B,A B,A B an

13、d A B are also well-formed formulas第13页/共44页Well-Formed Formulas ExampleExamples.Are the following well-formed formulas?(From definition,start with the variable of single-operand operator)1.(A (B)(C)(D)2.(A B)C)3.(A (B)(D)4.(A B)C第14页/共44页T1T2T3T4T5T1T2T2T2T2T1T1Full Binary Tree(满二叉树)ExampleBasis St

14、ep:any single node is a binary treeInductive Step:If T1 and T2 are full binary trees,then the following tree T is also a full 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=T1T2So,what i

15、s a full binary tree?第15页/共44页Basis:the empty set is an extended binary treeInductive:If T1 and T2 are extended binary trees,then the following 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 an

16、d T2 can be the same).Denoted T=T1T2Extended Binary Tree ExampleT0T1T2T3T4T1T1T1T0T1T0T0T5T6T7T8T9T13T0第16页/共44页Structural InductionApplying Structural Induction for recursively defined setsBasis Step:Show that the result is true for all elements specified in the basis step of the recursive definiti

17、onRecursive(or inductive)Step:Show that,if the result is true for the old elements used in constructing new elements,then it is also true for the new elements第17页/共44页Induction ExampleShow 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 th

18、at are multiples of 3Proof:let A be the set of all positive integers that are multiples of 3,A=3n|n=1,2,.We need to prove A S and S A,which proves S=AA 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

19、 induction basis,3 S.By recursive definition of S(let x=3k and y=3),3(k+1)=3k+3 S第18页/共44页Structural Induction ExampleProof(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(

20、x and y)used to build new elements are true(multiples of 3).Show 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第19页/共44页Structural Induction ExampleUse structural induction to show that l(xy)=l(x)+l(y)l(w)=length

21、of string w and x,y,w *over symbol set Basis 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)+1(by

22、 induction assumption)=l(x)+l(ya)(by definition of length)第20页/共44页Binary Tree ExampleRecursive 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 binary tree f

23、ormed from them,T=T1T2,has height h(T)=1+max(h(T1),h(T2)第21页/共44页Binary Tree ExampleRecursive 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 the number of nodes for

24、the full binary tree T=T1T2 isn(T)=1+n(T1)+n(T2)第22页/共44页Binary Tree ExampleTheorem: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=1Inductive:Assume for full binary tree T1,n(T1)2h(T

25、1)+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第23页/共44页Binary Tree ExampleProof(continued)n(T)=1+n(T1)+n(T2)(recursive definition)1+(2h(T1)+1 1)+(2h(T2)+1 1)(ii)and(iii)=2h(T1)+1 +2h(T2)+1 1 2max(2h(T1)+1,2h(T2)+1)1=22max(h(T1)+1,h(T2)+1)1(max(2

26、x,2y)=2max(x,y)=22max(h(T1),h(T2)+1 1=22h(T)1(recursive definition of h(T)=2h(T)+1 1 第24页/共44页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,verify that n(T5)2h(T5)+1 1 T1T2T3T4T5T1T2T2T2T2T1T1Binary Tree Example第25页/共44页Recursive AlgorithmsDe

27、finition:An algorithm is called recursive if 1.It solves a problem by reducing it to an instance of the same problem with smaller input2.This reduction must lead to the basis step for which the solution is known第26页/共44页Factorial Recursive AlgorithmComputing n!based on the recursive definition(i)0!=

28、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?第27页/共44页Power Recursive AlgorithmComputing an based on the recursive definition(i)a0=1 and(ii)an=a an-1 for n 0 procedure powe

29、r(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?第28页/共44页Sum Recursive AlgorithmWe use recursive algorithm to compute the sum of n numbers a1,a2,an.Example of sum(a1,a2,a3:3)=procedure sum(a1,an:list,n:positive Int

30、eger)if n=1 then sum(a1,an,n)=a1 else sum(a1,an,n)=an+sum(a1,an,n-1)第29页/共44页GCD Recursive AlgorithmComputing gcd(a,b)based on(i)Basis step:gcd(a,0)=a when a 0,and(ii)Recursive 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):=

31、gcd(b,a mod b)Example:Compute gcd(44,24)第30页/共44页Binary Search Recursive AlgorithmBinary search in a sorted list of n elements can be reduced to a comparison with 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

32、in ascending orderm:=(i+j)/2 if x=am thenreturn mm is the location for xelse if(x am and i am and j m)thenbinary-search(m+1,j,x)else return 0Not found!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第31页/共44页1.First split list successively

33、into pairs so the result is a balanced binary tree(upper half)2.Sorting is done by successively merging the pairs of lists in ascending order(bottom half)Merge Sort(归并排序)AlgorithmSplitMerge第32页/共44页Recursive Algorithm for Merge SortProcedure mergesort uses a subroutine merge(on the next slide)to mer

34、ge two lists into a sorted one in ascending orderprocedure ms(L=a1,an)ms for mergesort,omitting nif n 1 then return Lelse m:=n/2 L1:=a1,am L2:=am+1,an L:=merge(ms(L1),ms(L2)Example:ms(8,2,3,6,1)=第33页/共44页Merging ExampleLL1L2第34页/共44页Merging Two Listsprocedure merge(L1,L2:sorted lists in nondecreasin

35、g order)L:=empty list while L1 and L2 are both nonempty Remove smaller of first element of L1 and L2 from the list 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 LL is the merged list wi

36、th elements in nondecreasing order第35页/共44页Time Complexity of MergeLet m,2 m n,be the total number of numbers in the two lists to be merged.n is the number of numbers to be sorted by mergesortEvery comparison results in one element being removed from one of the two listsThere will be at most m 1 com

37、parisons(the last one does not need a comparison)This leads to O(m)time complexity第36页/共44页Time Complexity of Merge SortLet 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

38、is k,there are n(=2k)leavesIn merging the lists,the first step is to compare and sort the numbers at the leaves:n/2 comparisonsThe last step is compare and sort two lists right under the root:n 1 comparisons第37页/共44页Time Complexity of Merge SortTime complexity of the recursive merge sort algorithm i

39、s kO(n)=O(kn)=O(nlog2n)height=k:n/2=O(n)ComparisonsEach height from 2 to k-1:n/2 Comparisons 0 thenfor i:=1 to n p:=a p p is the result of an 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)RecursiveIterative第41页/共44页Algorithms for

40、 Fibonacci Functionprocedure fibonacci(n:nonnegative integer)if n=0 then fibonacci(0):=0else if n=1 thenfibonacci(1):=1else fibonacci(n):=fibonacci(n-1)+fibonacci(n-2)procedure iterative-fibonacci(n:nonnegative integer)if n=0 then y:=0else x:=0 x=f(0)y:=1y=f(1)for i:=1 to n-1z:=x+y z=f(n-1)+f(n-2)x:=yy:=z y is the nth Fibonacci numberRecursiveIterativef(2)=f(1)+f(0)=1+0=1f(3)=f(2)+f(1)=1+1=2f(4)=f(3)+f(2)=2+1=3f(5)=f(4)+f(3)=3+2=5f(6)=f(5)+f(4)=5+3=8第42页/共44页Exercises#8P357:1a-c,8,25P370:3,7,8,16,46b-c,47第43页/共44页感谢您的欣赏！第44页/共44页