Задание 27 ЕГЭ по информатике. Анализ данных

Содержание

Теория

Основные понятия

Точки (звёзды) заданы координатами (x, y) на плоскости.
Кластеры — группы точек, которые можно поместить в непересекающиеся прямоугольники заданных размеров H×W.
Центр кластера — точка, сумма расстояний от которой до всех остальных точек кластера минимальна.
Расстояние между точками (x1, y1) и (x2, y2) вычисляется по формуле Евклида:
=КОРЕНЬ((x1 - x2)^2 + (y1 - y2)^2)

Структура таблицы

Создайте лист с колонками:

A — координата X
B — координата Y
C — номер кластера (1, 2 или 3; аномалии — 0)
D — расстояние до центра (служебный столбец)
E — сумма расстояний (служебный столбец для кандидатов в центр)

Построение графика (диаграммы рассеяния)

Выделите столбцы A и B.
В меню выберите: Вставка → Диаграмма.
Тип диаграммы: Точечная (XY).
Удалите линии, оставьте только маркеры — это звёзды.
Для файла B по графику видно 3 плотных скопления и 3 одиночные точки — это аномалии (им присвоим кластер = 0).

Определение кластеров

Файл A: две плотные группы точек → кластеры 1 и 2.
Файл B: три плотные группы → кластеры 1, 2 и 3; аномальные точки → кластер 0.

Укажите номера кластеров в столбце C вручную, ориентируясь на график.

Упрощённый алгоритм поиска центра

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

Полезные формулы LibreOffice (русская локализация)

Среднее значение по кластеру (для X и Y):=СРЗНАЧЕСЛИ($C$2:$C$1001; 1; $A$2:$A$1001) — для X;=СРЗНАЧЕСЛИ($C$2:$C$1001; 1; $B$2:$B$1001) — для Y.
Расстояние от точки до центра (x̄,ȳ) (если в ячейках G2 и H2 записаны средние координаты):=ЕСЛИ($C2=1; КОРЕНЬ((A2-$G$2)^2 + (B2-$H$2)^2); "")
Сумма расстояний от кандидата до всех точек кластера:=СУММПРОИЗВ( КОРЕНЬ((A$2:A$1001 - $A2)^2 + (B$2:B$1001 - $B2)^2); ($C$2:$C$1001=$C2) )
Расстояние между центрами двух кластеров:=КОРЕНЬ((x1 - x2)^2 + (y1 - y2)^2)

Примеры решений заданий

Файл A (2 кластера, H=6, W=4,5)

Импортируйте данные в столбцы A (x) и B (y).
Постройте точечную диаграмму. Визуально определите 2 кластера.
В столбце C укажите номера кластеров: 1 и 2.
Для каждого кластера вычислите средние координаты:G2 = СРЗНАЧЕСЛИ($C$2:$C$1001; 1; $A$2:$A$1001)H2 = СРЗНАЧЕСЛИ($C$2:$C$1001; 1; $B$2:$B$1001)
G3 = СРЗНАЧЕСЛИ($C$2:$C$1001; 2; $A$2:$A$1001)

H3 = СРЗНАЧЕСЛИ($C$2:$C$1001; 2; $B$2:$B$1001)
Вычислите расстояния до среднего значения (в столбце D):=ЕСЛИ($C2=1; КОРЕНЬ((A2-$G$2)^2 + (B2-$H$2)^2); "")Отсортируйте по возрастанию D, выберите 5 ближайших точек — кандидаты в центр.
Для каждого кандидата вычислите сумму расстояний до всех точек своего кластера (в столбце E):=СУММПРОИЗВ( КОРЕНЬ((A$2:A$1001 - $A2)^2 + (B$2:B$1001 - $B2)^2); ($C$2:$C$1001=$C2) )Минимальное значение в столбце E определяет центр кластера.
Повторите шаги для второго кластера (Cluster=2).
После нахождения центров кластеров:min_x = МИН(центр_X_1; центр_X_2)min_y = МИН(центр_Y_1; центр_Y_2)
Для итогового вывода (масштаб ×10000):=ABS(ЦЕЛ(min_x*10000))=ABS(ЦЕЛ(min_y*10000))

Файл B (3 кластера, H=6, W=5, 3 аномалии)

