離散數(shù)學課件----function

1、Functions,,Definition of Function,Definition: Let A and B be nonempty sets. A function f from A to B, which is denoted f:A?B, is a relation from A to B such that for all a?A, f(a) contains just one element of B.A specia

2、l kind of binary relation Under f, each element in the domain of f has a unique image. Note: the domain of ?:A?B is A，but the range is not necessarily equal to B.,Image and counterimage,Let f:A?B, A’?A, then ?(A’)=

3、{y|y=f(x)，x?A’} is called the image of A’ under f.An element in Dom(f) corresponds a valueA subset of Dom(f) corresponds an imageLet B’?B, then f-1(B’)={x|x?A, f(x)?B’} is called the counterimage of B’ under f.What i

4、s f -1(f(A’)) ?A’? f -1(f(A’)) ?f -1(f(A’)) ? A’?,,Image and Counterimage,Special Types of Functions,Surjection?:A?B is a surjection or “onto” iff. Ran(?)=B, iff. ?y?B, ?x?A, such that f(x)=yInjection (one-to-one)?:

5、A?B is one-to-one iff. ?y?Ran(f), there is at most one x?A, such that f(x)=y iff. ?x1,x2?A, if x1?x2，then ?(x1) ??(x2) iff. ?x1,x2?A, if ?(x1) =?(x2)，then x1=x2Bijection(one-to-one correspondence)surjection plus injec

6、tion,,If A,B are nonempty setshow many different functions from A to B are there? |B||A| how many Injection from A to B are there?If |A|>|B| then 0 else |A|!*|A|C|B|how many Bijection from A to B are there?If

7、 |A|= |B| = m then M! else 0,Special Types of Functions: Examples,?:Z+?R, ?(x)= ln x, one-to-one?:R?Z, ?(x)= ?x?, onto?:R?R, ?(x)= 2x-1，bijection?:R?R?R?R, ?() = , bijectionTry to prove itWhat is ?({|x,y?R, y=x+1})?

8、R?{-1}?:N?N?N, ?() = | x2-y2|?(N?{0}) ={ n2|n?N}, ?-1({0}) ={|n?N},Characteristic Function of Set,Let U be the universal set, for any A?U, the characteristic function of A, fA:U?{0,1} is defined as fA(x)=1 iff. x?A,N

9、atural Function,R is an equivalence relation on set A, g : A?A/R, for all a?A, g(a)=R(a), then G is called a natural function on ANatural function is surjection For any R(a)?A/R, there exists some x?A，such that g(x)=R

10、(x),Images of Union and Intersection,Given f：A?B，and X,Y are subsets of A, then:f (X?Y) = f(X)?f (Y) f (X?Y) ? f(X)?f (Y),Composition of Functions,Since function is relation as well, the composition of relation can be

11、 applied for functions, with the results being relation.The composition of functions is still functionSuppose f :A?B, g:B?C, g?f is a relation from A to C. ?x?A, we have g?f (x)=g(f (x)). It is easy to prove that for

12、 every a in A, there is just one c in C, such that g(f (a))=c. So, g?f is a function.,Composition of Functions,Examples,f, g, h: function of Z: f(x) = 3x, g(x) = 3x+1, h(x) = 3x+2f ? gg ? ff ? g ? h,Associative Law,T

13、he composition of function is simply the composition of relation, so it is an associative operation.For any functions f :A?B, g:B?C, h:C?D,(h?g)?f= h?(g?f),Composition of Surjections,If f :A?B, g:B?C are both surje

14、ctions, then g?f:A?C is also surjection.Sketch of proof: For any y?C,since g is a surjection, there must be some t?B, such that g(t)=y. Similarily, since f is surjection，there must be some x?A, such that f(x)=t,

15、so, g?f(x)=y.,But…,If g?f is a surjection，can it be derived that f and g are both surjections as well？Obviously，g must be a surjection. How about f?If there is some t?B, for any x?A, f(x)?t, (i.e. f is not a surjectio

16、n！) then if g(B-t)=C, g?f is still a surjection.,Composition is a Surjection,t,Composition of Injections,If f :A?B, g:B?C are both injections, then g?f:A?C is a injection as well.Sketch of proof:By contradiction，suppos

17、e x1,x2?A, and x1?x2，but g?f(x1)=g?f(x2) ，let f (x1)=t1, f (x2)=t2，If t1=t2，then f is not a injection.If t1? t2，then g is not a injection.,But…,If g?f is a injection, can it be derived that f and g are both in

18、jections？Obviously, f must be a injection. How about g?Suppose that t1,t2?B, t1?t2，but g(t1)=g(t2) , (i.e. g is not a injection!) If t1 or t2 are not in Ran(f), then g?f still may be injection.,Composition is a Inje

19、ction,t1,t2,Identity Function on a Set,1A is the identity function on A：1A(x)=x for all x?A.For any f :A?B，f=1B?f = f ?1ASketch of proof: Proving that the set f is equal to the set f ?1A and 1B?fNote: if ?f, then

20、?f and ?1A if ? f ?1A，則? f , 且?1A， 則t=x, 所以?f .,Invertible Function,The inverse relation of f :A?B is not necessarily a function, even though f is.Examples: (Let A={a,b,c}, B={1,2,3})f = {, , } is a

21、 function, but f-1={, , } is not a function. f :A?B is called an invertible function, if its inverse relation, f -1:B?A is also a function.Example: f : N?N?N, f ()=2i(2j+1)-1 is a bijection f -1(2i(2j+1)-1)=,Inv

22、ertible Function,f :A?B is an invertible function if and only if f is a bijection. Sketch of proof: ?If f is not a injection, then there must be , ? f -1, and x1?x2. On the other hand, if f is not a surjection, then t

23、here is at least one element in B, which has not an image in A under f -1. Both cases are contradict to “f :A?B is invertible”. ? If f –1 is not a function, then，either there exist , ? f -1, and x1?x2，then f is not a i

24、njection, or there must be at least on element in B, which has not an image in A under f –1. Both cases are contradict to “f is a bijection”.,Hashing: the Idea,Index distribution Collision handling,The division method:

25、h(k)=k mod mThe multiplication method: h(k)=?m(kA mod 1)? (0<A<1),,Collision Handling: Closed Address,,,,,,,,,,,,,,,Each address is a linked list,,Load factor: 3,Collision Handling: Open Address,All elements are s

26、tored in the hash table, no linked list is used. So, ?, the load factor, can not be larger than 1.Collision is settled by “rehashing”: a function is used to get a new hashing address for each collided address, i.e. the

27、hash table slots are probed successively, until a valid location is found.,Linear Probing: an Example,,,,,,,,,H,Index,0,1,2,3,4,5,6,7,Hash function: h(x)=5x mod 8,1055,1492,1776,1918,,1812,Rehash function: rh(j)=(j+1) mo

28、d 8,1812,1945,1776,1055,1492,1918,Growth of function,Let R be a relation on set A, |A| = n and |R| = n2/2There are two algorithms to determine if R is transitive: T,SHow to judge which one is better?Time: stepsSpace:

29、 memorycomplexity,Growth of function,Let f:N->N is a function that describes the average number of steps needed to determine if R is transitiveThere are:ft(n) = n3/2 +n2/2 for algorithm Tfs(n) = n4/8 for algorithm

30、 S,Growth of function,Growth of function,Giving f:N→R+, g:N→R+,if there exists constants c ?R+ and k ?N such that for all n, f(n)?C×g(n), when n?kwe say that:f is O(g) f grows no faster than g does Growth of f

31、unction for algorithm analysis,How to make our judgment,Example1:ft(n) = n3/2 +n2/2, fs(n) = n4/8n3/2 +n2/2 =1So: when c=8, n>=1, ft(n)<=c*fs(n), ft is O(fs)Is fs O(ft)?Example2:f(n) = n3/2 +n2/2, g(n) = n3s

32、o, f is O(g)How about “g is O(f)”?,How to make our judgment,However: if a pair C,K exists, there are infinitely many such pairsLet f(x) = anxn+an-1xn-1+…+a1x+a0, then f(x) is O(xn),order,Same order:We say that f and

33、g have the same order if:f is O(g) and g is O(f)example3:3n4-5n2 and n4Lower order:If f is O(g) but g is not O(f), we say that:f is lower order than g, or:f grows more slowly than g,How to make our judgment,Actual

34、ly we can make our judgment like this:A function f isΟ(g) if limn→?[f(n)/g(n)]=c<?if there exists constants c ?R+ and k ?N such that for all n, f(n)?cg(n)Example: let f(n)=n2, g(n)=nlgn, then:f is not Ο(g), since

35、 limn→?[f(n)/g(n)]= limn→?[n2/nlgn]= limn→?[n/lgn]= limn→?[1/(1/nln2)]=?g isΟ(f), since limn→?[g(n)/f(n)]=0,Θrelation,n2/100+5n is O(3n4-5n2), is it O(10n4)?3n4-5n2 and 10n4 have the same orderActually, the simplest f

36、unction is n4 among the functions with same order of 3n4-5n2,Θrelation,Relation Θ on functions from N to R+:f Θg iff f and g have the same order3n4-5n2 Θ 10n4 , (n4, 3n4-5n2)? ΘTheorem1: Θ is an equivalence relation

37、proof: ……,The common orders,The equivalence class of Θ:Let A: {f|f:N->R+}, let s?A/ Θ? f, g ? s, f is O(g) and g is O(f)Among these equivalence class Θ-class, we have some common orders:Θ(1), Θ(n), Θ(n2), Θ(n3),

