|For errors we burn! -I said Alexa.
Incomprehensible algorithm -
This is very bad.
We are mistakes will win!
We have to do something here -
It is necessary to make the algorithm
Clear and intelligible
Visual inspection of Algorithms
When dealing with complex tasks like weather forecasting, command and control, management of large power stations or oil-chemical plant, it is necessary to create a large-scale algorithms, numbering hundreds of thousands and even millions of commands. Practice shows that the larger the algorithms, the more errors in them, the harder they are to find.Correcting errors in the huge and complex algorithms – a difficult and costly exercise, and the cost of failure is higher, the later it is detected.
The least damage to bring the errors that can be detected at once, to code generation and execution of programs on your computer – in the brain, or what is the same, the visual inspection. Checking the brain called, if the main work is done to find errors due to human intellectual efforts, and the computer plays an important though, but a supporting role. If such a test person scrutinizes computer drawings specifications and algorithms presented on paper or screen.
Brain scan, as well as any other activities necessary to properly design. The criterion of its effectiveness is the minimization of the average intellectual effort of the brain takes to identify mistakes. The neural structure of the brain is such that it can effectively carry out a visual inspection is not under any conditions, but only if verifiable figures possess high cognitive quality. To minimize the specific intellectual effort needed to significant cognitive characteristics drawings were well coordinated with the design characteristics of the brain. This means that the specifications and algorithms must be tailored for rapid and reliable verification, for easy and yet understood.
WHAT IS ERGONOMIC algorithm?
In this regard, it is useful to introduce the concept of ergonomic algorithm t. E. The algorithm satisfies the criteria ultrahigh understandability. The advantage of ergonomic algorithms that are much clearer, clearer, more clearly and effectively than usual. If the algorithm is not understood, it is difficult or even impossible to detect with bated error. Conversely, the clearer algorithm, the easier it is to find a defect. Therefore, a more intuitive, ergonomic algorithm is much better than usual.Better in the sense that it facilitates the identification of errors, and this is very important. The more bugs will be able to find a visual inspection, the greater the likelihood that the newly created algorithm is correct, error-free and reliable. In addition, the ergonomically convenient for the study of algorithms, it is easier to explain to another person.
In the previous chapter, we looked at several ways to improve the ergonomics of algorithms. In this chapter, continuing the theme, we try to answer the question: is it possible to improve the ergonomics of the algorithms using a formal method of equivalent transformations?
This will require a special conceptual apparatus, markedly different from the one usually used by programmers as traditional concepts are ill-suited to solve the problems of understanding and did not take into account the specificity of visual images.
What distinguishes the icon “Q” from the fork?
Fig. 1 (position I4) shows icon “issue.” It is so named because inside it write “yes-ations” issue, ie. E. A question that can be answered either “yes” or “no.” All other answers are not allowed. Here are examples of so-ations questions irons broke?Aunt came? Bob bought bread? Offender arrested? This pool of more than that? The temperature above zero?
Icon “issue” has one input and two outputs from the top: down and right. Yield left disabled and never used.
Fig. 2 (position 2) shows makroikona “fork in the road.” It contains the icon “issue”, a point and two shoulder fusion: the left and right (Fig. 14b). The left shoulder is a path from the lower exit icon-issue to the point of merger. The right shoulderbegins at the right exit icon-issue and ends at the confluence (Fig. 15). Thus, the shoulder is composed of the words “yes” or “no”, connecting lines, the point of merger, as well as icons. One of the two arms can be empty (not contain icons).
Forks are simple and complex. Simple fork contains only one icon-question. Examples of simple forks shown in Fig. 16. Fork is called complex if its shoulders there is at least one simple fork. Fig. 10a shows three sophisticated fork. For example, a fork in the road “Borsch delicious?” Complicated, since her left shoulder contains a simple fork “Borsch much too salty?”.Other examples of complex bifurcation shown in Fig. 17.
ROUTES AND ROUTES OF FORMULA
Fig. 18a shows a dragon diagram “Hunting a mammoth.” Replace the text inside icons letters. Instead, “The hunt for the mammoth,” write the letter A, instead of “Catch a mammoth” – the letter B, and so on. D. The result is a literal (literal) dragon diagram in Fig. 18b. Literal scheme is useful to describe the route.
Route – a graphical way from the beginning to the end of the algorithm, passing through icons and connecting lines. The route can be described by the formula, which is a sequence of letters denoting icons. All the icons, including the same, marked with different letters.
A linear (unbranched) algorithm has only one route and one formula. For example, the circuit of Fig. 18b described by the formula
|A B C D E|
Branched algorithm has a few (two or more) routes, and each route has its own, different from other formula (Fig. 19, 20).In the formulas, branched algorithms along with letters designating the icons used the word “yes” or “no” (separated by spaces).
What is castling?
Castling – the transformation algorithm, in which the left and right shoulder fork reversed. The simplest examples of castling shown in Fig. 8 and 21.
Two algorithms are called equivalently, if for each of the route of the first algorithm can find a pair of second route algorithm, and routes for each pair of the same formula. Referring to Fig. 22. It is easy to verify that the circuit in Fig. 22a and b have the same set of routes:
|A Yes B||And there is no|
Therefore, these dragon-circuit equivalent.
Formal transformation algorithm A1 A2 algorithm called tantamount if algorithms A1 and A2 are equivalent. This means that the reshuffle is tantamount transformation algorithms. When castling, the words “yes” and “no” must switch places.
FOR IMPROVEMENT Ergonomics
We have seen that a reshuffle of the algorithm in Fig. 8a afforded algorithm in Fig. 8b, which has a high ergonomic characteristics, as in Fig. 8b generally respected “the main route goes on a skewer.” This means that the equivalent transformation of “castling” in the example shown in Fig. 8 really improves the ergonomics of the algorithm.
Let us try to justify a similar finding for rice. 21 Consider the sequence of all the intermediate steps of reasoning.
In the first step hypothesize: to compare the two routes in Fig. 21a can use a sign “better-worse”.
In the second step we check the hypothesis by using reasoning: if pants fit – it’s okay if they have to tuck – it’s bad.Therefore, the use of the algorithm of feature “better-worse” legitimate.
The third step is mainly determined by the route that corresponds to sign an agreement on “good”. Consequently, the main route in Fig. 21a goes through the fork in his right shoulder, which corresponds to a good situation “pants fit – they do not have to tuck.”
The fourth step is to state that the main route in Fig. 21a goes on skewers. We conclude: the algorithm in Fig. 21a is a bad neergonomichnym, but it can be corrected by castling.
The fifth step perform castling and get more ergonomic algorithm in Fig. 21b. This procedure ends 1 .
Let us now consider a more complex algorithm in Fig. 10a. This algorithm is too bad, because it contains three bad (neergonomichnye) fork: 1) “menu is your favorite salad?” 2) “Borsch delicious?” 3) “Hot as a sole?”. By applying to a fork three operations “castling”, ergonomic get the algorithm in Fig. 10b.
Thus, based on the analysis of the examples we have seen: transformation equivalent to “reshuffle” improves ergonomics algorithms. However, this conclusion applies only to semantic algorithms (where you can specify the main route) and does not apply
a literal algorithms (where the concept of the main route becomes invalid). It follows that the application to the literal castling scheme in Fig. 22 is meaningless, since in this case does not affect the castling ergonomics.
Vertical and horizontal ASSOCIATION
It happens that in dragon patterns identical icons are repeated several times. For example, in Fig.23a icon “Give motorcycle repair and continue to be smarter,” occurs three times. This is bad: the obsessive repetition irritate the reader, who has to spend extra time and several times to read the same thing. Fortunately, you can eliminate some repetitions. Such a possibility appears if the same icons adjacent to each other, and their outputs are interconnected (Fig. 23a). In this case, the rule “reruns prohibited.” Elimination of repetitions performed by a vertical line (Fig. 23b) is called vertical union. It is easy to prove that the operation “vertical union” performs equivalent conversion algorithms.
The name “association” because many of the same icons are combined into one. The sequence of actions is as follows: first inputs of these icons are united by a vertical line, and then delete all the icons of the same, except for the extreme left.
Comparing the algorithms in Fig. 23a and b, it is easy to notice that the circuit in Fig. 23b has a higher ergonomics: it has become more compact, clear and understandable as free from mindless repetition icons. Hence the conclusion: the equivalent transformation of “vertical union” can improve the usability of algorithms.
Sometimes, to avoid repetition is not used vertical and horizontal line. The corresponding operation is called horizontal association. It is also equivalent to conversion.
Consider the example in Fig. 24a. First, using a combination of horizontal eliminate repetition icon “Eat porridge” and obtain the circuit in Fig. 24b. Then apply the vertical integration and prevent a repetition of the fork “There can be?”. The final result is shown in Fig. 24b. The scheme is more convenient and takes up less space than the original diagram in Fig.24a.
Disassembled example shows that the equivalent conversion “horizontal association” also improves ergonomics algorithms.
P p e d a s t e r e g n e: completing vertical and horizontal association, it is necessary to make sure that there were not crossing the trunk (Fig. 25).
ERGONOMICS literal Algorithms
Is it possible to improve the ergonomics of literal dragon circuits using equivalent conversions? We already know that the reshuffle is useless in this case. However, the vertical and horizontal association can significantly improve the ergonomics of literal schemes.
To see this, let us turn to Fig. 26 and 27. In fact, the circuit of Fig. 26a seems unnecessarily cumbersome: it contains seven verticals, thirteen icons and makes the reader six times read identifier in to make sure that the right six identical icons. A scheme is equivalent to it in Fig. 26b (obtained by combining the vertical) is free from this shortcoming. It is clear, simple and elegant, it contains only two vertical and eight icons, takes three times less space on a piece of paper (on the screen) and also has a total of two rectangular fracture lines (Fig. 26a – seven breaks). Thus literal diagram in Fig. 26b more ergonomic than its neighbor.
Even more cumbersome looks literal diagram in Fig. 27a, in which there are 14 verticals. A scheme is equivalent to it in Fig.27b (obtained by combining vertical and horizontal) wins again: to reduce the number of verticals almost five times (from 14 to 3) reducing the number of icons is more than three times (from 65 to 21), provides a more economical route topological ordering markedly reduces the total length of the connecting lines.
The analysis allows to conclude that in contrast to the castling, which is useful only for semantic dragon schemes, combining vertical and horizontal improve ergonomics is not only meaningful, but also literal algorithms.
WHAT TO DO IF ergonomic requirements
Contradict each other?
Until now, we have considered the simplest case, when various ergonomic requirements do not conflict. However, such conflicts are possible. Here are two ergonomic criteria that may conflict with each other:
- usually the main and side routes,
- minimize the number of verticals.
To eliminate the conflict should keep the principle: the rule route has a higher priority than the desire to reduce the number of verticals.
As an illustration, compare amounting circuit in Fig. 28. On the criterion “minimize the number of verticals” wins the scheme in Fig. 28a, having one less vertical. However, it violates the right route, and in two places. Firstly, the main route (when a person is healthy) is not aligned with the rotisserie. Secondly, the routes are not ordered from left to right, for the most severe disease (when a person is forced to go to the hospital) is in the middle vertically, and the left and right of it are more minor ailments. Thus, the diagram of Fig. 28a can not be considered ergonomic.
To correct the fault, you must:
- vertical separation at (this operation is the inverse of the vertical union);
- castling fork “sick?”;
- castling fork “The doctor helped?”.
As a result, we obtain the circuit in Fig. 28b, where all routes are ordered from left to right on the principle of “the right – the worse.” In fact, the left vertical means that things are going well, because a person is healthy; hence, the main route is on a skewer. The second vertical line indicates a slight indisposition, which can remove the tablet. The third vertical says health deteriorated need a doctor. Finally, the fourth (rightmost) vertical means that things are bad – I had to go to hospital.
As already mentioned, the circuit of Fig. 28b does not satisfy the ergonomic requirements to minimize the number of verticals. Nevertheless, we recognize its ergonomic, since higher priority is performed normally routes. This implies that (due to the presence of priorities) is a set of ergonomic requirements are interrelated and consistent.
ICON-BOX AS ergonomic RECEPTION
We already know that the language DRAGON prohibits the use of the intersection, cliffs and connectors. Hence the strict limitation: any dragon scheme should be placed entirely on a single sheet of paper. And if it gets too big and beyond the Procrustean bed? Then you can take larger paper such as A1. But if the scheme is huge and still does not fit? In this case there are special techniques to reduce the size of the dragon-circuit and cut it into pieces. These techniques make it possible to place the dragon diagram on the sheets of the desired size. Consider the problem on the “miniature” example.
Assume linear algorithm consists of fourteen icons, and the paper sheet is small, so that it can be placed vertically to ten icons. What to do?
Fig. 29 shows the two options to solve the problem. The algorithm in Fig. 29a is not necessary, since the operating point of the segment AB moves up, which is prohibited by the rules of the language of dragons. To overcome the difficulty in two ways: apply design “silhouette” (which was discussed in Ch. 6) or an algorithm to divide into two parts. Consider the latter method. To do this, remove some of the algorithm associated within the meaning of the icons, and instead draw the icon, the deputy called insert (Fig. 29b). Inserting need to be reminded of the seized icons. Inserting takes up little space – much less than thrown icons, so the algorithm becomes shorter. Of course, thrown icons do not disappear – they form a new algorithm – an algorithm insert.
Icon-insert – a team of “transfers control to the algorithm-box” (Fig. 30). Icon “end” of the algorithm inserts means: “Return to the main control algorithm.” This control is returned to a point located after the insert icon. In terms of programming algorithm insert – a procedure, and the icon insert – a statement “procedure call”.
WHAT IS SUBSTITUTION?
Operation “substitution” is associated with the icon insert. It is performed in three steps.
Step 1. From the dragon scheme is removed fragment having one input and one output.
Step 2. Instead, the substituted icon insert the name H.
Step 3. To erase a part of the icon is added to the header of the same name and an icon of the X-end; The result is an algorithm insert.
Two of the algorithm in Fig. 29 neravnosilny: they are not the same formula as the route in Fig. 29a contains 14 icons, and Fig. 29b – 17 icons (see. Also Fig. 30). However, we can easily see that the substitution – equivalent transformation algorithms as the original and converted algorithms produce the same results for the same input data. Incidentally, equivalent algorithms always equivalent (converse is not true). Thus, the operation of “substitution” is equivalent (but equivalent) conversion algorithms.
Improved ergonomic Algorithms
With a chain of equivalent transformations
When you draw an algorithm should strive to from the very beginning it has been to satisfy the rules and ergonomic. And if that does not happen? If the worst-first, as shown in Fig. 31a? In this case, the algorithm should be brought to mind by a series of equivalent transformations. Generally speaking, in the example of Fig. 31a is enough to make just two castling (converting both fork) and we’ll get the right answer – the required ergonomic diagram in Fig. 31d.
However, to make the presentation clearer, the better to take a different path and move toward the goal in small steps. To start using the visual formula in Fig. 32 and use it to replace the lower fork in Fig. 31a on the icon insert “Bring the room in order.” The result of the substitution is shown in Fig. 31b. Then perform castling and obtain the circuit in Fig. 31B. After that we carry back substitution using the formula in Fig. 32 and replace the insert icon to the fork “Inkwell broken?” The scheme is shown in Fig. 31g. Finally, we do another castling and arrive at the desired ergonomic diagram in Fig. 31d.
For the convenience of the reader in Fig. 33 gives a general summary of the equivalent transformations.
- The concept of the ergonomic algorithm is very important. Application of ergonomics to the theory of algorithms can significantly improve the comprehensibility of algorithms and programs.
- The concept of the ergonomic algorithm is defined by a finite set of well-defined rules and signs, such as “the main route to go on a skewer” and so on. D. Consequently, this concept is strict.
- The above four equivalent conversion algorithms confirms that ergonomics algorithms can be improved with simple and clear methods which in some ways can be considered formal.