Trial versions of the exam informatics. B5: encoding and decoding

SPECIFICATION
control measuring materials
a single state examination 2016 year
in informatics and ICT

1. Purpose of KIM USE

The Unified State Exam (hereinafter - the Unified State Exam) is a form of objective assessment of the quality of training of persons who have mastered educational programs middle general education, using tasks of a standardized form (control measuring materials).

The Unified State Exam is conducted in accordance with Federal Law No. 273-FZ of December 29, 2012 “On Education in the Russian Federation”.

Control measuring materials allow you to establish the level of development of graduates of the Federal component state standard secondary (complete) general education in computer science and ICT, basic and profile levels.

The results of the unified state exam in computer science and ICT are recognized educational organizations middle vocational education and educational organizations of higher professional education as the results of entrance examinations in computer science and ICT.

2. Documents defining the content of the KIM USE

3. Approaches to the selection of content, the development of the structure of the KIM USE

The content of the assignments was developed on the main topics of the course of computer science and ICT, combined into the following thematic blocks: "Information and its coding", "Modeling and computer experiment", "Numeral systems", "Logic and algorithms", "Elements of the theory of algorithms", "Programming "," Architecture of computers and computer networks "," Processing numerical information"," Technologies of information retrieval and storage ".
Content examination work the main content of the informatics and ICT course, its most important topics, the most significant material in them, which is unambiguously interpreted in most of the options for the informatics and ICT course taught at school, is covered.

The work contains both tasks of the basic level of complexity, testing the knowledge and skills provided for by the standard of the basic level, as well as
and tasks of increased and high levels of complexity, testing the knowledge and skills provided by the standard profile level... The number of tasks in the KIM version should, on the one hand, ensure a comprehensive check of the knowledge and skills of graduates acquired during the entire period of study in the subject, and, on the other hand, meet the criteria of complexity, sustainability of results, and measurement reliability. For this purpose, KIM uses two types of tasks: with a short answer and a detailed answer. The structure of the examination paper provides an optimal balance of assignments of different types and varieties, three levels of complexity, testing knowledge and skills at three different levels: reproduction, application in a standard situation, application in a new situation. The content of the examination paper reflects a significant part of the content of the subject. All this ensures the validity of the test results and the reliability of the measurement.

4. The structure of the KIM USE

Each version of the examination paper consists of two parts and includes 27 tasks that differ in form and level of difficulty.

Part 1 contains 23 tasks with a short answer.

In the examination paper, the following types of tasks with a short answer are proposed:

tasks for choosing and recording one or more correct answers from the proposed list of answers;
tasks for calculating a certain value;
tasks to establish the correct sequence, represented as a string of characters according to a certain algorithm.

The answer to the tasks of Part 1 is given by the corresponding entry in the form of a natural number or a sequence of symbols (letters and numbers), written without spaces and other separators.

Part 2 contains 4 tasks with a detailed answer.

Part 1 contains 23 tasks of basic, advanced and high difficulty levels. This part contains tasks with a short answer, implying an independent formulation and recording of an answer in the form of a number or a sequence of characters. The tasks check the material of all thematic blocks. In part 1, 12 tasks refer to basic level, 10 tasks for the increased difficulty level, 1 task for the high difficulty level.

Part 2 contains 4 tasks, the first of which is of increased difficulty level, the remaining 3 tasks high level difficulties. The tasks of this part involve writing a detailed answer in any form.

K.Yu. Polyakov
Unified State Exam in Informatics:
2016 and beyond ...
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

Structural changes in 2015-2016

2
Structural changes in 2015-2016
1) removal of part A
2) reducing the number of tasks
3) unification simple tasks (4, 6, 7, 9)
Goal: Leave more time to solve
difficult tasks.
4) Python language
!
K.Yu. Polyakov, 2015
Variability!
http://kpolyakov.spb.ru

Unified State Exam in Informatics: 2016 and beyond ...
3

How many units are in binary notation
hexadecimal number 12F016.
1
2
12 102
F
11112
0
1+1+4=6
Specify the smallest number whose binary notation
contains exactly three significant zeros and three ones.
Write the answer in decimal notation
1000112 = 35
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B1: binary number system

Unified State Exam in Informatics: 2016 and beyond ...
4
B1: binary number system

number 1025
1) "on the forehead" - translate ...
2) 1025 = 1024 + 1
1024 = 100000000002
1025 = 100000000012
Answer: 2
511?
511 = 512 - 1
= 10000000002 - 1 = 1111111112
Answer: 9
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B1: binary number system

Unified State Exam in Informatics: 2016 and beyond ...
5
B1: binary number system
How many units are in binary notation decimal
number 999?
1) "on the forehead" - translate ...
2) 999 = 1023 – 16 – 8
1023 = 1024 – 1 = 11111111112
minus two units: 8
519?
519 = 512 + 7
512 = 10000000002
7 = 1112
plus three units: 4
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B1: number systems

