12 тем: системы счисления, логика, алгоритмы, сложность, данные, комбинаторика, графы, криптография
Система счисления — способ записи чисел. В позиционных системах значение цифры зависит от её позиции (разряда). Любое число записывается набором цифр и основанием b:
Двоичная система (b = 2) — основа цифровой техники. Биты принимают значения 0 или 1.
Восьмеричная (b = 8) и шестнадцатеричная (b = 16) — компактная запись двоичных чисел. Одна шестнадцатеричная цифра = 4 бита (тетрада):
Перевод из двоичной в десятичную: умножаем каждую цифру на 2 в степени номера разряда и складываем.
Перевод из десятичной в двоичную: последовательно делим число на 2 и записываем остатки снизу вверх.
Переведите 1101₂ в десятичную.
Решение: 1·2³ + 1·2² + 0·2¹ + 1·2⁰ = 8 + 4 + 0 + 1 = 13.
Переведите 45₁₀ в двоичную.
Решение: 45 ÷ 2 = 22 (ост. 1); 22 ÷ 2 = 11 (ост. 0); 11 ÷ 2 = 5 (ост. 1); 5 ÷ 2 = 2 (ост. 1); 2 ÷ 2 = 1 (ост. 0); 1 ÷ 2 = 0 (ост. 1). Остатки снизу вверх: 101101₂.
Чему равно 255₁₀ в шестнадцатеричной?
Решение: 255 = 15·16¹ + 15·16⁰ = F F → FF₁₆.
Переведите 101011₂ в десятичную систему.
Решение: 1·2⁵ + 0·2⁴ + 1·2³ + 0·2² + 1·2¹ + 1·2⁰ = 32 + 0 + 8 + 0 + 2 + 1 = 43.
Сколько бит нужно, чтобы закодировать всё множество из 100 000 различных значений?
Решение: 2¹⁶ = 65 536 — мало, 2¹⁷ = 131 072 — достаточно. Нужно 17 бит.
1. Чему равно двоичное число 1111₂?
2. Сколько байт в кибибайте (KiB)?
3. Шестнадцатеричная цифра B равна десятичному числу:
Булева алгебра оперирует логическими значениями 0 (ложь) и 1 (истина). Программирование на них строит ветвления и условия.
Основные операции:
Приоритет: NOT > AND > OR. Как в математике скобки меняют порядок.
Законы де Моргана (важны для упрощения условий в коде):
A = 1, B = 0. Вычислите A ∧ (¬B).
Решение: ¬B = 1. Затем A ∧ 1 = 1 ∧ 1 = 1.
Упростите условие «не (год больше 2025, а зарплата больше 100000)».
Решение: По закону де Моргана: «год не больше 2025 ИЛИ зарплата не больше 100000».
Вычислите: ¬(1 ∨ 0) ∧ 1.
Решение: 1 ∨ 0 = 1; ¬1 = 0; 0 ∧ 1 = 0.
Упростите выражение: A ∨ (¬A ∧ B).
Решение: Через распределительный закон: A ∨ (¬A ∧ B) = (A ∨ ¬A) ∧ (A ∨ B) = 1 ∧ (A ∨ B) = A ∨ B.
1. Чему равно 1 ⊕ 1?
2. ¬(A ∧ B) эквивалентно:
Бит — минимальная единица информации, одно из двух состояний (0/1). Байт = 8 бит, кодирует 2⁸ = 256 значений.
Формула Хартли: количество информации, нужное для различения N равновероятных состояний:
Обратная задача — сколько значений можно закодировать I битами:
Единицы объёма данных:
Сколько бит информации требуется, чтобы закодировать результат броска кубика (6 граней)?
Решение: I = log₂ 6 ≈ 2,585 бит. На практике понадобится 3 бита (2³ = 8 ≥ 6).
Сколько байт в изображении размером 100 × 100 пикселей в режиме 256 цветов?
Решение: для 256 цветов нужен 1 байт на пиксель (2⁸ = 256). 100 × 100 × 1 = 10 000 байт.
Сколько бит содержит сообщение в 4 байта?
Решение: 4 × 8 = 32 бита.
Каким минимальным числом бит можно закодировать 12 состояний?
Решение: 2³ = 8 — мало, 2⁴ = 16 ≥ 12. Нужно 4 бита.
1. Чему равно log₂ 64?
2. Сколько байт в 2 КиБ?
Алгоритм — точное и понятное описание последовательности действий, ведущих от входных данных к результату. Свойства алгоритма: дискретность, понятность, определённость, результативность, массовость.
Основные структуры алгоритмов:
Пример типовой задачи: поиск максимального элемента в массиве.
Опишите алгоритм линейного поиска числа 42 в списке.
Решение: 1) начать с первого элемента; 2) если элемент равен 42 — остановиться и вернуть индекс; 3) перейти к следующему; 4) если список закончился — вернуть «не найдено».
Напишите псевдокод алгоритма, который считает количество чётных чисел в массиве.
Решение: count = 0; для каждого x: если x % 2 == 0, то count = count + 1; вернуть count.
1. Какая структура повторяет действия, пока выполняется условие?
2. Свойство алгоритма «результативность» означает:
O-нотация (Big O) описывает, как быстро растёт время или память алгоритма в зависимости от размера входных данных n. Важен порядок роста, а не константы.
Основные классы сложности (от быстрых к медленным):
| Запись | Название | Пример |
|---|---|---|
| O(1) | константная | доступ к элементу массива |
| O(log n) | логарифмическая | бинарный поиск |
| O(n) | линейная | линейный поиск |
| O(n log n) | линейно-логарифмическая | быстрая сортировка |
| O(n²) | квадратичная | вложенные циклы |
| O(2ⁿ) | экспоненциальная | перебор всех подмножеств |
Правило подсчёта: вложенные циклы перемножают размеры; последовательные участки складываются, но берётся самый «сильный» член.
Определите сложность двойного цикла, каждый из которых проходит n элементов.
Решение: n × n = O(n²).
Цикл по n элементам, внутри — цикл по 3 элементам. Сложность?
Решение: 3n — константа 3 отбрасывается, получаем O(n).
Сортировка пузырьком имеет сложность O(n²). Что быстрее для данных с n = 100: O(n) или O(n log n)?
Решение: O(n) = 100 шагов, O(n log n) ≈ 100 × 6,6 ≈ 660. Быстрее O(n) (это и логично — она младший порядок).
1. Класс O(n²) — это:
2. Просмотр всех элементов массива один раз — это:
Рекурсия — когда функция вызывает саму себя. Обязательно должны быть два элемента:
Классика: факториал и числа Фибоначчи.
Вычислите 4! по шагам.
Решение: 4! = 4·3! = 4·3·2! = 4·3·2·1! = 4·3·2·1·0! = 4·3·2·1·1 = 24.
Вычислите F(6) — шестое число Фибоначчи (с F(0) = 0).
Решение: Последовательность: 0, 1, 1, 2, 3, 5, 8. F(5) = 5, F(6) = 8.
Почему рекурсивные вычисления Фибоначчи медленные?
Решение: Один и тот же F(k) вычисляется много раз (экспоненциальный рост вызовов ≈ O(2ⁿ)). Выход — мемоизация или цикл.
1. Что обязательно должно быть у рекурсивной функции?
2. Чему равно 0! ?
Структура данных — способ организации хранения и доступа к данным. Влияет на скорость операций.
| Структура | Доступ к элементу | Добавление | Поиск |
|---|---|---|---|
| Массив | O(1) | в конец O(1)* | O(n) |
| Связный список | O(n) | в начало O(1) | O(n) |
| Стек (LIFO) | первый сверху O(1) | O(1) | O(n) |
| Очередь (FIFO) | первый снизу O(1) | O(1) | O(n) |
| Хеш-таблица | по ключу O(1) | O(1) | O(1)* |
| Бинарное дерево (сбалансированное) | O(log n) | O(log n) | O(log n) |
Звёздочкой отмечены средние случаи (амортизированно).
Почему список в Python неэффективен для удаления из начала?
Решение: При удалении первого элемента все остальные сдвигаются на позицию — операция стоит O(n). Поэтому используют deque.
В какую структуру данных удобно класть задачи, которые нужно обработать строго «последним пришёл — первым ушёл»?
Решение: Стек (LIFO). Пример — отмена действий (undo) в редакторе.
1. Принцип очереди:
2. Поиск в хеш-таблице в среднем стоит:
Комбинаторика считает число способов выбрать или упорядочить объекты.
Перестановки — порядок важен, берутся все n элементов:
Размещения — порядок важен, берут k из n:
Сочетания — порядок НЕ важен, берут k из n (например, выбор команды):
Правило умножения: если действие состоит из k этапов, а на каждом — mᵢ вариантов, то всего способов m₁ · m₂ · … · mₖ.
Сколько способов расставить 5 книг на полке?
Решение: P(5) = 5! = 5·4·3·2·1 = 120.
Из 10 кандидатов нужно выбрать команду из 3. Сколько способов?
Решение: C(10, 3) = 10! / (3! · 7!) = (10·9·8)/(3·2·1) = 120.
Сколько различных PIN-кодов из 4 цифр?
Решение: По правилу умножения: 10 · 10 · 10 · 10 = 10 000.
Из 7 человек нужно выбрать старосту и его заместителя (разные люди). Сколько способов?
Решение: Порядок важен → размещения: A(7, 2) = 7·6 = 42 способа.
Сколько способов выбрать 2 яблока из 5?
Решение: Порядок не важен → сочетания: C(5, 2) = 5!/(2!·3!) = 10.
1. Чему равно 4! ?
2. Выбрать 2 человека из 4 так, чтобы порядок не имел значения — это:
Вероятность события — доля благоприятных исходов среди всех равновозможных:
Вероятность всегда от 0 до 1. Сумма вероятностей всех исходов = 1.
Сложение несовместных событий:
Независимые события перемножаются:
Противоположное событие: P(не A) = 1 − P(A).
Вероятность выпадения 6 на кубике: 1 благоприятный исход из 6 → P = 1/6 ≈ 0,167.
Два раза подбросили монету. Вероятность двух орлов: (1/2) · (1/2) = 1/4.
В мешке 8 красных и 2 синих шара. Вероятность вытащить синий: 2/10 = 0,2.
Какова вероятность выпадения суммы 7 на двух кубиках?
Решение: Всего исходов 36. Пары, дающие 7: (1,6),(2,5),(3,4),(4,3),(5,2),(6,1) — 6 штук. P = 6/36 = 1/6.
Надёжность каждого из двух независимых серверов 95%. Какова вероятность, что откажут оба?
Решение: Отказ первого = 0,05, второго = 0,05. Оба откажут: 0,05 · 0,05 = 0,0025 (0,25%).
1. Вероятность выпадения «орла» один раз:
2. P(A и B) для независимых событий равна:
Вектор — упорядоченный набор чисел. В программировании — координаты точки, признак объекта, веса модели.
Скалярное произведение — сумма произведений соответствующих координат:
Длина вектора (норма):
Матрица — прямоугольная таблица чисел. Единичная матрица E — аналог числа 1.
Умножение матриц: элемент (i, j) результата = скалярное произведение i-й строки первой матрицы и j-го столбца второй.
Применения: компьютерная графика (трансформации), нейросети (веса и слои), криптография.
a = (1, 2), b = (3, 4). Скалярное произведение: 1·3 + 2·4 = 3 + 8 = 11.
Длина вектора (3, 4): √(9 + 16) = √25 = 5.
a = (1, 2, 3), b = (0, 1, 1). Найдите a · b.
Решение: 1·0 + 2·1 + 3·1 = 0 + 2 + 3 = 5.
Матрицы можно перемножать, если у первой n столбцов, а у второй — столько же строк. Можно ли перемножить (2×3) и (3×4)?
Решение: Да, 3 = 3. Размер результата — 2 × 4.
1. Скалярное произведение (1, 2) и (2, 1):
2. Длина вектора (6, 8):
Граф — множество вершин и рёбер, соединяющих их.
Способы хранения: список смежности (у каждой вершины список соседей) или матрица смежности.
Обходы: BFS (в ширину, через очередь) находит кратчайшие пути по числу рёбер; DFS (в глубину, через стек/рекурсию) — например, для поиска путей.
Типовые алгоритмы: Дейкстра (кратчайшие пути во взвешенном графе), поиск в ширину/глубину, топологическая сортировка.
Маршруты авиакомпании образуют направленный граф: есть рейс Москва → Самара, но нет обратного. Связь несимметрична — граф направленный.
Сколько рёбер у полного графа на 4 вершинах?
Решение: Каждая пара вершин соединена: C(4, 2) = 6 рёбер.
Почему BFS подходит для поиска кратчайшего маршрута в ненаправленном графе без весов?
Решение: Уровни обхода покрывают вершины по мере возрастания расстояния от старта: первая встреченная цель — на минимальном числе рёбер.
1. Дерево — это граф, в котором:
2. BFS использует структуру данных:
Остаток от деления (mod):
Пример: 17 mod 5 = 2, потому что 17 = 3·5 + 2.
Свойства mod:
НОД и алгоритм Евклида: НОД(a, b) = НОД(b, a mod b). На НОД строятся проверка делимости, сокращение дробей, генерация ключей.
Применение в криптографии: шифры на остатках (например, сдвиговый), хеширование, RSA. RSA использует то, что разложить произведение двух больших простых чисел на множители очень трудно.
Вычислите 234 mod 7.
Решение: 7·33 = 231, остаток 234 − 231 = 3.
Простой сдвиговый шифр (Цезаря): буква «А» с ключом 3 становится «Г», «Я» сдвигается по кругу.
Решение: индекс нового символа = (i + k) mod 26, где i — индекс буквы в алфавите.
Вычислите НОД(126, 84) алгоритмом Евклида.
Решение: НОД(126, 84): 126 mod 84 = 42; 84 mod 42 = 0. Ответ: НОД = 42.
Почему задачи «взломать пароль по хешу» сводят к большому перебору?
Решение: Хеш — односторонняя функция по модулю без обратной операции. Прямой математической формулы «обратно» нет, остаётся перебор всех вариантов (взрывная сложность).
1. Чему равно 100 mod 30?
2. Число чётно, если: