13th task: "Amount of information"
Difficulty level - increased,
The maximum score is 1,
Estimated completion time is 3 minutes.
Solution 13 of the USE task in informatics (K. Polyakov, v. 4):
Message volume - 7.5 kB... This message is known to contain 7680 characters. What is the power of the alphabet?
Answer: 256
✍ Show solution:
- Let's use the formula:
I = 7.5 KB = 7.5 * 2 13 bits
\ [K = \ frac (7.5 * 2 ^ (13)) (7680) = \ frac (7.5 * 2 ^ (13)) (15 * 2 ^ 9) = \ frac (7.5 * 16 ) (15) = 8 \]
2 8 = 256
different characters
(by the formula Q = 2 N)
Solution 13 of the exam in computer science (K. Polyakov, v. 6):
The power of the alphabet is 256 . How many KB of memory will be required to save 160 pages of text containing on average 192 characters on every page?
Answer: 30
✍ Show solution:
- Let's find the total number of characters on all pages (for convenience, we will use powers of two):
\ [I = (15 * 2 ^ (11)) * 2 ^ 3 bits = \ frac (15 * 2 ^ (14)) (2 ^ (13)) KB = 30 KB \]
I = 30 Kbyte
Solution 13 of the Unified State Exam in Informatics (K. Polyakov, vol. 3):
The two texts contain the same number of characters. The first text is composed in the alphabet by the power 16 characters and the second text is in the alphabet from 256 characters.
How many times is the amount of information in the second text greater than in the first?
Answer: 2
✍ Show solution:
- Formula required Q = 2 n
- Let's calculate the required number of bits to store one character for both texts:
Working with different systems
Unified State Exam 2017 collection by D.M. Ushakov's "10 training options ..." option 1:
The cable network is voting among viewers on which of the four films they would like to watch in the evening. The cable network is used by 2000
Human. Participated in the voting 1200
Human.
What is the amount of information ( in bytes) recorded by an automated voting system?
Answer: 300
✍ Show solution:
- Since the four movie numbers are stored in the computer system, you can find the number of bits needed to store the movie number:
Unified State Exam 2017 collection by D.M. Ushakov's "10 training options ..." option 10:
The school rehearsal exam is taken 105 Human. Each of them is assigned a special number that identifies it in the automatic response checking system. When registering a participant to record his number, the system uses the minimum possible number of bit, the same for each participant.
What is the amount of information in bits recorded by the device after registration 60
participants?
Answer: 420
✍ Show solution:
Solution 13 of the exam in computer science (K. Polyakov, v. 17):
The database stores records containing information about dates. Each record contains three fields: year (number from 1 to 2100), month number (day from 1 to 12) and the number of the day in the month (number from 1 to 31). Each field is recorded separately from other fields using the smallest possible number of bits.
Determine the minimum number of bits required to encode one record.
Answer: 21
✍ Show solution:
- Formula required Q = 2 n.
- Let's calculate the required number of bits to store each item of the entire record:
Solution 13 of the USE task in computer science (control option No. 1 of the examination paper, Simulator 2018, S. S. Krylov, D. M. Ushakov):
The rehearsal exam is passed 9
streams across 100
a person in everyone. Each of them is assigned a special code consisting of a stream number and a stream number. When coding these participant numbers, the checking system uses the minimum possible number of bit, the same for each participant, separately for the number of the stream and the number in the stream. In this case, to write the code, the minimum possible and equally integer amount is used bytes.
What is the amount of information in bytes recorded by the device after registration 80
participants?
Answer: 160
✍ Show solution:
- The code consists of two components: 1. stream number (in bits) and 2. sequential number (in bits). Let's find the number of bits needed to store them:
Computer systems and license plates
Solution 13 of the exam in computer science (K. Polyakov, v. 33):
The license plate consists of several letters (the number of letters is the same in all license plates), followed by three numbers. This uses 10 digits only 5 letters: H, O, M, E and R... You need to have at least 100 000 different numbers.
What is the smallest number of letters in a license plate?
Answer: 3
✍ Show solution:
- Formula required Q = m n.
13 task. Demo version of the exam 2018 informatics:
10 characters. Capital letters of the Latin alphabet are used as symbols, i.e. 26 various symbols. In the database for storing each password, the same and minimum possible integer is allocated byte bit.
Determine the amount of memory ( in bytes) required for storing data about 50
users.
In the answer, write down only an integer - the number of bytes.
Answer: 350
✍ Show solution:
- The main formula for solving this problem is:
- To find the number of bits required to store one password, you first need to find the number of bits required to store 1 character in the password. By the formula we get:
where Q- the number of character options that can be encoded with N bit.
Solution 13 of the USE task in informatics (diagnostic version of the exam paper, USE simulator 2018, S. S. Krylov, D. M. Ushakov):
In some countries, the license plate number consists of 7 characters... Each character can be one of 18 different letters or decimal digit.
Each such number in computer program written in the smallest possible and the same whole number byte, in this case, character-by-character coding is used and each character is encoded with the same and minimum possible amount bit.
Determine the amount of memory in bytes allocated by this program for writing 50
numbers.
Please provide only the number in your answer.
Answer: 250
✍ Show solution:
- Since the number can be used either one letter from 18 , or one digit from 10 , then only one of the following can be used as one character in the number 28 characters:
Unified State Exam 2017 collection by D.M. Ushakov "10 training options ..." option 6:
15 12 -character set A, B, C, D, E, F, G, H, I, K, L, M, N... The database for storing information about each user has the same and minimum possible integer byte... In this case, character-by-character passwords are used, all characters are encoded with the same and minimum possible number bit... In addition to the password itself, additional information is stored in the system for each user, for which 12 bytes per user.
Determine the amount of memory ( in bytes) required to store information about 30
users.
In the answer, write down only an integer - the number of bytes.
Answer: 600
✍ Show solution:
Unified State Exam in Informatics 2017 task 13 FIPI option 1 (Krylov S.S., Churkina T.E.):
When registering in a computer system, each user is given a password consisting of 7 characters and containing only characters from 33 -symbol alphabet. The database for storing information about each user has the same and minimum possible integer byte... In this case, character-by-character passwords are used, all characters are encoded with the same and minimum possible number bit... In addition to their own password, the system stores additional information for each user, for which an integer number of bytes is allocated; this number is the same for all users.
To store information about 60 users needed 900 byte.
How many bytes are allocated to store additional information about one user?
In response, write down only an integer - the number of bytes.
Answer: 9
✍ Show solution:
- First, let's define a password. According to the formula Q = M N we get:
Solution 13 of the exam in computer science (K. Polyakov, v. 58):
When registering in a computer system, each user is given a password consisting of 9 characters... Use as symbols uppercase and lowercase letters of the Latin alphabet (in it 26 characters), as well as decimal digits... The database for storing information about each user is allocated the same and minimum possible integer number of bytes. In this case, a character-by-character encoding of passwords is used, all characters are encoded with the same and minimum possible number of bits. In addition to the password itself, additional information is stored in the system for each user, for which the 18 bytes per user. Highlighted in the computer system 1 Kb to store information about users.
What is the largest number of users that can be stored in the system? In the answer, write down only an integer - the number of users.
Answer: 40
✍ Show solution:
- Since both uppercase and lowercase letters are used, we get all the options for characters for encoding:
Above we looked at examples of binary encoding of numbers, letters, colors. However, since any information presented in a computer is of a binary nature, it is very often necessary to compare binary codes and other types of information.
When encoded, information is written using symbols. For example, plain text is information encoded using a set of characters, such as the Russian alphabet. The character set used to encode data is called alphabet ... The number of characters in the alphabet is called the cardinality of the alphabet. The sequence of characters in the alphabet is called word .
If there are two different alphabets and a rule for converting words from one alphabet to words of another alphabet is given, then such a conversion process is called coding .
The most common is the binary encoding alphabet, consisting of 2 characters 0 and 1. It encodes all information in the computer.
In general, the coding problem is posed as follows: “There is a certain set of values (data set). It is necessary to map each value to a binary code that meets the following requirements:
· First, all codes must be of the same length - consist of the same number of bits. This is necessary to calculate the amount of encoded information and correct code recognition.
· Secondly, the length of the binary code should be the minimum required to encode all values from the set.
The minimum number of bits required to encode N elements of the set is determined from the following inequality
2 K-1 < N ≤ 2 K, (5)
where K is the number of bits required for encoding.
It can be seen from the inequality that in order to determine the number of bits, it is necessary to find a power of 2 greater than or equal to N, but closest to this number.
Another (reverse) formulation of tasks related to encoding a data set is: "What is the maximum number of binary codes that can be made from K bits?" The answer is expressed by the formula
N = 2 K. (6)
Analysis of tasks from demo versions of the exam
E1.1.(2004, A3) The chessboard consists of 64 fields: 8 columns by 8 lines. What is the minimum number of bits required to encode the coordinates of one chessboard?
E1.3.(2005, A3) A conventional traffic light without additional sections gives six types of signals (continuous red, yellow and green, flashing yellow and green, red and yellow at the same time). The electronic traffic light control device sequentially reproduces the recorded signals. In a row, 100 traffic signals have been recorded. In bytes, this information volume is
E1.5.(2007, A2) The light board consists of light bulbs, each of which can be in two states ("on" or "off"). What is the smallest number of lights on the scoreboard to transmit 50 different signals?
E1.7.(2008, A3) A code consisting of decimal digits is used to transmit a secret message. In this case, all digits are encoded with the same (minimum possible) number of bits. Determine the information volume of the message with a length of 150 characters.
E1.9.(2010, A2) In some countries, the license plate number is 7 characters long. The characters are 18 different letters and decimal digits in any order. Each such number in a computer program is recorded with the minimum possible and the same integer number of bytes, while using character-by-character coding and all characters are encoded with the same and minimum possible number of bits. Determine the amount of memory allocated by this program for recording 60 numbers.
From the analysis of the demonstration tasks, it can be concluded that the tasks associated with coding the dataset are included in the Unified State Exam in Informatics every year. The simplest are the tasks for determining the number of binary codes of the same length, which were proposed in 2005 (A2) and 2006 (A2). Most of the tasks are related to determining the minimum number of bits required to encode a dataset, and then calculating the information volume of a certain message. The main difficulty of these tasks is that they have a wide variety of specific settings. This is because encoding can be required for almost any dataset. The main thing in these tasks is to correctly determine the data set to be encoded.
Examples of typical tasks
A1.1. To transmit signals, use is made of a sequence of signs "+" and "-" with a length of 6 symbols. How many different signals can you encode with them? Choose the correct answer.
Solution
1. First of all, we note that since only 2 characters are used for coding, we have a place with binary coding, and the sequences consisting of the signs "+" and "-" are similar to binary codes of zeros and ones. Thus, one character in such a code can also be considered a bit.
2. Determine how many different 6-bit binary codes you can make. For this we use the formula N = 2K, where K = 6. Therefore, N = 64.
Let us use this example to explain why 6 bits can be used to make 64 different combinations of binary codes. The largest binary number of 6 bits is 1111112. If you translate this number into decimal code, you get the number
1 × 26 + 1 × 25 + 1 × 24 + 1 × 23 + 1 × 22 + 1 × 21 + 1 × 20 = 6310
At first glance, it may seem that 6 bits can be used to compose 63 different binary codes, ranging from the code corresponding to 110 = 0 and ending with the code corresponding to 6310 = 1111112. But we must not forget that there is another binary code of 6 bits - this is a number 0000002. Thus, a total of 64 different codes can be made.
Answer:
A1.2. For accounting purposes, each student is assigned a binary code of the same length. Is 9 bits enough to encode all the students in the school if the school has 1000 students? Calculate the difference between the maximum possible number of 9-bit binary codes and the number of students. Choose the correct answer.
Solution
1. Determine how many different binary codes with a length of 9 bits can be made. For this we use the formula N = 2K, where K = 9. Therefore, N = 512. We got that 512 binary codes with a length of 9 bits can be made. Obviously, this amount will not be enough to encode all 1000 students in the school. Choose the correct answer.
2. According to the problem statement, we find the difference between the number of binary codes and the number of students 512 - 1000 = –448.
Answer: 3 (3rd option from the proposed).
A1.3. To highlight the figure in an electronic watch, a rectangular light board of 7 oblong bulbs is used, which are located on it like the number 8, folded from matches. Each light bulb can be on or off. How many combinations of on and off bulbs are redundant? Choose the correct answer.
Solution
1. First of all, we note that since the lights on the scoreboard can be in only two states, then we have binary coding, and the combinations of on and off lights are similar to binary codes of zeros and ones. Thus, one light on the scoreboard is analogous to the 1st bit.
2. It is not necessary to imagine how the number 8 can be added out of 7 matches, although such electronic boards are actually found quite often, not only in watches, but also in other electronic devices.
3. From 7 bulbs, you can make 27 = 128 different light signals. And to highlight a digit, you only need 10 light signals.
4. Consequently, 128 - 10 = 118 light signals will be unused.
Answer: 4 (4th option from the proposed).
A1.4. The light board consists of light bulbs, each of which can be in two states ("on", "off"). What is the smallest number of light bulbs on the scoreboard so that 20 different signals can be transmitted with it? Choose the correct answer.
Solution
1. As in the previous task, the light signals of the board can be read as binary codes. However, according to the formulation, this problem is the reverse of the previous one.
2. To determine the minimum number of bulbs required to encode 20 signals, we find the power of 2, which is closest to 20, but greater. This is 25 = 32. Therefore, to encode 20 signals, you need 5 bulbs.
Answer: 1 (1st option from the proposed).
A1.5. The following data, encoded in binary code, is applied to the magnetic card for passage through the turnstile in the metro: the date of purchase of the card, the number of trips and the number tariff plan, which reflects the peculiarities of using the card. The date encodes the day, month and two last digits of the year separately. The metro uses 8 different tariff plans. A maximum of 60 trips can be recorded on the card. Each information element is encoded with the minimum required number of bits. Calculate in bits the informational amount of data encoded on the magnetic card. Choose the correct answer.
Solution
1. Determine the number of bits required to encode each data element - day of the month, month, year, rate plan and number of trips. There can be a maximum of 31 days in a month.
2. Choose a degree of 2 that is greater than 31, but the closest to this number is 32 = 25. So to encode, so to encode the ordinal numbers of the month, 5 bits are needed.
3. Similarly, we determine the number of bits required to encode other data elements. The table below shows the number of values and the number of bits.
Note. In this problem, it is impossible to add up all possible values, and then determine the total minimum number of bits required for encoding, since in order to recognize the code, you need to clearly know how many bits each individual data element occupies. So, if in this task you count the total number of values to be encoded, you get 213. To encode 213 values, 8 bits are enough, but the codes obtained in this way will not allow you to select individual data elements.
4. In the bottom line of the table, the information volume of data on the magnetic card is calculated - 25 bits.
Answer: 3 (3rd option from the proposed).
A1.6. To pass the exam in computer science, groups of 30 people or less are formed. Each exam participant is assigned a binary code. In the exam, each participant can score a maximum of 40 points. The results of the exam are entered into the file of the electronic examination sheet: the binary code of the participant and the binary code of the number of points scored. Determine the information volume of the file if 16 people came to the exam. Choose the correct answer.
Solution
1. Since there can be no more than 30 people in a group, then 5 bits will be needed to encode each participant, since 25 = 32 is the closest degree to 30 2. Thus, no matter how many people come to the exam, everyone will still be assigned 5-bit code.
2. Determine the number of bits required to encode the points scored. You can score 40 points in total. The closest but greater 40 degree 2 is 26 = 64. Therefore, we will use a 6-bit code to encode the points we have collected.
3. The data of one participant in the electronic record takes 5 + 6 = 11 bits.
4. A total of 16 people came to the exam, so 11 * 16 = 176 bits were entered in the list.
Answer:
A1.7. There are 16 teams participating in the Russian Football Championship in the Major League. Each team during the season plays with each team 2 times - once on its own field and once on the opponent's field. The results of the match are entered into the file - the date (the day and the month are coded separately, the year is not coded), the binary codes of the teams of the participants and the codes of the number of goals scored by the teams, for which 1 byte is allocated for the result of each team. For simplicity of coding months, we will assume that the football season lasts all 12 months (although in fact this is not the case). What is the information volume of the file in bytes after half a season has passed - half of all matches have been played. Choose the correct answer.
Solution
1. Determine the minimum number of bits required to encode a command. Since there are 16 teams, we find the power of 2 closest to 16 (or equal to). This will be the number 16 = 24. Therefore, 4 bits are needed to encode the command.
2. Determine the number of bits required to encode the date (see table).
3. Determine how many bits the record of the results of one match contains. To encode goals, allocates 1 byte for each team, that is, 8 bits. Everything needs to be folded
5 bits (code of the day of the month);
4 bits (month code);
4 bits (one command code);
· 4 bits (code of another command);
· 8 bits (code of the number of goals of one team);
· 8 bits (code of the number of goals of another team).
Thus, one record takes 33 bits.
4. Determine how many matches the teams play in total in the season. It is convenient to add the match grid, as is usually done.
At the bottom of the table are the matches of the 1st half of the season, at the top of the matches of the second half of the season. The cells that are not filled are highlighted in gray, since the team does not play with itself.
The table has 16 columns and 16 lines with the results of matches minus the filled cells - there are also 16 of them.
Thus, the total matches for the season are 16 * 16 - 16 = 256 - 16 = 240.
In half of the season, 120 matches are played.
5. The information volume of the file with the results after 120 played matches is 120 * 33 (bits). To convert to bytes, divide this number by * 33/8 = 15 * 33 = 495 bytes.
Answer: 2 (2nd option from the proposed).
Tasks for independent solution
C1.5. To encode characters in ASCII encoding, 1 byte is used. How many characters (power of the alphabet) can be encoded with 1 byte? Choose the correct answer.
C1.7. What is the minimum number of bits (binary digits) required to encode 4 arithmetic operations: addition, subtraction, multiplication, division? Choose the correct answer.
C1.9. How many characters does a message contain, written using a 16-character alphabet, if its information volume is 1/16 Kbyte. Choose the correct answer.
C1.11. Only Russian lowercase letters were used to encode information. What information volume in bytes will the message, consisting of 16 characters, have? Choose the correct answer.
C1.13. For communication, the Mumbo-Jumbo tribe uses a language containing 24 basic concepts and 3 bundles (ok) that allow you to connect these concepts. Messages are transmitted using drum beats in portions: concept + bundle. All concepts are coded with the same number of beats and links are coded with the same number of beats. How many drum beats are used in each portion of the messages?
C1.14. For communication in the language of the Mumbo-Jumbo tribe, 13 basic concepts and 4 bundles are used to combine these concepts. To transmit messages, the tribe uses a binary code: a combination of voiced and dull drum sounds. Messages are transmitted in chunks - concept + bunch. How many beats will it take to encode each chunk of the message?
Each memory cell in a ternary computer can take on three different values.(-1, 0, 1)... To store a certain value, 4 memory cells were allocated. How many different values can this value take?
Solution:
Another example of a task:
The school database stores records containing information about students:
<Фамилия>
<Имя>- 12 characters: Russian letters (first uppercase, other lowercase),
<Отчество>- 16 characters: Russian letters (first uppercase, other lowercase),
<Год рождения>- numbers from 1992 to 2003.
Each field is recorded using as few bits as possible. Determine the minimum number of bytes required to encode one record if the letters e and e are considered to be the same.
1) 282) 293)464)56
Solution:
it is obvious that you need to determine the minimum possible bit sizes for each of the four fields and add them;
important! it is known that the first letters of the name, patronymic and surname are always uppercase, so you can store them as lowercase and make them capitalized only when displayed on the screen (but we don't care anymore)
thus, for character fields, it is sufficient to use an alphabet of 32 characters (Russian lowercase letters, "e" and "e" are the same, no spaces are needed)
to encode each character of the 32-character alphabet, 5 bits are needed (32 = 2555 5), therefore, to store the first name, patronymic and last name, you need (16 + 12 + 16) 5 = 220 bits
there are 12 options for the year of birth, so you need to allocate 4 bits for it (2 4 = 16 ≥ 12)
so it takes 224 bits or 28 bytes in total
the correct answer is 1.
Tasks for training3:
The light board consists of light bulbs. Each light can be in one of three states ("on", "off" or "blinking"). What is the smallest number of light bulbs on the scoreboard to transmit 18 different signals?
1) 6 2) 5 3) 3 4) 4
The meteorological station monitors air humidity. The result of one measurement is an integer from 0 to 100 percent, which is written using the fewest possible bits. The station made 80 measurements. Determine the information volume of the observation results.
1) 80 bits 2) 70 bytes 3) 80 bytes 4) 560 bytes
A conventional traffic light without additional sections gives six types of signals (continuous red, yellow and green, flashing yellow and green, red and yellow at the same time). The electronic traffic light control device sequentially reproduces the recorded signals. In a row, 100 traffic signals have been recorded. In bytes, this information volume is
1) 37 2) 38 3) 50 4) 100
(The condition is incorrect, it means the number of whole bytes.)
How many different sequences of plus and minus symbols are there, exactly five characters long?
1) 64 2) 50 3) 32 4) 20
The chessboard consists of 8 columns and 8 rows. What is the minimum number of bits required to encode the coordinates of one chessboard?
1) 4 2) 5 3) 6 4) 7
The two texts contain the same number of characters. The first text is in a 16-character alphabet and the second text is in a 256-character alphabet. How many times is the amount of information in the second text greater than in the first?
1) 12 2) 2 3) 24 4) 4
What is the minimum number of bits required to encode positive numbers less than 60?
1) 1 2) 6 3) 36 4) 60
Two people play tic-tac-toe on a 4 by 4 square. How much information did the second player receive after learning the move of the first player?
1) 1 bit 2) 2 bits 3) 4 bits 4) 16 bits
The size of the message is 7.5 KB. This message is known to contain 7680 characters. What is the power of the alphabet?
1) 77 2) 256 3) 156 4) 512
Given a text of 600 characters. It is known that characters are taken from a 16 by 32 table. Determine the informational amount of text in bits.
1) 1000 2) 2400 3) 3600 4) 5400
The capacity of the alphabet is 256. How many KB of memory will it take to store 160 pages of text with an average of 192 characters per page?
1) 10 2) 20 3) 30 4) 40
The message size is 11 KB. The message contains 11264 characters. What is the power of the alphabet?
1) 64 2) 128 3) 256 4) 512
To encode a secret message, 12 special symbols are used. In this case, the symbols are encoded with the same minimum possible number of bits. What is the information volume of a 256-character message?
1) 256 bit 2) 400 bit 3) 56 bytes 4) 128 bytes
The alphabet has a capacity of 64. How many KB of memory would it take to store 128 pages of text with an average of 256 characters per page?
1) 8 2) 12 3) 244)36
7 note symbols are used to encode the musical notation. Each note is encoded with the same minimum number of bits. What is the information volume of a message consisting of 180 notes?
1) 180 bits 2) 540 bits 3) 100 bytes 4) 1 kB
The basket contains 8 black balls and 24 white ones. How many bits of information are there in the message that the black ball has been pulled?
1) 2 bits 2) 4 bits 3) 8 bits 4) 24 bits
The box contains 64 colored pencils. The message that a white pencil was taken out carries 4 bits of information. How many white pencils were in the box?
1) 4 2) 8 3) 16 4) 32
For a quarter, Vasily Pupkin received 20 ratings. The message that he received a four yesterday carries 2 bits of information. How many fours did Vasily get for a quarter?
1) 2 2) 4 3) 5 4) 10
The basket contains black and white balls. Among them are 18 black balls. The message that the white ball has been pulled carries 2 bits of information. How many balls are there in the basket?
1) 18 2) 24 3) 36 4) 48
The closed box contains 32 pencils, some of them 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 in the drawer?
1) 16 2) 24 3) 30 4) 32
Some alphabet contains 4 different symbols. How many three-letter words can be made from the characters of this alphabet if the characters in the word can be repeated?
1) 4 2) 16 3) 64 4) 81
In some country, a 6-character license plate is composed of capital letters (12 letters in total) and decimal digits in any order. Each character is encoded with the same and minimum possible number of bits, and each number - with the same and minimum possible number of bytes. Determine the amount of memory required to store 32 license plates.
1) 192 bytes 2) 128 bytes 3) 120 bytes 4) 32 bytes
1) 100 bytes 2) 150 bytes 3) 200 bytes 4) 250 bytes
The light board consists of luminous elements, each of which can glow in one of three different colors. How many different signals can be transmitted using a display consisting of four such elements (provided that all elements must be lit)?
1) 4 2) 16 3) 64 4) 81
In some country, a 6-character license plate is composed of capital letters (19 letters in total) and decimal digits in any order. Each character is encoded with the same and minimum possible number of bits, and each number - with the same and minimum possible number of bytes. Determine the amount of memory required to store 40 license plates.
1) 120 bytes 2) 160 bytes 3) 200 bytes 4) 240 bytes
In some country, a 6-character license plate is composed of capital letters (26 letters in total) and decimal digits in any order. Each character is encoded with the same and minimum possible number of bits, and each number - with the same and minimum possible number of bytes. Determine the amount of memory required to store 20 license plates.
1) 160 bytes 2) 120 bytes 3) 100 bytes 4) 80 bytes
To transmit signals in the fleet, special signal flags are used, which are hung in one line (the sequence is important). How many different signals can a ship transmit using four signal flags if the ship has three different types of flags (there is an unlimited number of flags of each type)?
To transmit signals in the fleet, special signal flags are used, which are hung in one line (the sequence is important). How many different signals can a ship transmit using five signal flags if the ship has four different types of flags (there is an unlimited number of flags of each type)?
The cyclocross is attended by 678 athletes. A special device registers the passage of each participant of the intermediate finish, recording his number using the minimum possible number of bits, the same for each athlete. What is the information volume of the message recorded by the device after 200 cyclists have passed the intermediate finish?
1) 200 bits 2) 200 bytes 3) 220 bytes 4) 250 bytes
In some country, a 7-character license plate is composed of capital letters (18 letters in total) and decimal digits in any order. Each character is encoded with the same and minimum possible number of bits, and each number - with the same and minimum possible number of bytes. Determine the amount of memory required to store 60 license plates.
1) 240 bytes 2) 300 bytes 3) 360 bytes 4) 420 bytes
Some signaling device transmits one of three signals in one second. How many different messages of four seconds can be transmitted with this device?
The database stores records containing information about dates. Each record contains three fields: a year (a number from 1 to 2100), a month number (a number from 1 to 12), and a day number in a month (a number from 1 to 31). Each field is recorded separately from other fields using the smallest possible number of bits. Determine the minimum number of bits required to encode one record.
Vasya and Petya send messages to each other using blue, red and green flashlights. They do this by turning on one flashlight for the same short time in a certain sequence. The number of flashes in one message - 3 or 4, between messages - pauses. How many different messages can boys send?
5 consecutive color bursts are used to encode 300 different messages. The flashes are of the same duration, each flash uses one light of a specific color. How many light bulbs should be used for transmission (specify the minimum number possible)?
Each cell of the 8 × 8 field is encoded with the minimum possible and the same number of bits. The solution to the problem of the "horse" passing the field is recorded by the sequence of codes of the visited cells. What is the amount of information after 11 made moves? (Recording of the solution begins from the initial position of the knight).
1) 64 bits 2) 9 bytes 3) 12 bytes 4) 96 bytes
Each cell of the 5 × 5 field is encoded with the minimum possible and the same number of bits. The solution to the problem of the "horse" passing the field is recorded by the sequence of codes of the visited cells. What is the amount of information after 15 made moves? (Recording of the solution begins from the initial position of the knight).
1) 10 bytes 2) 25 bits 3) 16 bytes 4) 50 bytes
The teacher, putting in the journal quarter marks in biology for the third quarter (3, 4, 5), noticed that the combination of three quarter marks in this subject is different for all students. What is the maximum number of students in this class?
Some alphabet contains four different symbols. How many words exactly 4 characters long can be made from words of a given alphabet (characters in a word can be repeated)?
In some country, a 10-character license plate is composed of capital letters (21 letters in total) and decimal digits in any order. Each character is encoded with the same and minimum possible number of bits, and each number - with the same and minimum possible number of bytes. Determine the amount of memory required to store 81 license plates.
1) 810 bytes 2) 567 bytes 3) 486 bytes 4) 324 bytes
The 22 square light board consists of luminous elements, each of which can glow in one of four different colors. How many different signals can be transmitted using a display consisting of four such elements (provided that all elements must be lit)?
The light board consists of luminous elements, each of which can glow in one of eight different colors. How many different signals can be transmitted using a display consisting of three such elements (provided that all elements must be lit)?
In some country, a 5-character license plate is composed of capital letters (30 letters in total) and decimal digits in any order. Each character is encoded with the same and minimum possible number of bits, and each number - with the same and minimum possible number of bytes. Determine the amount of memory required to store 50 license plates.
1) 100 bytes 2) 150 bytes 3) 200 bytes 4) 250 bytes
In some country, a 7-character license plate is composed of capital letters (30 letters in total) and decimal digits in any order. Each character is encoded with the same and minimum possible number of bits, and each number - with the same and minimum possible number of bytes. Determine the amount of memory required to store 32 vehicle numbers.
1) 160 bytes 2) 96 bytes 3) 224 bytes 4) 192 bytes
In some country, a 5-character license plate is composed of capital letters (26 letters in total) and decimal digits in any order. Each character is encoded with the same and minimum possible number of bits, and each number - with the same and minimum possible number of bytes. Determine the amount of memory required to store 40 license plates.
1) 160 bytes 2) 200 bytes 3) 120 bytes 4) 80 bytes
In some country, a 7-character license plate is composed of capital letters (22 letters in total) and decimal digits in any order. Each character is encoded with the same and minimum possible number of bits, and each number - with the same and minimum possible number of bytes. Determine the amount of memory required to store 50 license plates.
1) 350 bytes 2) 300 bytes 3) 250 bytes 4) 200 bytes
The light board consists of color indicators. Each indicator can be colored in four colors: white, black, yellow and red. What is the smallest number of light bulbs on the scoreboard so that it can transmit 300 different signals?
1) 4 2) 5 3) 6 4) 7
One memory cell of a ternary computer (one trit) can take one of three possible values: 0, 1, or –1. To store a certain value in the memory of such a computer, 4 cells were allocated. How many different values can this value take?
1) 8 2) 16 3) 64 4) 81
The message size is 11 KB. The message contains 11264 characters. What is the maximum power of the alphabet used in the transmission of the message?
1) 64 2) 128 3) 256 4) 512
Some country has 1000 inhabitants. Individual taxpayer numbers (TIN) contain only the numbers 0, 1, 2 and 3. What should be the minimum length of the TIN if all residents have different numbers?
Some country has 200 inhabitants. Individual taxpayer numbers (TIN) contain only the numbers 2, 4, 6 and 8. What should be the minimum length of the TIN if all residents have different numbers?
The two guard detachments, located at a great distance from each other, agreed to transmit messages to each other using red and green signal flares. How many different messages can you transmit, launch exactly 3 missiles?
How many messages could a traffic light transmit if it had three "eyes" burning at the same time, and each of them could change color and become red, yellow or green?
Some device transmits one of seven signals per second. How many different messages of 3 seconds length can be transmitted with this device?
To transmit signals in the fleet, special signal flags are used, which are hung in one line (the sequence is important). How many different types of flags must you have so that 8 different signals can be transmitted using a sequence of three flags (there is an unlimited number of flags of each type)?
There are 800 students in the school, student codes are written in the school information system using the minimum number of bits. What is the informational volume of the message about the codes of 320 students attending the conference?
1) 2560 bit 2) 100 byte 3) 6400 bit 4) 400 byte
In some countries, the license plate number is 8 characters long. The first character is one of 26 Latin letters, the remaining seven are decimal digits. Sample number - A1234567. Each character is encoded with the minimum possible number of bits, and each number is encoded with the same and minimum possible number of bytes. Determine the amount of memory required to store 30 license plates.
1) 180 bytes 2) 150 bytes 3) 120 bytes 4) 250 bytes
To register on the site of a certain country, the user needs to come up with a password that is exactly 11 characters long. The password can use decimal digits and 12 different characters of the local alphabet, and all letters are used in two weights - lowercase and uppercase. Each character is encoded with the same and minimum possible number of bits, and each password is encoded with the same and minimum possible number of bytes. Determine the amount of memory required to store 60 passwords.
1) 720 bytes 2) 660 bytes 3) 540 bytes 4) 600 bytes
To encode messages, it was decided to use sequences of different lengths, consisting of the signs “+” and “-.” How many different messages can be encoded using at least 2 and no more than 6 characters in each of them?
To encode messages, it was decided to use sequences of different lengths, consisting of the signs “+” and “-.” How many different messages can be encoded using at least 3 and no more than 7 characters in each of them?
To register on the site of a certain country, the user needs to come up with a password that is exactly 15 characters long. The password can use decimal digits and 11 different characters of the local alphabet, and all letters are used in two weights - lowercase and uppercase. Each character is encoded with the same and minimum possible number of bits, and each password is encoded with the same and minimum possible number of bytes. Determine the amount of memory required to store 30 passwords.
1) 360 bytes 2) 450 bytes 3) 330 bytes 4) 300 bytes
To register on the site of a certain country, the user needs to come up with a password that is exactly 11 characters long. The password can use decimal digits and 32 different characters in the local alphabet, and all letters are used in two weights - lowercase and uppercase. Each character is encoded with the same and minimum possible number of bits, and each password is encoded with the same and minimum possible number of bytes. Determine the amount of memory required to store 50 passwords.
1) 450 bytes 2) 400 bytes 3) 550 bytes 4) 500 bytes
1Often kilobytes stand for "KB", and megabytes for "Mb", but in demo tests the USE developers gave just such designations.
2In fact, it is not different way of solving, but a more rigorous justification of the previous algorithm.
3Sources of quests:
Demonstration versions of the USE 2004-2011
Guseva I.Yu. Unified State Exam. Computer Science: Practice Test Handouts. - SPb: Trigon, 2009.
Yakushkin P.A., Leshchiner V.R., Kirienko D.P. Unified State Exam 2010. Informatics. Typical test tasks. - M .: Exam, 2010.
Krylov S.S., Ushakov D.M. Unified State Exam 2010. Informatics. Thematic workbook. - M .: Exam, 2010.
Yakushkin P.A., Ushakov D.M. The most complete edition of typical options for real tasks of the exam 2010. Informatics. - M .: Astrel, 2009.
Abramyan M.E., Mikhalkovich S.S., Rusanova Ya.M., Cherdyntseva M.I. Informatics. Unified State Exam step by step. - M .: Research Institute of School Technologies, 2010.
Churkina T.E. Unified State Exam 2011. Informatics. Thematic training tasks. - M .: Eksmo, 2010.
Krylov S.S., Leshchiner V.R., Yakushkin P.A. Unified State Exam 2011. Informatics. Versatile student preparation materials. - M .: Intellect-center, 2011.
When converting information into binary code, it becomes necessary to determine the amount of information (amount of information) required to store this type of information.
Two concepts can be expressed (encoded) with one bit:
If the number of bits is increased to two, then four different events can be encoded:
Eight different events can be encoded with three bits:
By increasing the number of bits in the binary code by one, the number of encoded events doubles.
What the formula describes:
N = 2 i,
where N is the number of independent encoded events;
i - bit width of the binary code.
The powers of two reflect the number of events N, encoded with i [BIT]:
N, events |
Problem 1
The light board consists of light bulbs. Each light bulb can be in one of two states ("on", "off"). What is the smallest number of light bulbs on the scoreboard to transmit 18 different signals?Task 2
The light board consists of light bulbs. Each light bulb can be in one of three states ("on", "off", "blinking"). What is the smallest number of light bulbs on the scoreboard to transmit 18 different signals?for N = 18 it will be 27
from which it follows that i = 3.
Answer: 3 bulbs.
Problem 3
The cyclocross is attended by 119 athletes. A special device registers the passage of each participant of the intermediate finish, recording his number using the minimum possible number of bits, the same for each athlete. What is the information volume of the message recorded by the device after 70 cyclists have passed the intermediate finish?Problem 4
In some country, a 7-character license plate is composed of capital letters (26 letters in total) and decimal digits in any order. Each character is encoded with the same and minimum possible number of bits, and each number - with the same and minimum possible number of bytes. Determine the amount of memory required to store 20 license plates.Problem 5
The meteorological station monitors air humidity. The result of one measurement is an integer from 0 to 100 percent, which is written using the fewest possible bits. The station made 80 measurements. Determine the information volume of the observation results.Homework
1 The chessboard consists of 8 columns and 8 rows. What is the minimum number of bits required to encode the coordinates of one chess field.2 What is the minimum number of bits required to encode positive numbers less than 60?
3 To encode a secret message, 12 special symbols are used. In this case, the symbols are encoded with the same minimum possible number of bits. What is the information volume of a 256-character message?
4 7 note symbols are used to encode the musical notation. Each note is encoded with the same minimum number of bits. What is the information volume of a message consisting of 180 notes?
5 678 athletes participate in the cyclocross. A special device registers the passage of each participant of the intermediate finish, recording his number using the minimum possible number of bits, the same for each athlete. What is the information volume of the message recorded by the device after 200 cyclists have passed the intermediate finish?
6 In some country, a 6-character license plate is composed of capital letters (12 letters in total) and decimal digits in any order. Each character is encoded with the same and minimum possible number of bits, and each number - with the same and minimum possible number of bytes. Determine the amount of memory required to store 32 license plates.
7 How many different sequences of plus and minus symbols are there, exactly five characters long?
8 Some alphabet contains 4 different symbols. How many three-letter words can be made from the characters of this alphabet if the characters in the word can be repeated?
9 The light board consists of luminous elements, each of which can glow in one of three different colors. How many different signals can be transmitted using a display consisting of four such elements (provided that all elements must be lit)?
10 To transmit signals in the fleet, special signal flags are used, posted in one line (sequence is important). How many different signals can a ship transmit using four signal flags if the ship has three different types of flags (there is an unlimited number of flags of each type)?
11 To transmit signals in the fleet, special signal flags are used, posted in one line (sequence is important). How many different signals can a ship transmit using five signal flags if the ship has four different types of flags (there is an unlimited number of flags of each type)?
12 Some signaling device transmits one of three signals in one second. How many different messages of four seconds length can be transmitted using this device.
13 Vasya and Petya send messages to each other using blue, red and green flashlights. They do this by turning on one flashlight for the same short time in a certain sequence. The number of flashes in one message - 3 or 4, between messages - pauses. How many different messages can boys send?
14 5 consecutive color bursts are used to encode 300 different messages. The flashes are of the same duration, each flash uses one light of a specific color. How many light bulbs should be used for transmission (specify the minimum number possible)?
15 The teacher, putting in the journal quarter marks in biology for the third quarter (3, 4, 5), drew attention to the fact that the combination of three quarter marks in this subject is different for all students. What is the maximum number of students in this class?
16 Some alphabet contains four different characters. How many words exactly 4 characters long can be made from words of a given alphabet (characters in a word can be repeated)?
17 The 2x2 square light board consists of luminous elements, each of which can glow in one of four different colors. How many different signals can be transmitted using a display consisting of four such elements (provided that all elements must be lit)?
18 The light board consists of luminous elements, each of which can glow in one of eight different colors. How many different signals can be transmitted using a display consisting of three such elements (provided that all elements must be lit)?