38、Θ(lg(n)), Θ(nlg(n)), and Θ(2n),Rules for determining Θ_class,Θ(1): zero growthΘ(lg (n)) is lower than Θ(nk) if k>0f(n) = lg(n), t(n) = n, s(n) = n2, h(n) = n0.4Θ(na) is lower than Θ(nb) iff 0<a<bf(n) = n2, t

39、(n) = n4, s(n) = n2.1Θ(an) is lower than Θ(bn) iff 0<a<bf(n) = 2n, s(n) = 3n, h(n) = 3.1n,Some rules for determining Θ_class,Θ(nk) is lower than Θ(an) for any power nk and any a>1f(n) = n2, t(n) = n10000, s(n

40、) = 1.1nIf r is not zero,then Θ(rf) = Θ(f)f(n) = n2, t(n) = 10000n2 = 10000f(n),Some rules for determining Θ_class,If h is a nonzero function and Θ(f) is lower than(or the same as) Θ(g) , then Θ(fh) is lower than (or

41、the same as) Θ(gh) f(n) = n+1, g(n) = n2 , h(n) = 1.1nt(n) = fh(n) = 1.1n +1 , s(n) = gh(n) = 1.12nIf Θ(f) is lower than Θ(g) , then Θ(f+g) =Θ(g) f(n) = n2, g(n) = n3, how about t(n) = f(n)+g(n),Examples:,Determine

42、 the Θ-class:F(n) = 4n4-6n7+25n3Θ(n7)G(n) = lg(n)-3nΘ(n)H(n) = 1.1n +n15Θ(1.1n),Examples:,Rearrange the following in order from lowest to highest:Θ(1000n2-n), Θ(n0.2), Θ(1000000), Θ(1.3n), Θ(n+107) ,Θ(nlg(n))Θ(10

43、00000) Θ(n0.2)Θ(n+107) Θ(nlg(n))Θ(1000n2-n)Θ(1.3n),,,Relative Growth Rate,,,,g,Ω(g):functions that grow at least as fast as g,Θ(g):functions that grow at the same rate as g,Ο(g):functions that grow no faster as g,,,

44、,Permutation Function,Definition: A bijection from a set A to itself is called a permutation of A.Denotation:,Example of Permutation,S={1,2,3}, there are 6 different permutations,Example of Permutation,How about ?-1 ,

45、?????-1 =???? = ?,The composition of two permutations is another permutation,Cyclic Permutation and Transposition,If p is a permutation of S={1,2,…,n}, and p(i1)=i2, p(i2)=i3, …, p(ik-1)=ik, p(ik)=i1, for all oth

46、er x?S, p(x)=x, then p is called a cyclic permutation of S，when k=2, p is also called a transposition. Denotation: (i1 i2 … ik ) 6 permutation of S={1,2,3}: e =(1) =1s ;?=(1 2 3); ?=(1 3 2); ?=(2 3); ?=(1 3); ?=(1 2

47、),Disjoint Cyclic Permutations,Given two cyclic permutations of S: p =(i1 i2 … ik ), q =(j1 j2 … js ), if {i1, i2, …, ik} ? {j1, j2, …, js}=?，then p and q are disjoint. If p and q are disjoint, then p?q=q?p

48、For any x?S, there are three cases: x?{i1, i2, …, ik}; x?{j1, j2, …, js}; x?S-({i1, i2, …, ik}?{j1, j2, …, js})， it is easy to see (p?q)(x) = (q?p)(x) in all the three cases,Permutation as Product of Cycles,Theore

49、m: A permutation of a finite set that is not the identity or a cycle can be written as a product of disjoint cycles of length >=2 = (1 5 7) (4 8)

50、 =(1 2 3 5) (4 8 7 6),Permutation as Product of Transpositions,Every cycle p=(i1 i2 … ik ) can be represented as a product of k-1 transpositions (i1ik)…(i1i3) (i1i2)Proof by induction on k: k=2 is trivial.

51、 Considering p=(i1 i2 … ik ik+1 ), we need only to prove that p = (i1 ik+1 )。(i1 i2 … ik) There are four cases for any x?A, p(x)=(i1 ik+1 ) (i1 i2 … ik) (x)(1) x=ik (2) x=ik+1,(3) x?{ i1, i2, …, ik-1},,(4) otherwise

52、,Permutation as Product of Cycles,= (1 5 7) (4 8) =(1 2 3 5) (4 8 7 6),= (1 7) (1 5) (4 8),= (1 5) (1 3) (1 2) (4 8) (4 7) (4 6),Home Assignment,pp.176: 6,8, 10,14,24,32pp.187:2,12,16,20