ЕГЭ 2027 · Информатика
Справочник
Главное из уроков по темам: единицы и формулы объёма информации, системы счисления, логика, IP-адреса, коды, теория игр и приёмы Python для заданий с программой. Обозначения такие же, как в заданиях ЕГЭ 2027.
Единицы информации
| Единица | Сколько |
|---|---|
| 1 байт | 8 бит |
| 1 Кбайт | 1024 байт |
| 1 Мбайт | 1024 Кбайт |
| 1 Гбайт | 1024 Мбайт |
- В ЕГЭ Кбайт и Мбайт связаны с байтом степенью двойки: 1 Кбайт = 210 байт, 1 Мбайт = 220 байт.
- Из меньшей единицы в большую дели на 1024, из большей в меньшую умножай.
Объём информации
- Алфавит из N символов: на символ нужно i бит, где 2i ≥ N (наименьшее такое i).
- Сообщение из K символов: I = K · i.
- Изображение из W · H точек, N цветов: I = W · H · i, где 2i ≥ N.
- Звук: I = f · i · k · t: частота дискретизации f (Гц), глубина кодирования i (бит), число каналов k (моно 1, стерео 2), время t (с).
- Передача данных: I = v · t, скорость v в бит/с.
- Пароль или номер из K символов, если запись занимает целое число байт: байт на запись = K · i8, округлённое вверх.
Степени двойки
| n | 2n | n | 2n |
|---|---|---|---|
| 1 | 2 | 9 | 512 |
| 2 | 4 | 10 | 1024 |
| 3 | 8 | 11 | 2048 |
| 4 | 16 | 12 | 4096 |
| 5 | 32 | 13 | 8192 |
| 6 | 64 | 14 | 16384 |
| 7 | 128 | 15 | 32768 |
| 8 | 256 | 16 | 65536 |
Системы счисления
- Из системы с основанием b в десятичную: каждую цифру умножить на b в степени её номера справа (с нуля) и сложить. Например, 10112 = 8 + 2 + 1 = 11.
- Из десятичной в систему с основанием b: делить на b с остатком, пока не получится 0, остатки записать в обратном порядке.
- Двоичная и восьмеричная: каждой восьмеричной цифре соответствуют три двоичные. Двоичная и шестнадцатеричная: четыре двоичные.
- Шестнадцатеричные цифры: A = 10, B = 11, C = 12, D = 13, E = 14, F = 15.
- Число bk в системе с основанием b записывается единицей и k нулями, а число bk − 1 записывается k цифрами, равными b − 1.
- Python:
int('1A3', 16)переводит в десятичную,bin(x),oct(x),hex(x)в двоичную, восьмеричную и шестнадцатеричную. В любую систему: циклwhile x > 0, цифраx % b, дальшеx //= b.
Логика
| Операция | Запись | Python | Истинна, когда |
|---|---|---|---|
| отрицание | ¬A | not A | A ложно |
| конъюнкция (И) | A ∧ B | A and B | оба истинны |
| дизъюнкция (ИЛИ) | A ∨ B | A or B | хотя бы одно истинно |
| импликация | A → B | A <= B | везде, кроме 1 → 0 |
| тождество | A ≡ B | A == B | значения совпадают |
- В заданиях конъюнкцию пишут ещё как /\ или &, дизъюнкцию как \/ или вертикальную черту.
- Порядок действий без скобок: отрицание, конъюнкция, дизъюнкция, импликация, тождество.
- A → B равносильно ¬A ∨ B.
- Законы де Моргана: ¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B.
- Все наборы значений в Python:
for x, y, z in itertools.product([0, 1], repeat=3):.
IP-адреса и маски
- IP-адрес: четыре байта, записываются числами от 0 до 255 через точку.
- Маска в двоичной записи: сначала только единицы, потом только нули.
- Адрес сети: поразрядная конъюнкция адреса узла и маски. В Python для чисел
ip & mask. - Если в маске k нулей, в сети 2k адресов. Адрес из одних нулей в части узла обозначает саму сеть, из одних единиц служит широковещательным, поэтому узлам остаётся 2k − 2.
- Модуль
ipaddress:ipaddress.ip_network('192.168.32.0/255.255.224.0')перебирает адреса сети.
Коды и условие Фано
- Условие Фано: ни одно кодовое слово не является началом другого кодового слова. Тогда сообщение раскодируется однозначно.
- Коды удобно строить двоичным деревом: слова стоят в листьях, у каждого узла не больше двух ветвей.
- Чтобы найти самое короткое свободное слово, ищи в дереве незанятую ветку поближе к корню.
Теория игр: № 19–21
- Позиция выигрышная, если из неё есть ход в проигрышную позицию для соперника.
- Позиция проигрышная, если любой ход из неё ведёт в выигрышную позицию для соперника.
- Программой: рекурсивная функция «может ли ходящий выиграть не больше чем за m ходов» и перебор всех S из условия.
Python: частые приёмы
- Чтение чисел из файла:
nums = list(map(int, open('17.txt').read().split())). - Делители n: перебор d до √n, каждый делитель d даёт пару d и n // d.
- Простое число: больше 1 и не делится ни на одно число от 2 до √n.
- Все пары соседних элементов:
for i in range(len(a) - 1):, все пары вообще: два вложенных цикла,jотi + 1. - Перебор слов:
itertools.product('АБВ', repeat=5), перестановки:itertools.permutations(s). - Рекурсия с запоминанием:
from functools import lru_cacheи строка@lru_cache(None)над функцией. Глубину рекурсии поднимаетsys.setrecursionlimit(10000). - Целочисленное деление и остаток:
//и%, сразу оба:divmod(a, b).