Конспект: Подготовка к пересдаче ЕГЭ по информатике и разбор задания на кластеризацию

Ключевые тезисы общей подготовки

Пересдача часто легче основной волны.
Важно отработать типовые задачи и шаблоны решений.
Для успеха критически важно разобрать варианты Дальнего Востока (они часто совпадают с пересдачей).
Многие задачи решаются по готовым шаблонам и алгоритмам.

Разбор заданий первой части

Задание 1 (Графы)

Задача на определение длины пути или суммы дорог в графе.

Ищите "соло-пункт" (вершину с одной дорогой) как точку старта.
В симметричных графах можно использовать рандомный выбор на симметричных участках.
Пример: В представленном графе ответом для пути BD (или DB) было 9.

Задание 2 (Логические функции)

Классическое задание на анализ функции и сопоставление значений переменных.

Используйте код-шаблон для перебора комбинаций:

print('x y z w')
for x in 0,1:
    for y in 0,1:
        for z in 0,1:
            for w in 0,1:
                if f(x,y,z,w) == 0: # Условие из задачи
                    print(x, y, z, w)

В выводе ищите переменную, которая принимает только одно значение (например, всегда w=1).
Сопоставляйте оставшиеся строки таблицы истинности с условиями задачи.

Задание 3 (Базы данных/Excel)

Задача на фильтрацию и вычисления (часто вес, объём, выручка).

Используйте автофильтры в Excel или аналогичные инструменты.
Алгоритм:
1. Отфильтруйте по нужному товару (например, "крахмал картофельный").
2. Отфильтруйте по типу операции ("поступление").
3. Отфильтруйте по району/магазину и дате.
4. Скопируйте получившиеся данные.
5. Умножьте количество упаковок на вес/объём одной упаковки.
Внимание: Не забудьте про единицы измерения (кг, л) и корректный диапазон дат.

Задание 4 (Кодирование)

Задача на построение оптимального префиксного кода (дерева Фано/Хаффмана).

Цель: закодировать слово минимально возможным количеством двоичных знаков.
Стратегия: Буквы, которые встречаются чаще, должны иметь более короткие коды.
Метод: Постройте дерево, пробуя разные варианты расположения частых букв. Сравнивайте общую длину закодированного слова для каждого варианта и выбирайте наименьшую.
Пример: Для слова "КОНОГОН" выгоднее было сделать код для "О" короче, что дало итоговую длину 16 вместо 18.

Задание 5 (Алгоритмы для исполнителя)

Задача на анализ алгоритма, обрабатывающего двоичную запись числа.

Типичный сценарий: число N обрабатывается по правилу (например, если делится на 3, дописываются последние цифры, иначе остаток умножается на 3 и переводится в двоичный вид).
Решение: Напишите программу-перебор для N в заданном диапазоне, которая имитирует работу алгоритма и находит нужное число (максимальное, минимальное, ближайшее к заданному).
Шаблон: Используйте цикл for n in range(...), функции bin() для перевода в двоичную систему и срезы строк ([-3:]) для получения последних цифр.

Задание 6 (Черепаха)

Задача на вычисление площади/периметра пересечения или объединения двух прямоугольников.

На пересдаче с высокой вероятностью будут два прямоугольника.
Что нужно уметь: Находить площадь и периметр пересечения и объединения фигур, а также количество целочисленных точек внутри них.
Совет: Используйте готовый код для Черепахи, подставляя свои команды. Для нахождения площади пересечения визуально выделите общую область на чертеже и посчитайте клетки.

Задание 7 (Кодирование звука/изображения)

Типовая задача на расчёт объёма файла.

Формула: Объём = (Частота дискретизации) * (Глубина кодирования) * (Количество каналов) * (Время в секундах).
Важно: Внимательно читайте, в каких единицах просят ответ (биты, байты, Кбайты, Мбайты). Не забывайте переводить: /8 → байты, /1024 → Кбайты.
Округление: Если спрашивают "наименьшее целое количество Кбайт, необходимое для сохранения", результат нужно округлить вверх.

Задание 8 (Комбинаторика, слова)

Задача на перебор слов по заданным условиям.

Используйте функцию product из модуля itertools для генерации всех комбинаций букв.
Шаблон решения:
1. Сгенерируйте все слова заданной длины из заданного алфавита.
2. Отсортируйте их, если нужно в алфавитном порядке (sorted).
3. Пронумеруйте, начиная с 1.
4. В цикле проверяйте условия задачи (например, "номер нечётный", "не содержит букв В, Е, К", "содержит ровно две буквы Т").
5. Используйте метод .count() для подсчёта букв.
Ответом может быть количество слов или номера конкретных слов.