Unified State Exam in Informatics: 2016 and beyond ...
6
B1: number systems
Which of the following numbers can be written in
binary number system in the form 1xxx10, where x can
mean both 0 and 1?
1) 74
2) 38
3) 60
4) 47
1) 1000102 \u003d 34 N 1111102 \u003d 62
2) 1xxx10 is divisible by 2
3) 1xxx10 is not divisible by 4
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B2: logic functions

Unified State Exam in Informatics: 2016 and beyond ...
7
B2: logic functions
x1
1
!
x2
0
x3
x4
0
1
x5
x6
x7
x8
1
1
F
0
1
1
All options are simple AND or OR!
1) "on the forehead" - to substitute in the formulas ...
2) if all "OR" is one zero
check the line where F \u003d 0
x2 without inversion, x8 with inversion
3) if all "I" are one unit
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B2: logic functions

Unified State Exam in Informatics: 2016 and beyond ...
8
B2: logic functions
The table of the function z x x

? z
0
0
0
0
1
1
1
1
? y
0
0
1
1
0
0
1
1
K.Yu. Polyakov, 2015
? x
0
1
0
1
0
1
0
1
F
0
1
0
1
0
0
0
1
y.
z x x y
x (z y)
x 0 F 0
x 1
z 1
F 0
y 0
Answer: zyx
http://kpolyakov.spb.ru

B2: logic functions

Unified State Exam in Informatics: 2016 and beyond ...
9
B2: logic functions
A table of the function x y z x
Determine which columns are x, y, and z.
? z
0
0
0
0
1
1
1
1
? x
0
0
1
1
0
0
1
1
K.Yu. Polyakov, 2015
? y
0
1
0
1
0
1
0
1
F
0
0
1
0
1
1
1
1
y z.
x y z x y z
z 0 F x y
z 1 F x y x y
(x x) (y x) y
y x y 1
z 0
x 1 Reply: zxy
F 1
y 0
http://kpolyakov.spb.ru

B3: weight matrices of graphs

Unified State Exam in Informatics: 2016 and beyond ...
10
B3: weight matrices of graphs
A
A
B
C
D
E
F
Z
B
4
C
6
3
D
E
F
11
4
5
7
4
Z
30
27
10
8
2
29
1) asymmetric matrix (digraph)
2) two one-way roads
3) “how many roads there are passing through N
points? "
4) "... in at least N points?"
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B3: weight matrices of graphs

Unified State Exam in Informatics: 2016 and beyond ...
11
B3: weight matrices of graphs
1
1
2
2
3
45
4
5
6
6
45
55
3
15 60
2
10 40
15
20 35
4
55
2
55 60 20 55
35
45
45
E
AND
5
2
degree
peaks
K.Yu. Polyakov, 2015
D
2
40
7
B
7
10
3
4
5
TO
IN
degree 4
degree 5
D
Answer: 20
http://kpolyakov.spb.ru

B4-1: Tabular Databases

Unified State Exam in Informatics: 2016 and beyond ...
12
B4-1: Tabular Databases
1) how many descendants (children, grandchildren, great-grandchildren ...) does X have?
2) how many ancestors of X are there in the table?
3) find your maternal grandfather
23
24
25
K.Yu. Polyakov, 2015
34
57
35
42
http://kpolyakov.spb.ru

Unified State Exam in Informatics: 2016 and beyond ...
13

Messages contain letters P, O, S, T; used by
unambiguous binary
decoding. Code words:
T: 111, O: 0, P: 100.
Specify the shortest code word for the letter C, if
where the code will allow an unambiguous
decoding. If there are several such codes, specify
the code with the smallest numerical value.
1
0
0x 10
0xx
ABOUT
11
101
P
K.Yu. Polyakov, 2015
0
0
110
1
1
1
0
1
T
http://kpolyakov.spb.ru

B5: encoding and decoding

Unified State Exam in Informatics: 2016 and beyond ...
14
B5: encoding and decoding
Messages contain three vowels: A, E, I - and five
consonant letters: B, C, D, D, K. Letters are encoded
prefix code. It is known that all codewords for
consonants have the same length, and
A –1, E - 01, I - 001.
What is the smallest possible length of codewords for
consonant letters?
0
5 consonants 3 bits 4 bits 5 bits
4: 1xx
0
1
2: 01x
0
1
AND
1: 001
1
E
available: 000
000x 000xx
1
2
4
AND
K.Yu. Polyakov, 2015
6 bit
000xxx
8
http://kpolyakov.spb.ru

B6-1: automatic

Unified State Exam in Informatics: 2016 and beyond ...
15
B6-1: automatic
parity restored!
Input: natural number N.
1. The parity bit is appended to the end of the binary record
(sum of digits mod 2).
2. Another parity bit is added to the resulting string.
Specify the smallest number for which the result
execution of this algorithm will give the number
more than 125.
!
In step 2, 0 2 is added!
Should get even \u003d 126 or 128
Parity should be preserved after div 2!
126/2 \u003d 63 \u003d 1111112: - 6 units, parity
Answer:
K.Yu. Polyakov, 2015
31
http://kpolyakov.spb.ru

