离散数学代写: CS 205: Final Exam Question 1 – Functions

Computer Science Department – Rutgers University

Spring 2018

CS 205: Final Exam Question 1 – Functions

LetSN ={0,1,2,…,N−1},i.e.,theintegersgreaterthanorequalto0,andstrictlylessthanN. 1) Defineafunctionf:S13 􏰏→S13 byf(x)=6x mod13.

a) What is the domain of f? The range of f? The image of f?
b) Prove that f is injective, using the formal definition of injectivity.

c) Is f invertible? If so, give the values of its inverse function. 2) Defineafunctiong:S15 􏰏→S15 byg(x)=6x mod15.

16:198:205

  1. a)  What is the domain of g? The range of g? The image of g?
  2. b)  Show that g is not injective. If x1 and x2 in S15 map to the same value under g, what must be true about

    x1 and x2?

  3. c)  Show that g is not surjective. If y ∈ S15 is not mapped to by g, what must be true of y?
  4. d)  Give a set A ⊂ S15 and B ⊂ S15 such that g is an invertible map from A to B. Find the largest A, B you can.

Given a function f : S 􏰏→ S (unrelated to the above), a value x ∈ S is a fixed point or has order 1 if x = f(x). Similarly, x has order 2 if x = f(f(x)), and order 3 if x = f(f(f(x))). A point x has order k if applying f k-times to x yields x. If x never returns to x under repeated applications of f, then x has infinite order, or is transitory.

  1. 3)  ForanyN>1,giveanexampleofanf:SN 􏰏→SN thathasnofixedpoints.
  2. 4)  ForanyN>1,giveanexampleofanf:SN 􏰏→SN thathasonlyasinglepointoffiniteorder.
  3. 5)  Argue that for any N > 1, given f : SN 􏰏→ SN, if x has finite order, then x has an inverse under f, i.e., if every point x ∈ SN has a finite order, then f is invertible. Consider small examples first.

Suppose you had a program that, given an image file as input, returned a tag from a finite set of tags Tags = {cat, dog, orange, . . . , UFO, CannotBeDetermined}, describing the contents of that image (a standard computer vision problem).

  1. 6)  Describe this program as a function, mapping one set to another set. What is the domain, what is the range? Be as precise as you can be. Is this function invertible?
  2. 7)  Suppose that the program were restructured so that it returned a collection of tags describing the contents of the image. For instance, a picture of a dog and a cat sitting together might return {dog,cat}. Describe this program as a function, mapping one set to another set. What is the domain, what is the range? Be as precise as you can be. Is this function invertible?

1

Computer Science Department – Rutgers University Spring 2018

Bonus

A computer can generally be thought of as a device for executing sequences of commands known as programs. A program can be thought of as a description of a function mapping inputs to outputs. By running a computer over a potentially infinite amount of time, producing an infinite sequence of characters as output, we may interpret their computations as producing real numbers.

Thinking in terms of a program as a finite sequence of characters or commands and similarly assuming that the program input must also be finite – argue that there are real numbers that cannot be computed by any program.

Why is this argument independent of such facts as computer speed or architecture/design?

2