Задание 9 (Обработка числовых данных в файле)

Задача на анализ табличных данных из файла.

Типичные условия: "ровно одно число повторяется трижды", "максимальное из повторяющихся больше наименьшего из неповторяющихся" и т.п.
Алгоритм:
1. Откройте файл, считайте строки.
2. Для каждой строки (списка чисел) используйте метод .count() для анализа повторений.
3. Создайте списки для чисел с разным количеством повторений (например, p3 — те, что встречаются 3 раза).
4. Применяйте условия задачи к этим спискам (поиск максимума/минимума, сравнение).
Совет: Внимательно работайте с типами данных, преобразуйте строки в числа.

Задание 10 (Работа с текстом)

Поиск сочетаний букв в текстовом файле (часто с учётом дефисов).

Если в условии есть "в том числе в словах с дефисом", замените дефисы на пустую строку (replace("-", "")), чтобы "склеить" слова.
Используйте инструмент "Найти все" в текстовом редакторе или функцию count() в программе.
Пример: Найти все вхождения "то" (с большой буквы). Общее количество минус количество случаев, где "то" является отдельным словом.

Задание 11 (Системы счисления)

Задача на определение минимальной длины серийного номера.

Типичная формулировка: "Сколько символов должно быть в алфавите, чтобы закодировать N номеров, используя не более M байт?".

Решение (автокод):

for length in range(1, 10): # Перебираем длину номера
    total = alphabet_size ** length # Количество возможных номеров
    if total * bits_per_number / 8 > M_bytes:
        print(length)
        break

Переводите байты в биты (*8), если объём дан в байтах.

Задание 12 (Автоматы, машина Тьюринга)

Анализ программы для исполнителя (часто увеличение/уменьшение числа в двоичной системе).

Переведите исходное число в двоичную систему.
Промоделируйте шаги программы по состояниям (q0, q1...), отслеживая положение головки и изменение ячеек ленты.
Переведите результат обратно в десятичную систему для ответа.
Совет: На экзамене, скорее всего, будет знакомая операция (увеличение разряда, инверсия битов).

Задание 13 (Компьютерные сети)

Расчёт широковещательного адреса или адреса сети по IP и маске.

Используйте библиотеку ipaddress в Python.

Шаблон:

from ipaddress import *
net = ip_network('185.249.55.138/255.255.192.0', strict=False)
print(net.broadcast_address) # Широковещательный
print(net.network_address)   # Адрес сети

Если просят сумму байт адреса, сложите все числа в полученном IP.

Задание 14 (Позиционные системы счисления)

Нахождение основания системы счисления или количества определённых цифр в записи.

Частый тип: "Значение выражения записали в системе счисления с основанием p. Определите, при каком p в записи наибольшее количество нулей".
Алгоритм:
1. Вычислите значение выражения для всех p в заданном диапазоне.
2. Переведите результат в систему с основанием p.
3. Посчитайте нули в полученной записи.
4. Найдите максимум.
Лайфхак: Выведите все пары (p, количество_нулей) в Excel и отсортируйте.

Задание 15 (Множества, отрезки, делимость)

(Конспект по заданию 15 не был предоставлен в исходных частях).

Разбор задания на кластеризацию

Ключевые тезисы:

Задание связано с анализом кластеров и поиском центра кластера с наименьшим количеством элементов.
Для решения необходимо определить координаты центров кластеров (абсциссу и ординату).
Задание из варианта Дальнего Востока (ДВ) оценивается как более простое по ответу, но более сложное по логике кластеризации по сравнению с другими частями.
Автор предоставляет готовое решение («шпору») и обещает разбор на следующий день.

Суть задания

Задача заключается в анализе результатов кластеризации. Нужно:

Определить количество элементов (оранжевых гигантов) в каждом кластере.
Найти кластер с наименьшим количеством таких элементов.
Для этого кластера вывести координаты его центра:
- B1 — абсцисса (координата по оси X).
- B2 — ордината (координата по оси Y).

Автор отмечает, что ответ в этой части (ДВ) проще, чем в других вариантах (например, в варианте «А»), но сама логика кластеризации сложнее.

Решение и материалы

Автор демонстрирует полный код решения задачи.
Готовое решение («шпора») было выложено в Telegram-канал для участников.
Упоминается, что завтрашний вариант (Дальнего Востока) будет «изи» (лёгким) и не должен вызвать сложностей.

Планы и напутствие

На следующий день запланирован подробный разбор варианта Дальнего Востока.
Автор настраивает аудиторию на позитивный лад, утверждая, что после разбора все «пойдёте на изи напишите».
В конце — общее пожелание удачи всем зрителям.