Формулы ЕГЭ по информатике

ЕГЭ Информатика карточек: 15

Формулы для ЕГЭ по информатике: запись, расшифровка обозначений и пояснение к каждой. Разделы: Кодирование, Комбинаторика, Логика, Алгоритмы.

Алгоритм LZW замечает повторяющиеся цепочки символов и добавляет их в словарь. Когда знакомая цепочка встречается снова, вместо неё можно записать короткий код. Поэтому повторения в данных иногда помогают заметно уменьшить размер файла.

Кодирование

Число вариантов и биты

Сколько бит нужно, чтобы закодировать 30 учеников класса?

N = 2i

N
количество различных вариантов, штук
i
количество бит на один вариант, бит

Каждый бит удваивает число вариантов. Для 30 человек 4 бита мало (16), а 5 бит хватает (32). Берут наименьшее i, при котором 2i не меньше нужного числа.

Округлять надо ВВЕРХ: 4,9 бита не бывает, нужен целый пятый.

Задания по теме: Кодирование вариантов и мощность алфавита

Объём текста

Сколько весит сообщение из 200 символов?

I = K · i

I
информационный объём, бит
K
количество символов, штук
i
вес одного символа, бит

В кодировке ASCII символ занимает 8 бит (1 байт), в UTF-32 — 32 бита. 200 символов по 8 бит дают 1600 бит, то есть 200 байт.

В 1 байте 8 бит, в 1 килобайте 1024 байта, а не 1000 — степени двойки, а не десятки.

Задания по теме: Информационный объём текста

Скорость передачи данных

Сколько будет качаться файл на этом канале?

I = v · t

I
объём переданных данных, бит
v
скорость передачи, бит/с
t
время, с

Файл 10 МБ по каналу 8 Мбит/⁠с качается не 1,25 секунды, а 10: провайдер меряет скорость в мегаБИТах, а размер файла — в мегаБАЙТах. Разница в 8 раз.

Мбит/⁠с и МБ/⁠с — разные единицы. Это главная путаница в задачах на передачу данных.

Задания по теме: Скорость передачи данных

Объём изображения

Почему фотография весит мегабайты, а иконка — килобайты?

I = K · i

I
объём изображения, бит
K
количество пикселей (ширина × высота), штук
i
глубина цвета — бит на пиксель, бит

Фото 1920×1080 при глубине 24 бита занимает 1920·1080·24 ≈ 50 Мбит, то есть около 6 МБ без сжатия. Иконка 32×32 — меньше 4 КБ. Число пикселей растёт как квадрат стороны.

Глубина цвета связана с палитрой той же формулой N = 2i: 24 бита дают около 16,7 миллиона цветов.

Задания по теме: Кодирование звука и изображений

Комбинаторика

Число кодовых слов

Сколько разных паролей из 4 цифр можно составить?

N = mk

N
количество различных слов, штук
m
размер алфавита (сколько символов доступно), штук
k
длина слова, символов

На каждую позицию — m вариантов, позиций k. Для четырёхзначного PIN это 10⁴ = 10 000 комбинаций: перебрать их вручную нереально, а компьютером — мгновенно.

Формула считает варианты С ПОВТОРЕНИЯМИ: «1111» тоже пароль.

Задания по теме: Правило умножения и кодовые слова

Логика

Логические операции

Когда «И» истинно, а когда «ИЛИ»?

A ∧ B; A ∨ B; ¬A

A
первое высказывание (истина или ложь), 0 или 1
B
второе высказывание, 0 или 1

Конъюнкция ∧ («И») истинна только когда истинны оба. Дизъюнкция ∨ («ИЛИ») ложна только когда ложны оба. Отрицание ¬ переворачивает значение.

Импликация A → B ложна ровно в одном случае: A истинно, B ложно. Это самое частое место ошибок в таблицах истинности.

Задания по теме: Логические выражения

Алгоритмы

Сумма чисел от 1 до n

Сколько шагов сделает цикл, складывающий числа от 1 до n?

S = n · (n + 1) / 2

S
сумма чисел от 1 до n
n
последнее число, штук

Складывать по одному не нужно: сумма от 1 до 100 равна 100·101/2 = 5050. Приём приписывают Гауссу — числа с краёв разбиваются на пары с одинаковой суммой.

В трассировке алгоритма важно не число шагов, а значение переменной на выходе — их часто путают.

Системы счисления

Перевод в десятичную систему

Как перевести число в двоичную систему и обратно?

x = aₙ·2ⁿ + … + a₁·2¹ + a₀·2⁰

x
число в десятичной системе
a
цифра двоичной записи в разряде (индекс — номер разряда справа от нуля), 0 или 1

Каждый разряд — своя степень двойки. 10110110₂ = 128 + 32 + 16 + 4 + 2 = 182. Обратно переводят делением на 2 с записью остатков снизу вверх.

Шестнадцатеричная система устроена так же, но с основанием 16, где A = 10, B = 11, … F = 15.

Задания по теме: Двоичная система счисления

Триады и тетрады

Как перевести число из двоичной в шестнадцатеричную, минуя десятичную?

2 ↔ 8: группы по 3 цифры (триады) · 2 ↔ 16: группы по 4 (тетрады) · группируй справа налево