Импортируйте данные, постройте диаграмму рассеяния.
На графике отметьте 3 одиночные точки (аномалии), в столбце C присвойте им значение 0.
Для оставшихся точек определите кластеры: 1, 2, 3.
Для каждого кластера вычислите средние координаты:=СРЗНАЧЕСЛИ($C$2:$C$1001; 1; $A$2:$A$1001) и аналогично для Y.
Повторите шаги 5–6 из примера A для определения центра каждого кластера.
Посчитайте количество точек в каждом кластере:=СЧЁТЕСЛИ($C$2:$C$1001; 1),=СЧЁТЕСЛИ($C$2:$C$1001; 2),
=СЧЁТЕСЛИ($C$2:$C$1001; 3)
Определите кластеры с минимальным и максимальным количеством точек.
Вычислите расстояние между центрами этих кластеров:=КОРЕНЬ((x_макс - x_мин)^2 + (y_макс - y_мин)^2)
Для каждого кластера вычислите максимальное расстояние от центра до звезды:=МАКС(ЕСЛИ($C$2:$C$1001=c; КОРЕНЬ((A$2:A$1001 - x_c)^2 + (B$2:B$1001 - y_c)^2))) (ввод как формулу массива).
Общий максимум по всем кластерам:=МАКС(радиус_1; радиус_2; радиус_3)
Для итогового вывода (масштаб ×10000):=ЦЕЛ(расстояние_между_центрами*10000)=ЦЕЛ(максимальное_расстояние*10000)

Шаблон формул для LibreOffice Calc (русская локализация)

Средние координаты кластера 1:
G2: =СРЗНАЧЕСЛИ($C$2:$C$1001;1;$A$2:$A$1001)
H2: =СРЗНАЧЕСЛИ($C$2:$C$1001;1;$B$2:$B$1001)

Расстояния до центра:
D2: =ЕСЛИ($C2=1;КОРЕНЬ((A2-$G$2)^2+(B2-$H$2)^2);"")

Сумма расстояний до всех точек кластера:
E2: =СУММПРОИЗВ(КОРЕНЬ((A$2:A$1001-$A2)^2+(B$2:B$1001-$B2)^2);($C$2:$C$1001=$C2))

Количество точек в кластере:
=СЧЁТЕСЛИ($C$2:$C$1001;1)

Минимальная абсцисса и ордината центров (файл A):
=МИН(x1;x2)
=МИН(y1;y2)

Расстояние между центрами кластеров (файл B):
=КОРЕНЬ((x_макс - x_мин)^2 + (y_макс - y_мин)^2)

Максимальное расстояние от центра до звезды:
=МАКС(ЕСЛИ($C$2:$C$1001=c;КОРЕНЬ((A$2:A$1001-x_c)^2+(B$2:B$1001-y_c)^2)))

Окончательные значения для ответа:
=ABS(ЦЕЛ(min_x*10000))   =ABS(ЦЕЛ(min_y*10000))
=ЦЕЛ(dist_minmax*10000)  =ЦЕЛ(max_radius*10000)

Решение на Python

from math import hypot
from typing import List, Tuple

def read_pts(fn: str) -> List[Tuple[float, float]]:
    """
    Читает координаты точек из файла.
    
    Формат файла: каждая строка содержит два числа, разделённых пробелом.
    Десятичная запятая заменяется на точку.
    
    Args:
        fn: Имя файла для чтения
        
    Returns:
        Список кортежей (x, y) с координатами точек
    """
    pts = []
    with open(fn) as f:
        for line in f:
            a, b = line.split()
            pts.append((float(a.replace(",", ".")), float(b.replace(",", "."))))
    return pts

def split_by_boxes(pts: List[Tuple[float, float]], boxes: List[Tuple[float, float, float, float]]) -> List[List[Tuple[float, float]]]:
    """
    Разделяет точки по прямоугольным областям (кластерам).
    
    Каждая точка попадает в первый подходящий прямоугольник.
    Точки, не попавшие ни в один прямоугольник, игнорируются.
    
    Args:
        pts: Список точек (x, y)
        boxes: Список прямоугольников, каждый задан как (x_min, x_max, y_min, y_max)
        
    Returns:
        Список кластеров, где каждый кластер - список точек, попавших в соответствующий прямоугольник
    """
    cl = [[] for _ in boxes]
    for x, y in pts:
        for i, (x1, x2, y1, y2) in enumerate(boxes):
            if x1 <= x <= x2 and y1 <= y <= y2:
                cl[i].append((x, y))
                break
    return cl

def medoid(pts: List[Tuple[float, float]]) -> Tuple[float, float]:
    """
    Находит медоид кластера - точку с минимальной суммой расстояний до всех остальных.
    
    Алгоритм: точный перебор за O(n^2) с использованием симметрии расстояний.
    
    Args:
        pts: Список точек кластера
        
    Returns:
        Координаты медоида (x, y)
    """
    n = len(pts)
    s = [0.0] * n
    for i in range(n):
        xi, yi = pts[i]
        for j in range(i + 1, n):
            xj, yj = pts[j]
            d = hypot(xj - xi, yj - yi)
            s[i] += d
            s[j] += d
    return pts[min(range(n), key=lambda i: s[i])]

