The decision of the exam on computer science 5 task. To transfer numbers by channel with interference, the parity check code is used

Hearing 5. the tasks of the ege 2016 on computer science from demoralism. This task is to encode and decode information (able to interpret the results obtained during the simulation of real processes). This is the task of the basic level of complexity. An approximate time of execution of the task is 2 minutes.

Task 5:

On the communication channel, messages containing only four letters are transmitted: P, O, C, T; For transmission, a binary code that allows unambiguous decoding is used. For the letters T, O, P code words are used: T: 111, A: 0, P: 100.
Specify the shortest code word for the letter C, in which the code will allow unambiguous decoding. If there are several such codes, specify the code with the smallest numeric value.

Answer: ________

HAPPENING 5 TASKS EGE 2016:

To solve this task, you need to know the condition of Fano.

Fano condition:
The encoded message can be unambiguously decoded if no code word is the end of another code word.

Reverse condition Fano:
The encoded message can be unambiguously decoded from the end if no code word is the end of another code word.

Let's start checking in order:

0 - can not be, since the O-0 (also the code word cannot begin with 0, since the condition of Fano is not completed),

1 - can not be, because from the unit begins T-111 and P-100,

10 - can not be, because with 10 begins P-100,

11 - can not be, since the T-111 begins with 11,

100 - can not be because P-100,

101 — suitable, since the condition of Fano is performed,

110 — suitableSince the Fano condition is performed.

By the condition of the task, if the words are somewhat, you need to select the code with the smallest numerical value - so we choose 101 .

Task directory.
Transfer information. Select code

Sorting Basic First Simple First Complicated Popularity First Next First
Touch testing for these tasks
Return to the task catalog
Printing and copying version in MS Word

To encode some sequence consisting of letters to, l, m, n, decided to use an uneven binary code that satisfies the Fano condition. For the letter N used code word 0, for the letter to - code word 10. What is the smallest possible total length of all four code words?

Note.

Decision.

Find the shortest views for all letters. The code words 01 and 00 cannot be used, since the condition of Fano is disturbed. We use, for example, for the letter L code word 11. Then for the fourth letter it is impossible to choose a code word without disturbing the condition of Fano. Consequently, for the remaining two letters you need to use three-digit code words. Correct the letters L and M code words 110 and 111. Then the total length of all four code words is 1 + 2 + 3 + 3 \u003d 9.

Answer: 9.

For encoding some sequence consisting of letters A, B, B, G and D, an uneven binary code is used, which allows you to unambiguously decode the resulting binary sequence. This code: a - 1; B - 0100; In - 000; G - 011; D - 0101. It is required to reduce for one of the letters of the length of the code word so that the code can still be decoded unambiguously. The codes of the remaining letters should not change. What of the specified ways can this be done?

1) for the letter G - 11

2) for the letter in - 00

3) for the letter G - 01

4) it is impossible

Decision.

For one-to-member decoding, the code word resulting as a result should not be the beginning of any other. The first answer is not suitable, because the code of the letter A is the beginning of the code of the letter G. The second answer is suitable. The third version of the answer is not suitable, since, in this case, the code of the letter G is the beginning of the letter D.

The correct answer is subject to number: 2.

Answer: 2.

To encode some sequence consisting of letters and, k, l, m, n, decided to use an uneven binary code that satisfies the Fano condition. For the letter H used code word 0, for the letter K - code word 10. What is the smallest possible total length of all five code words?

Note. The Fano Condition means that no code word is the beginning of another code word. This provides the ability to unambiguously decrypt encoded messages.

Decision.

You can not use code words that start with 0 or from 10. 11 We also can't use, because then we will no longer be able to take any other codeword, and we need five. Therefore, we take three-digit 110. 111. Again, we cannot use it, because you need another code word, and at the same time there will be no more free. Now it remains to take only two words and it will be 1110 and 1111. Total we have 0, 10, 110, 1110 and 1111 - 14 characters.

Answer: 14.