B10: combinatorics

Unified State Exam in Informatics: 2016 and beyond ...
16
B10: combinatorics
How many 5-letter words there are only
letters P, I, R, and the letter P appears exactly 1 time.
P****
*P***
**P**
***P*
****P
K.Yu. Polyakov, 2015
24 \u003d 16 words
Answer: 16 5 \u003d 80.
http://kpolyakov.spb.ru

B12: addressing in networks

Unified State Exam in Informatics: 2016 and beyond ...
17
B12: addressing in networks
IP address 224.128.112.142
The network address is 224.128.64.0.
What is the third byte from the left of the mask?
don't forget about
*.*.112.*
senior units!
*.*.64.0
mask: 110000002 \u003d 192
192
112 = 011100002
64 = 010000002
!
K.Yu. Polyakov, 2015
Bitwise conjunction!
http://kpolyakov.spb.ru

B12: addressing in networks

Unified State Exam in Informatics: 2016 and beyond ...
18
B12: addressing in networks
IP address 111.81.208.27
The network address is 111.81.192.0.
What is the minimum value of the third from the left
byte mask?
*.*.208.*
*.*.192.0
208 =
192 =
mask:
mask:
110100002
110000002
111000002
110000002
192
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B14: Draftsman

Unified State Exam in Informatics: 2016 and beyond ...
19
B14: Draftsman
move by (–3, –3) 1)
REPEAT N TIMES
2)
shift by (a, b) 3)
shift by (27, 12) 4)
END REPEAT
move by (-22, -7)
3 N x 22 0
3 N y 7 0
smallest N\u003e 1
greatest N
all possible N
sum of all N
N x 25
N y 10
N \u003d common divisor (25,10)
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B14: Editor

Unified State Exam in Informatics: 2016 and beyond ...
20
B14: Editor
1) replace (v, w)
2) found (v)
WHILE found (222) OR found (888)
IF found (222)
THEN replace (222, 8)
ELSE replace (888, 2)
What is the result of processing line 88888 ... 8?
888888888…8
2 2 2
8
K.Yu. Polyakov, 2015
!
In 4 steps
removed
8 eights!
68 - 8 8 \u003d 4
68
8888 28
http://kpolyakov.spb.ru

Unified State Exam in Informatics: 2016 and beyond ...
21

city \u200b\u200bA to city L not passing through B?
D
B
F
IN
AND
D
K.Yu. Polyakov, 2015
AND
E
L
TO
http://kpolyakov.spb.ru

B15: number of paths in graphs

Unified State Exam in Informatics: 2016 and beyond ...
22
B15: number of paths in graphs
How many different paths are there from
city \u200b\u200bA to city L passing through D?
D
B
F
IN
AND
D
K.Yu. Polyakov, 2015
AND
E
L
TO
http://kpolyakov.spb.ru

B16: number systems

Unified State Exam in Informatics: 2016 and beyond ...
23
B16: number systems
How many ones are in binary
(ternary, ...) notation of the number X?
10N \u003d 100 ... 0
10N-1 \u003d 99 ... 9
N
N
2N \u003d 100 ... 02
N
3N \u003d 100 ... 03
N
K.Yu. Polyakov, 2015
2N-1 \u003d 11 ... 1
N
3N-1 \u003d 22 ... 2
N
http://kpolyakov.spb.ru

B16: number systems

Unified State Exam in Informatics: 2016 and beyond ...
24
B16: number systems
2N - 2M \u003d 2M (2N-M - 1)
\u003d 100 ... 02 11 ... 12
N-M
M
= 11…100…02
N-M
K.Yu. Polyakov, 2015
M
http://kpolyakov.spb.ru

B16: number systems

Unified State Exam in Informatics: 2016 and beyond ...
25
B16: number systems

numbers (24400–1) · (42200 + 2)?
(24400–1) · (42200 + 2) \u003d (24400–1) · (24400 + 1 + 1)
\u003d (24400–1) · (24400 + 1) + 24400–1
= 28800 – 1 + 24400–1
= 28800 + 24400 – 21
1
4399
1 + 4399 = 4400
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B16: number systems

Unified State Exam in Informatics: 2016 and beyond ...
27
B16: number systems
How many units are in a binary notation
values \u200b\u200bof the number 8148 - 4123 + 2654 - 17?
8148 = 2444
4123 = 2246
2654
17 = 16 + 1
= 24 + 2 0
2654 + 2444 – 2246 – 24 – 20
444 – 2246 – 24 – 20
2
1
444 – 2
1 + 444 – 2 = 443
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B16: number systems

