Кодирование
Число вариантов и биты
Сколько бит нужно, чтобы закодировать 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 миллиона цветов.
Задания по теме: Кодирование звука и изображений
Системы счисления
Перевод в десятичную систему
Как перевести число в двоичную систему и обратно?
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 путей. Обходи вершины по направлению стрелок, пока не дойдёшь до конечной.
Пути «через вершину Д» — перемножь число путей от старта до Д и от Д до финиша. Пути «не через Д» — из общего числа путей вычти проходящие через Д.
Задания по теме: Пути в графе