Each memory cell of a computer operating in the ternary number system 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 quantity take?
Solution:
Another example task:
The school database stores records containing information about students:
<Фамилия>
<Имя>- 12 characters: Russian letters (the first is capital, the rest are lowercase),
<Отчество>- 16 characters: Russian letters (the first is capital, the rest are lowercase),
<Год рождения>– numbers from 1992 to 2003.
Each field is written using the minimum possible number of bits. Determine the minimum number of bytes required to encode a single 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 sizes in bits for each of the four fields and add them;
important! it is known that the first letters of the first name, patronymic and last name are always uppercase, so you can store them in lowercase and make them uppercase only when displayed on the screen (but we don’t care about this anymore)
thus, for character fields, it is enough to use an alphabet of 32 characters (Russian lowercase letters, "e" and "ё" are the same, spaces are not needed)
to encode each character of the 32-character alphabet, 5 bits are needed (32 = 2555 5), so to store the first name, middle name and last name, you need (16 + 12 + 16) 5 = 220 bits
there are 12 options for the year of birth, so 4 bits must be allocated for it (2 4 = 16 ≥ 12)
thus a total of 224 bits or 28 bytes are required
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 "flashing"). What is the minimum number of light bulbs that must be on the scoreboard so that it can be used 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 smallest possible number of 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
An ordinary 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 unit plays back the recorded signals in sequence. 100 traffic lights were recorded in a row. In bytes, this information volume is
1) 37 2) 38 3) 50 4) 100
(The condition is incorrect, meaning the number of whole bytes.)
How many different sequences of plus and minus characters 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 chess field?
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 more information is there in the second text 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 field. How much information did the second player get 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 the characters are taken from a table of size 16 by 32. Determine the information volume of the text in bits.
1) 1000 2) 2400 3) 3600 4) 5400
The capacity of the alphabet is 256. How many KBytes of memory would be required 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
12 special symbols are used to encode the secret message. In this case, the characters are encoded with the same minimum possible number of bits. What is the information volume of a message with a length of 256 characters?
1) 256 bits 2) 400 bits 3) 56 bytes 4) 128 bytes
The capacity of the alphabet is 64. How many KBytes of memory would be required to store 128 pages of text with an average of 256 characters per page?
1) 8 2) 12 3) 244)36
To encode music notation, 7 note icons are used. Each note is encoded with the same minimum possible 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
There are 8 black balls and 24 white balls in a basket. How many bits of information does the message that the black ball has been drawn carry?
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 the quarter, Vasily Pupkin received 20 marks. The message that he received a four yesterday carries 2 bits of information. How many fours did Vasily get in a quarter?
1) 2 2) 4 3) 5 4) 10
The basket contains black and white balls. There are 18 black balls among them. The message that the white ball has been drawn carries 2 bits of information. How many balls are in the basket?
1) 18 2) 24 3) 36 4) 48
There are 32 pencils in a closed box, some of them are blue. One pencil is drawn at random. The message "this pencil is NOT blue" carries 4 bits of information. How many blue pencils are in the box?
1) 16 2) 24 3) 30 4) 32
Some alphabet contains 4 different characters. 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 made up of capital letters (12 letters in total) and decimal digits in any order. Each character is encoded with the same and 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 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 panel consists of luminous elements, each of which can be lit in one of three different colors. How many different signals can be transmitted using a scoreboard consisting of four such elements (assuming that all elements must be lit)?
1) 4 2) 16 3) 64 4) 81
In some country, a 6-character license plate is made up of capital letters (19 letters in total) and decimal digits in any order. Each character is encoded with the same and 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 40 license plates.
1) 120 bytes 2) 160 bytes 3) 200 bytes 4) 240 bytes
In some country, a 6-character license plate is made up of capital letters (26 letters in total) and decimal digits in any order. Each character is encoded with the same and 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 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, hung out in one line (the sequence is important). How many different signals can a ship send using four signal flags if the ship has three different types of flags (an unlimited number of flags of each type)?
To transmit signals in the fleet, special signal flags are used, hung out 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 (an unlimited number of flags of each type)?
678 athletes participate in cyclocross. A special device registers the passage of each of the participants of the intermediate finish, recording its 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 line?
1) 200 bits 2) 200 bytes 3) 220 bytes 4) 250 bytes
In some country, a 7-character license plate is made up of capital letters (18 letters in total) and decimal digits in any order. Each character is encoded with the same and 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 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 four-second messages can be sent using this device?
The database stores records containing information about dates. Each entry contains three fields: the year (a number from 1 to 2100), the number of the month (a number from 1 to 12), and the number of the day in the month (a number from 1 to 31). Each field is written separately from other fields using the minimum 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. This they do by turning on one flashlight for the same short amount of time in a certain sequence. The number of flashes in one message is 3 or 4, between messages there are pauses. How many different messages can boys send?
5 successive bursts of color are used to encode 300 different messages. Flashes of the same duration, each flash uses one bulb of a certain color. How many colors of light bulbs should be used in the 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 visited cells. What is the amount of information after 11 moves made? (The solution starts 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 visited cells. What is the amount of information after 15 moves? (The solution starts 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 grades in biology for the third quarter (3, 4, 5), noticed that the combination of three quarter grades in this subject is different for all students. What is the maximum number of students in this class?
Some alphabet contains four different characters. How many words exactly 4 characters long can be made from the words of the given alphabet (characters in a word can be repeated)?
In a certain country, a 10-character license plate is made up of capital letters (21 letters in total) and decimal digits in any order. Each character is encoded with the same and 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 81 license plates.
1) 810 bytes 2) 567 bytes 3) 486 bytes 4) 324 bytes
The 2x2 square light panel consists of luminous elements, each of which can light up in one of four different colors. How many different signals can be transmitted using a scoreboard consisting of four such elements (assuming that all elements must be lit)?
The light panel consists of luminous elements, each of which can be lit in one of eight different colors. How many different signals can be transmitted using a scoreboard consisting of three such elements (assuming that all elements must be lit)?
In some country, a 5-character license plate is made up of capital letters (30 letters in total) and decimal digits in any order. Each character is encoded with the same and 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 50 license plates.
1) 100 bytes 2) 150 bytes 3) 200 bytes 4) 250 bytes
In a certain country, a 7-character license plate is made up of capital letters (30 letters in total) and decimal digits in any order. Each character is encoded with the same and 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 32 license plates.
1) 160 bytes 2) 96 bytes 3) 224 bytes 4) 192 bytes
In some country, a 5-character license plate is made up of capital letters (26 letters in total) and decimal digits in any order. Each character is encoded with the same and 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 40 license plates.
1) 160 bytes 2) 200 bytes 3) 120 bytes 4) 80 bytes
In some country, a 7-character car number is made up of capital letters (22 letters in total) and decimal digits in any order. Each character is encoded with the same and 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 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 painted in four colors: white, black, yellow and red. What is the minimum number of light bulbs that must be on the scoreboard so that it can transmit 300 different signals?
1) 4 2) 5 3) 6 4) 7
One ternary computer memory location (one trite) 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 assigned. How many different values can this quantity take?
1) 8 2) 16 3) 64 4) 81
The message size is 11 KB. The message contains 11264 characters. What is the maximum cardinality of the alphabet used in the transmission of the message?
1) 64 2) 128 3) 256 4) 512
There are 1,000 people in a certain country. Individual Taxpayer Numbers (TINs) contain only the digits 0, 1, 2, and 3. What should be the minimum TIN length if all residents have different numbers?
There are 200 people in a certain country. Individual Taxpayer Numbers (TINs) contain only the digits 2, 4, 6, and 8. What should be the minimum TIN length if all residents have different numbers?
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 be sent, exactly 3 missiles launched?
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 3 s messages can be sent using this device?
To transmit signals in the fleet, special signal flags are used, hung out in one line (the sequence is important). How many different types of flags must be present in order to send 8 different signals 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 recorded in the school information system using a minimum number of bits. What is the information volume of the message about the codes of 320 students present at the conference?
1) 2560 bits 2) 100 bytes 3) 6400 bits 4) 400 bytes
In some country, the car number consists of 8 characters. The first character is one of 26 Latin letters, the remaining seven are decimal digits. An example number is 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 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 styles - lowercase and uppercase. Each character is encoded with the same and the 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 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 styles - lowercase and uppercase. Each character is encoded with the same and the 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 exactly 11 characters long. The password can use decimal digits and 32 different characters of the local alphabet, and all letters are used in two styles - lowercase and uppercase. Each character is encoded with the same and the 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 are denoted by “KB”, and megabytes are denoted by “MB”, but in the demo tests, the developers of the Unified State Exam cited just such designations.
2In fact, this is not a different way of solving, but a more rigorous justification of the previous algorithm.
3Quest sources:
Demonstration versions of the Unified State Examination 2004-2011.
Guseva I.Yu. USE. Informatics: handout of training tests. - St. Petersburg: Trigon, 2009.
Yakushkin P.A., Leshchiner V.R., Kirienko D.P. USE 2010. Informatics. Typical test tasks. - M.: Exam, 2010.
Krylov S.S., Ushakov D.M. USE 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 Unified State Examination 2010. Informatics. - M.: Astrel, 2009.
Abramyan M.E., Mikhalkovich S.S., Rusanova Ya.M., Cherdyntseva M.I. Informatics. USE step by step. - M.: Research Institute of School Technologies, 2010.
Churkina T.E. USE 2011. Informatics. Thematic training tasks. - M.: Eksmo, 2010.
Krylov S.S., Leshchiner V.R., Yakushkin P.A. USE 2011. Informatics. Universal materials for preparing students. - M.: Intellect-center, 2011.
When recoding information into a binary code, it becomes necessary to determine the amount of information (amount of information) necessary to store this type of information.
One bit can be expressed (encoded) two concepts:
If the number of bits is increased to two, then four different events can be encoded:
Three bits can encode eight different events:
By increasing the number of digits in the binary code by one, the number of encoded events is doubled.
What does the formula describe:
N=2 i ,
where N is the number of independent encoded events;
i - bit depth of the binary code.
Powers of two reflect the number of events N, encoded with i[BIT]:
N, events |
Task 1
The light board consists of light bulbs. Each light bulb can be in one of two states (“on”, “off”). What is the minimum number of light bulbs that must be on the scoreboard so that it can be used to transmit 18 different signals?Task 2
The light board consists of light bulbs. Each light can be in one of three states (“on”, “off”, “blinking”). What is the minimum number of light bulbs that must be on the scoreboard so that it can be used to transmit 18 different signals?for N=18 it will be 27
from which it follows that i = 3.
Answer: 3 bulbs.
Task 3
119 athletes participate in cyclocross. A special device registers the passage of each of the participants of the intermediate finish, recording its 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 line?Task 4
In some country, a 7-character license plate is made up of capital letters (26 letters in total) and decimal digits in any order. Each character is encoded with the same and 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 20 license plates.Task 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 smallest possible number of 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 12 special symbols are used to encode the secret message. In this case, the characters are encoded with the same minimum possible number of bits. What is the information volume of a message with a length of 256 characters?
4 7 note icons are used to encode music notation. Each note is encoded with the same minimum possible number of bits. What is the information volume of a message consisting of 180 notes?
5 Cyclocross has 678 athletes. A special device registers the passage of each of the participants of the intermediate finish, recording its 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 line?
6 In some country, a 6-character license plate is made up of capital letters (12 letters in total) and decimal digits in any order. Each character is encoded with the same and 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 32 license plates.
7 How many different sequences of plus and minus characters are there exactly five characters long?
8 Some alphabet contains 4 different characters. 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 panel consists of luminous elements, each of which can light up in one of three different colors. How many different signals can be transmitted using a scoreboard consisting of four such elements (assuming that all elements must be lit)?
10 For the transmission of signals in the fleet, special signal flags are used, hung out in one line (the sequence is important). How many different signals can a ship send using four signal flags if the ship has three different types of flags (an unlimited number of flags of each type)?
11 For the transmission of signals in the fleet, special signal flags are used, hung out 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 (an unlimited number of flags of each type)?
12 Some signaling device transmits one of three signals in one second. How many different four-second messages can be sent with this device.
13 Vasya and Petya are passing messages to each other using blue, red and green flashlights. This they do by turning on one flashlight for the same short amount of time in a certain sequence. The number of flashes in one message is 3 or 4, between messages there are pauses. How many different messages can boys send?
14 5 successive flashes of color are used to encode 300 different messages. Flashes of the same duration, each flash uses one bulb of a certain color. How many colors of light bulbs should be used in the transmission (specify the minimum number possible)?
15 The teacher, putting in the journal quarter grades in biology for the third quarter (3, 4, 5), noticed that the combination of three quarter grades 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 the words of the given alphabet (characters in a word can be repeated)?
17 The 2x2 square light panel consists of luminous elements, each of which can light up in one of four different colors. How many different signals can be transmitted using a scoreboard consisting of four such elements (assuming that all elements must be lit)?
18 The light panel consists of luminous elements, each of which can be lit in one of eight different colors. How many different signals can be transmitted using a scoreboard consisting of three such elements (assuming that all elements must be lit)?
13th task: "Amount of information"
Difficulty level - advanced,
Maximum score - 1,
Approximate execution time - 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
various characters
(according to the formula Q = 2 N)
Solution 13 of the USE task in informatics (K. Polyakov, v. 6):
The power of the alphabet is 256 . How many KBytes of memory is 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 KB
Solution 13 of the USE task in informatics (K. Polyakov, v. 3):
The two texts contain the same number of characters. The first text is in alphabetical order 16 characters, and the second text is in the alphabet from 256 characters.
How many times more information is there in the second text than in the first?
Answer: 2
✍ Show solution:
- Formula needed Q = 2n
- Let's calculate the required number of bits to store one character for both texts:
Working with various systems
USE 2017 collection of D.M. Ushakov "10 training options ..." option 1:
The cable network holds a vote among viewers on which of the four films they would like to watch tonight. The cable network is used 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 numbers of the four movies are stored in the computer system, we can find the number of bits needed to store the movie number:
USE 2017 collection of D.M. Ushakov "10 training options ..." option 10:
Rehearsal exam at school 105 human. Each of them is given a special number that identifies him in the automatic system for checking answers. 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 USE task in informatics (K. Polyakov, v. 17):
The database stores records containing information about dates. Each entry contains three fields: year (number from 1 to 2100), month number (day 1 to 12) and the number of the day in the month (number from 1 to 31). Each field is written separately from other fields using the minimum possible number of bits.
Determine the minimum number of bits required to encode one record.
Answer: 21
✍ Show solution:
- Formula needed Q = 2n.
- Let's calculate the required number of bits to store each item of the entire record:
Solution 13 of the USE task in informatics (control version No. 1 of the examination paper, Simulator 2018, S.S. Krylov, D.M. Ushakov):
Rehearsal exam passed 9
flows by 100
person in everyone. Each of them is allocated a special code consisting of a stream number and a number in the stream. In 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 number is used. bytes.
What is the amount of information in bytes written by the device after registration 80
participants?
Answer: 160
✍ Show solution:
- The code consists of two components: 1. stream number (in bits) and 2. sequence number (in bits). Find the number of bits needed to store them:
Computer systems and license plates
Solution 13 of the USE task in informatics (K. Polyakov, v. 33):
The car number consists of several letters (the number of letters is the same in all numbers), followed by three digits. At the same time, they use 10 digits but only 5 letters: N, O, M, E and R. Must have at least 100 000 various numbers.
What is the minimum number of letters that should be in a car number?
Answer: 3
✍ Show solution:
- Formula needed 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, each password is stored with the same and the smallest possible integer byte bit.
Determine the amount of memory ( in bytes) needed to store 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, first you need to find the number of bits required to store 1 character in the password. According to the formula we get:
where Q- the number of character variants that can be encoded using N bit.
Solution 13 of the USE task in computer science (diagnostic version of the examination paper, USE simulator 2018, S.S. Krylov, D.M. Ushakov):
In some country, the license plate consists of 7 characters. Each character can be one of 18 different letters or decimal figure.
Each such number in a computer program is written in the minimum possible and the same integer number. byte, while character-by-character coding is used and each character is encoded by the same and the minimum possible number bit.
Determine the amount of memory in bytes, assigned by this program for recording 50
numbers.
Give your answer only as a number.
Answer: 250
✍ Show solution:
- Since the number can contain either one letter from 18 , or one digit from 10 , then only one of the 28 characters:
USE 2017 collection of 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. In the database for storing information about each user, the same and the smallest possible integer is allocated byte. In this case, character-by-character coding of passwords is used, all characters are encoded in the same and the 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) needed to store information about 30
users.
In the answer, write down only an integer - the number of bytes.
Answer: 600
✍ Show solution:
USE 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 -character alphabet. In the database for storing information about each user, the same and the smallest possible integer is allocated byte. In this case, character-by-character coding of passwords is used, all characters are encoded in the same and the minimum possible number. bit. In addition to its own password, additional information is stored in the system 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:
- Let's decide on a password first. According to the formula Q = M N we get:
Solution 13 of the USE task in informatics (K. Polyakov, v. 58):
When registering in a computer system, each user is given a password consisting of 9 characters. Used as symbols uppercase and lowercase letters of the Latin alphabet (in it 26 characters), as well as decimal digits. The database stores information about each user with the same and the smallest possible integer number of bytes. In this case, character-by-character coding of passwords is used, all characters are encoded with the same and the minimum possible number of bits. In addition to the password itself, additional information is stored in the system for each user, for which 18 bytes per user. Allocated in the computer system 1 Kb to store information about users.
What is the maximum number of users that information can be stored in the system? In your answer, write down only an integer - the number of users.
Answer: 40
✍ Show solution:
- Since both uppercase and lowercase letters are used, we get the total number of character options for encoding:
Above we have considered examples of binary coding 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 with other types of information.
When encoding 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 alphabetically . The number of characters in an 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 is given for converting words from one alphabet to words of another alphabet, then such a conversion process is called coding .
The most common is the binary coding alphabet, consisting of 2 characters 0 and 1. It encodes all the information in the computer.
In general terms, the coding problem is formulated as follows: “There is a certain set of values (data set). Each value must be assigned a binary code that satisfies the following requirements:
· Firstly, all codes must be 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 must be the minimum required to encode all values from the set.
The minimum number of bits required to encode N elements of a 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) statement of problems associated with 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 the demo versions of the exam
E1.1.(2004, A3) The chessboard consists of 64 fields: 8 columns by 8 rows. What is the minimum number of bits required to encode the coordinates of one chess field?
E1.3.(2005, A3) An ordinary 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 unit plays back the recorded signals in sequence. 100 traffic lights were recorded in a row. In bytes, this information volume is
E1.5.(2007, A2) The light panel consists of bulbs, each of which can be in two states (“on” or “off”). What is the minimum number of light bulbs that must be on the scoreboard so that it can 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 content of the message with a length of 150 characters.
E1.9.(2010, A2) In some country, the license plate has 7 characters. The characters are 18 different letters and decimal digits in any order. Each such number in a computer program is written in the minimum possible and the same integer number of bytes, while character-by-character coding is used and all characters are encoded in the same and minimum possible number of bits. Determine the amount of memory that this program allocates for writing 60 numbers.
From the analysis of the demo tasks, it can be concluded that tasks related to coding a data set are included in the USE in computer science 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 data set, and further calculating the information volume of a message. The main difficulty of these tasks lies in the fact that they have a wide variety of specific settings. This is due to the fact that 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
P1.1. For signal transmission, sequences of "+" and "-" signs are used, each 6 characters long. How many different signals can be encoded with them? Choose the correct answer.
Solution
1. First of all, we note that since only 2 characters are used for encoding, we have a binary encoding, and 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. Let's determine how many different binary codes with a length of 6 bits can be composed. To do this, we use the formula N = 2K, where K=6. Therefore, N = 64.
Let's use this example to explain why 64 different combinations of binary codes can be made from 6 bits. The largest binary number of 6 bits is 1111112. If you translate this number into decimal code, you get the number
1x26 + 1x25 + 1x24 + 1x23 + 1x22 + 1x21 + 1x20 = 6310
At first glance, it may seem that 63 different binary codes can be composed of 6 bits, starting 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 the number 0000002. In total, 64 different codes can be made in this way.
Answer:
P1.2. For accounting, each student is assigned a binary code of the same length. Is 9 bits enough to encode all the students in a school if there are 1000 students in the school? 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 composed. To do this, we use the formula N = 2K, where K=9. Therefore, N = 512. We found that it is possible to compose 512 binary codes with a length of 9 bits. Obviously, this number is not enough to encode all 1000 students of the school. Choose the correct answer.
2. According to the condition of the problem, 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 ones).
P1.3. To display a number in an electronic clock, a rectangular light panel of 7 oblong light bulbs is used, which are located on it like the number 8, composed of matches. Each light bulb can be in the "on" or "off" state. How many combinations of on and off bulbs are superfluous? Choose the correct answer.
Solution
1. First of all, we note that since the bulbs on the scoreboard can only be in two states, then we have a binary coding, and the combinations of on and off bulbs are similar to binary codes of zeros and ones. Thus, one light bulb on the scoreboard is an analogue of the 1st bit.
2. It is not necessary to imagine how the number 8 can be added from 7 matches, although indeed such electronic scoreboards are quite common, not only in watches, but also in other electronic devices.
3. From 7 light bulbs, 27 = 128 different light signals can be made. And for highlighting the number, only 10 light signals are needed.
4. Consequently, 128 - 10 = 118 light signals will be unused.
Answer: 4 (4th option from the proposed).
P1.4. The light panel consists of bulbs, each of which can be in two states ("on", "off"). What is the minimum number of light bulbs that must be on the scoreboard so that it can transmit 20 different signals? Choose the correct answer.
Solution
1. Just as in the previous problem, we can consider the light signals of the display as binary codes. However, the formulation of 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, 5 light bulbs are needed to encode 20 signals.
Answer: 1 (1st option from the proposed ones).
P1.5. The following data encoded in binary code is applied to the magnetic card for passing through the turnstile in the metro: the date of purchase of the card, the number of trips and the number of the tariff plan, which reflects the features of using the card. The date encodes the day, month and the last two digits of the year separately. The metro uses 8 different tariff plans. A maximum of 60 trips can be entered on the card. Each information element is encoded with the minimum required number of bits. Calculate in bits the information volume of the 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, tariff plan and number of trips. There can be a maximum of 31 days in a month.
2. We choose a power of 2 greater than 31, but the closest to this number is 32=25. Therefore, to encode, therefore, 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, you cannot 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 must clearly know how many bits each individual data element occupies. So, if in this task we count the total number of values to be encoded, then we get 213. To encode 213 values, 8 bits are enough, but the codes obtained in this way will not allow us to select individual data elements.
4. In the bottom row of the table, the information volume of data on the magnetic card is calculated - 25 bits.
Answer: 3 (3rd option from the proposed ones).
P1.6. To pass the exam in computer science, groups of 30 people or less are formed. Each participant in the exam 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 \u003d 32 is the degree closest 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. In total, you can score 40 points. The nearest but greater 40 power of 2 is 26=64. Therefore, we will use a 6-bit code to encode the points scored.
3. The data of one participant in the electronic statement takes 5+6=11 bits.
4. In total, 16 people came to the exam, so 11 * 16 = 176 bits were entered into the statement.
Answer:
P1.7. 16 teams participate in the Russian Football Championship in the Premier League. Each team during the season plays with each team 2 times - once at home and 1 time at the opponent's field. The results of the match are entered into the file - the date (day and month are coded separately, the year is not coded), binary codes of the teams of participants and 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 the 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 degree of 2 closest to 16 (or equal). This will be the number 16=24. Therefore, 4 bits are needed to encode a 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 heads, it allocates 1 byte for each command, i.e. 8 bits. All you need to add
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 for the number of goals of one team);
8 bits (code for the number of goals of the other team).
Thus, one record occupies 33 bits.
4. Determine how many matches the teams play in the season. It is convenient to attach a grid of matches, 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. Cells that are not filled in are highlighted in gray, because the team does not play with itself.
The table has 16 columns and 16 rows with the results of the matches minus the filled cells - there are also 16 of them.
Thus, the total number of matches for the season is 16 * 16 - 16 = 256 - 16 = 240.
120 matches are played in half of the season.
5. The information volume of the file with the results after 120 played matches is 120 * 33 (bits). To convert to bytes, this number must be divided by * 33 / 8 = 15 * 33 = 495 bytes.
Answer: 2 (2nd option from the proposed ones).
Tasks for independent solution
C1.5. 1 byte is used to encode characters in ASCII encoding. How many characters (power of the alphabet) can be encoded in 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 KB. Choose the correct answer.
C1.11. To encode information, only Russian lowercase letters were used. What is the information volume in bytes of a message consisting of 16 characters? Choose the correct answer.
C1.13. For communication, the Mumbo Yumbo tribe uses a language containing 24 basic concepts and 3 bundles (ok) that allow you to connect these concepts. Messages are transmitted with the help of drum beats in portions: concept + bundle. All concepts are encoded with the same number of strokes and ligaments are encoded with the same number of strokes. How many drum beats are used in each message portion?
C1.14. For communication in the language of the Mumbo-Yumbo tribe, 13 basic concepts and 4 bundles are used to connect these concepts. To transmit messages, the tribe uses a binary code: a combination of voiced and deaf sounds of the drum. Messages are transmitted in portions - concept + bundle. How many beats will it take to encode each portion of the message?