Unified State Exam in Informatics: 2016 and beyond ...
28
B16: number systems
How many twos are in a ternary notation
values \u200b\u200bof the number 9118 + 3123 - 27?
9118 = 3236
27 = 33
K.Yu. Polyakov, 2015
3236 + 3123 – 33
1
120 twos
http://kpolyakov.spb.ru

B16: number systems

Unified State Exam in Informatics: 2016 and beyond ...
29
B17: queries in search engines
Inquiry
USA | Japan | China
Japan | China
(USA & Japan) | (USA & China)
USA
A \u003d USA
Inquiry
A | B
B
A & B
A
Pages
450
260
50
?
B \u003d Japan | China
Pages
450
260
50
?
A
A&B
B
NА | B \u003d NA + NB - NA & B
NA \u003d 450 - 260 + 50 \u003d 240
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B17: queries in search engines

Unified State Exam in Informatics: 2016 and beyond ...
30
P \u003d and Q \u003d. Indicate the smallest
the possible length of a segment A such that the expression
(x P) (((x Q) (x A)) (x P))
is identically true, that is, equal to 1 for any
the value of the variable x.
P (x P),
Q (x Q),
A (x A)
P (Q A P)
P (Q A P)
P Q A P P Q A
P Q A
P
Q
K.Yu. Polyakov, 2015
P
37
40
60
77
x
20
Q
http://kpolyakov.spb.ru

B18: logical operations, sets

Unified State Exam in Informatics: 2016 and beyond ...
31

Set A: integers... Expression
(x (2, 4, 6, 8, 10, 12)) → (((x (4, 8, 12, 116))
¬ (x A)) → ¬ (x (2, 4, 6, 8, 10, 12)))
is true for any value of x. Define
smallest possible sum of elements
the set A.
P x (2, 4, 6, 8, 10, 12),
Q x (4, 8, 12, 116),
A x A
P (Q A P)
P Q A
Amin P Q P Q (4, 8, 12)
K.Yu. Polyakov, 2015
= 24
http://kpolyakov.spb.ru

B18: logical operations, sets

Unified State Exam in Informatics: 2016 and beyond ...
32
B18: logical operations, sets

(x & 49<> 0) ((x & 33 \u003d 0) (x & A<> 0))

P x & 49 0,
A x & A 0
P (Q A)
Q x & 33 0,
P (Q A) P Q A
P Q A (P Q) A
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B18: logical operations, sets

Unified State Exam in Informatics: 2016 and beyond ...
33
B18: logical operations, sets
"&" - bitwise conjunction (AND). Expression
(x & 49<> 0) ((x & 33 \u003d 0) (x & A<> 0))
true for any natural x. Define
smallest possible A.
x & 49
bit number
5 4 3 2 1 0
49 = 110001
X \u003d abcdef
X & 49 \u003d ab000f
x & 49 \u003d 0 all bits (5, 4, 0) are zero
x & 49<>
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B18: logical operations, sets

Unified State Exam in Informatics: 2016 and beyond ...
34
B18: logical operations, sets
"&" - bitwise conjunction (AND). Expression
(x & 49<> 0) ((x & 33 \u003d 0) (x & A<> 0))
true for any natural x. Define
smallest possible A.
(P Q) A
P: x & 49<> 0 among the bits (5, 4, 0) there are nonzero
Q: x & 33 \u003d 0 all bits (5, 0) are zero
bit number
5 4 3 2 1 0
33 = 100001
!
?
Bit 4 is non-zero!
K.Yu. Polyakov, 2015
What follows from this?
Amin \u003d 24 \u003d 16
http://kpolyakov.spb.ru

B18: logical operations, sets

Unified State Exam in Informatics: 2016 and beyond ...
35
B18: logical operations, sets
"&" - bitwise conjunction (AND). Expression
(x & A<> 0) ((x & 20 \u003d 0) (x & 5<> 0))
true for any natural x. Define

P x & 20 0,
A x & A 0
A (P Q)
Q x & 5 0,
A (P Q) A P Q
P Q A (P Q) A
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B18: logical operations, sets

Unified State Exam in Informatics: 2016 and beyond ...
36
B18: logical operations, sets
"&" - bitwise conjunction (AND). Expression
(x & A<> 0) ((x & 20 \u003d 0) (x & 5<> 0))
true for any natural x. Define
highest possible A.
(P Q) A
P: x & 20 \u003d 0 all bits (4, 2) are zero
Q: x & 5 \u003d 0 all bits (2, 0) are zero
!
Bits (4, 2, 0) in x are zero!
Amax \u003d 24 + 22 + 20 \u003d 21
K.Yu. Polyakov, 2015
They will zero out
bits of number
for &!
http://kpolyakov.spb.ru

B18: logical operations, sets

Unified State Exam in Informatics: 2016 and beyond ...
37
B19: processing arrays

c: \u003d 0;
for i: \u003d 1 to 9 do
if A< A[i] then begin
c: \u003d c + 1;
t: \u003d A [i];
permutation of a pair
A [i]: \u003d A; when sorting
A: \u003d t
bubble
end;

