Functions ■A function f:A→B is one-to-one(i.e.,not one-to-many）if for any x,y∈A (x≠y),f(x)≠f(y). ■A function f:A→B is onto if the range of f is B. A function is a bijection if it is both one-to-one and onto. Examples (all domains being natural number set): .f(x)=x2 is neither one-to-one nor onto. What does this function do? .f(z)=x+1 is one-to-one but not onto. ●f(r)=「is onto but not one-to-o 3 5 f(x)=x+2(x mod 2)-1is a bijection
Functions A function f:A→B is one-to-one (i.e., not one-to-many) if for any x,y∈A (x≠y), f(x) ≠ f(y). A function f:A→B is onto if the range of f is B. A function is a bijection if it is both one-to-one and onto. Examples (all domains being natural number set): What does this function do? 3 4 1 2 5 6 … …
Inverse and Generalized Inverse Function If a function is a bijection,then it has an inverse function. The inverse function f-1:B A is defined as f-1(y)=x if and only if f(x)=y. If a function is not a bijection,then it does not have an inverse function, but we can often define a generalized inverse function: Not one-to-one? Not onto? ·Use one of the ·Assign values for preimages points outside the range Example:In linear algebra,a matrix A can be For any x in the image viewed as a linear transformation/function that space of A,AGx=x.So maps each vector to another vector.Its inverse Gx is a preimage of x. matrix,if there is one,represents the inverse transformation.However,when the matrix is For any vector x singular,we can define its generalized inverse outside the image space matrix as a matrix G such that AGA=A. of A,Gx is defined
Inverse and Generalized Inverse Function If a function is a bijection, then it has an inverse function. If a function is not a bijection, then it does not have an inverse function, but we can often define a generalized inverse function: Example: In linear algebra, a matrix A can be viewed as a linear transformation/function that maps each vector to another vector. Its inverse matrix, if there is one, represents the inverse transformation. However, when the matrix is singular, we can define its generalized inverse matrix as a matrix G such that AGA=A. Not one-to-one? • Use one of the preimages Not onto? • Assign values for points outside the range f f-1 f f-1 For any x in the image space of A, AGx=x. So Gx is a preimage of x. For any vector x outside the image space of A, Gx is defined
Composition of Functions Suppose we have two functions f:A-B and g:BC.A composition of them produces a new function h=fog where for any A,h(x)=g(f()). Be aware of the difference in the order ■If f and g are both one- If h is one-to-one,then f to-one,then h is also is also one-to-one,but g one-to-one. may not be one-to-one. If f and g are both onto, ■If h is onto,then g is then h is also onto. also onto,but f may not be onto. ■If f and g are both bijections,the h is It is possible to produce also a bijection. a bijection h with neither f nor g being a bijection
Composition of Functions If f and g are both oneto-one, then h is also one-to-one. If f and g are both onto, then h is also onto. If f and g are both bijections, the h is also a bijection. Be aware of the difference in the order If h is one-to-one, then f is also one-to-one, but g may not be one-to-one. If h is onto, then g is also onto, but f may not be onto. It is possible to produce a bijection h with neither f nor g being a bijection. f g
Functional and Functional Programming In mathematics and computer science,we often consider functionals,which are fun reverse []=[] essentially functions of functions.We reverse (x:xs)=(reverse xs)@[x] say f:A-B is a functional or operator i A list reverse program in ML Either A is a set of functions; Or B is a set of functions; Following this idea,one of the Or both A and B are sets of functions. important programming paradigms (in d addition to imperative Example:the differential operator dx programming/objective oriented programming)functional programming,is which maps a function to its derivative. established. An interesting result by Turing is that No variable with changing values,no Lambda-calculus is Turing-complete,and construction/destruction of thus any algorithm can be represented by objects,.. functions or functionals. Everything is static:You just define functions,and functions of functions,…
In mathematics and computer science, we often consider functionals, which are essentially functions of functions. We say f:A→B is a functional or operator if Either A is a set of functions; Or B is a set of functions; Or both A and B are sets of functions. Example: the differential operator which maps a function to its derivative. An interesting result by Turing is that Lambda-calculus is Turing-complete, and thus any algorithm can be represented by functions or functionals. Functional and Functional Programming Following this idea, one of the important programming paradigms (in addition to imperative programming/objective oriented programming) functional programming, is established. No variable with changing values, no construction/destruction of objects,… Everything is static: You just define functions, and functions of functions,… A list reverse program in ML
From Function to Functionality Our typical computational task is,for a function f,given an input x,to find f(x). This may be possible,or impossible,depending on f. COMPUTABILITY THEORY Shortly,you are going to see it is impossible for the vast majority of functions. Even for those functions that can be computed,the time/space/communications needed is a big problem. Usually the need for time/space/communications grows when the input gets bigger. Computational Complexity For many functions,the need grows so fast that computing Communication is simplyinfeasible. Complexify Already bad enough?Nol While a function is always deterministic, sometimes we need to compute a functionality,which is probabilistic
From Function to Functionality Our typical computational task is, for a function f, given an input x, to find f(x). This may be possible, or impossible, depending on f. Shortly, you are going to see it is impossible for the vast majority of functions. Even for those functions that can be computed, the time/space/communications needed is a big problem. Usually the need for time/space/communications grows when the input gets bigger. For many functions, the need grows so fast that computing is simply infeasible. Already bad enough? No! • While a function is always deterministic, sometimes we need to compute a functionality, which is probabilistic