Analysis of algorithms

It is possible to carry the following to the main methods of the description of algorithms:

• Verbal and formular (in a natural language);

• Structural or block and circuit;

• With use of special algorithmic languages;

• By means of graphs diagrams;

• By means of Petri nets.

Before compilation of programs verbal and formular and block and circuit methods more often are used. Sometimes before compilation of programs on low-level languages of programming such as Assembler language algorithm of the program write, using constructions of some high degreed programming language. It is convenient to use the program description of algorithms of functioning of difficult program systems. So, for the description of principles of functioning of OS the Algol-like high-level language of programming was used.

In case of a verbal and formular method the algorithm registers in the form of the text with formulas on the points defining sequence of actions. Let, for example, it is necessary to find value of the following expression: у=2а-(х+6).

The algorithm of the solution of this task can be written by a verbal and formular method in the following look:

1. To enter values a and x.

2. To add x and 6.

3. To multiplicate a on 2.

4. To subtract from 2а the sum(х+6).

5. To output y as result of expression evaluation.

The flowchart shall contain all ramifying, cycles and appeals to the subprograms, containing in the program.

Main computing algorithms: finite state machines, the Turing machines, it is easy also difficult solvable tasks.

The Turing machine (MT) – the abstract performer (the abstract computer). It was offered by Alan Turing in 1936 for formalization of concept of algorithm.

The Turing machine is extension of the finite state machine and, according to Church thesis – Turing, is capable to imitate all other performers (by means of the job of rules of transition), somehow implementing process of step by step computation in which each step of computation is rather elementary.

Turing machine device

The composition of the Turing machine includes the tape infinite in both sides (the Turing machines which have some infinite tapes are possible), partitioned into cells, and the control device, capable to be in one of a set of statuses. The number of possible statuses of the control device is finite and precisely set.

The control device can move to the left and to the right on a tape, to read and write in tape cells characters of some finite alphabet. The special empty character filling all cells of a tape, except those from them (finite number) on which input data are written is selected.

The control device works according to rules of transition which represent the algorithm implemented by this Turing machine. Each rule of transition orders to the machine, depending on a current status and the character watched in the current cell, to write in this cell the new character, to pass to a new status and to move on one cell to the left or to the right. Some statuses of the Turing machine can be marked as terminal, and transition to any of them means the operation end, an algorithm stop.

The Turing machine is called as determined if to each combination of a status and the tape character in the table there corresponds no more than one rule. If there is pair «the tape character – a status» for which there are 2 and more commands, such Turing machine is called as nondeterministic.

Turing machine description

The specific Turing machine is set by listing of set members of letters of the alphabet of A, a set of statuses of Q and rule set on which the machine works. They look like: q_ia_j→q_i1a_j1d_k ((if the head is in q_i status, and in a surveyed cell the letter q_i, s written, the head passes to a_j, status, in a cell instead of q_i1, in to a_j written a_j1, registers, the head does movement of d_k, which has three options: on a cell to the left (L), on a cell to the right (R) to remain on a place (N). For each possible configurations<q_i, a_j>available exactly one rule. Rules aren't present only for a final status, having got in which machine stops. Besides, it is necessary to specify finite and initial statuses, an initial configuration on a tape and layout of a head of the machine.

Date: 2015-12-24; view: 1732