Algorithms and Environmental Engineering - Mathematics and Statistics for the Environment - page 92

Here, the problem—finding the greatest common divisor of two numbers—is specified by stat-
ing what is to be computed; the problem statement itself does not require that any particular algo-
rithm be used to compute the value. Such method-independent specifications can be used to define
the meaning of algorithms: the meaning of an algorithm is the value that it computes.
Several methods can be used to compute the required value; Euclid's method is just one. The
chosen method assumes a set of standard operations (such as basic operations on the whole number
and a means to repeat an operation) and combines these operations to form an operation that com-
putes the required value. Also, it is not at all obvious to the vast majority of people that the proposed
algorithm does actually compute the required value. That is one reason why a study of algorithms
is important—to develop methods that can be used to establish what a proposed algorithm achieves.
4.3 EXPRESSING ALGORITHMS
Although an in-depth discussion of algorithms is beyond the scope of this text, the analysis of algo-
rithms often requires us to draw upon a body of mathematical operations. Some of these operations
are as simple as high-school algebra, but others may be less familiar to the average environmental
engineer. Along with learning how to manipulate asymptotic notations and solving recurrences,
several other concepts and methods must be learned to analyze algorithms.
Methods for evaluating bounding summations, for example, occur frequently in the analysis of
algorithms and are used when an algorithm contains an iterative control construct such as a while
or for loop. In this case, the running time can be expressed as the sum of the times spent on each
execution of the body of the loop. Many of the formulas commonly used in analyzing algorithms
can be found in any calculus text. In addition, in order to analyze many algorithms, we must be
familiar with the basic definitions and notations for sets, relations, functions, graphs, and trees. A
basic understanding of elementary principles of counting (permutations, combinations, and the like)
is important as well. Most algorithms used in environmental engineering require no probability for
their analysis; however, a familiarity with these operations can be useful.
Because mathematical and scientific analyses (and many environmental engineering functions)
are so heavily based on numbers, computation has tended to be associated with numbers; however,
this need not be the case. Algorithms can be expressed using any formal manipulation system—that
is, any system that defines a set of entities and a set of unambiguous rules for manipulating those
entities. For example, SKI calculus consists of three combinators (entities) called, coincidentally, S ,
K , and I. The computation rules for the calculus are
1. Sfgx → fx ( gx )
2. Kxy → x
3. Ix → x
where f , g , x , and y are strings of the three entities. SKI calculus is computationally complete; that
is, any computation that can be performed using any formal system can be performed using SKI
calculus. (Equivalently, all algorithms can be expressed using SKI calculus.) Not all systems of
computation are equally as powerful, though; some problems that can be solved using one system
cannot be solved using another. Further, it is known that problems exist that cannot be solved using
any formal computation system.
4.4 GENERAL ALGORITHM APPLICATIONS
Practical applications of algorithms are ubiquitous. All computer programs are expressions of
algorithms, where the instructions are expressed in computer language being used to develop the
program. Computer programs are described as expressions of algorithms, as an algorithm is a gen-
eral technique for achieving some purpose and can be expressed in a number of different ways.