|
Читайте также: |
Instructions contained in a program should realize some task, solve a problem. It is possible of course to write a program consisting of random instructions, but it doesn't make much sense.
Thus, a program should be considered from other (then technical, characterized by executing of instructions by the CPU) point of view.
Since programs are designed to solve problems, the starting point should be determined by formulating the problem or the task, the way of solving it and steps leading to achievement of the goal. In other words - by formulation of the algorithm that solves the problem or performs the task.
ALGORITHM is a recipe leading to solution of the given problem; set of commands concerning some objects (data) - with determined order of execution. These commands are executed by a device, which in response to signals representing commands reacts in their realization. Device may be represented by a human, computer or other appliance.
(source: PWN Encyclopedia)
Algorithms are expressed in many ways: in natural language, graphically using a chart or in so called pseudocode (a language for expressing algorithms, independent of existing, available programming languages).
Imagine one wants to buy a computer and needs to configure it to calcualte its price (by adding prices of its parts).
The simplest solution realizing the above task is shown below:
1. Pick a CPU from the price list and store its price.
2. Pick RAM memory modules from the price list and store their price.
3. Pick a motherboard from the price list and store its price.
4. Pick a graphics card from the price list and store its price.
5. Pick a hard disk from the price list and store its price.
6. Pick a CDROM or DVD drive from the price list and store its price.
7. Pick a sound card from the price list and store its price.
8. Pick other necessary accessories and store their prices.
9. Sum all the prices up.
This solution is encoded in natural language. Graphically this algorithm can be represented as shown on the picture.
Notice precisely specified order of the steps in the sequence on commands. The algorithm has well defined starting point. Its proper execution and stop is guaranteed. It can be executed many times with different input data - in this case with different configurations of the hardware.
This algorithm is understandable for a man. One can apply it using a pen and a piece of paper.
Now the question arises: how the task of calculating of the price can be done by a computer?
As can be easily guessed, the above algorithm has to be rewritten in some programming language to obtain its source code, which can be then translated to the machine language understandable by the CPU. Thus obtained binary executable can be run on a computer.
However from the beginning we encounter some fundamental problems: what the formula "pick..., store its price" does really mean?
Since the program is based on the algorithm, and will be executed by a computer its instructions should be formulated in terms of computer actions.
Notice also, that generally an algorithm processes some input data (supplied by a user) to obtain output data as a result.
Thus the following has to be specified: what data and when should be supplied to the program, and how they should be processed by the computer.
There are 3 possibilities (at least):
In the first case the above algorithm changes only a bit, but remember that it is formulated in terms of computer activities.
1. Ask user for CPU price
2. Ask user for motherboard price
...
n-1. Sum given prices up
n. Display result to the user
The two other of the above possibilities lead to much more sophisticated algorithms.
Note that the above simple algorithm has quite general form. Its translation to a specific programming language requires taking many decisions, for example:
These decisions relate to the so called user interface (the manner in which program communicates with user) and also to the structure of the algorithm in respect to its resistance to errors and ease of modifications. For example the above algorithm should check, whether the given input data are really numbers. Programmer should also consider storing the prices of components in case of potential future requirements pertaining to the output data: besides the sum, detailed "calculations report" might be needed as result (presenting price of each component or even its share in final price).
The mere reaction to erroneous input data changes sequence of steps in considered algorithm.
Solution to any problem requires usually - besides some simple sequence of steps - the following:
Taking into account possibility of potential errors in the input data and the need for storing prices of the components, algorithm for calculating price of a computer may look like this:
1. Ask a user for the CPU price.
2. If the price given is not a number, notify the user about error and go to step 1.
3. Store the given price of the CPU (for later reference)
4. Ask a user for the motherboard price.
5. If the price given is not a number, notify the user about error and go to step 4.
6. Store the given price of the motherboard (for later reference)
... other components
... other components
n-1. Calculate the sum of the components
n. Display result
In flow chart decisions are represented by the rhombus.
Example: flow chart for the algorithm calculating tax.
Algorithms are usually written in pseudocode - formalized (to some degree) form of natural language, independent of any programming language. Pseudocode is much closer to a programming language than natural language and is easier to transform into program written in some definite programming language. Various handbooks on programming present different forms of pseudocode. One can easily define one's own version.
Pseudocode uses variables - symbolic representation of data (more about variables will be explained in the next lecture; for now let's treat them as variables in mathematical formulae).
Operations on variables are coded with the help of operators - symbols of mathematical operations: addition, subtraction, multiplication, division etc. (more on this in the next lecture).
Pseudocode also uses words and expressions precisely defining the meaning of fragments of algorithms (actions, instructions). For example taking a decision can be written down this way:
if (condition) then...
or
if (condition) then...
else...
and iteration loops (i.e. repeated execution of fragments of the algorithm)
execute until (condition)...
execute modifying value of the variable i from p to l...
Whereas input and output of data can be expressed by means of words: read, write.
Applying symbols +, - i * for expressing operations of addition, subtraction and multiplication, parentheses (like in mathematics) for grouping of operations and special words for expressing actions and decisions, algorithm for calculation of tax may be written down as follows:
read income
if (income > 74048) then tax = 17048.44 + 0.4 * (income - 74048)
else if (income > 37024) then
tax = 6541.24 + 0.3 * (income - 37024)
else tax = 0.19 * income - 493.32
write tax
Such notation of this algorithm demonstrates two problems.
Firstly, error in input data changes sequence of steps carried out by the algorithm and causes return to the instruction reading input data. In pseudocode such action is written down as jump to specific fragment of the algorithm (go to...), denoted by a label (labels are words ended with colon ':'). By the way let's introduce to the pseudocode braces ("{", "}") for grouping of actions; for example:
if (condition) then {
action 1
action 2
}
If condition is fulfilled, actions grouped inside the braces are executed.
dataInput1:
write "Give the price of the CPU"
read CPUprice
if (CPUprice is not a number) then {
write "Wrong data"
go to dataInput1
}
dataInput2:
write "Give0 the price of the motherboard"
read MBprice
if (MBprice is not a number) then {
write "Wrong data"
go to dataInput2
}
...
result = sum of prices
write result
However such notation causes, that algorithms (and programs) are hardly readable, their logic complicated and are subject to errors.
That's why most of programming languages do not use the go to (goto) instruction any more. Instead iteration loops are applied. For this reason flow charts have lost popularity too (it turns out, that flow charts are not always translatable into languages without the "goto" instruction).
Thus, the algorithm for calculating computer price should be expressed in other form. Let's use iteration loops and introduce boolean (logical) variable named dataRequired with 2 possible values yes and no.
dataRequired = yes
execute until (dataRequired) {
write "Give the price of the CPU"
read CPUprice
if (CPUprice is not a number) then write "Wrong data"
else dataRequired = no
}
dataRequired = yes
execute until (dataRequired) {
write "Give the price of the motherboard"
read MBprice
if (MBprice is not a number) then write "Wrong data"
else dataRequired = no
}
...
result = sum of prices
write result
At the beginning, the value of the variable dataRequired is yes and the condition in execute until is fulfilled. Therefore execution of the instructions grouped between the braces starts. If the data read (CPUprice) is not a number, the message "Wrong data" is displayed. The value of the variable dataRequired does not change then and the actions grouped between the braces are executed again (because the condition in execute until is still fulfilled). On the contrary, if CPUprice is a number, the variable dataRequired gets the value of no in which case the condition in execute until is not fulfilled anymore and the actions between the braces are not executed. The algorithm continues execution from the instruction following right brace '}' - it reads the price of the motherboard.
Another problem we encounter in this algorithm is repeating similar (almost identical) actions. Consider reading price of CPU, motherboard and other components - all of these operations look similarly. For this reason we might isolate these actions and write them down in form of so called procedure or function. Written down once they may be executed repeatedly for various components of a computer.
This means, that problem of calculating the price of a computer is divided into two sub problems:
Each of these problems may be solved separately, concentrating on features specific to its context.
This way of programming is called structural programming.
The following lectures introduce the notion of function and their usage in programs.
To sum up:
Note that programs do not only reflect steps (commands, actions) of algorithms, but also represent processed data. These data might be represented as single separate copies or grouped into sets (tied somehow and/or ordered somehow). In such case we can speak of data structures.
Thus, another definition of program can be quoted (by N.Wirth):
PROGRAM is a concrete formulation of an abstract algorithm based on specific representation of data structure.
Both definitions are consistent. The first, quoted at the beginning of the lecture ("program is encoded sequence of instructions for the CPU or other hardware devices") stresses actions executed by a program, the second ("concrete formulation of an abstract algorithm") stresses creation of a program.
The text of the program (its source code) is written in a programming language.
Each programming language has its alphabet - set of characters (letters and digits) from which symbols of the language (sequences of characters) are built. Syntactic rules define acceptable ways for building symbols and acceptable order of their occurrences in a program. Semantics defines meaning of symbols. For example in a programming language whose alphabet is built from letters, digits and special characters, the names of variables are constructed from letters and digits. Some character sequences denoting language instructions are reserved ("if"). The manner of joining symbols is specified (for example formula "if (a == b) a = 0;" is syntactically correct whereas formula "if a =b a =0" is not) and the meaning of sequences of symbols is defined (for example formula "a = 3" means assigning value of 3 to the variable "a").
There exists many (tens of thousands) programming languages. They may be classified using various criteria.
Undoubtedly the most important is logical structure of the language and the art of creating programs using it.
Imperative languages require a specification of sequence of steps that realize given task, whereas declarative languages describe relations between data in terms of function (functional languages) or rules (relational languages, logical programming languages), and result of execution of a program is obtained by means of applying to the specified relations special "built in language" algorithms. Object Oriented Programming consists in combining data and operations on these data, what gives an opportunity to create and use in programs new data types better reflecting domain of a given problem. Procedural programming (sometimes associated with imperative programming) separates data and functions, not supplying simple and adequate ways of reflecting domain of a problem in data structures it uses.
Examples of procedural languages are ALGOL, FORTRAN, PL/I, C. Object oriented languages are Smalltalk, Java, C++ and C#. The best known functional language is Haskell, and logical programming language is Prolog.
Other division concerns methods in which program's source code is transformed into CPU instructions.
Two classes can be differentiated here: compiled and interpreted languages.
A compiler translates program's source code into the CPU's instructions, checking its syntactic correctness and informing about errors. Thus, compilation consists in translation of languages and syntax verification.
In compiled languages program's text (the source code) is translated into binary (intermediate) code by a specific program called compiler. Another (in most cases) program, usually called linker generates from intermediate code binary executable of the program (which is ready to run) and stores it on the hard disk as an executable file (for example with "exe" extension or with executable attribute set). This is how "C" or "C++" languages work. In other cases compiler produces symbolic code, which is executed by means of interpretation by the program called interpreter. The Java language behaves like this.
An interpreter executes source code directly. Therefore syntactic verification takes place while program is running. Some interpreted languages compile to intermediate code allowing syntactic verification prior to running.
Source or intermediate code of interpreted languages is read and executed by a specific program called interpreter, which generates (on the fly) the CPU instructions corresponding to the instructions found in the source.
Examples of interpreted languages are: REXX, ObjectREXX, Perl, PHP.
To sum up: process of programming might be depicted using the following algorithm:
Summary
The lecture answers the following questions:
The above points define too the scope of knowledge and ability acquainted reading the lecture.
Exercises
Lecture 2
Дата добавления: 2015-11-16; просмотров: 79 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Programs and algorithms | | | Fundamentals of programming I |