tailieunhanh - Lecture Notes for CS120: An Introduction to Computing 1 Subhashis Banerjee S

Modern computers based on integrated circuits are millions to billions of times more capable than the early machines, and occupy a fraction of the space.[2] Simple computers are small enough to fit into mobile devices, and mobile computers can be powered by small batteries. Personal computers in their various forms are icons of the Information Age and are what most people think of as "computers". However, the embedded computers found in many devices from MP3 players to fighter aircraft and from toys to industrial robots are the most numerous | Lecture Notes for CS120 An Introduction to Computing1 Subhashis Banerjee S. Arun-Kumar Department of Computer Science and Engineering Indian Institute of Technology New Delhi 110016 email suban sak @ August 2 2003 1Copyright 1997-2003 Subhashis Banerjee and S. Arun-Kumar. All Rights Reserved. These notes may be used in an academic course with the prior consent of the authors. 2 Contents I Models of computation 5 1 Introduction 7 2 Mathematical preliminaries 9 Sets. 9 Relations and Functions. 11 Principle of Mathematical Induction. 11 3 A functional model of computation 17 The primitive expressions. 18 Substitution of functions. 20 Substitution using let. 21 Definition of functions using conditionals. 23 Functions as inductively defined computational processes . 24 Recursive processes. 26 Analysis of correctness and efficiency. 28 Correctness. 28 Efficiency . 28 Efficiency Why and How . 29 In the long run Asymptotic analysis and Orders of growth . 30 More examples of recursive algorithms. 31 Scope rules. 41 Tail-recursion and iterative processes. 43 Correctness of an iterative process. 45 More examples of iterative processes. 46 4 The Imperative model of computation 53 The primitives for the imperative model . 53 Variables and the assignment instruction . 54 Assertions . 56 The if then else instruction. 58 The while do instruction. 61