K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B19: processing arrays

Unified State Exam in Informatics: 2016 and beyond ...
38
B19: processing arrays
1)
2)
3)
4)
5)
6)
6
9
9
9
9
9
9
9
6
7
7
7
7
7
7
7
6
6
6
6
6
2
2
2
2
2
2
2
1
1
1
5
5
5
5
5
5
5
1
1
1
1
0
0
0
0
3
3
3
3
3
3
3
0
4
4
4
4
4
4
4
0
8
8
8
8
8
8
8
0
c \u003d 6
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B19: processing arrays

Unified State Exam in Informatics: 2016 and beyond ...
39
B19: processing arrays
Array with indices from 0 to 9.
c: \u003d 0;
for i: \u003d 1 to 9 do
if A [i]< A then begin
c: \u003d c + 1;
t: \u003d A [i];
A [i]: \u003d A;
permutation of a pair
A: \u003d t
end;
What value will the variable "c" have?
4 7 3 8 5 0 1 2 9 6
4 7 3 8 5 0 1 2 9 6
4 7 3 8 5 0 1 2 9 6
K.Yu. Polyakov, 2015
c \u003d 2
http://kpolyakov.spb.ru

B19: processing arrays

Unified State Exam in Informatics: 2016 and beyond ...
40
B19: processing arrays

s: \u003d 0;
n: \u003d 10;
for i: \u003d 0 to n-1 do begin
s: \u003d s + A [i] -A
end;

s: \u003d A-A + A-A + A -...
+ A-A + A-A + A-A
max \u003d 999 - 100 \u003d 899
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B19: processing arrays

Unified State Exam in Informatics: 2016 and beyond ...
41
B19: processing arrays
An array with indices from 0 to 10.
s: \u003d 0;
n: \u003d 10;
for i: \u003d 0 to n-2 do begin
s: \u003d s + A [i] -A
end;
The array contained three-digit natural numbers.
What is the greatest meaning of "s"?
s: \u003d A-A + A-A + A -...
+ A-A + A-A + A-A
max \u003d 999 + 999 - 100 - 100 \u003d 1798
1798
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B19: processing arrays

Unified State Exam in Informatics: 2016 and beyond ...
42
B20: loops and conditions ("learn the algorithm")
Specify the smallest five-digit number x for which
will print first 6 and then 3.
a: \u003d 0;
Minimum and maximum!
b: \u003d 10;
readln (x);
while x\u003e 0 do begin
y: \u003d x mod 10;
x: \u003d x div 10;
33336
if y\u003e a then a: \u003d y;
if y< b then b:= y;
end;
writeln (a); (maximum digit)
writeln (b); (minimum digit)
!
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B20: loops and conditions ("learn the algorithm")

Unified State Exam in Informatics: 2016 and beyond ...
43
B20: cycles and conditions
Specify the smallest number x, greater than 100, at which
will print 26.
var x, L, M: integer;
begin
x is odd: gcd (x, 65) \u003d 26
readln (x);
x is even: gcd (x, 52) \u003d 26
L: \u003d x; M: \u003d 65;
if L mod 2 \u003d 0 then x is divisible by 26,
M: \u003d 52;
is not a multiple of 52!
while L<> M do
GCD (104.52) \u003d 52
104
if L\u003e M then
L: \u003d L - M
Answer: 130
else
M: \u003d M - L;
writeln (M);
Euclid's Algorithm!
end.
!
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B20: cycles and conditions

Unified State Exam in Informatics: 2016 and beyond ...
44
B21: cycles and procedures

begin
i
f (i)
f: \u003d n * (n-1) +10
1
10
end;
…
2
12
readln (k);
3
16
i: \u003d 0;
4
22
while f (i)< k do
5
30
36
i: \u003d i + 1;
writeln (i);
6
40
Stop: k<= f(i)
31 … 40
10
K.Yu. Polyakov, 2015
?
For k \u003d 30?
23 … 30
8
http://kpolyakov.spb.ru

B21: cycles and procedures

Unified State Exam in Informatics: 2016 and beyond ...
45
B21: cycles and procedures
Find the number of distinct values \u200b\u200bof k for which
the program gives the same answer as for k \u003d 36.
function f (n: longint): longint;
begin
Stop:
f: \u003d n * (n-1) +10
f (i-1)< k <= f(i)
end;
(i-1) * (i-2) +10< k <= i*(i-1)+10
…
i2-3i + 12< k <= i2-i+10
readln (k);
i: \u003d 0;
i \u003d 6: 30< k <= 40
while f (i)< k do
31 … 40
i: \u003d i + 1;
writeln (i);
Answer: 10
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B21: cycles and procedures

