Информатика · учебный маршрут
Случайность, численные оценки и целостность
Проверьте алгоритм на конечных вариантах и отделите счёт от обещаний надёжности. Для каждого результата укажите источник случайности или доверия.

Чему научитесь
Объяснять равновероятность, устойчивую оценку, ошибку фильтра и проверку подлинности.
Что пригодится
- Доля и вероятность
- Хеш как отображение данных
10 тем по порядку
Читайте объяснение или сразу переходите к заданию
- Практика
Резервуарная выборка: как один слот остаётся равномерным
Резервуарная выборка одного элемента: правило замены, вероятность сохранения и разница между позицией и значением.
- Практика
Fisher—Yates: почему случайный обмен требует правильной границы
Перемешивание Fisher—Yates: выбор из оставшегося диапазона, равномерность перестановок и ошибка обмена со всем массивом.
- Практика
Онлайновая дисперсия: обновляем среднее без разности больших квадратов
Онлайновая сумма квадратов отклонений: состояние n, среднее и M2, порядок обновления и выбор знаменателя дисперсии.
- Практика
Фильтр Блума: возможное совпадение и невозможность обычного удаления
Классический фильтр Блума: биты, ложноположительный ответ, точная отрицательная проверка и риск сброса общего бита.
- Практика
LRU: как последнее обращение меняет следующего кандидата на удаление
LRU на трассе запросов: порядок последнего использования, попадание и вытеснение, различие с FIFO и сроком годности.
- Практика
LFU: частота обращений и правило разрешения равенства
LFU на короткой трассе: счётчики обращений, частота против недавности и явное правило для одинаковых частот.
- Практика
Дерево Меркла: как ветвь проверки связана с доверенным корнем
Доказательство включения в дерево Меркла: соседние хеши, порядок объединения и необходимость доверенного корня.
- Практика
Подпись и шифрование: проверка автора не означает скрытый текст
Цифровая подпись и шифрование: роли ключей, открытость подписанного текста и независимая проверка принадлежности ключа.
- Практика
Воспроизводимая сборка: почему одного хеша исходников недостаточно
Воспроизводимая сборка: фиксированные исходники, окружение и выбранные артефакты, причины различающихся байтов.
- Практика
Время и часовой пояс: локальная отметка может быть неоднозначной
Локальное время и часовой пояс: UTC-смещение, правила зоны, повторяющийся час и длительность между моментами.
Как заниматься
Нужно проходить все темы подряд?
Последовательность помогает связать понятия, но можно открыть любую тему. Если задача уже знакома, начните с практики: ответ сопровождается объяснением.
Что делать, если ответ оказался неверным?
Прочитайте объяснение к ответу и сопоставьте его с разобранным примером. Найдите первый шаг, где ваше рассуждение отличается, затем попробуйте решить задание ещё раз.