【英文版】计算机科学概论--Chap12.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,.,*,An Introductionto Computer Science,计算机科学引论,XIANG,，,Hui,向辉,Shandong University,1,.,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,2,.,Functions,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,3,.,Functions,(continued),Computing,a function:,Determining the output value associated with a given set of input values,Noncomputable,function:,A function that cannot be computed by any algorithm,4,.,Figure 12.1,An attempt to display the function that converts measurements in yards into meters,5,.,Figure 12.2,The components of a Turing machine,6,.,Turing Machine Operation,Inputs at each step,State,Value at current tape position,Actions at each step,Write a value at current tape position,Move read/write head,Change state,7,.,Figure 12.3,A Turing machine for incrementing a value,8,.,Church-Turing Thesis,The functions that are computable by a Turing machine are exactly the functions that can be computed by any algorithmic means.,9,.,Universal Programming Language,A language with which a solution to any computable function can be expressed,Examples:“Bare Bones”and most popular programming languages,10,.,The Bare Bones Language,Bare Bones is a simple,yet universal language.,Statements,clear,name,;,incr,name,;,decr,name,;,while,name,not 0 do;end,;,11,.,Figure 12.4,A Bare Bones program for computing,X,x,Y,12,.,Figure 12.5,A Bare Bones implementation of the instruction“copy Today to Tomorrow”,13,.,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.,14,.,Figure 12.6,Testing a program for self-termination,15,.,Figure 12.7,Proving the unsolvability of the halting program,16,.,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)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).,17,.,Figure 12.8,A procedure MergeLists for merging two lists,18,.,Figure 12.9,The merge sort algorithm implemented as a procedure MergeSort,19,.,Figure 12.10,The hierarchy of problems generated by the merge sort algorithm,20,.,Figure 12.11,Graphs of the mathematical expressions,n,lg,n,n,lg,n,and,n,2,21,.,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 time,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.,22,.,Figure 12.12,A graphic summation of the problem classification,23,.,Public-Key Cryptography,Key:,A value used 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,24,.,Encrypting the Message 10111,Encrypting keys:n=91 and e=5,10111,two,=23,ten,23,e,=23,5,=6,436,343,6,436,343 91 has a remainder of 4,4,ten,=100,two,Therefore,encrypted version of 10111 is 100.,25,.,Decrypting the Message 100,Decrypting keys:d=29,n=91,100,two,=4,ten,4,d,=4,29,=288,230,376,151,711,744,288,230,376,151,711,744 91 has a remainder of 23,23,ten,=10111,two,Therefore,decrypted version of 100 is 10111.,26,.,Figure 12.13,Public key cryptography,27,.,Figure 12.14,Establishing an RSA public key encryption system,28,.,