Unified State Exam in Informatics: 2016 and beyond ...
46
B21: cycles and procedures
Find the smallest value of k for which
the program gives the same answer as for k \u003d 10.
def f (n):
Stop:
return n * n * n
f (i-1)< g(k) <= f(i)
def g (n):
(i-1) 3< 2k+3 <= i3
return 2 * n + 3
3 < 23 <= i3
k \u003d 10:
(i-1)
k \u003d int (input ())
i \u003d 3
i \u003d 1
while f (i)< g(k):
8 < 2k+3 <= 27
i + \u003d 1
3 … 12
print (i)
Answer: 3
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

B21: cycles and procedures

Unified State Exam in Informatics: 2016 and beyond ...
47
B22: programs for performers
1) add 1
2) multiply by 2
How many programs are there for which out of 2
the number 29 is obtained and the trajectory of calculations
contains the number 14 and does not contain the number 25?
N is odd
K N 1
Recurrent formula: K N
K N 1 K N / 2 N even
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
1
1
2
2
3
3
5
5
7
7
10
10
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
13
13
13
13
13
13
13
13
13
13
13
0
0
0
13
13
new start
K.Yu. Polyakov, 2015
you can't come here
http://kpolyakov.spb.ru

B22: programs for performers

Unified State Exam in Informatics: 2016 and beyond ...
48
C24: bug fixes
A natural number x is read, you need to find
the number of significant digits in its binary notation.
readln (x);
c: \u003d 0;
while x\u003e 0 do begin
c: \u003d c + x mod 2;
x: \u003d x div 10
end;
writeln (c)
1)
2)
3)
4)
?
?
What counts?
When it works
right?
Only for x \u003d 1
wrong initial value
invalid loop condition
incorrect change of variables
wrong conclusion
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C24: bug fixes

Unified State Exam in Informatics: 2016 and beyond ...
49
C24: bug fixes
You need to write a program that displays
the maximum digit of a number multiple of 3. If the number is not
digits divisible by 3, it is required to display "NO" on the screen.
-1
readln (N);
maxDigit: \u003d N mod 10;
When it works
while N\u003e 0 do begin
right?
digit: \u003d N mod 10;
if digit mod 3 1) \u003d last
0 then digit is divisible by 3
if digit\u003e maxDigit
then
2) last
the figure is less than
maxDigit: \u003d required
digit; result
N: \u003d N div 10;
-1
end;
if maxDigit \u003d 0 then writeln ("NO")
else writeln (maxDigit);
?
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C24: bug fixes

Unified State Exam in Informatics: 2016 and beyond ...
50

For a given sequence of non-negative
whole numbers, you need to find the maximum
the product of its two elements, the numbers of which
differ by at least 8. Number of elements
the sequence does not exceed 10,000.
Problem A (2 points). O (N2) in time, O (N) in memory.
Problem B (3 points). O (N) in time, O (N) in memory.
Problem B (4 points). O (N) in time, O (1) in memory.
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

Unified State Exam in Informatics: 2016 and beyond ...
51
C27: hard programming task
Problem A (2 points). The data is stored in an array.
var N: integer;
a: array of integer;
i, j, max: integer;
begin
readln (N);
for i: \u003d 1 to N do read (a [i]);
max: \u003d -1;
for i: \u003d 9 to N do
for j: \u003d 1 to i-8 do
if (a [j] * a [i]\u003e max) then
max: \u003d a [j] * a [i];
writeln (max)
end.
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C27: hard programming task

Unified State Exam in Informatics: 2016 and beyond ...
52
C27: hard programming task
Problem B (3 points). Data in an array, time O (N).
i-8
i
a [i]
m
accumulate!
max a [j] a [i] max a [j] a [i]
j
j
max: \u003d 0;
m: \u003d 0;
for i: \u003d 9 to N do begin
if a\u003e m then m: \u003d a;
if m * a [i]\u003e max then max: \u003d m * a [i];
end;
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C27: hard programming task

Unified State Exam in Informatics: 2016 and beyond ...
53
C27: hard programming task

i-8
i
we store in an array
var a: array of integer;
x
Initial filling of the array:
for i: \u003d 1 to 8 do read (a [i]);
Promotion:
for i: \u003d 1 to 7 do
a [i]: \u003d a;
a: \u003d x;
K.Yu. Polyakov, 2015
!
It's the turn!
http://kpolyakov.spb.ru

C27: hard programming task

Unified State Exam in Informatics: 2016 and beyond ...
54
C27: hard programming task
Problem B (4 points). Memory O (1), time O (N).
a
x
const d \u003d 8; (shift)
... (already read the first d pieces)
max: \u003d 0;
m: \u003d 0;
for i: \u003d d + 1 to N do begin
read (x);
if a\u003e m then m: \u003d a;
if m * x\u003e max then max: \u003d m * x;
for j: \u003d 1 to d-1 do
a [j]: \u003d a;
a [d]: \u003d x;
end;
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C27: hard programming task