To encode some sequence consisting of letters and, k, l, m, n, decided to use an uneven binary code that satisfies the Fano condition. For the letter l used code word 1, for the letter M - code word 01. What is the smallest possible total length of all five code words?

Note. The Fano Condition means that no code word is the beginning of another code word. This provides the ability to unambiguously decrypt encoded messages.

Decision.

Fano's condition - no code word can be the beginning of another code word. Since there is already a code word 1, no other can start with 1. only with 0. Also, it can not start with 01, since we already have 01. That is, any new code word will start from 00. But it can not To be 00, since otherwise we will not be able to take a single code word, because all the longer words start either from 1, or from 00, or from 01. We can take either 000 or 001. But not both immediately, since again In this case, we will no longer be able to take a single new code. Then Take 001. And since we have only two codes left, we can take 0000 and 0001. Total we have: 1, 01, 001, 0000, 0001. Total 14 characters.

To see a presentation with pictures, design and slides, download its file and open in PowerPoint on your computer.
Text Content Slides Presentation: Preparations for the Egressant Informatiki Society No. 1 G. Azov Balamutova Irina Aleksandrovna2015. Encoding and decoding information. (Tasks 5) Data encoding, combinatorics, number system (task 10) Content of the topic "Coding and decoding." Theory 1 Outcoming 2 Outcoming 3 Outcomes for training Code: Coding Data, Combinatorics, Systems Systems 1 Out 2 Options 3 Options 4 Options 5 Options For Training Site Literature Sites EEH2 decoded from the beginning if the Fano condition is satisfied: no code word is the beginning of another code word; The encoded message can be unambiguously decoded from the end if the reverse Fano condition is performed: no code word is the end of the other code word; the Fano condition is sufficient, but not prerequisite Unambiguous decodingTeoria3 Coding is the transfer of information from one language to another. Coding can be uniform and uneven, and 4 letters g (there are no other letters in messages). Every letter is encoded by a binary sequence. When choosing the code, two requirements were taken into account: a) no codeword is the beginning of another (it is necessary that the code allows unambiguous decoding); b) The total length of the encoded message must be as small as possible. How the code from the above should be selected for encoding letters a, b, in and g? 555551) A: 0, b: 10, in: 110, g: 1112) A: 0, b: 10, in: 01, g: 113) a: 1, b: 01, in: 011, g: 0014) A: 00, B: 01, C: 10, G: 11 Beading 15 We first choose codes, In which no codeword coincides with the beginning of another (such codes call the prefix) for code 2, the condition "A" is not performed, since the code word of the letter in (01) begins with the code word of the letter A (0) for code 3 condition " A "is not performed, since the code word of the letter B (011) begins with the code word Letters B (01) for codes 1 and 4, the condition is performed, they are considered having fun about the total number of bits in the message for code 1: 16 ∙ 1 + 8 · 2 + 4 ∙ 3 + 4 ∙ 3 \u003d 56 Bitching the total number of bits in a message for code 4: 16 ∙ 2 + 8 · 2 + 4 ∙ 2 + 4 ∙ 2 \u003d 64 Tyakod 1 gives the smallest length of the message, so we choose its response: 1.6 Tasks 1 for encoding some sequence consisting of letters A, B, B, G, decided to use an uneven binary code that satisfies the Fano condition. For the letter A, I used code word 0, for the letter B - code word 110.Kova The smallest possible total length of all four code words? 1) 7 2) 8 3) 9 4) 107 Output 2 solution (method 1, exception options): Fano condition This means that no code word coincides with the beginning of another code list, there is already a code word 0, no other code word begins with 0 since there is code 110, code words 1, 11 are prohibited; In addition, no other code word can begin with 110tically, you need to select two more code words for which these limitations are performed. There is one permissible code word from two characters: 10 If you select a code word 10 for the letter in, then one remains The permissible threeximwall code word - 111, which can be selected for the letter of the G8 value of Task 2 by selecting code words A - 0, B - 110, B - 10, G - 111, we obtain the total length of the code words 9 characters. If you do not choose B - 10, that is, there are three permissible threeximilical code words: 100, 101 and 110; When choosing any two of them for letters in and g, we obtain the total length of the code words 10, which is more than 9; Therefore, select Option 3 (9 characters) Answer: 3. Solution Tape 2 (continued) 9 ab10100Recution (Method 2, Tree construction): Fano Correction means that no code word coincides with the beginning of another code word; At the same time in the code tree, all code words should be located in the leaves of the tree that do not have descendants; we construct a tree for the specified code words A - 0 and b - 110: 10 Feed 2 Stroke lines 2 "Empty" branches are marked for which you can "attach" leaves For code words of letters in (10) and (111) ab10100vgvybrav code words A - 0, b - 110, B - 10, G - 111, we obtain the total length of the code word code 9, the symptoms: 3. Task 2 method 2, construction of a tree continuation11 On the communication channel, messages containing only 4 letters P, O, C, T; For transmission, a binary code that allows unambiguous decoding is used. For the letters T, O, P code words are used: T: 111, ABOUT: 0, P: 100. For the shortest code word for the letter C, in which the code will allow unambiguous decoding. If there are several such codes, specify the code with the smallest numeric value. 12 Output 3 OT101000P1Recution (Method 2, Tree Building): Fano Correction means that no codeword coincides with the beginning of another code word; At the same time, in the code tree, all code words should be located in the leaves of the tree, that is, in nodes that do not have descendants; we construct a tree for the specified code words about - 0, T - 111 and P - 100: 13 Operations of the task 3 were marked by two " empty "branches that can be" attached "a sheet for code word letter C: 101 or 110; Of these, the minimum value of the code 101rection of the problem 3 (continued) 14 15 masters are marked two "empty" branches, for which you can "attach" a sheet for the code word letter C: 101 or 110; Of these, the minimum value is the code 101.ot101000p1Shevit the code words A - 0, b - 110, B - 10, g - 111, we obtain the total length of the code word code words 9. The symbol: 101. Solution of the problem 3 (continued) 15 Black and white raster image is encoded Right, starting from the upper left corner and ending in the lower right corner. When encoding 1 denotes black, and 0 - white. BD9AA5 2) BDA9B5 3) BDA9D5 4) DB9DAB 16 Outstitch 4 "Extend" a raster image into a chain: first first (top) string, then - second, etc. : in this strip 24 cells, black fill in units, and white - zeros: Since each figure in a hexadecimal system is declined exactly in 4 binary figures, we break the strip on the tetrads - groups of four cells (in this case, it's not all right where to start the breakdown, since In the strip, the integer number of Tetrad - 6): Translation of the tetrads into the hexadecimal system, we obtain the numbers b (11), D (13), A (10), 9, D (13), and 5, that is, the BDA9D5 chain is the correct answer - 3.17Reshenie problem April 1 string2 stroka3 line4 stroka1011110110101001110101011 string2 stroka3 line4Reshenie task 4 (continued) Target 5 № 7746. To encode a sequence consisting of letters A, B, C and D, used an uneven binary code to uniquely decode the resulting binary sequence. This code: a - 1; B - 0100; In - 000; G - 011; D - 0101. It is required to reduce for one of the letters of the length of the code word so that the code can still be decoded unambiguously. The codes of the remaining letters should not change. What of the specified ways can this be done? 1) For the letter G - 112) for the letter in - 003) for the letter G - 014) it is not possible: 19 tasks for self-decisions2
Task 5 No. 1104. For encoding the letters X, E, L, O, D, decided to use the binary representation of numbers 0, 1, 2, 3 and 4, respectively (with the preservation of one inconcent zero in the case of a single-digit presentation). If you encode the sequence of Icewright letters in this way and the result will be recorded by hexadecimal code, it will turn out 1) 999С2) 32541453) 123F 4) 2143034 Answer: 20 Answers Task 5 No. 1104Helode0123400011011100Snamed You should submit data to the number of the number in binary code: Code the sequence of letters: Ice - 100110011111100 . Now we will break this view on the fourths to the right left and transfer the resulting set of numbers in the decimal code, then in hexadecimal. 1001 1001 1001 1100 - 9 9 9 12 - 999С. The correct answer is specified at number 1.21 Task 5 No. 7193 for transmission over the communication channel of the message consisting only of characters A, B, B, and G, is used uneven (in length) Code: A - 0; B - 100; In - 101. What kind of code word you need to encode the symbol g, so that it is minimal, and the code allows you to unambiguously split the encoded message to the characters? 1) 12) 113) 01 Decision4) 010 http://inf.reshuege.ru/test?Theme\u003d232 Answer: 222
Task 5 No. 9293.23 for encoding some sequence consisting of letters and, k, l, m, n, decided to use an uneven binary code that satisfies the Fano condition. For the letter l used code word 1, for the letter M codeword 01. What is the smallest possible total length of all five code words? Note. The Fano Condition means that no code word is the beginning of another code word. This provides the ability to unambiguous decryption of encoded messages. RESULT: 4Entens http://inf.reshuege.ru/test?Theme\u003d23123
24 Promotive training Video Tutorial LinksLinkHttps: //www.youtube.com/watch? V \u003d bobnzjwlsnu Topic: data encoding, combinatorics, number systems (tasks 10) 25 What you need to know: Russian alphabet Principles of work with numbers recorded in positional specificity systems The word consists from l letters, and there are N1 options for selecting the first letter, N2 options for choosing a second letter, etc., the number of possible words is calculated as a product N \u003d N1 · N2 · ... · NLAI word consists of l letters, and each letter may be Native n methods, the number of possible words is calculated as N \u003d NL26Teorya Vasya is 5-letter words in which there are only letters C, L, O, N, and the letter C is used in each word exactly 1 time. Each of the other allowable letters can occur in the Word any number of times or not to meet at all. A word is considered to be any permissible sequence of letters, not necessarily meaningful. How many words are there, which can write Vasya? 27 Feed 1 letter C can stand at one of five places: from ****, * with ***, ** s **, *** s * and **** With, where * denotes any of the remaining three characters in each case, in each other four positions, any of the three letters l, o, H, therefore, at a given location, the letter C we have 34 \u003d 81 variants of the entire variants 5 · 81 \u003d 405.Wrant: 405.28Recuration How many different symbolic sequences of length 5 in a four-letter alphabet (A, C, G, T), which contain exactly two letters a? 29 Candle 2 solution (option 1, bust): Consider various options for words of 5 letters that contain two Letters A and begin with A: AA *** A * A ** A ** A * A *** The stars refers to any character from the set (C, G, T), that is, one of three characters. So, in each template there are 3 positions, each of which can be fill in three ways, so the total number of combinations (for each template!) Is 33 \u003d 27 Total 4 templates, they give 4 · 27 \u003d 108 combinations. The score of the letter A is on the second position, there are only three of them: * AA ** * A * A * * A ** AONI gives 3 · 27 \u003d 81 combination of template, where the first in the score of the letter A is on the third position: ** AA * ** A * and they give 2 · 27 \u003d 54 combinations and one template, where the combination of AA is at the end of *** AA, they give 27 combinations. Total we get (4 + 3 + 2 + 1) · 27 \u003d 270 combinations: 270 . Making (continued) 31 All 4-letter words made up of letters to, l, p, t, recorded in alphabetical order and are numbered. Here is the beginning of the list: kkkk2. Kkl3. Kkkr4. CKT ...... write down the word that stands at 67th place from the beginning of the list. 32Read 3 The easiest solution to this task is to use the number systems; Indeed, here the alphabetical alphabetical order here is equivalent to the arrangement in an increase in the numbers recorded in the chimeful number system (the base of the number system is equal to the number of letters used). Fill the replacement of K0, L1, P2, T3; Since the numbering of words begins with a unit, and the first number of KKKK0000 is 0, number 67 will stand the number 66, which must be translated into the fourth system: 66 \u003d 10024 After performing a reverse replacement (numbers per letter), we get the word LCKR. RESULT: LCKR .333Production 34 Options 4 Task 10 No. 6777. How many words of length 5 can be made up of the letters E, G, E? Each letter can enter the word several times. 35Recel in alphabet M symbols, the number of all possible "words" (messages) length n is q \u003d Mn. In our case, n \u003d 5, m \u003d 3. Consequently, Q \u003d 35 \u003d 243. Answer: 243. 36 Options 5 Task 10 No. 4797. There are 32 pencils in the closed box, some of them are blue. At random is taken out one pencil. The message "This pencil is not blue" carries 4 bits of information. How many blue pencils in the box? 37 Shenonna formula: where x is the amount of information in the message about the event P, P is the probability of the event P. The likelihood that it was not blue where - the number of blue pencils. Usessed by the Schuenonna formula, we get that \u003d 30-year-old training session Self-training Video Tutorial LinkslinkHttps: / /www.youtube.com/watch?v\u003dbobnzjwlsnu Literature LiteratureHttp: //kpolyakov.narod.ru/ Krylov S.S., Churkina Tue. EGE 2015. Informatics and ICT. Typical exam options. - M.: "National Education", 2015. Leschinner V.R. Ege 2015. Informatics. Typical test tasks. - M.: Exam, 2015.Evich L.N., Kulabukh S.Yu. Informatics and ICT. Preparation for the EEG-2015. - Rostov-on-Don: Legion, 2014. Ushakov D.M., Yakushkin P.A. Computer science. The most complete publication of typical options for the tasks of the EE 2. - M.: Astrel, 2014. Evich L.N., Kulabukhov S.Yu. Informatics and ICT. Preparation for the EEG-2015. - Rostov-on-Don: Legion, 2014. Ostrovskaya E.M., Satykina N.N. Ege 2015. Informatics. We rent without problems! - M.: Eksmo, 2014. Satykina N.N., Ostrovsky E.M. Ege 2015. Informatics. Thematic training tasks. - M.: Eksmo, 2014.Sorina E.M., Zorin M.V. Ege 2015. Informatics. Collection of tasks. - M.: Eksmo, 2015.39 Useful sites for preparing for the exam! 40informatics - it's just http://easyinformatics.ru/Videosulation Problems of EGE-2013 http: //www.agechev.rf/ege.htm Temporary portal for preparing for Exams http://inf.reshuege.ru/?redir\u003d1Egue on computer science 2013 http://infogehelp.ru/40

