Lecture notes Mathematical foundation of Computer science

theoretical foundations of computer science lecture notes pdf and theoretical foundations of computer science important questions | pdf free download
DavidCooper Profile Pic
Published Date:11-07-2017
Your Website URL(Optional)
Foundations of Computer Science Computer Science Tripos Part 1a Lawrence C Paulson Computer Laboratory University of Cambridge lcpcl.cam.ac.uk Copyright° c 2000 by Lawrence C. PaulsonI Foundations of Computer Science 1 This course has two objectives. First (and obvious) is to teach program- ming. Second is to present some fundamental principles of computer science, especially algorithm design. Most students will have some programming ex- perience already, but there are few people whose programming cannot be improved through greater knowledge of basic principles. Please bear this point in mind if you have extensive experience and ¯nd parts of the course rather slow. The programming in this course is based on the language ML and mostly concerns the functional programming style. Functional programs tend to be shorter and easier to understand than their counterparts in conventional languages such as C. In the space of a few weeks, we shall be able to cover most of the forms of data structures seen in programming. The course also covers basic methods for estimating e±ciency. Courses in the Computer Laboratory are now expected to supply a Learn- ing Guide to suggest extra reading, discussion topics, exercises and past exam questions. For this course, such material is attached at the end of each lec- ture. Extra reading is mostly drawn from my book ML for the Working Programmer (second edition), which also contains many exercises. The only relevant exam questions are from the June 1998 papers for Part 1A. Thanks to Stuart Becker, Silas Brown, Frank King, Joseph Lord, James Margetson and Frank Stajano for pointing out errors in these notes. Please inform me of further errors and of passages that are particularly hard to understand. If I use your suggestion, I'll acknowledge it in the next printing. Suggested Reading List My own book is, naturally, closest in style to these notes. Ullman's book is another general introduction to ML. The Little MLer is a rather quirky tutorial on recursion and types. Harrison is of less direct relevance, but worth considering. See Introduction to Algorithms for O-notation. ² Paulson, Lawrence C. (1996). ML for the Working Programmer. Cam- bridge University Press (2nd ed.). ² Ullman, Je®rey D. (1993) Elements of ML Programming. Prentice Hall. ² Mattias Felleisen and Daniel P. Friedman (1998). The Little MLer. MIT Press. ² Harrison, Rachel (1993). Abstract Data Types in Standard ML. Wiley. ² Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest (1990). Introduction to Algorithms. MIT Press.I Foundations of Computer Science 2 Computers: a child can use them; NOBODY can fully understand them Master complexity through levels of abstraction Focus on 2 or 3 levels at most Slide 101 Recurring issues: ² what services to provide at each level ² how to implement them using lower-level services ² the interface: how the two levels should communicate A basic concept in computer science is that large systems can only be understood in levels, with each level further subdivided into functions or services of some sort. The interface to the higher level should supply the advertised services. Just as important, it should block access to the means by which those services are implemented. This abstraction barrier allows one level to be changed without a®ecting levels above. For example, when a manufacturer designs a faster version of a processor, it is essential that existing programs continue to run on it. Any di®erences between the old and new processors should be invisible to the program.I Foundations of Computer Science 3 Example I: Dates Abstract level: names for dates over a certain range Concrete level: typically 6 characters: YYMMDD Date crises caused by INADEQUATE internal formats: Slide 102 ² Digital’s PDP-10: using 12-bit dates (good for at most 11 years) ² 2000 crisis: 48 bits could be good for lifetime of universe Lessons: ² information can be represented in many ways ² get it wrong, and you will pay Digital Equipment Corporation's date crisis occurred in 1975. The PDP- 10 was a 36-bit mainframe computer. It represented dates using a 12-bit 12 format designed for the tiny PDP-8. With 12 bits, one can distinguish 2 = 4096 days or 11 years. The most common industry format for dates uses six characters: two for the year, two for the month and two for the day. The most common \solution" to the year 2000 crisis is to add two further characters, thereby altering ¯le sizes. Others have noticed that the existing six characters consist of 48 bits, already su±cient to represent all dates over the projected lifetime of the universe: 48 14 11 2 =2:8£ 10 days = 7:7£ 10 years Mathematicians think in terms of unbounded ranges, but the represen- tation we choose for the computer usually imposes hard limits. A good pro- gramming language like ML lets one easily change the representation used in the program. But if ¯les in the old representation exist all over the place, there will still be conversion problems. The need for compatibility with older systems causes problems across the computer industry.I Foundations of Computer Science 4 Example II: Floating-Point Numbers 3 Computers have integers like 1066 and reals like 1:066£ 10 A floating-point number is represented by two integers Slide 103 For either sort of number, there could be different precisions The concept of DATA TYPE: ² how a value is represented ² the suite of available operations Floating point numbers are what you get on any pocket calculator. In- ternally, a °oat consists of two integers: the mantissa (fractional part) and the exponent. Complex numbers, consisting of two reals, might be provided. We have three levels of numbers already Most computers give us a choice of precisions, too. In 32-bit precision, 31 31 integers typically range from 2 ¡ 1 (namely 2,147,483,647) to¡2 ; reals 35 are accurate to about six decimal places and can get as large as 10 or so. For reals, 64-bit precision is often preferred. How do we keep track of so many kinds of numbers? If we apply °oating-point arithmetic to an integer, the result is unde¯ned and might even vary from one version of a chip to another. Early languages like Fortran required variables to be declared as integer or real and prevented programmers from mixing both kinds of number in a computation. Nowadays, programs handle many di®erent kinds of data, including text and symbols. Modern languages use the concept of data type to ensure that a datum undergoes only those operations that are meaningful for it. Inside the computer, all data are stored as bits. Determining which type a particular bit pattern belongs to is impossible unless some bits have been set aside for that very purpose (as in languages like Lisp and Prolog). In most languages, the compiler uses types to generate correct machine code, and types are not stored during program execution.I Foundations of Computer Science 5 Some Abstraction Levels in a Computer user high-level language operating system Slide 104 device drivers,::: machine language registers & processors gates silicon These are just some of the levels that might be identi¯ed in a computer. Most large-scale systems are themselves divided into levels. For example, a management information system may consist of several database systems bolted together more-or-less elegantly. Communications protocols used on the Internet encompass several layers. Each layer has a di®erent task, such as making unreliable links reliable (by trying again if a transmission is not acknowledged) and making insecure links secure (using cryptography). It sounds complicated, but the necessary software can be found on many personal computers. In this course, we focus almost entirely on programming in a high-level language: ML.I Foundations of Computer Science 6 What is Programming? ² to describe a computation so that it can be done mechanically —expressions compute values Slide 105 —commands cause effects ² to do so efficiently, in both coding & execution ² to do so CORRECTLY, solving the right problem ² to allow easy modification as needs change programming in-the-small vs programming in-the-large Programming in-the-small concerns the writing of code to do simple, clearly de¯ned tasks. Programs provide expressions for describing mathe- matical formulae and so forth. (This was the original contribution of For- tran, the formula translator. Commands describe how control should °ow from one part of the program to the next. As we code layer upon layer in the usual way, we eventually ¯nd ourselves programming in-the-large: joining large modules to solve some possibly ill- de¯ned task. It becomes a challenge if the modules were never intended to work together in the ¯rst place. Programmers need a variety of skills: ² to communicate requirements, so they solve the right problem ² to analyze problems, breaking them down into smaller parts ² to organize solutions sensibly, so that they can be understood and modi¯ed ² to estimate costs, knowing in advance whether a given approach is feasible ² to use mathematics to arrive at correct and simple solutions We shall look at all these points during the course, though programs will be too simple to have much risk of getting the requirements wrong.I Foundations of Computer Science 7 Floating-Point, Revisited Results are ALWAYS wrong—do we know how wrong? Von Neumann doubted whether its benefits outweighed its COSTS Slide 106 Lessons: ² innovations are often derided as luxuries for lazy people ² their HIDDEN COSTS can be worse than the obvious ones ² luxuries often become necessities Floating-point is the basis for numerical computation: indispensable for science and engineering. Now read this 3, page 97 It would therefore seem to us not at all clear whether the modest advantages of a °oating binary point o®set the loss of memory capacity and the increased complexity of the arithmetic and control circuits. Von Neumann was one of the greatest ¯gures in the early days of computing. How could he get it so wrong? It happens again and again: ² Time-sharing (supporting multiple interactive sessions, as on thor) was for people too lazy to queue up holding decks of punched cards. ² Automatic storage management (usually called garbage collection)was for people too lazy to do the job themselves. ² Screen editors were for people too lazy to use line-oriented editors. To be fair, some innovations became established only after hardware advances reduced their costs. Floating-point arithmetic is used, for example, to design aircraftbut would you °y in one? Code can be correct assuming exact arithmetic but deliver, under °oating-point, wildly inaccurate results. The risk of error outweighs the increased complexity of the circuits: a hidden cost As it happens, there are methods for determining how accurate our an- swers are. A professional programmer will use them.I Foundations of Computer Science 8 Why Program in ML? It is interactive It has a flexible notion of data type Slide 107 It hides the underlying hardware: no crashes Programs can easily be understood mathematically It distinguishes naming something from UPDATING THE STORE It manages storage for us ML is the outcome of years of research into programming languages. It is unique among languages to be de¯ned using a mathematical formalism (an operational semantics) that is both precise and comprehensible. Several commercially supported compilers are available, and thanks to the formal de¯nition, there are remarkably few incompatibilities among them. Because of its connection to mathematics, ML programs can be designed and understood without thinking in detail about how the computer will run them. Although a program can abort, it cannot crash: it remains under the control of the ML system. It still achieves respectable e±ciency and pro- vides lower-level primitives for those who need them. Most other languages allow direct access to the underlying machine and even try to execute illegal operations, causing crashes. The only way to learn programming is by writing and running programs. 1 If you have a computer, install ML on it. I recommend Moscow ML, which runs on PCs, Macintoshes and Unix and is fast and small. It comes with extensive libraries and supports the full language except for some aspects of modules, which are not covered in this course. Moscow ML is also available under PWF. Cambridge ML is an alternative. It provides a Windows-based interface (due to Arthur Norman), but the compiler itself is the old Edinburgh ML, which is slow and buggy. It supports an out-of-date version of ML: many of the examples in my book 12 will not work. 1 http://www.dina.kvl.dk/sestoft/mosml.htmlI Foundations of Computer Science 9 2 The Area of a Circle: A =¼r val pi = 3.14159; val pi = 3.14159 : real pi 1.5 1.5; Slide 108 val it = 7.0685775 : real fun area (r) = pirr; val area = fn : real - real area 2.0; val it = 12.56636 : real The ¯rst line of this simple ML session is a value declaration. It makes the name pi stand for the real number 3.14159. (Such names are called iden- ti¯ers.) ML echoes the name (pi) and type (real) of the declared identi¯er. The second line computes the area of the circle with radius 1.5 using the 2 formula A =¼r . We use pi as an abbreviation for 3.14159. Multiplication is expressed using , which is called an in¯x operator because it is written in between its two operands. ML replies with the computed value (about 7.07) and its type (again real). Strictly speaking, we have declared the identi¯er it, which ML pro- vides to let us refer to the value of the last expression entered at top level. To work abstractly, we should provide the service \compute the area of a circle," so that we no longer need to remember the formula. So, the third line declares the function area. Given any real number r, it returns another real number, computed using the area formula; note that the function has type real-real. The fourth line calls function area supplying 2.0 as the argument. A circle of radius 2 has an area of about 12.6. Note that the brackets around a function's argument are optional, both in declaration and in use. The function usespi to stand for 3.14159. Unlike what you may have seen in other programming languages, pi cannot be \assigned to" or otherwise updated. Its meaning within area will persist even if we issue a new val declaration for pi afterwards.I Foundations of Computer Science 10 Integers; Multiple Arguments & Results fun toSeconds (mins, secs) = secs + 60mins; val toSeconds = fn : int int - int fun fromSecondss=(sdiv60,smod 60); Slide 109 val fromSeconds = fn : int - int int toSeconds (5,7); val it = 307 : int fromSeconds it; val it = (5, 7) : int int Given that there are 60 seconds in a minute, how many seconds are there inm minutes ands seconds? Function toSeconds performs the trivial calculation. It takes a pair of arguments, enclosed in brackets. We are now using integers. The integer sixty is written 60; the real sixty would be written 60.0. The multiplication operator, , is used for type int as well as real:itis overloaded. The addition operator, +,is also overloaded. As in most programming languages, multiplication (and division) have precedence over addition (and subtraction): we may write secs+60mins instead of secs+(60mins) The inverse of toSeconds demonstrates the in¯x operators div and mod, which express integer division and remainder. FunctionfromSeconds returns a pair of results, again enclosed in brackets. Carefully observe the types of the two functions: toSeconds : int int - int fromSeconds : int - int int They tell us that toSeconds maps a pair of integers to an integer, while fromSeconds maps an integer to a pair of integers. In a similar fashion, an ML function may take any number of arguments and return any number of results, possibly of di®erent types.I Foundations of Computer Science 11 Summary of ML’s numeric types int: the integers ² constants 0 1 ˜1 2 ˜2 0032::: Slide 110 ² infixes + - div mod real: the floating-point numbers ² constants 0.0 ˜1.414 3.94e˜7::: ² infixes +-/ ² functions Math.sqrt Math.sin Math.ln::: The underlined symbolsval andfun are keywords: they may not be used as identi¯ers. Here is a complete list of ML's keywords. abstype and andalso as case datatype do else end eqtype exception fn fun functor handle if in include infix infixr let local nonfix of op open orelse raise rec sharing sig signature struct structure then type val where while with withtype The negation of x is written x rather than -x, please note. Most lan- guages use the same symbol for minus and subtraction, but ML regards all operators, whether in¯x or not, as functions. Subtraction takes a pair of numbers, but minus takes a single number; they are distinct functions and must have distinct names. Similarly, we may not write +x. Computer numbers have a ¯nite range, which if exceeded gives rise to an Over°ow error. Some ML systems can represent integers of arbitrary size. If integers and reals must be combined in a calculation, ML provides functions to convert between them: real : int - real convert an integer to the corresponding real floor : real - int convert a real to the greatest integer not exceeding it ML's libraries are organized using modules, so we use compound identi- ¯ers such as Math.sqrt to refer to library functions. In Moscow ML, library units are loaded by commands such as load"Math";. There are thousands of library functions, including text-processing and operating systems functions in addition to the usual numerical ones.I Foundations of Computer Science 12 For more details on ML's syntax, please consult a textbook. Mine 12 and WikstrÄ om's 15 may be found in many College libraries. Ullman 14, in the Computer Lab library, is also worth a look. Learning guide. Related material is in ML for the Working Programmer, pages 147, and especially 1732. Exercise 1.1 One solution to the year 2000 bug involves storing years as two digits, but interpreting them such that 50 means 1950 and 49 means 2049. Comment on the merits and demerits of this approach. Exercise 1.2 Using the date representation of the previous exercise, code ML functions to (a) compare two years (b) add/subtract some given number of years from another year. (You may need to look ahead to the next lecture for ML's comparison operators.)II Foundations of Computer Science 13 Raising a Number to a Power fun npower(x,n) : real = if n=0 then 1.0 Slide 201 else x npower(x, n-1); val npower = fn : real int - real Mathematical Justification (forx=0 6 ): 0 x =1 n+1 n x =x£x : The function npower raises its real argument x to the power n, a non- negative integer. The function is recursive: it calls itself. This concept should be familiar from mathematics, since exponentiation is de¯ned by the rules shown above. The ML programmer uses recursion heavily. n+1 n For n¸ 0, the equation x =x£x yields an obvious computation: 3 2 1 0 x =x£x =x£x£x =x£x£x£x =x£x£x: The equation clearly holds even for negative n. However, the corresponding computation runs forever: ¡1 ¡2 ¡3 x =x£x =x£x£x =¢¢¢ Now for a tiresome but necessary aside. In most languages, the types of arguments and results must always be speci¯ed. ML is unusual in proving type inference: it normally works out the types for itself. However, sometimes ML needs a hint; function npower has a type constraint to say its result is real. Such constraints are required when overloading would otherwise make a function's type ambiguous. ML chooses type int by default or, in earlier versions, prints an error message. Despite the best e®orts of language designers, all programming languages have trouble points such as these. Typically, they are compromises caused by trying to get the best of both worlds, here type inference and overloading.II Foundations of Computer Science 14 An Aside: Overloading Functions defined for bothint andreal: ² operators ˜+- Slide 202 ² relations == The type checker requires help — a type constraint fun square (x)=xx; AMBIGUOUS fun square (x:real)=xx; Clear Nearly all programming languages overload the arithmetic operators. We don't want to have di®erent operators for each type of number Some lan- guages have just one type of number, converting automatically between dif- ferent formats; this is slow and could lead to unexpected rounding errors. Type constraints are allowed almost anywhere. We can put one on any occurrence of x in the function. We can constrain the function's result: fun squarex=xx: real; fun squarex:real=xx; ML treats the equality test specially. Expressions like if x=y then ::: are ¯ne providedx andy have the same type and equality testing is possible 1 for that type. Note thatxy is ML for x6=y. 1 All the types that we shall see for some time admit equality testing. Moscow ML allows even equality testing of reals, which is forbidden in the latest version of the ML library. Some compilers may insist that you write Real.==(x,y).II Foundations of Computer Science 15 Conditional Expressions and Typebool if b then x else y not(b) negation ofb Slide 203 p andalso q ´ if p then q else false p orelse q ´ if p then true else q A Boolean-valued function fun evenn=(nmod2=0); val even = fn : int - bool A characteristic feature of the computer is its ability to test for condi- tions and act accordingly. In the early days, a program might jump to a given address depending on the sign of some number. Later, John McCarthy de¯ned the conditional expression to satisfy (if true then x else y)=x (if false then x else y)=y ML evaluates the expression if B then E else E by ¯rst evaluatingB. 1 2 If the result is true then ML evaluates E and otherwise E . Only one of 1 2 the two expressions E and E is evaluated If both were evaluated, then 1 2 recursive functions like npower above would run forever. The if-expression is governed by an expression of type bool, whose two values are true and false. In modern programming languages, tests are not built into \conditional branch" constructs but have an independent status. Tests, or Boolean expressions, can be expressed using relational opera- tors such as and =. They can be combined using the Boolean operators for negation (not), conjunction (andalso) and disjunction (orelse). New properties can be declared as functions, e.g. to test whether an integer is even. Note. The andalso and orelse operators evaluate their second operand only if necessary. They cannot be de¯ned as functions: ML functions evalu- ate all their arguments. (In ML, any two-argument function can be turned into an in¯x operator.)II Foundations of Computer Science 16 Raising a Number to a Power, Revisited fun power(x,n) : real = if n=1 then x else if even n then power(xx, n div 2) Slide 204 else x power(xx, n div 2) Mathematical Justification: 1 x =x 2n 2 n x =(x ) 2n+1 2 n x =x£ (x ) : n+1 n For large n, computing powers using x = x£x is too slow to be practical. The equations above are much faster: 12 6 3 1 2 =4 =16 =16£ 256 =16£ 256 = 4096: Instead of n multiplications, we need at most 2 lgn multiplications, where lgn is the logarithm of n to the base 2. We use the function even, declared previously, to test whether the expo- nent is even. Integer division (div) truncates its result to an integer: dividing 2n + 1 by 2 yields n. A recurrence is a useful computation rule only if it is bound to terminate. Ifn 0 then n is smaller than both 2n and 2n + 1. After enough recursive calls, the exponent will be reduced to 1. The equations also hold if n· 0, but the corresponding computation runs forever. Our reasoning assumes arithmetic to be exact; fortunately, the calculation is well-behaved using °oating-point.II Foundations of Computer Science 17 Expression Evaluation E )E )¢¢¢)E )v 0 1 n Sample evaluation forpower: Slide 205 power(2; 12)) power(4; 6) ) power(16; 3) ) 16£power(256; 1) ) 16£ 256) 4096: Starting withE , the expressionE is reduced toE until this process 0 i i+1 concludes with a value v.A value is something like a number that cannot be further reduced. 0 0 We write E)E to say that E is reduced to E . Mathematically, they 0 0 are equal: E = E , but the computation goes from E to E and never the other way around. Evaluation concerns only expressions and the values they return. This view of computation may seem to be too narrow. It is certainly far removed from computer hardware, but that can be seen as an advantage. For the traditional concept of computing solutions to problems, expression evaluation is entirely adequate. Computers also interact with the outside world. For a start, they need some means of accepting problems and delivering solutions. Many computer systems monitor and control industrial processes. This role of computers is familiar now, but was never envisaged at ¯rst. Modelling it requires a notion of states that can be observed and changed. Then we can consider updating the state by assigning to variables or performing input/output, ¯nally arriving at conventional programs (familiar to those of you who know C, for instance) that consist of commands. For now, we remain at the level of expressions, which is usually termed functional programming.II Foundations of Computer Science 18 Example: Summing the Firstn Integers fun nsum n = if n=0 then 0 else n + nsum (n-1); Slide 206 val nsum = fn: int - int nsum 3)3+nsum 2 )3+(2+nsum 1) )3+(2+(1+nsum 0)) )3+(2+(1+0))):::) 6 The function call nsumn computes the sum 1 +¢¢¢ +n rather naÄ ³vely, hence the initial n in its name. The nesting of parentheses is not just an artifact of our notation; it indicates a real problem. The function gathers up a collection of numbers, but none of the additions can be performed until nsum 0 is reached. Meanwhile, the computer must store the numbers in an internal data structure, typically the stack. For largen,say nsum 10000, the computation might fail due to stack over°ow. We all know that the additions can be performed as we go along. How do we make the computer do that?II Foundations of Computer Science 19 Iteratively Summing the Firstn Integers fun summing (n,total) = if n=0 then total else summing (n-1, n + total); Slide 207 val summing = fn : int int - int summing (3; 0))summing (2; 3) )summing (1; 5) )summing (0; 6)) 6 Function summing takes an additional argument: a running total. If n is zero then it returns the running total; otherwise, summing adds to it and continues. The recursive calls do not nest; the additions are done immedi- ately. A recursive function whose computation does not nest is called iterative or tail-recursive. (Such computations resemble those that can be done using while-loops in conventional languages.) Many functions can be made iterative by introducing an argument anal- ogous to total, which is often called an accumulator. The gain in e±ciency is sometimes worthwhile and sometimes not. The functionpower is not iterative because nesting occurs whenever the exponent is odd. Adding a third argument makes it iterative, but the change compli- cates the function and the gain in e±ciency is minute; for 32-bit integers, 31 the maximum possible nesting is 30 for the exponent 2 ¡ 1. Obsession with tail recursion leads to a coding style in which functions have many more arguments than necessary. Write straightforward code ¯rst, avoiding only gross ine±ciency. If the program turns out to be too slow, tools are available for pinpointing the cause. Always remember KISS (Keep It Simple, Stupid). I hope you have all noticed by now that the summation can be done even more e±ciently using the arithmetic progression formula 1+¢¢¢ +n =n(n+1)=2:

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.