Разбей двоичную запись на группы по 4 цифры справа налево и замени каждую группу её шестнадцатеричной цифрой: 11010110 → 1101|0110 → D6₁₆. Для восьмеричной системы группы по 3 цифры: 101101 → 101|101 → 55₈. Обратный перевод — та же замена: каждая цифра разворачивается обратно в свою тройку или четвёрку.

Группируй строго от правого края; если в самой левой группе не хватает цифр — допиши нули слева. Из восьмеричной в шестнадцатеричную напрямую перейти нельзя — только через двоичную.

Задания по теме: Двоичная система счисления

Как записать 2¹⁰ − 1 в двоичной?

2ⁿ − 1 → n единиц в двоичной записи

Число 2ⁿ − 1 при положительном целом n записывается в двоичной системе как n единиц подряд.

2¹⁰ − 1 = 1024 − 1 = 1023
n = 10 → десять единиц подряд

1111111111₂ = 1023₁₀.

n — положительное целое. Индексы ₂ и ₁₀ обозначают двоичную и десятичную системы.

Задания по теме: Единицы в двоичной записи

Алгебра логики

Законы де Моргана

Как раскрыть НЕ над скобкой, где стоит И или ИЛИ?

¬(A ∧ B) = ¬A ∨ ¬B ; ¬(A ∨ B) = ¬A ∧ ¬B

A
первое высказывание (0 или 1)
B
второе высказывание (0 или 1)

Отрицание над скобкой переходит на каждое высказывание, а операция меняется на противоположную: И становится ИЛИ и наоборот. Например, НЕ(x > 3 И x < 10) превращается в (x ≤ 3) ИЛИ (x ≥ 10). Это главный инструмент упрощения выражений в заданиях 2 и 15.

Частая ошибка — поменять операцию, но забыть навесить отрицания на A и B (или наоборот). Меняется и то и другое одновременно.

Задания по теме: Логические выражения

Импликация

Почему «если 2·2 = 5, то Луна из сыра» — истинное высказывание?

A → B = ¬A ∨ B

A
посылка — высказывание до стрелки
B
следствие — высказывание после стрелки

Импликация A → B ложна в единственном случае: A истинно, а B ложно. Из ложной посылки следует что угодно, поэтому «если 2·2 = 5, то Луна из сыра» — истина. Для преобразований заменяй стрелку по формуле: (x > 5) → (x > 3) = (x ≤ 5) ИЛИ (x > 3), а это истинно при любом x.

Импликация не симметрична: A → B и B → A — разные выражения. При ложном A результат — истина при любом B.

Задания по теме: Логические выражения

Побитовые операции

Что на самом деле делает операция & с двумя числами?

&: единица там, где 1 у обоих · |: единица там, где 1 хотя бы у одного · считай столбиком в двоичной

Поразрядные операции сравнивают числа бит за битом в двоичной записи. Для 12 & 10 запиши 1100 и 1010 столбиком: единица остаётся там, где она у обоих чисел, — выйдет 1000, то есть 8. А 12 | 10 = 1110 = 14, потому что ИЛИ зажигает бит, когда единица есть хотя бы в одном из чисел.

Проверка бита: x & 2ᵏ ≠ 0 означает, что бит номер k (нумерация с нуля, справа) равен единице. Записывай оба числа с одинаковым числом разрядов, дописывая нули слева.

Задания по теме: Логические выражения

Кодирование информации

Условие Фано

Как код читается однозначно, если между буквами нет разделителей?

ни одно кодовое слово — не начало другого → сообщение декодируется однозначно

Если ни одно кодовое слово не совпадает с началом другого, сообщение читается слева направо без запятых единственным способом. Код {0, 10, 110, 111} условие выполняет: строка 0110111 разбирается только как 0|110|111. В задании 4 из подходящих вариантов выбирай самое короткое слово, которое не нарушает условие для всего набора.

Достаточно любого из двух условий: прямого Фано (не начало другого) или обратного (не окончание другого) — второе означает однозначное чтение справа налево. Проверять оба сразу не требуется.

Задания по теме: Правило умножения и кодовые слова

Алгоритмы и графы

Подсчёт путей в графе

Как быстро посчитать все пути из А в К по стрелкам?

путей в вершину = сумма путей во все вершины, откуда ведёт стрелка · путей в старт = 1

Подписывай у каждой вершины число путей до неё: у старта единица, у любой другой — сумма чисел всех вершин, из которых в неё идёт стрелка. Если в Г ведут стрелки из Б (3 пути) и В (2 пути), то до Г ровно 3 + 2 = 5 путей. Обходи вершины по направлению стрелок, пока не дойдёшь до конечной.

Пути «через вершину Д» — перемножь число путей от старта до Д и от Д до финиша. Пути «не через Д» — из общего числа путей вычти проходящие через Д.

Задания по теме: Пути в графе

Продолжить тренировку

Откройте тренажёр, чтобы решать похожие задания и отслеживать прогресс по темам. Для тренажёра нужен вход; на этой странице вход не нужен.

Задание в формате экзамена с разбором

Родителю

Приложение — для ученика. Родителю ставить его не нужно: кабинет родителя открывается в браузере. Родитель видит фактическую активность, регулярность и повторяющиеся ошибки. Проверять решения самостоятельно не требуется.