def avg_dist_excluding_self(c: Tuple[float, float], pts: List[Tuple[float, float]]) -> float:
    """
    Вычисляет среднее расстояние от центра до всех точек кластера, исключая сам центр.
    
    Args:
        c: Координаты центра (x, y)
        pts: Список точек кластера (включая центр)
        
    Returns:
        Среднее расстояние от центра до остальных точек
    """
    s = 0.0
    skipped = False
    for x, y in pts:
        if not skipped and x == c[0] and y == c[1]:
            skipped = True
            continue
        s += hypot(x - c[0], y - c[1])
    return s / (len(pts) - 1)

def solve_A() -> Tuple[int, int]:
    """
    Решает задачу для файла A: находит минимальное и максимальное расстояния
    между центрами кластеров и точками другого кластера.
    
    Кластер 1: x[2,8], y[10,15]
    Кластер 2: x[1,7], y[19,23]
    
    Returns:
        Кортеж (P1, P2), где:
        - P1: минимальное расстояние от центра одного кластера до точки другого (×10000)
        - P2: максимальное расстояние от центра одного кластера до точки другого (×10000)
    """
    boxes = [(2, 8, 10, 15), (1, 7, 19, 23)]
    c = split_by_boxes(read_pts("27var01A.txt"), boxes)
    c1, c2 = medoid(c[0]), medoid(c[1])
    d12 = [hypot(x - c1[0], y - c1[1]) for x, y in c[1]]
    d21 = [hypot(x - c2[0], y - c2[1]) for x, y in c[0]]
    p1 = min(min(d12), min(d21))
    p2 = max(max(d12), max(d21))
    return int(p1 * 10000), int(p2 * 10000)


def solve_B() -> Tuple[int, int]:
    """
    Решает задачу для файла B: находит средние расстояния от центров
    минимального и максимального кластеров до их точек.
    
    Кластер 1: x[13,17.3], y[14,20]
    Кластер 2: x[13,18], y[7,11]
    Кластер 3: x[20,28], y[4,9]
    
    Примечание: в данных B есть 2 "пограничные" точки с x≈17.14 и x≈17.23, y≈15..16.
    Они явно относятся к кластеру 1, поэтому верхнюю границу по x чуть расширяем до 17.3.
    
    Returns:
        Кортеж (Q1, Q2), где:
        - Q1: среднее расстояние от центра минимального кластера до его точек (×10000)
        - Q2: среднее расстояние от центра максимального кластера до его точек (×10000)
    """
    boxes = [(13, 17.3, 14, 20), (13, 18, 7, 11), (20, 28, 4, 9)]
    c = split_by_boxes(read_pts("27var01B.txt"), boxes)
    centers = [medoid(ci) for ci in c]
    sizes = [len(ci) for ci in c]
    i_min = min(range(3), key=lambda i: sizes[i])
    i_max = max(range(3), key=lambda i: sizes[i])
    q1 = avg_dist_excluding_self(centers[i_min], c[i_min])
    q2 = avg_dist_excluding_self(centers[i_max], c[i_max])
    return int(q1 * 10000), int(q2 * 10000)

a1, a2 = solve_A()
b1, b2 = solve_B()
print(a1, a2)
print(b1, b2)

Практические замечания

Вместо медианы используем среднее значение — это проще и достаточно точно для учебных данных.
Аномалии легко определить визуально по диаграмме и исключить вручную.
Все функции приведены в русской локализации LibreOffice Calc. Параметры разделяются точкой с запятой.
Используйте автозаполнение и фильтры, чтобы ускорить выбор кандидатов.

Задания для тренировки

Простые

Средние

https://inf-ege.sdamgia.ru/problem?id=70554 Смотреть разбор

https://kompege.ru/task?id=21425 Смотреть разбор

https://kompege.ru/task?id=21932 Смотреть разбор

27 Крылов С.С. 2026 Вариант 1. Смотреть разбор на Python Смотреть код

Основные понятия

Структура таблицы

Построение графика (диаграммы рассеяния)

Определение кластеров

Упрощённый алгоритм поиска центра

Полезные формулы LibreOffice (русская локализация)

Примеры решений заданий

Файл A (2 кластера, H=6, W=4,5)

Файл B (3 кластера, H=6, W=5, 3 аномалии)

Решение на Python

Практические замечания

Задания для тренировки

Простые

Средние

Сложные