1、,an introductionto computer science,計算機科學(xué)引論,xiang， hui shandong university,2,chapter 12: theory of computation,12.1 functions and their computation 12.2 turing machines 12.3 universal programming languages 12.4 a noncomputable function 12.5 complexity of problems 12.6 public-key cryptography,3,funct

2、ions,function: a correspondence between a collection of possible input values and a collection of possible output values so that each possible input is assigned a single output,4,functions (continued),computing a function: determining the output value associated with a given set of input values nonc

3、omputable function: a function that cannot be computed by any algorithm,5,figure 12.1 an attempt to display the function that converts measurements in yards into meters,6,figure 12.2 the components of a turing machine,7,turing machine operation,inputs at each step state value at current tape positio

4、n actions at each step write a value at current tape position move read/write head change state,8,figure 12.3 a turing machine for incrementing a value,9,church-turing thesis,the functions that are computable by a turing machine are exactly the functions that can be computed by any algorithmic means

5、.,10,universal programming language,a language with which a solution to any computable function can be expressed examples: “bare bones” and most popular programming languages,11,the bare bones language,bare bones is a simple, yet universal language. statements clear name; incr name; decr name; while

6、 name not 0 do; end;,12,figure 12.4 a bare bones program for computing x x y,13,figure 12.5 a bare bones implementation of the instruction “copy today to tomorrow”,14,the halting problem,given the encoded version of any program, return 1 if the program is self-terminating, or 0 if the program is not

7、.,15,figure 12.6 testing a program for self-termination,16,figure 12.7 proving the unsolvability of the halting program,17,complexity of problems,time complexity: the number of instruction executions required unless otherwise noted, “complexity” means “time complexity.” a problem is in class o(f(n)

8、if it can be solved by an algorithm in q(f(n). a problem is in class q(f(n) if the best algorithm to solve it is in class q(f(n).,18,figure 12.8 a procedure mergelists for merging two lists,19,figure 12.9 the merge sort algorithm implemented as a procedure mergesort,20,figure 12.10 the hierarchy of

9、problems generated by the merge sort algorithm,21,figure 12.11 graphs of the mathematical expressions n, lg n, n lg n, and n2,22,p versus np,class p: all problems in any class q(f(n), where f(n) is a polynomial class np: all problems that can be solved by a nondeterministic algorithm in polynomial t

10、ime nondeterministic algorithm = an “algorithm” whose steps may not be uniquely and completely determined by the process state whether the class np is bigger than class p is currently unknown.,23,figure 12.12 a graphic summation of the problem classification,24,public-key cryptography,key: a value u

11、sed to encrypt or decrypt a message public key: used to encrypt messages private key: used to decrypt messages rsa: a popular public key cryptographic algorithm relies on the (presumed) intractability of the problem of factoring large numbers,25,encrypting the message 10111,encrypting keys: n = 91 and e = 5 10111two = 23ten 23e = 235 = 6,436,343 6,436,343 91 has a remainder of 4 4ten = 100two therefore, encrypted version of 10111 is 100.,26,decrypting the message 100,decrypting keys: d = 29, n = 91 100two = 4ten 4d = 429 = 288,230,376,151,711,744 288,230,376,151,711,744 91 ha