53425-計算機科學概論原書chapter

1、Chapter 18Limitations of Computing2Chapter GoalsDescribe the limits that the hardware places on the solution to computing problemsDiscuss how the finiteness of the computer impacts the solutions to numeric problemsDiscuss ways to ensure that errors in data transmission are detectedDescribe the limit

2、s that the software places on the solutions to computing problems3Chapter GoalsDiscuss ways to build better softwareDescribe the limits inherent in computable problems themselvesDiscuss the continuum of problem complexity from problems in Class P to problems that are unsolvable4Limits on ArithmeticP

3、recisionThe maximum number of significant digits that can be representedWith 5 digits precision, the range of the numbers we can represent is -99,999 through +99,9995Limits on ArithmeticWhat happens if we allow one of these digits (lets say the leftmost one, in red) to represent an exponent? For exa

4、mplerepresents the number +3,245 * 1036Limits on ArithmeticThe range of numbers we can now represent is much larger-9,999 * 109 to +9,999 * 109 but we can represent only four significant digitsSignificant digitsThose digits that begin with the first nonzero digit on the left and end with the last no

5、nzero digit on the right7Limits on ArithmeticThe four leftmost digits are correct, and the balance of the digits are assumed to be zero We lose the rightmost, or least significant, digits8Limits on ArithmeticTo represent real numbers, we extend our coding scheme to represent negative exponents For e

6、xample4,394 * 10-2 = 43.94or22 * 10-4 = 0.00229Limits on ArithmeticLet the current sign be the sign of the exponent and add a sign to the left to be the sign of the number itselfWhat is the largest negative number?The smallest positive number?The smallest negative number? 10Limits on ArithmeticRepre

7、sentational error or round-off errorAn arithmetic error caused by the fact that the precision of the result of an arithmetic operation is greater than the precision of the machineUnderflowResults of a calculation are too small to represent in a given machineOverflowResults of a calculation are too l

8、arge to represent in a given machineCancellation errorA loss of accuracy during addition or subtraction of numbers of widely differing sizes, due to the limits of precisionGive examples of each of these errors11Limits on ArithmeticThere are limitations imposed by the hardware on the representations

9、of both integer numbers and real numbersIf the word length is 32 bits, the range of integer numbers that can be represented is 22,147,483,648 to 2,147,483,647There are software solutions, however, that allow programs to e these limitations For example, we could represent a very large number as a lis

10、t of smaller numbers12Limits on ArithmeticFigure 18.1 Representing very large numbers13Limits on ComponentsAlthough most errors are caused by software, hardware components do failHave you ever had a hardware failure?14Limits on CommunicationsError-detecting codes Techniques to determine if an error

11、has occurred during the transmission of data and then alert the systemError-correcting codes Error-detecting codes that detect an error has occurred and try to determine the correct value 15Limits on CommunicationsParity bit An extra bit that is associated with each byte, used to ensure that the num

12、ber of 1 bits in a 9-bit value (byte plus parity bit) is odd (or even) across all bytes Parity bits are used to detect that an error has occurred between the storing and retrieving of a byte or the sending and receiving of a byte16Limits on CommunicationsOdd parity requires that the number of 1s in

13、a byte plus the parity bit be oddFor exampleIf a byte contains the pattern 11001100, the parity bit would be 1, thus giving an odd number of 1sIf the pattern were 11110001, the parity bit would be 0, giving an odd number of 1sEven parity uses the same scheme, but the number of 1 bits must be even17L

14、imits on CommunicationsCheck digitsA software variation of the same scheme is to sum the individual digits of a number and store the units digit of that sum with the numberFor example, given the number 34376, the sum of the digits is 23, so the number would be stored as 343763Error-correcting codesI

15、f enough information about a byte or number is kept, it is possible to deduce what an incorrect bit or digit must be18Complexity of SoftwareCommercial software contains errorsThe problem is complexitySoftware testing can demonstrate the presence of bugs but cannot demonstrate their absenceAs we find

16、 problems and fix them, we raise our confidence that the software performs as it shouldBut we can never guarantee that all bugs have been removed19Software EngineeringRemember the four stages of computer problem solving? Write the specificationsDevelop the algorithmImplement the algorithmMaintain th

17、e programMoving from small, well-defined tasks to large software projects, we need to add two extra layers on top of these: Software requirements and specifications20Software EngineeringSoftware requirements A statement of what is to be provided by a computer system or software productSoftware speci

