Как решать задание 27 ЕГЭ по информатике — кластерный анализ и программирование

О чём задание

Задание 27 — самое сложное в ЕГЭ по информатике (2 первичных балла, как и задание 26). Тебе дают файлы с координатами точек на плоскости (в файле А — до 1000, в файле Б — до 10 000). Нужно:

Разбить точки на кластеры (группы близких точек)
Найти центр каждого кластера — точку из набора, от которой сумма расстояний до всех остальных точек кластера минимальна
Вычислить ответ по формуле из условия

Задание идёт с двумя файлами: файл А (обычно 2 кластера, до 1000 точек — проще) и файл Б (обычно 3 кластера, до 10 000 точек — сложнее).

Что нужно знать

Расстояние между точками

Евклидово расстояние: d = sqrt((x2-x1)² + (y2-y1)²)

Центр кластера (медоид)

В условиях ЕГЭ центр кластера — это точка из набора данных, для которой сумма расстояний до всех остальных точек кластера минимальна. В математике такая точка называется медоид. Это не среднее арифметическое координат (центроид), хотя среднее — хорошее начальное приближение для поиска медоида.

Кластер

Группа точек, расположенных «близко» друг к другу. В задачах обычно кластеры хорошо разделены визуально — между ними большой пробел.

Алгоритм решения

Шаг 1: Визуализация (опционально, но полезно)

Открой файл в Excel или Google Sheets, построй точечную диаграмму. Ты сразу увидишь кластеры.

Шаг 2: Разделение на кластеры

Простой подход: если кластеры хорошо разделены — отсортируй по X (или Y), найди большие разрывы между соседними значениями. Разрыв = граница кластера.

Программный подход на Python:

# Чтение данных
with open('data.txt') as f:
    points = []
    for line in f:
        x, y = map(float, line.split())
        points.append((x, y))

# Сортировка и визуальный поиск разрывов
points.sort()
for i in range(1, len(points)):
    dx = points[i][0] - points[i-1][0]
    if dx > 1:  # порог зависит от данных
        print(f"Разрыв между {i-1} и {i}: dx={dx}")

Шаг 3: Поиск центра кластера (медоида)

Для каждого кластера найди точку с минимальной суммой расстояний:

import math

def find_medoid(cluster):
    min_dist = float('inf')
    medoid = None
    for p in cluster:
        total = sum(
            math.sqrt((p[0]-q[0])**2 + (p[1]-q[1])**2)
            for q in cluster
        )
        if total < min_dist:
            min_dist = total
            medoid = p
    return medoid

Шаг 4: Вычисление ответа

Подставь координаты центров кластеров в формулу из условия. Обычно ответ — это int(Px * 10000) и int(Py * 10000) для каждого файла.

Оптимизация для больших данных

Перебор всех пар точек — O(n²). Для 10 000 точек это 100 миллионов операций. Может быть медленно. Оптимизации:

Среднее как приближение: вычисли среднее X и Y кластера, затем проверяй только точки вблизи этого среднего
Уменьшение выборки: если кластер очень большой, можно искать медоид среди ближайших к среднему 100-200 точек

Типичные ошибки

Ошибка 1: Центр кластера ≠ среднее. Среднее арифметическое координат — это центроид (геометрический центр). Центр кластера из условия ЕГЭ — это медоид, реальная точка из набора с минимальной суммой расстояний. Обычно они близки, но не совпадают.

Ошибка 2: Неправильное разделение на кластеры. Если кластеры пересекаются по одной из координат — сортировка только по X не поможет. Используй визуализацию.

Ошибка 3: Точность вычислений. Работай с float, не округляй промежуточные результаты. Округляй только финальный ответ.

Ошибка 4: Забыл про файл Б. Задание требует ответы для обоих файлов. Файл Б сложнее — там больше кластеров и может потребоваться другой порог разделения.

Сколько времени тратить

Задание 27 стоит 2 первичных балла (как и задание 26). По рекомендациям ФИПИ на него стоит выделять не менее 40 минут. Если файл А решился быстро, а файл Б не поддаётся — сдай хотя бы ответ для А (можно получить 1 балл из 2).

Подготовка

Задание 27 требует навыков программирования и работы с данными. Начни с простых задач на кластеризацию и постепенно увеличивай сложность. В TuteMe есть задачи разного уровня с автоматической проверкой.

Попробовать бесплатно →