задание 1
Графы и таблицы: сопоставление схемы и весовой матрицы
Сопоставление графа дорог с весовой матрицей, где номера вершин не совпадают с буквами. Вершины опознают по степеням и уникальным связям, затем по таблице находят длину нужного ребра.
задание 2
Таблицы истинности логических функций
Нужно определить, какой переменной логической функции соответствует каждый столбец неполной таблицы истинности. Удобно перебрать строки программой или упростить выражение и рассуждать вручную.
задание 3
Реляционная база данных в электронных таблицах
Работа с реляционной базой из нескольких связанных таблиц: отбор записей по условиям, подстановка данных из справочников и подсчёт итогов с помощью фильтров, ВПР или сводных таблиц.
задание 4
Двоичное кодирование, условие Фано
Построение двоичного префиксного кода по условию Фано: подбор кратчайших кодовых слов для оставшихся символов. Решается вручную с помощью двоичного дерева кодов.
задание 5
Алгоритмы обработки двоичной и троичной записи числа
Анализ алгоритма, который строит новое число по двоичной или троичной записи исходного: дописывание разрядов, проверка чётности единиц. Проще всего перебрать входные значения короткой программой.
задание 6
Исполнитель Черепаха, точки на координатной сетке
Исполнитель Черепаха рисует фигуру по командам с циклом, а ученик считает целые точки внутри или на границе контура. Фигуру удобно построить на бумаге или отрисовать через turtle в Python.
задание 7
Объём растровых изображений и звука
Расчёт информационного объёма растровых изображений и звуковых записей: связь разрешения, глубины цвета, частоты дискретизации и размера файла, перевод единиц измерения информации.
задание 8
Комбинаторика: слова и числа
Подсчёт слов и чисел с ограничениями на буквы, позиции и соседство символов. Небольшие случаи решаются правилами произведения и суммы, а сложные - перебором через itertools.product.
задание 9
Обработка строк электронной таблицы по условиям
Анализ строк электронной таблицы с числами: проверка условий о повторах, среднем, максимуме и подсчёт подходящих строк. Решается формулами в таблице или программой, читающей CSV.
Открытая тема Поиск слов в текстовом документе
Поиск в большом текстовом документе точной словоформы как отдельного слова, с учётом или без учёта регистра. Используется поиск текстового редактора с параметрами или обработка текста программой.
задание 11
Объём информации: пароли и идентификаторы
Вычисление объёма памяти для паролей и идентификаторов: минимальное число бит на символ, округление до целых байт на запись и объём данных для заданного числа пользователей.
задание 12
Исполнитель Редактор: замены в строке
Исполнитель Редактор циклически заменяет цепочки символов в строке. Нужно проследить результат работы алгоритма с командами заменить и нашлось - вручную по закономерностям или моделированием в Python.
задание 10
IP-адреса и маски сети
Работа с IP-адресами и масками подсети: поразрядная конъюнкция, определение адреса сети, числа адресов и допустимых масок. Удобно решать с модулем ipaddress или вручную в двоичной записи.
задание 13
Исполнение алгоритмов: состояние, циклы и остановка
Пошаговое исполнение команд, инвариант и причина завершения цикла.
задание 14
Позиционные системы счисления
Действия с числами в позиционных системах счисления: подсчёт цифр в записи значения выражения, поиск неизвестной цифры или основания. Выражения с большими степенями разумно считать программой.
Открытая тема задание 15
Логические формулы с параметром
Поиск параметра, при котором логическая формула с делимостью, отрезками или поразрядной конъюнкцией истинна при любом x. Надёжный способ - перебор значений параметра и x в программе.
задание 16
Рекурсивные функции
Вычисление значений рекурсивно заданных функций, в том числе с большой глубиной вызовов. Помогают кэширование, итеративный пересчёт или алгебраическое упрощение разности значений.
Открытая тема задание 17
Обработка числовой последовательности из файла
Обработка последовательности чисел из файла: поиск пар или троек соседних элементов по условиям делимости, записи числа и сравнения с максимумом. Решается программой за один-два прохода.
Открытая тема задание 18
Динамическое программирование на клетчатом поле
Поиск максимальной и минимальной суммы на пути Робота по клетчатому полю, иногда со стенами. Решается динамикой в электронной таблице или программой, заполняющей таблицу оптимальных сумм.
задания 19–21
Выигрышные стратегии в играх с кучами камней
Анализ игры с одной или двумя кучами камней: определение выигрышных и проигрышных позиций и числа ходов до победы. Решается рекурсивным перебором позиций или построением таблицы вручную.
задание 22
Параллельные процессы и критический путь
Определение минимального времени выполнения набора взаимозависимых процессов при параллельном запуске. По сути это поиск критического пути в графе зависимостей, удобно считать в электронной таблице.
Количество программ исполнителя
Подсчёт числа программ исполнителя, переводящих одно число в другое, с обязательными и запрещёнными точками траектории. Решается динамикой по числам или рекурсивной функцией.
задание 24
Обработка символьных строк из файла
Анализ длинной символьной строки из файла: поиск самой длинной подстроки с заданным свойством, подсчёт комбинаций символов. Требует аккуратной программы с одним проходом или скользящим окном.
Открытая тема задание 23
Алгоритмы на графах: пути в DAG
Топологический порядок и динамический подсчёт путей с обязательными и запрещёнными вершинами.
задание 25
Маски чисел и делители
Поиск чисел по маске с символами ? и *, а также чисел с заданными свойствами делителей. Решается программой: перебор кратных с проверкой через fnmatch или эффективный перебор делителей до корня.
задание 26
Сортировка и жадные алгоритмы на данных из файла
Задачи на выбор и распределение объектов из файла - архивация файлов, упаковка, очереди. Данные сортируют и применяют жадную стратегию, аккуратно обрабатывая дополнительное условие выбора.
Открытая тема задание 27
Анализ данных: кластеры точек
Разбиение множества точек на кластеры и поиск их центров по минимальной сумме расстояний. Точки группируют по удалённости, центры находят программой, а затем вычисляют средние координаты.