18、fications A detailed description of the function, inputs, processing, outputs, and special features of a software product; it provides the information needed to design and implement the software21Software EngineeringTesting techniques have been a running thread throughout this bookThey are mentioned

19、 here again as part of software engineeringCan you define walk-throughs and inspections?22Software EngineeringUse of SE techniques can reduce errors, but they will occurA guideline for the number of errors per lines of code that can be expectedStandard software: 25 bugs per 1,000 lines of programGoo

20、d software: 2 errors per 1,000 linesSpace Shuttle software: 1 error per 10,000 lines23Formal VerificationThe verification of program correctness, independent of data testing, is an important area of theoretical computer science researchFormal methods have been used successfully in verifying the corr

21、ectness of computer chipsIt is hoped that success with formal verification techniques at the hardware level can lead eventually to success at the software level24Notorious Software ErrorsAT&T Down for Nine HoursIn January of 1990, AT&Ts long-distance telephone network came to a screeching halt for n

22、ine hours, because of a software error in an upgrade to the electronic switching systems25Notorious Software ErrorsMariner 1 Venus Probe This probe, launched in July of 1962, veered off course almost immediately and had to be destroyedThe problem was traced to the following line of Fortran code:DO 5

23、 K = 1. 3The period should have been a comma.An $18.5 million space exploration vehicle was lost because of this typographical error26Comparing Algorithms27Big-O AnalysisWe use a special notation to compare algorithmsBig-O notationA notation that expresses computing time (complexity) as the term in

24、a function that increases most rapidly relative to the size of a problem28Big-O AnalysisFunction of size factor N:f(N) = N4 + 100N2 + 10N + 50Then f(N) is of order N4or, in Big-O notation, O(N4).For large values of N, N4 is so much larger than 50, 10N, or even 100 N2 that we can ignore these other t

25、erms29Big-O Analysis30Big-O AnalysisCommon Orders of MagnitudeO(1) is called bounded timeAssigning a value to the ith element in an array of N elementsO(log2N) is called logarithmic timeAlgorithms that successively cut the amount of data to be processed in half at each step typically fall into this

26、categoryFinding a value in a list of sorted elements using the binary search algorithm is O(log2N)31Big-O AnalysisO(N) is called linear timePrinting all the elements in a list of N elements is O(N)O(N log2N)Algorithms of this type typically involve applying a logarithmic algorithm N timesThe better

27、sorting algorithms, such as Quicksort, Heapsort, and Mergesort, have N log2N complexity32Big-O AnalysisO(N2) is called quadratic timeAlgorithms of this type typically involve applying a linear algorithm N times. Most simple sorting algorithms are O(N2) algorithmsO(2N) is called exponential timeO(n!)

28、 is called factorial timeThe traveling salesperson graph algorithm is a factorial time algorithm33Big-O AnalysisTable 18.2 Comparison of rates of growth34Big-O AnalysisFigure 18.3 Orders of complexity35Turing MachinesTuring machine A model Turing machine was developed in the 1930s and consists of a

29、control unit with a read/write head that can read and write symbols on an infinite tape36Turing MachinesWhy is such a simple machine (model) of any importance? It is widely accepted that anything that is intuitively computable can be computed by a Turing machineIf we can find a problem for which a T

30、uring-machine solution can be proven not to exist, then the problem must be unsolvableFigure 18.4 Turing machine processing37Halting ProblemThe Halting problemGiven a program and an input to the program, determine if the given program will eventually stop with this particular input. If the program d

31、oesnt stop, then it is in an infinite loop and this problem is unsolvable38Halting ProblemAssume that there exists a Turing-machine program, called SolvesHaltingProblem that determines for any program Example and input SampleData whether program Example halts given input SampleDataFigure 18.5 Propos

32、ed program for solving the Halting problem39Halting ProblemFigure 18.6 Proposed program for solving the Halting problem40Halting ProblemNow lets construct a new program, NewProgram, that takes program Example as both program and data And uses NewProgram the algorithm from SolvesHaltingProblem to wri

33、te “Halts” if Example halts and “Loops” if it does not haltHalting ProblemsLets now apply program SolvesHaltingProblem to NewProgram, using NewProgram as dataIf SolvesHaltingProblem prints “Halts”, program NewProgram goes into an infinite loopIf SolvesHaltingProblem prints “Loops”, program NewProgram prints “Halts” and stopsIn either case, SolvesHaltingProblem gives the wrong answerBecause SolvesHaltingProblem gives the wrong answer in at least one case, it doesnt work on all cases4142Halting ProblemFigure 18.7 Construction of NewProgram43Classification of Algorithm