Unified State Exam in Informatics: 2016 and beyond ...
55
C27: hard programming task
Problem B (4 points). No shift (turn-ring).
i 0
1
2
3
9
1
5
6
7
k
0
a
4
10
2 11
3 12
4 5
8
9
N-1
10 11 12 13 14 15 16 17 18
7
6
7
8
a: \u003d data [i];
for i: \u003d 0 to d-1 do read (a [i]);
for i: \u003d d to N-1 do begin
read (x);
k: \u003d i mod d;
if a [k]\u003e m then m: \u003d a [k];
if m * x\u003e max then max: \u003d m * x;
a [k]: \u003d x;
end;
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C27: hard programming task

Unified State Exam in Informatics: 2016 and beyond ...
56
C27: hard programming task
Calculate the maximum even product of two
indications, between the moments of transmission of which
at least 8 minutes have passed.
x
support
1) the maximum of all
2) maximum even
x
even even * any
even any * even
K.Yu. Polyakov, 2015
we store in an array
(turn)
http://kpolyakov.spb.ru

C27: hard programming task

Unified State Exam in Informatics: 2016 and beyond ...
57
C27: hard programming task
for i: \u003d d to N-1 do begin
read (x);
k: \u003d i mod d;
maximum
even
if a [k]\u003e m then m: \u003d a [k];
if ((a [k] mod 2 \u003d 0) and
(a [k]\u003e mEven)) then mEven: \u003d a [k];
if x mod 2 \u003d 1 then begin
received
odd
if mEven * x\u003e max then
max: \u003d mEven * x;
end
received
even
else
if m * x\u003e max then max: \u003d m * x;
a [k]: \u003d x;
end;
K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

C27: hard programming task

Unified State Exam in Informatics: 2016 and beyond ...
58
findings
!
K.Yu. Polyakov, 2015
Variability!
http://kpolyakov.spb.ru

findings

Unified State Exam in Informatics: 2016 and beyond ...
59
The end of the film
POLYAKOV Konstantin Yurievich
Doctor of Technical Sciences, teacher of informatics
GBOU Secondary School No. 163, St. Petersburg

K.Yu. Polyakov, 2015
http://kpolyakov.spb.ru

For school graduates. It should be taken by those who plan to enter universities for the most promising specialties, such as information security, automation and control, nanotechnology, systems analysis and control, rocket complexes and astronautics, nuclear physics and technology, and many others.

Read the general information about the exam and start preparing. Changes compared to last year in the new version of the KIM USE 2019 there is practically no. The only thing is that fragments of programs written in C have disappeared from the tasks: they have been replaced with fragments written in C ++. And also the opportunity to write an algorithm in natural language as an answer was removed from task number 25.

Assessment of the exam

Last year, in order to pass the Unified State Exam in computer science at least for the top three, it was enough to score 42 primary points. They were given, for example, for correctly completing the first 9 items of the test.

It is not yet known exactly how it will be in 2019: you need to wait for an official order from Rosobrnadzor on the compliance of primary and test points... Most likely it will appear in December. Considering that the maximum primary score remained the same for the whole test, most likely it will not change and minimum score... We focus on these tables so far:

The structure of the exam test

Computer science is the longest exam (the USE in mathematics and literature takes the same length), the duration is 4 hours.

In 2019, the test consists of two parts, including 27 tasks.

Part 1: 23 tasks (1–23) with a short answer, which is a number, a sequence of letters or numbers.
Part 2: 4 tasks (24–27) with a detailed answer, the complete solution of the tasks is written on the answer form 2.

All tasks are connected in one way or another with a computer, but during the exam it is not allowed to use it to write a program in group C tasks. In addition, the tasks do not require complex mathematical calculations and the calculator is also not allowed to use.

Preparation for the exam

Go through uSE tests online free of charge without registration and SMS. The presented tests are identical in complexity and structure to the real exams conducted in the corresponding years.

Download demo versions of the exam in computer science, which will allow you to better prepare for the exam and take it easier. All proposed tests are designed and approved to prepare for Unified State Exam by Federal Institute of Pedagogical Measurements (FIPI). In the same FIPI, all the official versions of the exam are being developed.
The tasks that you will see, most likely, will not be encountered in the exam, but there will be tasks similar to the demo ones, on the same topic or simply with different numbers.

General USE figures

Year	Minimum USE score	Average score	Number of participants	Not passed,%	Qty 100-point	Duration exam time, min.
2009	36
2010	41	62,74	62 652	7,2	90	240
2011	40	59,74	51 180	9,8	31	240
2012	40	60,3	61 453	11,1	315	240
2013	40	63,1	58 851	8,6	563	240
2014	40	57,1				235
2015	40	53,6				235
2016	40					235
2017	40					235
2018

State final examination 2019 in informatics for graduates of the 9th grade of educational institutions is carried out in order to assess the level of general education of graduates in this discipline. The main elements of content from the informatics section that are verified in testing:

Ability to assess the quantitative parameters of information objects.
Ability to determine the meaning of a logical expression.
Ability to analyze formal descriptions of real objects and processes.
Knowledge about the file system of data organization.
Ability to represent the formula dependence in graphical form.
Ability to execute an algorithm for a specific performer with a fixed set of commands.
Ability to encode and decode information.
Ability to execute a linear algorithm written in algorithmic language.
Ability to execute the simplest cyclic algorithm written in algorithmic language.
Ability to execute a cyclic algorithm for processing an array of numbers written in an algorithmic language.
Ability to analyze information presented in the form of diagrams.
Ability to search in a ready-made database for a formulated condition.
Knowledge of the discrete form of representation of numerical, textual, graphic and sound information.
Ability to write a simple linear algorithm for a formal performer.
Ability to determine the speed of information transfer.
Ability to execute a natural language algorithm that processes character strings or lists.
Ability to use information and communication technologies.
Ability to search for information on the Internet.
Ability to process a large amount of data using a spreadsheet or database.
Ability to write a short algorithm in the environment of a formal executor or in a programming language.

Dates for passing the OGE in informatics 2019:
June 4 (Tuesday), June 11 (Tuesday).

There are no changes in the structure and content of the 2019 examination paper compared to 2018.

In this section you will find online teststhat will help you prepare for passing the OGE (GIA) in computer science. We wish you success!

The standard test of the OGE (GIA-9) of the 2019 format in computer science and ICT contains two parts. The first part contains 18 tasks with a short answer, the second part contains 2 tasks that must be performed on a computer. Therefore, in this test only the first part (first 18 tasks) is presented. According to the current exam structure, among these 18 items, only the first 6 items offer answer options. However, for the convenience of passing the tests, the site administration decided to offer answer options for each task. However, for tasks in which answer options are not provided by the compilers of real control and measuring materials (CMM), we decided to significantly increase the number of these answer options in order to bring our test as close as possible to what you will have to face at the end of the school year.

The OGE standard test (GIA-9) of the 2018 format in computer science and ICT contains two parts. The first part contains 18 tasks with a short answer, the second part contains 2 tasks that must be performed on a computer. Therefore, in this test only the first part (first 18 tasks) is presented. According to the current exam structure, among these 18 items, only the first 6 items offer answer options. However, for the convenience of passing the tests, the site administration decided to offer answer options for each task. However, for tasks in which the answer options are not provided by the compilers of real control and measuring materials (CMM), we decided to significantly increase the number of these answer options in order to bring our test as close as possible to what you will have to face at the end of the school year.

The OGE standard test (GIA-9) of the 2018 format in computer science and ICT contains two parts. The first part contains 18 tasks with a short answer, the second part contains 2 tasks that must be performed on a computer. Therefore, in this test only the first part (first 18 tasks) is presented. According to the current exam structure, among these 18 items, only the first 6 items offer answer options. However, for the convenience of passing the tests, the site administration decided to offer answer options for each task. However, for tasks in which the answer options are not provided by the compilers of real control and measuring materials (CMMs), we decided to significantly increase the number of these answer options in order to bring our test as close as possible to what you will have to face at the end of the school year.

The OGE standard test (GIA-9) of the 2017 format in informatics and ICT contains two parts. The first part contains 18 tasks with a short answer, the second part contains 2 tasks that must be performed on a computer. Therefore, in this test only the first part (first 18 tasks) is presented. According to the current exam structure, among these 18 items, only the first 6 items offer answer options. However, for the convenience of passing the tests, the site administration decided to offer answer options for each task. However, for tasks in which the answer options are not provided by the compilers of real control and measuring materials (CMMs), we decided to significantly increase the number of these answer options in order to bring our test as close as possible to what you will have to face at the end of the school year.

The standard OGE test (GIA-9) of the 2016 format in computer science and ICT contains two parts. The first part contains 18 tasks with a short answer, the second part contains 2 tasks that must be performed on a computer. Therefore, in this test only the first part (first 18 tasks) is presented. According to the current exam structure, among these 18 items, only the first 6 items offer answer options. However, for the convenience of passing the tests, the site administration decided to offer answer options for each task. However, for tasks in which the answer options are not provided by the compilers of real control and measuring materials (CMMs), we decided to significantly increase the number of these answer options in order to bring our test as close as possible to what you will have to face at the end of the school year.

The standard test of the OGE (GIA-9) of the 2015 format in computer science and ICT contains two parts. The first part contains 18 tasks with a short answer, the second part contains 2 tasks that must be performed on a computer. Therefore, in this test only the first part (first 18 tasks) is presented. According to the current exam structure, among these 18 items, only the first 6 items offer answer options. However, for the convenience of passing the tests, the site administration decided to offer answer options for each task. However, for tasks in which the answer options are not provided by the compilers of real control and measuring materials (CMMs), we decided to significantly increase the number of these answer options in order to bring our test as close as possible to what you will have to face at the end of the school year.

When completing tasks 1-18, choose only one correct answer.

When completing tasks 1-8, choose only one correct answer.