Лекция: Computers and algorithms
We live in the age of the computer revolution. Like any revolution, it is widespread, all-pervasive, and will have a lasting impact. It is as fundamental to our economic and social order as was the industrial revolution. It will affect the thinking patterns and life style of every individual.
The industrial revolution was essentially the augmentation of man's physical powers, the amplification of man's muscle. The pressing of a button could cause a large machine to stamp a pattern in a metal sheet. The movement of a lever could result in a heavy scoop scraping out a mass of coal. Certain repetitive aspects of man's physical activities were replaced by machines.
By analogy, the computer revolution is the augmentation of man's mental powers; the amplification of man's brain. The pressing of a button can cause a machine to perform intricate calculations, to make complex decisions, or to store and retrieve vast quantities of information. Certain repetitive aspects of man's mental activities are being replaced by machines.
What is a computer, that it can have such a revolutionary impact? A first step toward an answer is to say that a computer is a machine which can carry out routine mental tasks by performing simple operations at high speed. The simplicity of the operations (typical examples are the addition or comparison of two numbers) is offset by the speed at which they are performed (about a million a second). The result is that large numbers of operations can be performed, and significant tasks can be accomplished.
Of course, a computer can accomplish only those tasks which can be specified in terms of the simple operations it can execute. To get a computer to carry out a task one must tell it what operations to perform—in other words, one must describe how the task is to be accomplished. Such a description is called an algorithm. An algorithm describes the method by which a task is to be accomplished. The algorithm consists of a sequence of steps which if faithfully performed will result in the task, or process, being carried out.
The notion of an algorithm is not peculiar to computer science—there are algorithms which describe all kinds of everyday processes.
In general, the agent which carries out a process is called a processor. A processor may be a person, a computer, or some other electronic or mechanical device. A processor carries out a process by obeying, or executing, the algorithm which describes it. Execution of an algorithm involves execution of each of its constituent steps.
From the discussion above it is apparent that a computer is simply a particular kind of processor. Of course, it is rather a special kind of processor; otherwise computers would not have had such a rapid and significant impact on so many areas of life. The features which make it special are described below.
(1) the central processing unit (CPU), which performs the basic operations,
(2) the memory, which holds;
(a) the algorithm specifying the operations to be performed
(b) the information, or data, upon which the operations are to act;
(3) the input and output devices (l/0 devices), through which the algorithm and the data are fed into the memory, and through which the computer communicates the results of its activities.
These components comprise the computer hardware: that is, the physical units from which a computer is built.
The CPU of a typical computer can perform between one million and ten million operations a second. Although these operations are very simple the formidable speed with which they are performed means that even quite complex algorithms, requiring large numbers of operations, can be executed very quickly. By comparison the human brain is very slow, so it is not surprising that people have been replaced by computers in many activities where speed is a major requirement. Human beings do, however, currently retain significant advantages over computers. For example, it appears that the brain is capable of performing many operations at once whereas (with minor exceptions) a present-day computer can perform only one operation at a time.
Despite the high speed of computers there remain many processes which are simply too time consuming to be feasibly carried out. (An example is the formulation of a winning strategy for chess by studying all chess games which could possibly be played.)
Contrary to popular mythology computers seldom make mistakes, though they do occasionally break down. The mistakes which achieve prominence in the news media, such as an electricity bill for a million dollars or a false alert about nuclear attack, are almost invariably a result of a fault in the algorithm being executed or an error in the input data. On very rare occasions an electronic fault may cause a computer to execute an algorithm incorrectly, but the probability of this is minute, and in any case such malfunctions are usually detected immediately.
A computer is in a sense a totally willing and obedient slave: it will faithfully execute the algorithm it is given, and if necessary it will do so repeatedly without complaint. Such fidelity is of course both a strength and a weakness, since the computer will execute the algorithm quite blindly, whether or not it correctly describes the process intended.
One of the prime characteristics of a computer is its ability to store vast quantities of information which it can access very quickly. Memory capacities and access speeds vary widely according to the storage medium used; some computers can store several thousand million items of information, and can access some of these items in as little as 100 nanoseconds (a nanosecond is 10-9 seconds, or one thousand millionth of a second). Impressive though these figures are, they are somewhat deceptive. As we shall see later, computer memory is organized in such a way that an item of information can be retrieved only if its location in the storage medium is precisely known. This means that a lot of effort must be put into keeping track of where information is located—effort which increases both the time to design an algorithm and the time to execute it.