Информатика · учебный маршрут

Случайность, численные оценки и целостность

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

Синие фигурные скобки держат между собой оранжевый квадрат.

Чему научитесь

Объяснять равновероятность, устойчивую оценку, ошибку фильтра и проверку подлинности.

Что пригодится

  • Доля и вероятность
  • Хеш как отображение данных

10 тем по порядку

Читайте объяснение или сразу переходите к заданию

  1. Резервуарная выборка: как один слот остаётся равномерным

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

    Практика
  2. Fisher—Yates: почему случайный обмен требует правильной границы

    Перемешивание Fisher—Yates: выбор из оставшегося диапазона, равномерность перестановок и ошибка обмена со всем массивом.

    Практика
  3. Онлайновая дисперсия: обновляем среднее без разности больших квадратов

    Онлайновая сумма квадратов отклонений: состояние n, среднее и M2, порядок обновления и выбор знаменателя дисперсии.

    Практика
  4. Фильтр Блума: возможное совпадение и невозможность обычного удаления

    Классический фильтр Блума: биты, ложноположительный ответ, точная отрицательная проверка и риск сброса общего бита.

    Практика
  5. LRU: как последнее обращение меняет следующего кандидата на удаление

    LRU на трассе запросов: порядок последнего использования, попадание и вытеснение, различие с FIFO и сроком годности.

    Практика
  6. LFU: частота обращений и правило разрешения равенства

    LFU на короткой трассе: счётчики обращений, частота против недавности и явное правило для одинаковых частот.

    Практика
  7. Дерево Меркла: как ветвь проверки связана с доверенным корнем

    Доказательство включения в дерево Меркла: соседние хеши, порядок объединения и необходимость доверенного корня.

    Практика
  8. Подпись и шифрование: проверка автора не означает скрытый текст

    Цифровая подпись и шифрование: роли ключей, открытость подписанного текста и независимая проверка принадлежности ключа.

    Практика
  9. Воспроизводимая сборка: почему одного хеша исходников недостаточно

    Воспроизводимая сборка: фиксированные исходники, окружение и выбранные артефакты, причины различающихся байтов.

    Практика
  10. Время и часовой пояс: локальная отметка может быть неоднозначной

    Локальное время и часовой пояс: UTC-смещение, правила зоны, повторяющийся час и длительность между моментами.

    Практика

Как заниматься

Нужно проходить все темы подряд?

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

Что делать, если ответ оказался неверным?

Прочитайте объяснение к ответу и сопоставьте его с разобранным примером. Найдите первый шаг, где ваше рассуждение отличается, затем попробуйте решить задание ещё раз.

Все темы: Информатика