We are constantly involved in solving problem. The problems may concern our survival in a competitive and hostile environment, may concern our curiosity to know more and more of various facets of nature or may be about any other issues of interest to us. Problem may be a state of mind of a living being, of not being satisfied with some situation. However, for our purpose, we may take the unsatisfactory/ unacceptable/ undesirable situation itself, as a problem.
Two ideas lie gleaming on the jeweller’s velvet. The first is the calculus; the second, the algorithm. The calculus and the rich body of mathematical analysis to which it gave rise made modern science possible; but it has been the algorithm that has made possible the modern world.
David Berlinski
in
The Advent of the Algorithm, 2000
One way of looking at a possible solution of a problem, is as a sequence of activities (if such a sequence exists at all), that if carried out using allowed/available tools, leads us from the unsatisfactory (initial) position to an acceptable, satisfactory or desired position. For example, the solution of the problem of baking delicious pudding may be thought of as a sequence of activities, that when carried out, gives us the pudding (the desired state) from the raw materials that may include sugar, flour and water (constituting the initial position)using cooking gas, oven and some utensils etc. (the tools). The sequence of activities when carried out gives rise to a process.
Technically, the statement or description in some notation, of the process is called an algorithm, the raw materials are called the inputs and the resulting entity (in the above case, the pudding) is called the output. In view of the importance of the concept of algorithm, we repeat:
An algorithm is a description or statement of a sequence of activities that constitute a process of getting the desired outputs from the given inputs.
Later we consider in detail the characteristics features of an algorithm. Next, we define a closely related concept of computer program.
Computer Program: An algorithm, when expressed in a notation that can be understood and executed by a computer system is called a computer program or simply a program.We should be clear about the distinction between the terms viz., a process, a program and an algorithm.
A process is a sequence of activities actually being carried out or executed, to solve a problem. But algorithm and programs are just descriptions of a process in some notation. Further, a program is an algorithm in a notation that can be understood and be executed by a computer system.
It may be noted that for some problems and the available tools, there may not exist any algorithm that should give the desired output. For example, the problem of baking delicious pudding may not be solvable, if no cooking gas or any other heating substance is available. Similarly, the problem of reaching the moon is unsolvable, if no spaceship is available for the purpose.
These examples also highlight the significance of available tools in solving a problem. Later, we discuss some of mathematical problems which are not solvable. But, again these problems are said to be unsolvable, because of the fact that the operations (i.e., the tools) that are allowed to be used in solving the problems, are from a restricted pre-assigned set.
Notation for expressing algorithms
This issue of notation for representations of algorithms will be discussed in some detail, later. However, mainly, some combinations of mathematical symbols, English phrases and sentences, and some sort of pseudo-high-level language notations, shall be used for the purpose.
Particularly, the symbol ‘<--’ is used for assignment. For example, x<--y + 3, means that 3 is added to the value of the variable y and the resultant value becomes the new value of the variable x. However, the value of y remains unchanged.
If in an algorithm, more than one variables are required to store values of the same type, notation of the form A[1..n] is used to denote n variables A[1], A[2], … A[n].
In general, for the integers m, n with m <-- n, A [m..n] is used to denote the variables A[m], A[m+1], …, A[n]. However, we must note that another similar notation A[m, n] is used to indicate the element of the matrix (or two-dimensional array) A, which is in mth row and nth column. Role and Notation for Comments
Role and Notation for Comments
The comments do not form that part of an algorithm, corresponding to which there is an (executable) action in the process. However, the comments help the human reader of the algorithm to better understand the algorithm. In different programming languages, there are different notations for incorporating comments in algorithms. We use the convention of putting comments between pair of braces, i.e., { } . The comments may be inserted at any place within an algorithm. For example, if an algorithm finds roots of a quadratic equation, then we may add the following comments, somewhere in the beginning of the algorithm, to tell what the algorithm does:
No comments:
Post a Comment