Программирование и кластеризация

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

Высокий уровеньPythonАлгоритмы60–90 мин✓ Полный урок

Что нужно понимать

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

n²

Сложность

Полный перебор пар или расстояний может быть допустим только для небольших кластеров.

Точки

Для координат используйте float и аккуратно считайте расстояния.

Центроид-медоид

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

Ключевая идея

Сначала сделайте корректное решение на малом примере, затем оцените n и только после этого оптимизируйте. В задачах про кластеры особенно важно не перепутать среднее координат с центром, определённым условием.

Надёжный алгоритм решения

Прочитай формат файла

Пары координат, числа или другой набор данных.

Раздели данные по условию

Для кластеров — выдели группы точек корректным критерием.

Реализуй целевую функцию

Например, сумму евклидовых расстояний от кандидата до остальных точек.

Найди лучший кандидат

Сравни только допустимые точки, если центр должен принадлежать исходному набору.

Оцени сложность

Проверь, проходит ли O(n²); при больших n ищи структуру или иной алгоритм.

Типичная ошибка: Среднее арифметическое координат не обязано быть точкой из набора и не всегда совпадает с центроидом, который определён как исходная точка с минимальной суммой расстояний.

Пошаговый разбор

Мини-кластер состоит из точек A(0,0), B(0,2), C(2,0). Центром считаем одну из исходных точек с минимальной суммой расстояний.

Исходные данныеМодель

Σd(A)=2+2=4
Σd(B)=2+√8≈4.83
Σd(C)=2+√8≈4.83

РезультатРазбор

Минимальная сумма расстояний у точки A(0,0).

Значит центр этого мини-кластера — A, а не среднее координат.

РазборОткрывай шаги по очереди

AB=2, AC=2, BC=√8.

A:4; B:2+√8; C:2+√8.

4 меньше примерно 4.83, поэтому центром является A(0,0).

Тренажёр

Ответь на оба вопроса. Правильные ответы автоматически отмечают практику выполненной.

Практика

Закрепи алгоритм

2 вопроса

Запиши координаты центра мини-кластера через пробел.

Сколько вычислений расстояния выполнит простой двойной цикл по 100 кандидатам и 100 точкам, включая расстояние точки до себя?

Шпаргалка на экзамен

Строго следуй определению целевой величины.
Для координат используй float и hypot/формулу расстояния.
Сначала корректность, потом оптимизация.
Оцени сложность по размеру входных данных.

Урок 27 завершён

Курс 1–27 завершён

Прогресс урока сохраняется локально в браузере.

← Задание 26 К каталогу 1–27 →

Тематика «Программирование и кластеризация» сверена с актуальным каталогом ЕГЭ‑2026; примеры и тренажёры ТурбоУроки составлены самостоятельно. Каталог заданий ↗