entranceFormal executors are predominantly. "Informatics"
Mathematical foundations of computer science
A.G. Gein
Academic plan
| #_NEWSPAPERS | Lecture |
Lecture 1What is the “mathematical foundations of computer science”. Why is computer science often considered a close family? Information and its coding. Mathematics of codes. Error-correcting codes. Economical coding. |
|
| Lecture 2.Mathematical models of formal executors. What is formal information processing? End- nye machines. What comes first: the language or the performer? Grammar of the language. Recognized languages. Universal performers bodies (Turing machine, Post machine). |
|
| Lecture 3.Algorithm and its properties. Algorithmic undecidability. Computability. Complexity. | |
| Control work number 1. | |
| Lecture 4 Counts. Graphs and digraphs. In what tasks do they arise? Various properties of graphs (Eulerian, Hamiltonian news, planarity, bipartite). Networks. flows in networks. Representation of graphs. Basic algorithms on graphs. |
|
| Lecture 5. Logical models in computer science. Algebra of statements. Boolean functions. normal forms. Full boolean function classes. Relay-contact circuits. Valves. Mathematical models of the processor and computer memory. predicates and relations. Relational algebra. Theoretical basis relational DBMS. Logic programming languages and their mathematical basis. |
|
| Control work number 2. | |
| Lecture 6. Computer number theory and computational geometry. Why do we need number theory in computers sciences? Race for prime numbers. How to factorize a number? What is the difference between theoretical geometry and computing? Why is smooth on paper, but clumsy on the computer? Basic rules and algorithms of computing geometry. |
|
| 23/2007 | Lecture 7. Data protection. Symbol information protection. What needs to be protected? Electronic signature. Systems verification. Cryptosystems with a public key. Protection graphic information. Mathematics of electronic watermarks. |
| 24/2007 | Lecture 8. Fundamentals of teaching methods of mathematical foundations of informatics. |
| Final work |
Lecture 2
Mathematical models of formal executors
"Elegance is chilly in this vain light." Such a phrase was composed by a computer using one of the first programs for generating texts in natural languages. But the emotion conveyed by this phrase is, of course, inaccessible to a computer. And the computer cannot understand the meaning of this phrase. Because he is just a formal performer.
In our public mind, the word “formal” usually has a negative connotation. With the contemptuous stigma "formalist" we reward an official who acts solely on the basis of the instructions given to him, not wanting to delve into the essence of the problem put before him.
But is it always bad to be a formal performer? Will the owner of the shepherd be happy when, at the command “Face!” his four-legged friend will think about whether to mess with the bandit. Or when the plane, in response to the movement by the pilot of the helm, continues to fly on the same course, because you don’t want to make a U-turn. And the operator of a nuclear reactor, having abandoned the instructions, will control it on a whim. Agree that even a person sometimes needs to be a formal performer. As for devices for automatic information processing, an informal path is simply impossible for them. Recall that, as noted in Lecture 1, informatics deals with the study of precisely the processes automated processing information.
Processing (transformation) of information is a fairly widely understood information process. Information processing is understood as obtaining new information from existing information or transforming the form of information presentation.
The detective collected evidence and pointed out who committed the crime. The mathematician compared the statements known to him and proved a new theorem. DI. Mendeleev, based on information about the chemical properties of elements, formulated the periodic law. In all these examples, new information has emerged as a result of information processing.
The calculation of the sum of two numbers should also be recognized as information processing - after all, from two known data, a new, previously unknown one is obtained. The processing of information is, for example, the translation of a sentence from Russian into a foreign language.
At first glance, between the information processing processes indicated in the two previous paragraphs, a big difference. The main difference here is that in order to search for a criminal or prove a new theorem, there are no and cannot be specified strict rules on how the initial information should be processed. As they say, a person in these cases acts heuristically. Adding two numbers, we are already guided by rigidly specified rules. Such work can be entrusted to a technical device that is able to understand and execute the instructions prescribed to it. Devices that are controlled by instructions and perform their work automatically are called programmable and are said to perform their work formally.
In particular, we can talk about the formal processing of information. The performer performing such processing should not delve into the meaning of the actions performed by him; therefore, the formal processing of information, as a rule, concerns changing the form of its presentation, and not the content.
So, it is convenient to understand information processing as any transformation of its content or presentation form.
However, whatever the way of processing information - formal or heuristic, there is something or someone that performs this processing. He is usually called performer.
Formal executors can be arranged in quite different ways. To study them, as in any science, modeling is used. What mathematical models are used to study formal executors, we will tell in this lecture.
§ 3. Formal performer: automaton
Man has been very successful in creating a variety of devices that perform a particular job in accordance with clear instructions. At the same time, he is no longer required to constantly be near this device in order to control it. In this case, the device is said to do the work automatically, and the device itself is called automatically.
In reality, the machines are very different. This may be a vending machine for tickets for commuter trains, or a machine for packaging finished products, or a machine for manufacturing any parts. Automata of the latter type are often called industrial robots.
From the point of view of computer science, it does not matter what the machine is made of. The only important thing is that it perceives some signals as commands and performs some action on each command, passing from one state to another. Therefore, we can assume that each automaton is described by a set of possible states, a list of valid commands, and an enumeration of the state from which the automaton passes under the influence of each command. For example, if there are only two commands, then they can be denoted by letters, say, a and b, or numbers, the states of the automaton - letters q 1, q 2, ..., qm, and you can list the options for transition from one state to another using the table (see Table 1).
Table 1
The cell located at the intersection of a row and a column indicates the state into which the automaton passes, which was in the state indicated in the heading of the same column and received the command indicated in the heading of the same line. It is clear to everyone that such a table is an information model of a real automaton.
The automaton can also be described by another information model - a digraph*. The vertices of the digraph are the states of the automaton, the arcs are the transitions from one state to another. On each arc there is a mark showing which command the transition is carried out on. Then the automaton described in Table. 2 will be displayed as shown in rice. 1.
table 2
One of the states is called the initial state - it is in it that the automaton is located before the start of work. Let us agree to always denote the initial state q 1. Some of the states are final - bringing the automaton to this state is the goal of controlling the automaton using one or another sequence of commands. For example, if this is a railroad ticket vending machine, then in the initial state the machine waits for coins to start flowing into the coin acceptor. There are two final states: issuance of a ticket and a refund. In addition, there are intermediate states - the calculation of the amount of money transferred to the machine by this moment. The commands that change the machine from one state to another are dropping a coin into the coin acceptor, pressing the ticket issue button, or pressing the money back button. The fact that this state is final will be denoted by the letter K in parentheses near the designation of this state. For instance, q 2(K).
It is clear that the goal of controlling the automaton is to issue to it such a sequence of commands that transfers it from the initial state to some final one. Since each command is denoted by a letter, the set of commands understood by this automaton can be considered as some alphabet A. Then the sequence of commands, i.e. program, will be written as a word in this alphabet. For example, the word aba translates the automaton described in Table. 2, out initial stateq 1 per state q 4 . It can be said that the word aba defines on the digraph of this automaton some route from the state q 1 per state q 4 .
The set of all those words that transfer the automaton from the initial state to one of the final states forms a certain formal language. This language is called language recognized by the machine. If for some language there is at least one automaton that this language recognizes, then such a language is called recognizable.
On the rice. 2 shows an automaton that has two states - q 1 (K) and q 2 - and understands two commands, which are indicated by the numbers 0 and 1. It is easy to figure out that the language recognized by this automaton consists of those and only those words that contain an even number of ones and any number of zeros. In other words, this automaton calculates the sum of the digits in the number written in binary system reckoning.
Suppose now we have a fixed alphabet A, and L- some set of words, composed of symbols of the given alphabet. Is it always possible to construct an automaton such that the set L was a recognizable language for him? The answer is no.
Theorem. Let A = {a, b}, L = {a n b n, where n runs through the set of all natural numbers). A bunch of L is not a recognized language.
Recording a n, appearing in the formulation of this theorem, means that the letter a repeated n once.
The proof of the theorem uses one of the most important mathematical methods - by contradiction. So let's assume that L- recognized language. This means that there exists an automaton that is translated into some final state by any word of this language. Let this machine have k states. Consider the word a k b k. It belongs to the language L and, consequently, transfers this automaton from the initial state q 1 to some final state q s . Since the letter a repeats at least as many times as the number of states of the automaton, there is such a state q t , which for the first k letter applications a will be run twice (cf. rice. 3). Let the automaton go to the state for the first time q t as a result of applying a u, and the next time it will be in the same state after applying a u + v. Consider the word a k + v b k. It is clear that the application of this word to the initial state q 1 will bring it to the same final state q s . This means that the given word is also recognizable by the given automaton and, therefore, must belong to the language L. But in many L there is no such word. The resulting contradiction shows that the assumption made is false, i.e. machine for which given set would serve as a recognizable language does not exist.
Rice. 3. Route on the Automaton Digraph from the Initial State q 1 to final state q s (up to the state q t letter a standing on arches u times, on a cycle - more v once)
Since not every set of words is a recognizable language, the question arises which sets are suitable for this. Mathematicians have found convenient ways descriptions of recognizable languages, and these methods formed the basis for the construction of all currently existing programming languages.
Questions and tasks
1. What two information models can represent an automaton?
2. What is the language recognized by this machine?
3. What language is called recognizable?
4. For the machine shown in rice. 1, determine what state it will be in after executing a sequence of commands
a) abba; v) babaabaaa;
b) ababbabbb; G)* a n b n.
5. For the machine shown in rice. 2, make a description in the form of a table.
6. Graph information model the automaton specified in Table. 3.
Table 3
7. What language over the two-character alphabet (0, 1) is recognized by the automaton shown in rice. 4?
Rice. 4
8. What language is over the two-character alphabet ( a, b) is recognized by the automaton given in Table. 3?
9. Graph the information model of an automaton that would recognize a language over the alphabet (0, 1) consisting of all words containing exactly 5 consecutive ones.
10. Graph the information model of an automaton that would recognize a language over the alphabet (0, 1) consisting of all words containing exactly 5 ones.
11. Graph the information model of an automaton that would recognize a language over the alphabet (0, 1) consisting of all words starting with one (i.e., this automaton distinguishes natural numbers written in binary from arbitrary sequences characters 0 and 1).
12. Among the languages listed below L 1 , L 2 , L 3 , L 4 , defined over the two-character alphabet (1; 2), indicate the recognizable ones. For each of the recognizable languages, construct an automaton that recognizes it; for each of the unrecognizable languages, prove that it is unrecognizable.
a) L 1 consists of all words that are even natural numbers starting with the digit 1;
b) L 2 consists of all words in which the number of ones is a natural number ending in 3;
v) L 3 consists of all words in which the number of twos is a prime number;
G) L 4 consists of all words that are natural numbers divisible by 3.
13. What is the difference between “life according to laws” and “life according to concepts” from the point of view of computer science?
§ 4. Universal performer
Computer games... Probably, everyone who has ever dealt with a computer has seen, and perhaps even played, some kind of computer game. On the screen, some objects in the form of living beings or technical devices obey the commands of the player, others are controlled by a computer that executes given program. All these objects are formal executors, each with its own set of valid actions. Only these objects are not real, but simulated by a computer. It turns out that with the help of one formal performer others are imitated.
If we try to formulate what it means that one performer is imitated with the help of another, we get the following. They say that the formal performer A imitates a formal performer V, if
Each object on which the performer performs actions V, uniquely corresponds to the object on which the performer performs actions A(imitation of the performer's environment);
To each allowable action of the performer V over one or another object of the environment, the permissible action of the performer is uniquely associated A over the corresponding object of its environment (imitation of actions);
Each instruction written for the performer V and leading during its execution to a certain result (i.e. to a certain state of the environment of the performer and himself), can be transformed by imitation of valid actions into an instruction for the performer A, the execution of which leads to the corresponding result in the environment of the executor A.
However, the assumption that the performers A and V the different environment in which they exist is not important from an informational point of view. For example, performer A deals with numbers and V transforms graphic images. But you already know that in fact, in each of these cases, it is a matter of transforming suitably encoded information. Moreover, it can be considered that the same binary code is used. In this sense, it can be considered that the environment of the performer is simply the same - information presented in the form of an encoded message.
One of the most important questions of theoretical computer science is: is there such a formal executor that can be used to imitate any formal executor? It is natural to call such a performer universal. It is easy to understand that, as a physical device, a universal executor does not exist - after all, information can be encoded with arbitrarily long messages, and any physical carrier is finite. If we talk about the universal performer as an ideal object, then it turns out that the answer to the question asked is positive. And it was obtained almost simultaneously and independently by two outstanding scientists - A. Turing (in 1936) and E. Post (in 1937). The performers they proposed differed from each other, but it turned out that they could imitate each other, and most importantly, imitate any formal performer in general.
A universal performer is usually called a machine. It is also customary to give machines the names of their inventors. So the universal performer, invented by A. Turing, is called the Turing machine; performer described by E. Post - Post's machine. Later, other universal performers appeared, for example, Minsky's machine.
So, we can assume that we have a message written in some alphabet, and it needs to be converted into another message. Of course, writing instructions to a formal executor for processing a specific pair of messages is a simple matter. But you already know that instructions (i.e. algorithms) that allow solving a whole class of tasks of the same type are of real interest - the so-called “algorithm mass property”. For example, such a task: to add one more predetermined symbol to the right of any message. If, say, a sequence of identical characters acts as a code for a natural number - the number of characters in the sequence is the encoded natural number - then in fact we are talking about creating an algorithm for increasing the number by 1.
It is natural to assume that the message is recorded on tape. Moreover, it is convenient to imagine this tape divided into identical cells, and each cell contains exactly one message symbol. Since the messages can be arbitrarily long, we will agree to imagine the tape as endless. Empty cells will be considered filled with the “space” symbol. Thus, we declared that any alphabet that we will use to record messages on this tape necessarily contains a “space”. Let's agree to label it a 0 . The remaining characters of the alphabet used to record messages on the tape will be denoted a 1 , a 2 , ..., a n. If, for example, we need to write down the problem of calculating the sum of two numbers, then the alphabet can be taken as follows: a 0; one; 2; 3; 4; 5; 6; 7; eight; 9; 0; ,; +; =. For a particular pair of data (i.e. two numbers), the tape record might look, for example, as shown in rice. 5.
Rice. 5
Of course, we will not write the symbol on the tape in empty cells a 0, meaning it's there. In addition, we agree that the first character of the message, other than a space, always stands in the same cell - on rice. 4 it is marked with Ї. We will call this cell initial.
The message written to the tape is processed by some device, and the result is again written to the tape. Since the performer is formal, he does not delve into the meaning of the message, but according to the instructions drawn up for him, he replaces one character with another. We are not interested in how such a replacement is physically carried out, so we can imagine that a certain automaton moves along the tape, which reads a character from a cell on the tape, processes the information received, prints another character in the cell (if it is prescribed by the instruction) and shifts to the neighboring cell - right or left.
You already know that each automaton is described by a set of states. It is customary to designate the states of the indicated reading and printing machine with letters q 0 , q 1 , q 2 , ..., q m . At the same time, we agree that when the machine is turned on, i.e. at the beginning of the work, it is always in the same state, which we will denote q 0 , and is located opposite the initial cell.
Thus, a Turing machine is formally described by a set of two alphabets: A = {a 1 , a 2 , ..., a) and Q = {q 0 , q 1 , q 2 , ..., q m ). Alphabet A called external and serves to record the original messages, the alphabet Q called internal and describes the set of states of the reader-printer. We will depict the Turing machine as shown in rice. 6.
Rice. 6
On the rice. 6 shows the moment of operation of the Turing machine, when the reader-printer scans the third cell from the initial one (by this moment it contained the symbol a s 3) and is in a state q k.
So, the valid actions of the Turing machine are as follows:
Write any character of the external alphabet to the tape section (the character that was there before is overwritten);
Move to the next section;
Change the state to one of those indicated by the symbol of the internal alphabet;
Stop working (stop).
Of course, in this enumeration, each line contains not one action, but a group of actions of the same type - there are as many “write a character of the external alphabet” actions as there are these characters, you can move to the next section to the right or to the left, there are as many actions to change the state as of these states (i.e. how many characters of the internal alphabet).
Now we need to say how commands are written to perform the specified actions. Each command of the machine contains at most one action from each group of actions and has the form
The commands actually look like this:
a i q j - write to the monitored section a i , move to the right (to the next section) and go to the state q j;
a i q j - write to the monitored section a i , move to the left and go to the state q j;
a i S q j - write to the monitored section ai, stop and go to the state q j .
To carry out actions, the Turing machine has an operational-logical block. This block has two inputs: through one of them information is received about which character is in the cell being monitored, through the other - information about the state of the machine at a given step of its work. This information uniquely determines which command the machine should execute. Since a command can contain an instruction to perform three actions - writing a character to tape, shifting, and changing state - the operational-logic block has three outputs: writing a character A, offset M and state change Q(cm. rice. 7).
Rice. 7. Operational-logical block of the Turing machine
Since this block has only two inputs, it is convenient to represent its response to the symbols fed to them in the form of a rectangular table in which rows and columns are marked with symbols of the external and internal alphabets, respectively (see Table 4). Commands are written in the cells of the table. If the car is opposite the cage where it is written a i, while its state is qj, then the command is executed at the intersection of the line marked with the symbol ai, and the column marked with qj.
Table 4
This table is called functional diagram this machine; it plays the role of instructions (programs) for the Turing machine. From it, in particular, it is clear what are the external and internal alphabets of the machine.
Let, for example, a sequence of a certain number of the same character “*” be written on a tape. Then the functional diagram given in Table. 5 causes the Turing machine to increment the number of stars in that sequence.
Table 5
It is impossible to prove that a Turing machine is a universal executor. Just as, for example, it is impossible to prove the law of conservation of energy in physics. But the practice of compiling algorithms shows that any problem that a person can solve today can be programmed on a Turing machine. This experimental fact, called the Turing thesis, is formulated as follows: for a problem there is a solution algorithm if and only if there is a suitable Turing machine by which this problem can be solved.
Questions and tasks
1. What formal performer is called universal?
2. What is a Turing machine?
3. How is one Turing machine different from another?
4. What is called the functional diagram of a Turing machine?
5. Is it true that a Turing machine with a functional diagram written for it is a finite automaton?
6. Depict in the form of a sequence of drawings how the information on the tape changes during the operation of the Turing machine, described by the functional diagram in Table. 5.
7. Following the functional diagram described in Table. 5, Turing machine attributes to given sequence asterisks one more asterisk on the left. Make a functional diagram, according to which the asterisk will be assigned to the right of the given sequence.
8. The operation of the Turing machine is described by the following functional diagram:
Determine what message will be on the tape after the end of the machine, and indicate in front of which cell at that moment its writing block will be located.
Rice. eight
Rice. 9
9. On the tape of a Turing machine there is a string consisting of several consecutive “*” characters, followed by several “#” characters, and at the end of the line there is an “e” character (one of options such a line is given in rice. 5).
Rice. 10
For each of the following functional diagrams, determine what task it is intended to solve. (Hint: to get a convincing answer, apply the function diagram to the various options for filling the information feed with sequences of characters from the external alphabet.)
10. Let the outer alphabet consist of the symbol “ a 0” and the digits 0, 1, 2, ..., 9. A natural number is written on the tape. Come up with a Turing machine and make a functional diagram for it, according to which the given number will be increased by 1.
11. Let the outer alphabet consist of the symbol “ a 0” and the digits 0, 1, 2, ..., 9. A natural number is written on the tape. Draw a functional diagram for a Turing machine that will write the sum of the digits of this number on a tape. The answer must be written to the right of the original number, separated from it by a space.
Rice. 11
P.S. Feeling like a Turing machine is useful, but tiring. We recommend tasks 8 and 9 to be done manually. As for tasks 10 and 11, manual testing of the functional diagrams you have drawn up may not be effective. In this regard, we propose to use the computer implementation of the Turing machine, created by R. Zartdinov. It can be obtained on the website of the newspaper "Informatika" ( inf.1september.ru). Here is how, for example, the functional diagram from task 8 c) looks like on this machine - the differences are that instead of the letter S, a road sign is shown, and instead of the symbol “ a 0 ” is written “_” (when entering a command in a cell of the table, however, you need to press the “space” key, and not “_”). The program is provided with detailed help on how to work with it. The interface of this program is very simple. In addition, you can find a description of this implementation of the Turing machine in the newspaper Informatika No. 8, 2006. There you will also find an analysis of several more problems for programming the Turing machine; you just need to keep in mind that they use a slightly different (which is completely unprincipled) command system.
* Recall that a graph is a collection of points called peaks, and lines connecting some of the vertices. If a direction is indicated on the lines connecting the vertices, then the graph is called oriented(abbreviated digraph), and the lines are called it arcs. In an ordinary graph, i.e. undirected, the lines connecting the vertices are called ribs. More about graphs will be discussed in lecture 4.
Main question: ?
Guiding questions:
§ What are the performers?
§ What characterizes the performer?
§ How to make the performer understand and execute the algorithm?
Research objectives:
§ Find examples of different performers.
§ Determine how performers differ.
§ Find out what characterizes the performers.
§ Investigate why performers cannot always execute the algorithm.
§ Give examples of algorithms and identify the performer in them.
Examples of performers
A new wardrobe was brought into the house... That is, there is no wardrobe as such yet, doors, shelves, screws and other details of the future container of clothes and linen are laid out on the floor. Father and I, following detailed instructions Let's start assembling. Here the instruction acts as an algorithm, and my father and I act as its executor.
In mathematics lessons, we perform various calculations - we multiply and divide by a column, we add simple fractions. In these cases, we are the executors of the corresponding algorithms.
But the performer can be not only a person. A variety of devices, including a computer, can also execute the algorithms specified by them. For example, Lunokhod, a self-propelled automatic vehicle delivered to the Moon in 1970, performed the most complex algorithms, moving along the lunar surface and collecting the information people needed. Industrial robots replace people in production; in everyday life, housewives also come to the aid of devices that can act according to specified algorithms.
Fairy tale performers
Performers are often found in fairy tales. In one of them, Ivan Tsarevich says to the Hut-on-Kuryih-Legs: “Hut, hut! Get up to the forest with your back, to me in front! In this case, the command must be given very precisely so that the performer understands it. In the fairy tale "Ali Baba and the Forty Thieves", the magic door was opened by the command "Sesame, open!". Greedy Kasim, who secretly entered the cave, forgot this phrase and could not leave the cave.
Both the Cabin-On-Chicken-Legs and the magic door have much in common: they are able to understand and execute some precisely given commands, that is, they are performers.
Who is a performer?
An algorithm executor is a living being or a technical object capable of performing the actions prescribed by the algorithm.
Performers can be:
§ machines: machine tools, robots, Appliances(washing machine, tape recorder, player, etc.), computers;
§ plants: sunflower (unfolds in the sun), water lilies (close at night);
§ animals: trained dog (nurse, search, hunting), cat;
§ people: student, worker, soldier, teacher, ...
Are all performers the same?
Animals and humans as performers differ from all other performers in three main ways:
§ They understand commands in various ways (eg "Sit down!", "Sit down!", "Sit down!").
§ They may refuse to execute a command if they do not like it ("Eat semolina!", "Shoot at the window with a slingshot!", "Give me a bone!"). That is, a person, and to a certain extent an animal, have a will and are responsible for their actions.
§ They may different time perform the same commands in different ways (for example, you can wash the floor with your hands, or you can use a mop).
There are two kinds of performers!
Now let's think about this question: since performers differ in some of their characteristics, does it mean that they should not be divided into two classes? Then it is not difficult to guess that animals and humans will fall into one class, and all other performers into another. It remains to determine how to name these classes and determine what properties the performer must have in order to get into one or another group.
Formal and informal
To do this, let's recall one of the properties of the algorithm, namely formality, which means that the performer may not understand the meaning of the algorithm, but still execute it correctly ... Can a person or an animal always do this? Probably not, therefore, it cannot be said that they execute the algorithm formally, so we will assume that a person and an animal are informal performers.
So, while executing the algorithm, the performer may not delve into the meaning of what he is doing and still get the desired result. In such cases, they say that the performer acts formally, that is, he is distracted from the content of the task and only performs all actions in a strict sequence. This is a formal performer.
If the performer makes some changes to the algorithm (changes the sequence of steps; skips some, considering them unnecessary or insignificant), then they say that such a performer is not formal.
Artist characteristics
The performer, like any object, has its own characteristics.
The performer is characterized by:
§ SKI (executor's command system) - a set of commands that the performer understands and can execute.
Each executor can execute commands only from some strictly specified list.
§ Environment - the conditions in which the performer can execute commands. The performer's environment can also be called his "Habitat".
§ And disclaimers:
1. "I do not understand" - this command is not in the list of commands of the performer, and he did not understand it. Probably, we made a mistake in writing the text of the command, the command is not included in the SKI.
2. "Can't" - the executor understood the command, but cannot execute it. For example, the command “forward” is given to the robot, and there is a wall in front and it cannot go. Or the dog was commanded to “Sit!”, and she is already sitting.
How can the performer execute the algorithm?
The performer will be able to execute the algorithm if it is known to him, if the algorithm was told to him. Language is the most important way for people to communicate. Getting into a foreign country and not knowing the national language, a person is completely helpless. Sign language, facial expressions, writing with pictures (pictographic writing) can come to the rescue, but all this only partially improves the situation.
Natural language (Russian, English, French, ...) is the basis for the full communication of people.
Natural languages are figurative and polysemantic. If you look into the explanatory dictionary of the Russian language, you can find out, for example, that there are more than 20 meanings for the word "go". Here are just a few examples: A person is walking along a road; it's raining; time is running; this dress suits her; mushrooms will go later, in September; Let's go fishing tomorrow, shall we? - goes!
In natural language, completely different concepts can be denoted by the same word. As a rule, a person from the general meaning of the text, sometimes without even thinking, from the whole set of meanings of the word, selects exactly the one that the sender of the message had in mind. But imagine yourself in the place of a formal performer who does not delve into the meaning of the entire message. In this case, how will you understand the phrases: sour mine; early escape; ate everywhere; familiar environment?
To make sure that the language of a formal performer cannot be ambiguous, we tried using a formal translator to translate from English a text that tells about ... Try to guess what it is about.
Wood deals today - it's die-cut from pine plywood, then dipped in liquid chemicals that produce an easily ignited, extinguishable board.
And it was about a simple wooden match, but how was it possible to explain to the translator that from all the meanings of the word "match" it was necessary to choose not "deal", but "match", from the meanings of the word "tip" - "tip", and not "advice" that "die" means not only "die", but also "stamp", not to mention the complexities of grammatical constructions?
What is a program?
For a formal performer, the language of communication cannot be ambiguous; for such performers, special artificial languages are developed and used, where individual words and the expressions are not open to different interpretations.
The algorithm described in the language of the performer is called a program.
To learn how to write programs in a particular language, you need to study the alphabet, vocabulary and grammatical rules by which sentences are built in this language, while no deviations from the rules for writing words and sentences are allowed, otherwise the performer will simply refuse to follow your instructions and will not be perplexed and worry about mistakes, as Mishka's friend does from A. Shibaev's poem:
A letter came to me
I look -
From the camp from Mishka ...
Here is a wonderful bow and I'm licking
- Written in a letter.
Onion lick? What are miracles?
Probably joking rogue ...
Reading further:
Here is a fox, a beautiful long rod ...
The other day in the forest I found sadness
and was very happy...
No, no, he's not joking! I'm afraid,
My friend is seriously ill.
Will return - it is necessary to heal:
Make the rules teach...
§ There are two types of performers: formal and non-formal.
§ The executor is characterized by a system of commands, environment and failures.
§ In order for the performer to understand us, it is necessary to write an algorithm in the language of the performer, that is, write a program.
| Lesson planning and lesson materials | 6 classes | Lesson planning for the academic year (FSES) | Artists around us
Lesson 24
Artists around us
Work in the environment of the executor Grasshopper
Formal performers
Formal performers
There are two types of performers: formal and informal. A formal executor always executes the same command in the same way. An informal executor can execute a command in different ways.
For example, when you repeatedly listen to a disc with your favorite music, you can be sure that it is played by the player (formal artist) in the same way. But it is unlikely that any of the singers (an informal performer) will be able to perform a song from their repertoire in exactly the same way several times.
As a rule, a person acts as an informal performer. Formal executors are mainly technical devices. A person in the role of an informal performer is responsible for his own actions. The object controlling it is responsible for the actions of a formal executor.
Let us consider in more detail the set of formal executors. Formal executors are extremely diverse, but for each of them it is possible to specify the range of tasks to be solved, the environment, the system of commands, the system of failures, and the modes of operation.
1. Range of tasks to be solved. Each executor is created to solve a certain class of tasks.
2. Executor environment. The area, environment, conditions in which the performer operates are usually called the environment of this performer.
3. Executor command system. The instruction to perform a separate completed action of the performer is called a command. The set of all commands that can be executed by some performer forms the SCI - the system of commands of the performer.
4. Executor failure system. The “I don’t understand” refusal occurs when the performer is given a command that is not included in his SKI. Refusal "I can not" occurs when the command from the SCI cannot be executed by him in specific environmental conditions.
5. Performer operating modes. For most performers, direct and program control modes are provided. In the first case, the executor waits for commands from the control object and immediately executes each incoming command. In the second case, the executor is first given a complete sequence of commands (program), and then he executes all these commands in automatic mode. A number of performers work only in one of these modes.
The performer is a person, a group of people, an animal or technical device, capable of executing a specific set of commands. Examples: Object is an executor!! Power on / off button on the computer case Skip to the beginning Pause Stop Skip to the end Playback Command system of the performer - CD player
More complex performer. Works on programs created by man. Programs are chosen by the person. The machine works automatically. More complex performer. Works on programs created by man. Programs are chosen by the person. The machine works automatically. Performer - washing machine
Informal and formal executors The role of an informal executor is most often played by a person The role of a formal executor is most often played by a technical device Informal executor is responsible for his own actions The object controlling him is responsible for the actions of a formal executor
Formal Executor A formal executor always executes the same command in the same way. Automatic filling and packing machine For each formal executor, you can specify: range of tasks to be solved; environment; command system; failure system; operating modes.
System of executor's failures Failure "I do not understand" occurs if a command is given that is not included in the SKI. Failure "I can not" occurs if the command from the SKI cannot be executed in specific environmental conditions. ? Washing machine cannot execute the rinse command if there is no water connected to the machine. ?
Automation is the replacement of part of human labor by the work of a machine: the process of solving a problem is presented as a sequence of simple operations; a machine is created that can perform these operations in a given sequence; the execution of the algorithm is entrusted to an automatic device; a person is freed from routine activities. Automation
Most importantly, an Executor is a person, a group of people, an animal or a technical device capable of carrying out given commands. A formal executor always executes the same command in the same way. For each formal executor, you can specify: - the range of tasks to be solved; -environment; - a system of commands; – a system of failures; - modes of operation.
Algorithm implementers. Formal execution of the algorithm. Computer as a formal executor of algorithms (programs).
Lesson type: combined.
Lesson Objectives:
Introduce the concept of "executor object";
Introduce students to the third stage of algorithm development;
Introduce the concept of "Program";
Familiarize yourself with the rules for designing and calling the program;
Learn how to solve problems for programming with a linear algorithm.
Lesson objectives:
cognitive :
To organize the work of students in the study and primary consolidation of knowledge bycollective and independent practical activity.
Developing:
Using an integrated approach, show students the meaning that the concept of "performing object" has in nature, everyday life, technology and everyday life.
To ensure the development of schoolchildren's skills that contribute to the development of memory, logical thinking and the application of existing knowledge and skills in the preparation of programs in a programming language.
Educational:
Formation information culture, skills and abilities of collective and independent mastery of knowledge;
To cultivate a culture of speech when answering at the blackboard, respect for all participants in the educational process.
During the classes
Organizational stage
Mutual greetings of the teacher and students; fixing absent; checking the external condition of the classroom; checking the preparedness of students for the lesson; organization of attention and internal readiness.
Announcement of the topic and objectives of the lesson. Repetition of material
Today in the lesson we will continue to study the technology of solving problems using a computer. We have already got acquainted with the concept of an algorithm and its properties. And before proceeding to the study of new material, we will check your readiness for the lesson.
Front poll:
List the stages of solving a problem using a PC (problem statement, defining conditions, building a problem model, describing an algorithm for solving a problem, choosing an optimal environment for solving, describing an algorithm using selected software tools, testing the solution of the problem, if necessary - correction of the solution of the problem)
List the main properties of the algorithm (discreteness, accuracy, understandability, mass character, effectiveness)
List the main forms of representation of algorithms (verbal, graphic, program, tabular)
Explanation of the new material:
Algorithms for solving various problems must be feasible in the environment where you need to get the result. In this environment, there must be an object that will execute the algorithm. Consider an example. Petya wanted tea. He boiled water in a teapot, put a bag of tea leaves in a cup, poured boiling water into it, added two teaspoons of sugar, stirred them with a spoon and drank his tea with pleasure. Let's draw up Petya's algorithm of actions in the form of a flowchart (the teacher calls the student to the blackboard).
In this example, all these actions are performed by Petya, therefore, he is the object that performs the algorithm. Petya is able and able to perform the actions specified in the algorithm. It performs these actions in the order listed. The object that executes the algorithm is calledperformer .
Distinguish between formal and informal performers. A formal executor executes the same command in the same way. An informal executor can execute a command.
Formal executors are extremely diverse, but for each of them the following characteristics can be indicated: the range of tasks to be solved (appointment), environment, command system, and mode of operation.
The range of tasks to be solved. Each executor is created to solve a certain range of tasks - building symbol chains, performing calculations, drawing pictures on a plane, and so on.
Executor environment are the conditions under which the algorithm can be executed.
Performer Command System (SCI) - a list of actions that the performer is able to understand and perform.
System of failures of executors - a list of failures that occurs when it is impossible to execute the algorithm in specific conditions.
Performer operating modes – direct and program control mode. Direct control - the performer waits for a command from a person and executes each command immediately. Program control - the executor is given a sequence of commands (program), and then executes the commands in automatic mode. Some performers only work in one of the modes.
The performers encountered in the tasks are “Grasshopper”, “Calculator”, “Pendulum”, “Turtle”, “Arrow”, “Dyer”, “Arrow”, “Turtle”, “Aquarius”, etc. others
Example: Performer Turtle moves on the computer screen, leaving a trail in the form of a line. The command system consists of the following commands:
Forwardn(wheren- integer) - causes movement onnsteps in the direction of movement - in the direction in which her head and body are turned.
Rightm(wherem– integer) – causes a change in the direction of movement bymdegrees clockwise.
Record RepeatK [<Команда1> <Команда2> … <Команда n>] - means that the sequence of commands in brackets will be repeatedkonce.
Think about what shape will appear on the screen after the Turtle executes the following algorithm:
Repeat 12[ Right 45 Forward 20 Right 45]
Answer:
Example: Instruction system The calculator consists of two instructions, which are assigned numbers:
1 - subtract 1
2 - multiply by 3
When writing the algorithm, for brevity, only the numbers of commands are indicated. For example, algorithm 21212 means the following
multiply by 3
Subtract 1
multiply by 3
Subtract 1
multiply by 3
Using this algorithm, the number 1 is converted to 15: ((1*3-1)*3-1)*3=15
Example: The Executor Robot operates on a checkered field, between adjacent cells of which there can be walls. The robot moves around the cells of the field and can execute the following commands: up, down, right, left.
When each such command is executed, the Robot moves to the next cell in the specified direction. If there is a wall between the cells in this direction, then the Robot is destroyed.
What will happen to the Robot if it executes a sequence of commands: right, down, right, down, right. Having started moving from cell A. What sequence of commands should the Robot execute in order to move from cell A to cell B without collapsing from the walls?
An algorithm presented in a language understandable to the Contractor is calledprogram .
Program – an ordered sequence of commands (instructions), required by the computer to solve the task.
The main difficulty in developing programs for a computer lies precisely in creating or finding an algorithm. Drawing up a program according to a known algorithm is called coding.
Programming (coding) is the process of compiling a program for a computer.
Each algorithm presented as a program must have a unique name that does not match the words built into the language. The program has a header that contains its name. The new algorithm is stored in the computer memory under its own name, and it can be called (executed) by entering the name of this program. Programs have the same properties as algorithms.
Lesson summary:
Dialog:
What new did you learn at the lesson?
What is the practical significance of the issue under study?
What are the positive aspects of the lesson.
Wishes
Thanks for the lesson!