New version page

UT CS 302 - Theory of Computation

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

PowerPoint PresentationChapter 12: Theory of ComputationFunctionsFunctions (continued)Figure 12.1 An attempt to display the function that converts measurements in yards into metersFigure 12.2 The components of a Turing machineTuring Machine OperationFigure 12.3 A Turing machine for incrementing a valueChurch-Turing ThesisUniversal Programming LanguageThe Bare Bones LanguageFigure 12.4 A Bare Bones program for computing X x YFigure 12.5 A Bare Bones implementation of the instruction “copy Today to Tomorrow”The Halting ProblemFigure 12.6 Testing a program for self-terminationFigure 12.7 Proving the unsolvability of the halting programComplexity of ProblemsFigure 12.8 A procedure MergeLists for merging two listsFigure 12.9 The merge sort algorithm implemented as a procedure MergeSortFigure 12.10 The hierarchy of problems generated by the merge sort algorithmFigure 12.11 Graphs of the mathematical expressions n, lg n, n lg n, and n2P versus NPFigure 12.12 A graphic summation of the problem classificationPublic-Key CryptographyEncrypting the Message 10111Decrypting the Message 100Figure 12.13 Public key cryptographyFigure 12.14 Establishing an RSA public key encryption systemCopyright © 2012 Pearson Education, Inc. Chapter 12:Theory of ComputationComputer Science: An OverviewEleventh Editionby J. Glenn BrookshearCopyright © 2012 Pearson Education, Inc. 0-2Chapter 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 CryptographyCopyright © 2012 Pearson Education, Inc. 0-3Functions•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 outputCopyright © 2012 Pearson Education, Inc. 0-4Functions (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 algorithmCopyright © 2012 Pearson Education, Inc. 0-5Figure 12.1 An attempt to display the function that converts measurements in yards into metersCopyright © 2012 Pearson Education, Inc. 0-6Figure 12.2 The components of a Turing machineCopyright © 2012 Pearson Education, Inc. 0-7Turing 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 stateCopyright © 2012 Pearson Education, Inc. 0-8Figure 12.3 A Turing machine for incrementing a valueCopyright © 2012 Pearson Education, Inc. 0-9Church-Turing Thesis•The functions that are computable by a Turing machine are exactly the functions that can be computed by any algorithmic means.Copyright © 2012 Pearson Education, Inc. 0-10Universal Programming LanguageA language with which a solution to any computable function can be expressed–Examples: “Bare Bones” and most popular programming languagesCopyright © 2012 Pearson Education, Inc. 0-11The Bare Bones Language•Bare Bones is a simple, yet universal language.•Statements–clear name;–incr name;–decr name;–while name not 0 do; … end;Copyright © 2012 Pearson Education, Inc. 0-12Figure 12.4 A Bare Bones program for computing X x YCopyright © 2012 Pearson Education, Inc. 0-13Figure 12.5 A Bare Bones implementation of the instruction “copy Today to Tomorrow”Copyright © 2012 Pearson Education, Inc. 0-14The Halting Problem•Given the encoded version of any program, return 1 if the program is self-terminating, or 0 if the program is not.Copyright © 2012 Pearson Education, Inc. 0-15Figure 12.6 Testing a program for self-terminationCopyright © 2012 Pearson Education, Inc. 0-16Figure 12.7 Proving the unsolvability of the halting programCopyright © 2012 Pearson Education, Inc. 0-17Complexity 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 (f(n)).•A problem is in class (f(n)) if the best algorithm to solve it is in class (f(n)).Copyright © 2012 Pearson Education, Inc. 0-18Figure 12.8 A procedure MergeLists for merging two listsCopyright © 2012 Pearson Education, Inc. 0-19Figure 12.9 The merge sort algorithm implemented as a procedure MergeSortCopyright © 2012 Pearson Education, Inc. 0-20Figure 12.10 The hierarchy of problems generated by the merge sort algorithmCopyright © 2012 Pearson Education, Inc. 0-21Figure 12.11 Graphs of the mathematical expressions n, lg n, n lg n, and n2Copyright © 2012 Pearson Education, Inc. 0-22P versus NP•Class P: All problems in any class (f(n)), where f(n) is a polynomial•Class NP: All problems that can be solved by a nondeterministic algorithm in polynomial timeNondeterministic 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.Copyright © 2012 Pearson Education, Inc. 0-23Figure 12.12 A graphic summation of the problem classificationCopyright © 2012 Pearson Education, Inc. 0-24Public-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 numbersCopyright © 2012 Pearson Education, Inc. 0-25Encrypting 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.Copyright © 2012 Pearson Education, Inc. 0-26Decrypting 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 has a remainder of 23•23ten = 10111two•Therefore, decrypted version of 100 is 10111.Copyright © 2012 Pearson Education, Inc. 0-27Figure 12.13 Public key cryptographyCopyright © 2012 Pearson Education, Inc. 0-28Figure 12.14 Establishing an RSA public key encryption


View Full Document
Download Theory of Computation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Theory of Computation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Theory of Computation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?