Analysis of task 5 of the Unified State Exam in computer science.
For effective preparation in computer science, brief theoretical material for completing the task is given for each task. Over 10 training tasks with analysis and answers have been selected, developed based on the demo version of previous years.
There are no changes to the 2019 Unified State Exam KIM in computer science and ICT.
Areas in which knowledge will be tested:
- Programming;
- Algorithmization;
- ICT tools;
- Information activities;
- Information processes.
Necessary actions when preparation:
- Repetition of the theoretical course;
- Solution tests in computer science online;
- Knowledge of programming languages;
- Improve mathematics and mathematical logic;
- Use a wider range of literature – school curriculum is not enough for success on the Unified State Exam.
Exam structure
The duration of the exam is 3 hours 55 minutes (255 minutes), an hour and a half of which is recommended to be devoted to completing the tasks of the first part of the KIMs.
The tasks in the tickets are divided into blocks:
- Part 1- 23 tasks with short answer.
- Part 2- 4 tasks with detailed answers.
Of the proposed 23 tasks of the first part of the examination paper, 12 belong to the basic level of testing knowledge, 10 – to increased complexity, 1 – to a high level of complexity. Three problems of the second part high level complexity, one – increased.
When making a decision, it is necessary to record a detailed answer (free form).
In some tasks, the text of the condition is presented in five programming languages at once - for the convenience of students.
Points for computer science assignments
1 point - for 1-23 tasks
2 points - 25.
3 points - 24, 26.
4 points - 27.
Total: 35 points.
To enter a mid-level technical university, you must score at least 62 points. To enter the capital's university, the number of points must correspond to 85-95.
To successfully write an examination paper, a clear knowledge of theory and constant practice in solving tasks.
Your formula for success
Work + work on mistakes + carefully read the question from beginning to end to avoid mistakes = maximum score on the Unified State Exam in computer science.
To view the presentation with pictures, design and slides, download its file and open it in PowerPoint on your computer.
Text content of presentation slides: Preparation for the Unified State Examination Informatics teacher MBOU Secondary School No. 1, Azova Balamutova Irina Aleksandrovna 2015 Encoding and decoding of information. (Tasks 5) Data encoding, combinatorics, number systems (Tasks 10) Contents of the topic “Encoding and decoding information.” TheoryTask 1Task 2Task 3Task 4Tasks for trainingTopic: Data coding, combinatorics, number systemsTheoryTask 1Task 2Task 3Task 4Task 5Tasks for trainingReferences USEFUL SITES FOR PREPARATION TOVKI K USE2 is decoded from the beginning if the Fano condition is satisfied: no code word is the beginning of another code word; an encoded message can be unambiguously decoded from the end if the inverse Fano condition is satisfied: no code word is the end of another code word; the Fano condition is sufficient, but not necessary condition unambiguous decoding theory3 Coding is the translation of information from one language to another. Encoding can be uniform or uneven. With uniform encoding, all symbols are encoded with codes of equal length. With uneven encoding, different characters can be encoded with codes of different lengths. 4 theory Messages are transmitted over a communication channel, each of which contains 16 letters A, 8 letters B, 4 letters C and 4 letters G (there are no other letters in the messages). Each letter is encoded as a binary sequence. When choosing a code, two requirements were taken into account: a) not one code word is the beginning of another (this is necessary for the code to allow unambiguous decoding); b) the total length of the encoded message should be as small as possible. Which code from the following should be chosen to encode the letters A, B, C and D? 555551) A: 0, B: 10, C: 110, D: 1112) A: 0, B:10, C:01, D:113) A:1, B:01, C:011, D:0014) A:00, B:01, C:10, D:11Task 15, first select the codes, in which not a single code word coincides with the beginning of another (I call such codes prefix); for code 2, condition “a” is not satisfied, since the code word of the letter B (01) begins with the code word of the letter A (0); for code 3, the condition “ a" is not fulfilled, since the code word of the letter B (011) begins with the code word of the letter B (01) for codes 1 and 4 the condition is met, we consider them further, we calculate the total number of bits in the message for code 1: 16∙1 + 8 2 + 4∙3 + 4∙3 = 56 bits count the total number of bits in the message for code 4: 16∙2 + 8 2 + 4∙2 + 4∙2 = 64 bit code 1 gives the shortest message length, so choose it Answer: 1.6 Solution task 1 To encode a certain sequence consisting of the letters A, B, C, D, we decided to use an uneven binary code, satisfying the Fano condition. For the letter A we used code word 0, for letter B we used code word 110. What is the smallest possible total length of all four code words? 1) 7 2) 8 3) 9 4) 107 Problem 2 Solution (method 1, eliminating options): Fano condition means that no codeword is the same as the beginning of another codeword, since there is already a codeword 0, no other codeword can begin with 0, since there is a code 110, codewords 1, 11 are prohibited; in addition, no other codeword can begin with 110, so you need to choose two more codewords for which these restrictions are met. There is one valid codeword of two characters: 10 if you choose codeword 10 for the letter B, then there is one left the permissible three-character code word is 111, which can be selected for the letter G8. Solution to problem 2. By choosing code words A – 0, B – 110, C – 10, D – 111, we get the total length of the code words 9 characters. If you do not select B – 10, that is, three valid three-character codewords: 100, 101 and 110; when choosing any two of them for the letters B and G, we get the total length of code words 10, which is more than 9; therefore, we choose option 3 (9 characters) Answer: 3. Solution to problem 2 (continued) 9 AB10100 Solution (method 2, tree construction): Fano’s condition means that not a single code word coincides with the beginning of another code word; at the same time, in the code tree, all code words must be located in the leaves of the tree that have no descendants; let’s build a tree for the given code words A - 0 and B - 110:10 Task 2, dashed lines mark two “empty” branches to which leaves can be “attached” for code words of letters B (10) and G (111)AB10100VG, having chosen code words A – 0, B – 110, C – 10, D – 111, we obtain the total length of code words 9 characters Answer: 3. Problem 2 method 2, tree construction continued 11 Messages containing only 4 letters P, O, S, T are transmitted through the communication channel; For transmission, a binary code is used that allows unambiguous decoding. For the letters T, O, P, the following code words are used: T: 111, O: 0, P: 100. Specify the shortest code word for the letter C, at which the code will allow unambiguous decoding. If there are several such codes, indicate the code with the smallest numerical value. 12Task 3 OT101000P1Solution (method 2, tree construction): Fano’s condition means that not a single code word coincides with the beginning of another code word; at the same time, in the code tree, all code words must be located in the leaves of the tree, that is, in nodes that have no descendants; let's build a tree for the given code words O - 0, T - 111 and P - 100: 13 Solution of problem 3 Dashed lines mark two " empty” branches on which you can “attach” a sheet for the code word of the letter C: 101 or 110; of these, the minimum value is code 101 Solution of problem 3 (continued) 14 15 Dashed lines mark two “empty” branches on which you can “attach” a sheet for the code word of the letter C: 101 or 110; of these, the minimum value is code 101. OT101000P1S Having chosen code words A – 0, B – 110, C – 10, D – 111, we obtain the total length of code words 9 characters Answer: 101. Solution to problem 3 (continued) 15 Black and white raster image encoded line by line, starting from the left top corner and ending in the lower right corner. When encoding, 1 represents black and 0 represents white. BD9AA5 2) BDA9B5 3) BDA9D5 4)DB9DAB 16Task 4 “extend” the raster image into a chain: first the first (top) line, then the second, etc.: there are 24 cells in this strip, fill the black ones with ones, and fill the white ones with ones zeros: since each digit in the hexadecimal system is decomposed into exactly 4 binary digits, we divide the strip into tetrads - groups of four cells (in in this case it doesn’t matter where to start the breakdown, since there are an integer number of tetrads in the strip - 6): converting tetrads into hexadecimal system, we obtain sequentially the numbers B (11), D(13), A(10), 9, D(13) and 5, that is, the chain BDA9D5, so the correct answer is 3.17 Solution to problem 4 1 line 2 line 3 line 4 line 1011110110101001110101011 line 2 line 3 line 4 line 1011110110101001 1101010118 Solving the problem 4 (continued) Task 5 No. 7746. To encode a certain sequence consisting of the letters A, B, C, D and D, a non-uniform binary code is used, which makes it possible to unambiguously decode the resulting binary sequence. Here is the code: A - 1; B - 0100; B - 000; G - 011; D - 0101. It is required to reduce the length of the code word for one of the letters so that the code can still be decoded unambiguously. The codes of the remaining letters should not change. Which of the following methods can this be done? 1) for the letter G - 112) for the letter B - 003) for the letter G - 014) this is impossible Answer: 19 problems for independent solution2
Task 5 No. 1104. To encode the letters X, E, L, O, D, we decided to use the binary representation of the numbers 0, 1, 2, 3 and 4, respectively (with the preservation of one insignificant zero in the case of a single-digit representation). If you encode the sequence of letters ICE DRIVE in this way and write the result in hexadecimal code, you will get 1) 999С2) 32541453) 123F 4) 2143034 Answer: 20 answers Task 5 No. 1104 HELOD0123400011011100 First, you should present the data in the condition of a number in binary code: encode the sequence of letters: ICE DRIVE - 1001100110011100 Now let's divide this representation into quadruples from right to left and convert the resulting set of numbers first into decimal code, then into hexadecimal. 1001 1001 1001 1100 - 9 9 9 12 - 999C. The correct answer is indicated under number 1.21 Task 5 No. 7193 To transmit a message over a communication channel consisting only of the characters A, B, C and D, an uneven (in length) code is used: A – 0; B – 100; Q – 101. What code word should be used to encode the symbol G so that its length is minimal, and the code allows for an unambiguous division of the encoded message into symbols? 1) 12) 113) 01 Solution4) 010 http://inf.reshuege.ru/test?theme=232 Answer:222
Task 5 No. 9293.23 To encode a certain sequence consisting of the letters I, K, L, M, N, we decided to use a non-uniform binary code that satisfies the Fano condition. For the letter L we used code word 1, for the letter M we used code word 01. What is the shortest possible total length of all five code words? Note. The Fano condition means that no codeword is the beginning of another codeword. This makes it possible to unambiguously decrypt encrypted messages. Answer: 4 Solution http://inf.reshuege.ru/test?theme=23123
24Tasks for training video lesson linklinkhttps://www.youtube.com/watch?v=BoBnzjwLsnU Topic: Data coding, combinatorics, number systems (Tasks 10) 25 What you need to know: Russian alphabet principles of working with numbers written in positional number systems if the word consists of L letters, and there are n1 options for choosing the first letter, n2 options for choosing the second letter, etc., then the number of possible words is calculated as the product N = n1 · n2 · … · nL if the word consists of L letters, and each letter can be is chosen in n ways, then the number of possible words is calculated as N = nL26 theory Vasya composes 5-letter words that contain only the letters S, L, O, N, and the letter S is used exactly 1 time in each word. Each of the other valid letters can appear in a word any number of times or not at all. A word is any valid sequence of letters, not necessarily meaningful. How many words are there that Vasya can write?27Task 1 The letter C can appear in one of five places: С****, *С***, **С**, ***С* and **** C, where * denotes any of the remaining three characters in each case in the remaining four positions there can be any of the three letters L, O, N, therefore, with a given arrangement of the letter C we have 34 = 81 options, a total of 5 · 81 = 405 options. Answer: 405.28solution How many different character sequences of length 5 are there in a four-letter alphabet (A, C, G, T) that contain exactly two letters A?29Problem 2 Solution (option 1, search): consider various options words of 5 letters that contain two letters A and begin with A:AA*** A*A** A**A* A***AZHere the asterisk denotes any character from the set (C, G, T), that is one of three symbols. So, in each template there are 3 positions, each of which can be filled in three ways, so the total number of combinations (for each template!) is 33 = 27 in total 4 templates, they give 4 27 = 108 combinations30solution Now we consider templates where the first to counting, the letter A is in the second position, there are only three of them: *AA** *A*A* *A**Athey give 3 · 27 = 81 combinations of two patterns, where the first letter A is in the third position: **AA* **A*And they give 2 · 27 = 54 combinations and one pattern, where the combination AA is at the end ***AA they give 27 combinations, in total we get (4 + 3 + 2 + 1) · 27 = 270 combinations Answer: 270 .Solution (continued)31 All 4-letter words made up of the letters K, L, R, T are written in alphabetical order and numbered. Here is the beginning of the list: KKKK2. KKKL3. KKKR4. KKKT......Write down the word that is in 67th place from the beginning of the list. 32Task 3 The simplest solution to this problem is to use number systems; indeed, here the arrangement of words in alphabetical order is equivalent to the arrangement in ascending order of numbers written in the quaternary number system (the base of the number system is equal to the number of letters used). Let us make the replacement K0, L1, P2, T3; since the numbering of words begins with one, and the first number КККК0000 is 0, number 67 will be the number 66, which needs to be converted to the quaternary system: 66 = 10024 Having performed the reverse replacement (of numbers with letters), we get the word LKKR. Answer: LKKR .33Solution 34Task 4 Task 10 No. 6777. How many words of length 5 can be made from the letters E, G, E? Each letter can appear in a word several times. 35SolutionIf there are M characters in the alphabet, then the number of all possible “words” (messages) of length N is equal to Q = MN. In our case, N = 5, M = 3. Therefore, Q = 35 = 243. Answer: 243. 36Task 5 Task 10 No. 4797. There are 32 pencils in a closed box, some of them are blue. One pencil is taken out at random. The message “this pencil is NOT blue” carries 4 bits of information. How many blue pencils are there in the box? 37 Shannon’s formula: where x is the amount of information in the message about event P, p is the probability of event P. the probability that they got NOT blue where is the number of blue pencils. Using Shannon’s formula, we find that Y = 30 Solution 38 Tasks for training self-preparation video tutorial link link https:/ /www.youtube.com/watch?v=BoBnzjwLsnU REFERENCEShttp://kpolyakov.narod.ru/ Krylov S.S., Churkina T.E. Unified State Exam 2015. Computer science and ICT. Typical exam options. - M.: “National Education”, 2015. Leshchiner V.R. Unified State Exam 2015. Computer Science. Typical test tasks. - M.: Exam, 2015. Evich L.N., Kulabukhov S.Yu. Computer Science and ICT. Preparation for the Unified State Exam 2015. - Rostov-on-Don: Legion, 2014. Ushakov D.M., Yakushkin P.A. Computer science. The most complete edition of standard versions of Unified State Examination 2014 tasks. - M.: Astrel, 2014. Evich L.N., Kulabukhov S.Yu. Computer Science and ICT. Preparation for the Unified State Exam 2015. - Rostov-on-Don: Legion, 2014. Ostrovskaya E.M., Samylkina N.N. Unified State Exam 2015. Computer Science. We rent without any problems! - M.: Eksmo, 2014. Samylkina N.N., Ostrovskaya E.M. Unified State Exam 2015. Computer Science. Thematic training tasks. - M.: Eksmo, 2014. Zorina E.M., Zorin M.V. Unified State Exam 2015. Computer Science. Collection of tasks. - M.: “Eksmo”, 2015. 39 Useful sites for PREPARING FOR the Unified State Exam!40Informatics is easy http://easyinformatics.ru/Video analysis of the Unified State Exam-2013 task http://www.ageychev.rf/ege.htmlEducational portal for preparing for exams http://inf.reshuege .ru/?redir=1USE in computer science 2013 http://infoegehelp.ru/40
The lesson is devoted to how to solve task 5 of the Unified State Exam in computer science
The 5th topic is characterized as tasks basic level difficulty, execution time – approximately 2 minutes, maximum score – 1
- Coding- is the presentation of information in a form convenient for its storage, transmission and processing. The rule for converting information to such a representation is called code.
- Coding happens uniform And uneven:
- with uniform encoding, all symbols correspond to codes of the same length;
- with uneven encoding different characters correspond to codes of different lengths, this makes decoding difficult.
Example: Let's encrypt the letters A, B, C, D using binary coding uniform code and count the number of possible messages:
So we got uniform code, because the length of each codeword is the same for all codes (2).
Encoding and decryption of messages
Decoding (decoding)- this is the restoration of a message from a sequence of codes.
To solve problems with decoding, you need to know the Fano condition:
Fano condition: no codeword must be the beginning of another codeword (which ensures messages are unambiguously decoded from the beginning)
Prefix code is a code in which no code word coincides with the beginning of another code word. Messages using this code are decoded unambiguously.
Unambiguous decoding is provided:
Solving 5 Unified State Exam tasks
Unified State Exam 5.1: To encode the letters O, B, D, P, A, we decided to use the binary representation of the numbers 0, 1, 2, 3 and 4, respectively (with the preservation of one insignificant zero in the case of a single-digit representation).
Encode the sequence of letters WATERFALL in this way and write the result in octal code.
✍ Solution:
- Let's convert the numbers into binary codes and match them with our letters:
Result: 22162
Unified State Exam decision of this assignment in computer science, video:
Let's look at the analysis of task 5 of the Unified State Exam:
Unified State Exam 5.2: For 5 letters of the Latin alphabet, their binary codes are specified (for some letters - from two bits, for some - from three). These codes are presented in the table:
| a | b | c | d | e |
|---|---|---|---|---|
| 000 | 110 | 01 | 001 | 10 |
What set of letters is encoded by the binary string 1100000100110?
✍ Solution:
- First, we check the Fano condition: no codeword is the beginning of another codeword. The condition is true.
- We break the code from left to right according to the data presented in the table. Then let's translate it into letters:
✎ 1st solution:
Result: b a c d e.
✎ 2nd solution:
110
000 01
001 10
Result: b a c d e.
In addition, you can watch a video of the solution to this Unified State Exam assignment in computer science:
Let's solve the following 5th task:
Unified State Exam 5.3:
To transmit numbers over a noisy channel, a parity check code is used. Each of its digits is written in binary representation, with leading zeros added to a length of 4, and the sum of its elements modulo 2 is added to the resulting sequence (for example, if we transmit 23, we get the sequence 0010100110).
Determine what number was transmitted over the channel in the form 01100010100100100110.
✍ Solution:
- Let's consider example from the problem statement:
Answer: 6 5 4 3
You can watch a video of the solution to this Unified State Exam assignment in computer science:
Unified State Exam 5.4:
To encode a certain sequence consisting of the letters K, L, M, N, they decided to use a non-uniform binary code that satisfies the Fano condition. The code word 0 was used for the letter H, and the code word 10 for the letter K.
What is the shortest possible total length of all four codewords?
✍ Solution:
✎ 1 solution option based on logical conclusions:
- Let's find the shortest possible codewords for all letters.
- Code words 01 And 00 cannot be used, since then the Fano condition is violated (they start from 0, and 0 - This N).
- Let's start with two-digit codewords. Let's take for the letter L a codeword 11 . Then it is impossible to select a code word for the fourth letter without violating the Fano condition (if you then take 110 or 111, then they begin with 11).
- This means that three-digit code words must be used. Let's encode the letters L And M code words 110 And 111 . The Fano condition is satisfied.
✎ Option 2:
(N) -> 0 -> 1 character (K) -> 10 -> 2 characters (L) -> 110 -> 3 characters (M) -> 111 -> 3 characters Answer: 9
Unified State Exam in Informatics 5 task 2017 FIPI option 2 (edited by Krylov S.S., Churkina T.E.):
Messages containing only 4 letters are transmitted through the communication channel: A, B, C, D; For transmission, a binary code is used that allows unambiguous decoding. For the letters A, B, C, the following code words are used: A: 101010, B: 011011, C: 01000.
Г, at which the code will allow unambiguous decoding. the smallest numerical value.
✍ Solution:
- The smallest codes could look like 0 And 1 (single digit). But this would not satisfy the Fano condition ( A starts with one - 101010 , B starts from scratch - 011011 ).
- Next least code it would be a two letter word 00 . Since it is not a prefix of any of the presented codewords, then G = 00.
Result: 00
Unified State Examination in Informatics 5 task 2017 FIPI option 16 (edited by Krylov S.S., Churkina T.E.):
To encode a certain sequence consisting of the letters A, B, C, D and D, we decided to use a non-uniform binary code, which allows us to unambiguously decode the binary sequence appearing on the receiving side of the communication channel. The code used was: A - 01, B - 00, C - 11, D - 100.
Indicate what code word the letter D should be encoded with. Length this code word must be least of all possible. The code must satisfy the property of unambiguous decoding. If there are several such codes, indicate the code with the lowest numerical value.
✍ Solution:
Result: 101
A more detailed analysis of the lesson can be seen in the video of the Unified State Exam in Computer Science 2017:
Unified State Examination in Informatics 5 task 2017 FIPI option 17 (Krylov S.S., Churkina T.E.):
To encode a certain sequence consisting of the letters A, B, C, D, D and E, we decided to use a non-uniform binary code, which allows us to unambiguously decode the binary sequence appearing on the receiving side of the communication channel. The code used was: A - 0, B - 111, C - 11001, D - 11000, D - 10.
Indicate what code word the letter E should be encoded with. The length of this codeword should be the shortest possible. The code must satisfy the property of unambiguous decoding. If there are several such codes, indicate the code with the lowest numerical value.
✍ Solution:
1 - not suitable (all letters except A begin with 1) 10 - not suitable (corresponds to code D) 11 - not suitable (the beginning of codes B, C and D) 100 - not suitable (code D - 10 - is the beginning of this code) 101 - not suitable (code D - 10 - is the beginning of this code) 110 - not suitable (the beginning of code B and D) 111 - not suitable (corresponds to code B) 1000 - not suitable (code D - 10 - is the beginning of this code) 1001 - not suitable (code D - 10 - is the beginning of this code) 1010 - not suitable (code D - 10 - is the beginning of this code) 1011 - not suitable (code D - 10 - is the beginning of this code) 1100 - not suitable ( beginning of code B and D) 1101 - suitable
Result: 1101
More detailed solution This task is presented in the video tutorial:
Task 5. Demo version of the Unified State Exam 2018 computer science (FIPI):
Encrypted messages containing only ten letters are transmitted over the communication channel: A, B, E, I, K, L, R, S, T, U. An uneven binary code is used for transmission. Code words are used for nine letters. 
Specify the shortest code word for the letter B, under which the code will satisfy the Fano condition. If there are several such codes, indicate the code with the smallest numerical value.
✍ Solution:
Result: 1100
For a detailed solution to this 5th task from the demo version of the Unified State Exam 2018, watch the video:
Task 5_9. Model exam options 2017. Option 4 (Krylov S.S., Churkina T.E.):
Encrypted messages containing only four letters are transmitted over the communication channel: A, B, C, D; For transmission, a binary code is used that allows unambiguous decoding. For letters A, B, IN code words used:
A: 00011 B: 111 C: 1010
Specify the shortest code word for the letter G, in which the code will allow unambiguous decoding. If there are several such codes, indicate the code with the smallest numerical value.
✍ Solution:
Result: 00
Task 5_10. Training option No. 3 from 10/01/2018 (FIPI):
Messages containing only letters are transmitted over the communication channel: A, E, D, K, M, R; For transmission, a binary code that satisfies the Fano condition is used. The following codes are known to be used:
E – 000 D – 10 K – 111
Specify the shortest possible encoded message length DEDMAKAR.
In your answer, write a number - the number of bits.
✍ Solution:
D E D M A K A R 10,000 10,001 01,111 01,110
Result: 20
See the solution to the task:
5th task: “Encoding and decoding messages”
Difficulty level - basic,
Maximum score - 1,
Approximate execution time is 2 minutes.
Unified State Exam 5.1: To encode the letters O, B, D, P, A, we decided to use the binary representation of the numbers 0, 1, 2, 3 and 4, respectively (with the preservation of one insignificant zero in the case of a single-digit representation).
Encode the sequence of letters WATERFALL in this way and write the result in octal code.
Answer: 22162
✍ Show solution:
- Let's convert the numbers into binary codes and match them with our letters:
Unified State Exam 5.2: For 5 letters of the Latin alphabet, their binary codes are specified (for some letters - from two bits, for some - from three). These codes are presented in the table:
| a | b | c | d | e |
|---|---|---|---|---|
| 000 | 110 | 01 | 001 | 10 |
What set of letters is encoded by the binary string 1100000100110?
Answer: b a c d e
✍ Show solution:
- First, we check the Fano condition: no codeword is the beginning of another codeword. The condition is true.
- We break the code from left to right according to the data presented in the table. Then let's translate it into letters:
✎ 1st solution:
Result: b a c d e.
✎ 2nd solution:
110 000 01 001 10Unified State Exam 5.3:
To transmit numbers over a noisy channel, a parity check code is used. Each of its digits is written in binary representation, with leading zeros added to a length of 4, and the sum of its elements modulo 2 is added to the resulting sequence (for example, if we transmit 23, we get the sequence 0010100110).
Determine what number was transmitted over the channel in the form 01100010100100100110.
Answer: 6 5 4 3
✍ Show solution:
- Let's consider example from the problem statement:
Unified State Exam 5.4:
To encode a certain sequence consisting of the letters K, L, M, N, they decided to use a non-uniform binary code that satisfies the Fano condition. The code word 0 was used for the letter H, and the code word 10 for the letter K.
What is the shortest possible total length of all four codewords?
Answer: 9
✍ Show solution:
✎ 1 solution option based on logical conclusions:
- Let's find the shortest possible codewords for all letters.
- Code words 01 And 00 cannot be used, since then the Fano condition is violated (they start from 0, and 0 - This N).
- Let's start with two-digit codewords. Let's take for the letter L a codeword 11 . Then it is impossible to select a code word for the fourth letter without violating the Fano condition (if you then take 110 or 111, then they begin with 11).
- This means that three-digit code words must be used. Let's encode the letters L And M code words 110 And 111 . The Fano condition is satisfied.
✎ Option 2:
(N) -> 0 -> 1 character (K) -> 10 -> 2 characters (L) -> 110 -> 3 characters (M) -> 111 -> 3 characters Unified State Exam in Informatics 5 task 2017 FIPI option 2 (edited by Krylov S.S., Churkina T.E.):
Messages containing only 4 letters are transmitted through the communication channel: A, B, C, D; For transmission, a binary code is used that allows unambiguous decoding. For the letters A, B, C, the following code words are used: A: 101010, B: 011011, C: 01000.
Specify the shortest code word for the letter G, at which the code will allow unambiguous decoding. the smallest numerical value.
Answer: 00
✍ Show solution:
- The smallest codes could look like 0 And 1 (single digit). But this would not satisfy the Fano condition ( A starts with one - 101010 , B starts from scratch - 011011 ).
- The next smallest code would be a two letter word 00 . Since it is not a prefix of any of the presented codewords, then G = 00.
Unified State Examination in Informatics 5 task 2017 FIPI option 16 (edited by Krylov S.S., Churkina T.E.):
To encode a certain sequence consisting of the letters A, B, C, D and D, we decided to use a non-uniform binary code, which allows us to unambiguously decode the binary sequence appearing on the receiving side of the communication channel. The code used was: A - 01, B - 00, C - 11, D - 100.
Indicate what code word the letter D should be encoded with. Length this code word must be least of all possible. The code must satisfy the property of unambiguous decoding. If there are several such codes, indicate the code with the lowest numerical value.
Answer: 101
✍ Show solution:
Unified State Examination in Informatics 5 task 2017 FIPI option 17 (Krylov S.S., Churkina T.E.):
To encode a certain sequence consisting of the letters A, B, C, D, D and E, we decided to use a non-uniform binary code, which allows us to unambiguously decode the binary sequence appearing on the receiving side of the communication channel. The code used was: A - 0, B - 111, C - 11001, D - 11000, D - 10.
Indicate what code word the letter E should be encoded with. The length of this codeword should be the shortest possible. The code must satisfy the property of unambiguous decoding. If there are several such codes, indicate the code with the lowest numerical value.
Answer: 1101
✍ Show solution:
1 - not suitable (all letters except A begin with 1) 10 - not suitable (corresponds to code D) 11 - not suitable (the beginning of codes B, C and D) 100 - not suitable (code D - 10 - is the beginning of this code) 101 - not suitable (code D - 10 - is the beginning of this code) 110 - not suitable (the beginning of code B and D) 111 - not suitable (corresponds to code B) 1000 - not suitable (code D - 10 - is the beginning of this code) 1001 - not suitable (code D - 10 - is the beginning of this code) 1010 - not suitable (code D - 10 - is the beginning of this code) 1011 - not suitable (code D - 10 - is the beginning of this code) 1100 - not suitable ( beginning of code B and D) 1101 - suitable
Task 5. Demo version of the Unified State Exam 2018 computer science (FIPI):
Encrypted messages containing only ten letters are transmitted over the communication channel: A, B, E, I, K, L, R, S, T, U. An uneven binary code is used for transmission. Code words are used for nine letters.
Specify the shortest code word for the letter B, under which the code will satisfy the Fano condition. If there are several such codes, indicate the code with the smallest numerical value.