Chapter 1 Computers and Programs Objectives To understand the respective roles of hardware and software in a comput- ing system. To learn what computer scientists study and the techniques that they use. To understand the basic design of a modern computer. To understand the form and function of computer programming languages. To begin using the Python programming language. To learn about chaotic models and their implications for computing. 1.1 The Universal Machine Almost everyone has used a computer at one time or another.Perhaps you have played computer games or used a computer to write a paper or balance your checkbook.Computers are used to predict the weather,design airplanes,make movies,run businesses,perform financial transactions,and control factories. Have you ever stopped to wonder what exactly a computer is?How can one device perform so many different tasks?These basic questions are the starting point for learning about computers and computer programming. A modern computer can be defined as"a machine that stores and manipu- lates information under the control of a changeable program."There are two 1
Chapter 1 Computers and Programs Objectives • To understand the respective roles of hardware and software in a computing system. • To learn what computer scientists study and the techniques that they use. • To understand the basic design of a modern computer. • To understand the form and function of computer programming languages. • To begin using the Python programming language. • To learn about chaotic models and their implications for computing. 1.1 The Universal Machine Almost everyone has used a computer at one time or another. Perhaps you have played computer games or used a computer to write a paper or balance your checkbook. Computers are used to predict the weather, design airplanes, make movies, run businesses, perform financial transactions, and control factories. Have you ever stopped to wonder what exactly a computer is? How can one device perform so many different tasks? These basic questions are the starting point for learning about computers and computer programming. A modern computer can be defined as "a machine that stores and manipulates information under the control of a changeable program." There are two
2 Chapter 1.Computers and Programs key elements to this definition.The first is that computers are devices for ma- nipulating information.This means we can put information into a computer, and it can transform the information into new,useful forms,and then output or display the information for our interpretation. Computers are not the only machines that manipulate information.When you use a simple calculator to add up a column of numbers,you are entering information (the numbers)and the calculator is processing the information to compute a running sum which is then displayed.Another simple example is a gas pump.As you fill your tank,the pump uses certain inputs:the current price of gas per gallon and signals from a sensor that reads the rate of gas flowing into your car.The pump transforms this input into information about how much gas you took and how much money you owe. We would not consider either the calculator or the gas pump as full-fledged computers,although modern versions of these devices may actually contain em- bedded computers.They are different from computers in that they are built to perform a single,specific task.This is where the second part of our definition comes into the picture:Computers operate under the control of a changeable program.What exactly does this mean? A computer program is a detailed,step-by-step set of instructions telling a computer exactly what to do.If we change the program,then the computer performs a different sequence of actions,and hence,performs a different task. It is this flexibility that allows your PC to be at one moment a word processor, at the next moment a financial planner,and later on,an arcade game.The machine stays the same,but the program controlling the machine changes. Every computer is just a machine for executing (carrying out)programs. There are many different kinds of computers.You might be familiar with Mac- intoshes and PCs,but there are literally thousands of other kinds of computers both real and theoretical.One of the remarkable discoveries of computer sci- ence is the realization that all of these different computers have the same power; with suitable programming,each computer can basically do all the things that any other computer can do.In this sense,the PC that you might have sitting on your desk is really a universal machine.It can do anything you want it to do, provided you can describe the task to be accomplished in sufficient detail.Now that's a powerful machine!
Chapter 1. Computers and Programs key elements to this definition. The first is that computers are devices for manipulating information. This means we can put information into a computer, and it can transform the information into new, useful forms, and then output or display the information for our interpretation. Computers are not the only machines that manipulate information. When you use a simple calculator to add up a column of numbers, you are entering information (the numbers) and the calculator is processing the information to compute a running sum which is then displayed. Another simple example is a gas pump. As you fill your tank, the pump uses certain inputs: the current price of gas per gallon and signals from a sensor that reads the rate of gas flowing into your car. The pump transforms this input into information about how much gas you took and how much money you owe. We would not consider either the calculator or the gas pump as full-fledged computers, although modern versions of these devices may actually contain em- bedded computers. They are different from computers in that they are built to perform a single, specific task. This is where the second part of our definition comes into the picture: Computers operate under the control of a changeable program. What exactly does this mean? A computer program is a detailed, step-by-step set of instructions telling a computer exactly what to do. If we change the program, then the computer performs a different sequence of actions, and hence, performs a different task. It is this flexibility that allows your PC to be at one moment a word processor, at the next moment a financial planner, and later on, an arcade game. The machine stays the same, but the program controlling the machine changes. Every computer is just a machine for executing (carrying out) programs. There are many different kinds of computers. You might be familiar with Macintoshes and PCs, but there are literally thousands of other kinds of computers both real and theoretical. One of the remarkable discoveries of computer sci- ence is the realization that all of these different computers have the same power; with suitable programming, each computer can basically do all the things that any other computer can do. In this sense, the PC that you might have sitting on your desk is really a universal machine. It can do anything you want it to do, provided you can describe the task to be accomplished in sufficient detail. Now that's a powerful machine!
1.2.Program Power 3 1.2 Program Power You have already learned an important lesson of computing:Software (pro- grams)rules the hardware (the physical machine).It is the software that de- termines what any computer can do.Without software,computers would just be expensive paperweights.The process of creating software is called program- ming,and that is the main focus of this book. Computer programming is a challenging activity.Good programming re- quires an ability to see the big picture while paying attention to minute detail. Not everyone has the talent to become a first-class programmer,just as not ev- eryone has the skills to be a professional athlete.However,virtually anyone can learn how to program computers.With some patience and effort on your part, this book will help you to become a programmer. There are lots of good reasons to learn programming.Programming is a fundamental part of computer science and is,therefore,important to anyone in- terested in becoming a computer professional.But others can also benefit from the experience.Computers have become a commonplace tool in our society.Un- derstanding the strengths and limitations of this tool requires an understanding of programming.Non-programmers often feel they are slaves of their comput- ers.Programmers,however,are truly in control.If you want to become a more intelligent user of computers,then this book is for you. Programming can also be loads of fun.It is an intellectually engaging ac- tivity that allows people to express themselves through useful and sometimes remarkably beautiful creations.Believe it or not,many people actually write computer programs as a hobby.Programming also develops valuable problem- solving skills,especially the ability to analyze complex systems by reducing them to interactions of understandable subsystems. As you probably know,programmers are in great demand.More than a few liberal arts majors have turned a couple of computer programming classes into a lucrative career option.Computers are so commonplace in the business world today that the ability to understand and program computers might just give you the edge over your competition,regardless of your occupation. 1.3 What is Computer Science? You might be surprised to learn that computer science is not the study of com- puters.A famous computer scientist named Edsger Dijkstra once quipped that computers are to computer science what telescopes are to astronomy.The com-
1.2. Program Power 1.2| Program Power You have already learned an important lesson of computing: Software (programs) rules the hardware (the physical machine). It is the software that determines what any computer can do. Without software, computers would just be expensive paperweights. The process of creating software is called programming, and that is the main focus of this book. Computer programming is a challenging activity. Good programming re- quires an ability to see the big picture while paying attention to minute detail. Not everyone has the talent to become a first-class programmer, just as not ev- eryone has the skills to be a professional athlete. However, virtually anyone can learn how to program computers. With some patience and effort on your part, this book will help you to become a programmer. There are lots of good reasons to learn programming. Programming is a fundamental part of computer science and is, therefore, important to anyone in- terested in becoming a computer professional. But others can also benefit from the experience. Computers have become a commonplace tool in our society. Understanding the strengths and limitations of this tool requires an understanding of programming. Non-programmers often feel they are slaves of their computers. Programmers, however, are truly in control. If you want to become a more intelligent user of computers, then this book is for you. Programming can also be loads of fun. It is an intellectually engaging activity that allows people to express themselves through useful and sometimes remarkably beautiful creations. Believe it or not, many people actually write computer programs as a hobby. Programming also develops valuable problemsolving skills, especially the ability to analyze complex systems by reducing them to interactions of understandable subsystems. As you probably know, programmers are in great demand. More than a few liberal arts majors have turned a couple of computer programming classes into a lucrative career option. Computers are so commonplace in the business world today that the ability to understand and program computers might just give you the edge over your competition, regardless of your occupation. 1.3 1 What is Computer Science? You might be surprised to learn that computer science is not the study of computers. A famous computer scientist named Edsger Dijkstra once quipped that computers are to computer science what telescopes are to astronomy. The com-
Chapter 1.Computers and Programs puter is an important tool in computer science,but it is not itself the object of study.Since a computer can carry out any process that we can describe,the real question is What processes can we describe?Put another way,the fundamental question of computer science is simply What can be computed?Computer sci- entists use numerous techniques of investigation to answer this question.The three main ones are design,analysis,and experimentation. One way to demonstrate that a particular problem can be solved is to actu- ally design a solution.That is,we develop a step-by-step process for achieving the desired result.Computer scientists call this an algorithm.That's a fancy word that basically means"recipe."The design of algorithms is one of the most important facets of computer science.In this book you will find techniques for designing and implementing algorithms. One weakness of design is that it can only answer the question What is com- putable?in the positive.If I can devise an algorithm,then the problem is solv- able.However,failing to find an algorithm does not mean that a problem is unsolvable.It may mean that I'm just not smart enough,or I haven't hit upon the right idea yet.This is where analysis comes in. Analysis is the process of examining algorithms and problems mathemati- cally.Computer scientists have shown that some seemingly simple problems are not solvable by any algorithm.Other problems are intractable.The algo- rithms that solve these problems take too long or require too much memory to be of practical value.Analysis of algorithms is an important part of computer science;throughout this book we will touch on some of the fundamental princi- ples.Chapter 13 has examples of unsolvable and intractable problems. Some problems are too complex or ill-defined to lend themselves to anal- ysis.In such cases,computer scientists rely on experimentation;they actually implement systems and then study the resulting behavior.Even when theoret- ical analysis is done,experimentation is often needed in order to verify and refine the analysis.For most problems,the bottom line is whether a working, reliable system can be built.Often we require empirical testing of the system to determine that this bottom-line has been met.As you begin writing your own programs,you will get plenty of opportunities to observe your solutions in action. I have defined computer science in terms of designing,analyzing,and evalu- ating algorithms,and this is certainly the core of the academic discipline.These days,however,computer scientists are involved in far-flung activities,all of which fall under the general umbrella of computing.Some example areas in- clude networking,human-computer interaction,artificial intelligence,computa-
Chapter 1. Computers and Programs puter is an important tool in computer science, but it is not itself the object of study. Since a computer can carry out any process that we can describe, the real question is What processes can we describe? Put another way, the fundamental question of computer science is simply What can be computed? Computer sci- entists use numerous techniques of investigation to answer this question. The three main ones are design, analysis, and experimentation. One way to demonstrate that a particular problem can be solved is to actually design a solution. That is, we develop a step-by-step process for achieving the desired result. Computer scientists call this an algorithm. That's a fancy word that basically means "recipe." The design of algorithms is one of the most important facets of computer science. In this book you will find techniques for designing and implementing algorithms. One weakness of design is that it can only answer the question What is computable? in the positive. If I can devise an algorithm, then the problem is solv- able. However, failing to find an algorithm does not mean that a problem is unsolvable. It may mean that I'm just not smart enough, or I haven't hit upon the right idea yet. This is where analysis comes in. Analysis is the process of examining algorithms and problems mathematically. Computer scientists have shown that some seemingly simple problems are not solvable by any algorithm. Other problems are intractable. The algorithms that solve these problems take too long or require too much memory to be of practical value. Analysis of algorithms is an important part of computer science; throughout this book we will touch on some of the fundamental principles. Chapter 13 has examples of unsolvable and intractable problems. Some problems are too complex or ill-defined to lend themselves to analysis. In such cases, computer scientists rely on experimentation; they actually implement systems and then study the resulting behavior. Even when theoretical analysis is done, experimentation is often needed in order to verify and refine the analysis. For most problems, the bottom line is whether a working, reliable system can be built. Often we require empirical testing of the system to determine that this bottom-line has been met. As you begin writing your own programs, you will get plenty of opportunities to observe your solutions in action. I have defined computer science in terms of designing, analyzing, and evaluating algorithms, and this is certainly the core of the academic discipline. These days, however, computer scientists are involved in far-flung activities, all of which fall under the general umbrella of computing. Some example areas in- clude networking, human-computer interaction, artificial intelligence, computa-
1.4.Hardware Basics 5 Output CPU Devices Input Devices Main Secondary Memory Memory Figure 1.1:Functional View of a Computer. tional science (using powerful computers to model scientific data),databases, software engineering,web and multimedia design,management information systems,and computer security.Wherever computing is done,the skills and knowledge of computer science are being applied. 1.4 Hardware Basics You don't have to know all the details of how a computer works to be a successful programmer,but understanding the underlying principles will help you master the steps we go through to put our programs into action.It's a bit like driving a car.Knowing a little about internal combustion engines helps to explain why you have to do things like fill the gas tank,start the engine,step on the accelerator, etc.You could learn to drive by just memorizing what to do,but a little more knowledge makes the whole process much more understandable.Let's take a moment to"look under the hood"of your computer. Although different computers can vary significantly in specific details,at a higher level all modern digital computers are remarkably similar.Figure 1.1 shows a functional view of a computer.The central processing unit (CPU)is the "brain"of the machine.This is where all the basic operations of the computer are carried out.The CPU can perform simple arithmetic operations like adding two numbers and can also do logical operations like testing to see if two numbers are equal The memory stores programs and data.The CPU can only directly access information that is stored in main memory (called RAM for Random Access Mem- ory).Main memory is fast,but it is also volatile.That is,when the power is
1.4. Hardware Basics Output CPU Devices Input Devices Secondary Memory Main Memory Figure 1.1: Functional View of a Computer. tional science (using powerful computers to model scientific data), databases, software engineering, web and multimedia design, management information systems, and computer security. Wherever computing is done, the skills and knowledge of computer science are being applied. 1.4 Hardware Basics You don't have to know all the details of how a computer works to be a successful programmer, but understanding the underlying principles will help you master the steps we go through to put our programs into action. It's a bit like driving a car. Knowing a little about internal combustion engines helps to explain why you have to do things like fill the gas tank, start the engine, step on the accelerator, etc. You could learn to drive by just memorizing what to do, but a little more knowledge makes the whole process much more understandable. Let's take a moment to "look under the hood" of your computer. Although different computers can vary significantly in specific details, at a higher level all modern digital computers are remarkably similar. Figure 1.1 shows a functional view of a computer. The central processing unit (CPU) is the "brain" of the machine. This is where all the basic operations of the computer are carried out. The CPU can perform simple arithmetic operations like adding two numbers and can also do logical operations like testing to see if two numbers are equal. The memory stores programs and data. The CPU can only directly access information that is stored in main memory (called RAM for Random Access Memory). Main memory is fast, but it is also volatile. That is, when the power is