Single state exam The computer science consists of 27 tasks. In task 5, the skills of encoding and decoding information are checked. The schoolboy must be able to encode and decode information in various number systems, as well as decrypt messages and choose the optimal code. Here you can learn how to solve the task of 5 EGE on computer science, as well as study examples and ways to solve on the basis of detailed disassembled tasks.

All tasks EGE All tasks (107) Ege Quest 1 (19) Ege Quest 3 (2) EE Assignment 4 (11) EE Assignment 5 (10) EE Assignment 6 (7) EE Assignment 7 (3) EE Assignment 9 (5) EEG TASK 10 (7) EGE QUESTION 11 (1) EGE TASK 12 (3) EGE TASK 13 (7) EGE TASK 16 (19) EGE OPTION 17 (4) EGE without number (9)

For encoding letters decided to use binary performance

For encoding letters, the binary representation of numbers 0, 1, 2, 3 and 4 was decided to use, respectively (with the preservation of one inconcent zero in the case of a single-digit presentation). If you encode the sequence of letters in this way and the result is to record the octal code, it will turn out ...

For transmission over the communication channel, the message consisting only of characters

For transmission over the communication channel, a message consisting only of symbols A, B, B, and G is used by seductive encoding. A message is transmitted via the communication channel. Code the message to this code. The resulting binary number is transferred to a hexadecimal view.