Информатика

Почему переход от больших электронно-ламповых ЭВМ к персональным компьютерам считается качественным этапом в истории вычислительной техники?

1. Потому что ламповые ЭВМ поддерживали только один язык программирования
2. Потому что ламповые ЭВМ не могли подключаться к сети
3. Потому что персональные компьютеры полностью отказались от операционных систем
4. Потому что персональные компьютеры сделали вычислительную мощность доступной отдельным людям и малым организациям

Какое из приведенных утверждений лучше всего объясняет важность появления графического пользовательского интерфейса (GUI) для развития персональных компьютеров?

1. Он полностью отменил необходимость операционных систем
2. Он позволил компьютерам работать быстрее на уровне процессора
3. Он был необходим только для компьютерных игр
4. Он сделал взаимодействие с компьютером более наглядным и доступным для неподготовленных пользователей

Какое ключевое преимущество транзистора по сравнению с электронными лампами позволило сделать компьютеры значительно более практичными?

Выберите правильный вариант ответа

1) Возможность выполнять операции с плавающей запятой

2) Меньший размер, энергопотребление и большая надежность

3) Поддержка нескольких операционных систем одновременно

4) Встроенная поддержка графического интерфейса

Как изменение параметра minPts влияет на форму k-distance графика и выбор εε?

1. При увеличении minPts k-расстояния уменьшаются, и локоть смещается к нулю
2. minPts влияет только на итоговые кластеры и никак не связан с k-distance графиком
3. При увеличении minPts k-расстояния, как правило, возрастают, и локоть смещается вправо и вверх
4. Изменение minPts вообще не рекомендуется, он всегда фиксирован

Как выбор параметра k (количество соседей для k-distance) связан с параметром minPts в DBSCAN?

1. Часто выбирают k=minPts или k=minPts−1
2. Обычно выбирают k=1, независимо от minPts
3. Связи между k и minPts нет, они подбираются совершенно независимо
4. k всегда должен быть намного больше minPts

Зачем сортировать k-расстояния по возрастанию перед построением k-distance графика?

1. Чтобы разнесённые во времени наблюдения шли подряд
2. Чтобы визуально выделить резкий переход от плотных областей к шуму
3. Чтобы получить симметричный график относительно середины
4. Чтобы можно было напрямую прочитать индексы кластеров

На k-distance графике по оси абсцисс отложены отсортированные объекты датасета. Что обычно показывается по оси ординат?

Выберите верный вариант ответа

1. Расстояние до ближайшего соседа k=1 для каждого объекта
2. Индекс объекта в исходном порядке выборки
3. Среднее расстояние от объекта до всех других объектов
4. Расстояние до k-го ближайшего соседа для каждого объекта

Реализуйте полный алгоритм DBSCAN. Напишите программу

 

Формат входных данных

n eps minPts : n - число точек (натуральное число не больше 100, eps - положительное вещественное число не больше 3, minPts - натуральное число не больше 5)

n строк: x y (координаты точек, вещественные числа, по модулю меньше 10**5 )

Формат выходных данных

n строк: номер кластера для каждой точки:

• -1 для шума
• нумерация кластеров с 0

Дан набор точек. Напишите программу, которая считает количество соседей у заданной точки в радиусе eps

Формат входных данных
Первая строка: n eps — количество точек и радиус (n - натуральное, не превышает 100 , eps - вещественное)
Следующие n строк: x y — координаты точек (целые числа, по модулю не превышают 100)
Последняя строка: qx qy — точка запроса (целые числа, по модулю не превышают 100). 
Гарантируется, что заданная точка находится в заданном наборе точек.

Формат выходных данных
Одно число — количество соседей (не считая саму точку)

Дано: eps = 2, minPts = 3
Точки: A(1, 1),  B(2, 1),  C(3, 1),  D(10, 10)

Какой тип у точки D?

Выберите верный вариант ответа

1. Ядровая точка
2. Граничная точка
3. Шумовая точка
4. Невозможно определить

Посмотрите на эти данные:

Данные:

   ●●●●●●●●●

  ●●●●●●●●●●●

 ●●●●     ●●●●

●●●●        ●●●●

 ●●●        ●●●

  ●●        ●●

   ●        ●

(форма буквы "C")

Если применить k-means с k=2, какой результат наиболее вероятен?

Выберите верный вариант ответа:

1. K-means правильно найдёт кластер в форме "C"
2. K-means разделит "C" на левую и правую части
3. K-means не сможет работать с такими данными
4. K-means найдёт только один кластер

Реализуйте алгоритм k-means для одномерных данных (только координата x).

Для одномерных данных расстояние между точками вычисляется как модуль разности: |x₁ - x₂|

При равном расстоянии до нескольких центров точка присваивается кластеру с меньшим номером.

 

Формат входных данных

- Первая строка: два целых числа n и k (1 ≤ k ≤ n ≤ 1000) — количество точек и кластеров

- Вторая строка: n целых чисел через пробел — значения точек (−10⁶ ≤ xᵢ ≤ 10⁶)

- Третья строка: k вещественных чисел через пробел — начальные центры кластеров

 

Формат выходных данных

- Первая строка: k вещественных чисел — финальные центры кластеров (округлённые до 1 знака после запятой)

- Вторая строка: n целых чисел — номер кластера (0-индексация) для каждой точки в порядке их появления во входных данных

Учёный решил провести кластеризацию множества звёзд по их расположению на карте звёздного неба. Кластер звёзд — это набор звёзд (точек), лежащих внутри прямоугольника высотой H и шириной W. Каждая звезда принадлежит ровно одному кластеру. Центроид кластера — это одна из звёзд кластера, сумма расстояний от которой до всех остальных звёзд этого кластера минимальна. Расстояние между звёздами вычисляется по формуле Евклида: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)

Вам дан список координат звёзд и количество кластеров k. Известно, что все кластеры имеют размер \(H \times W\) и чётко разделены (расстояние между кластерами значительно больше их размера).

Необходимо:

1. Разделить звёзды на k кластеров

2. Найти центроид каждого кластера

3. Вычислить \(P_x\) — среднее арифметическое x-координат всех центроидов

4. Вычислить \(P_y\) — среднее арифметическое y-координат всех центроидов

5. Вывести результат в заданном формате

 

Формат входных данных

- Первая строка содержит два целых числа n и k (\(1 \le n \le 1000\), \(1 \le k \le 10\)) — количество звёзд и количество кластеров.

- Вторая строка содержит два вещественных числа H и W — размеры каждого кластера.

- Следующие n строк содержат по два вещественных числа \(x_i\)и \(y_i\) (\(-10^6 \le x_i, y_i \le 10^6\)) — координаты звёзд.

 

Формат выходных данных

Выведите два целых числа через пробел:

- Целую часть от \(|P_x \times 10000|\)

- Целую часть от \(|P_y \times 10000|\)

где |x| обозначает абсолютное значение числа x.

Даны точки на координатной плоскости:

A(1, 1), B(2, 1), C(1, 2), D(8, 8), E(9, 8), F(8, 9)

Центры кластеров:
C1(1.5, 1.5) и C2(8.5, 8.5)

К какому кластеру относится точка G(5, 5)?

1. Кластер 1 (C1)
2. Кластер 2 (C2)
3. На границе кластеров (равные расстояния)
4. Не относится ни к одному кластеру

Какое расстояние чаще всего используется в k-means?

1. Расстояние на карте города
2. Евклидово расстояние
3. Время в пути
4. Количество шагов

В чём главный недостаток алгоритма k-means?

1. Слишком быстро работает
2. Результат зависит от начальной инициализации центров
3. Не может работать с числовыми данными
4. Всегда создаёт ровно 10 кластеров

Как выбрать оптимальное количество кластеров k?

1. Всегда использовать k=2
2. k должно быть равно количеству точек
3. Методом локтя (Elbow method) или другими эвристиками
4. Случайным образом

Сколько раз может измениться положение центра кластера в k-means?

1. Ровно один раз
2. Ровно k раз (где k — количество кластеров)
3. От 0 до бесконечности (зависит от данных)
4. Центр никогда не меняется после инициализации

Что такое центроид (центр кластера) в алгоритме k-means?

1) Самая первая точка в кластере
2) Точка со средними координатами всех точек кластера
3) Точка, которая находится дальше всего от других кластеров
4) Случайная точка из кластера

Алгоритм K-Means — это итеративный алгоритм кластеризации, который разбивает множество точек на K кластеров. Алгоритм работает следующим образом:

1. Инициализация: задаются начальные координаты K центров кластеров
2. Назначение: каждая точка относится к кластеру с ближайшим центром (по евклидову расстоянию)
3. Пересчёт: центр каждого кластера пересчитывается как среднее арифметическое координат всех точек, принадлежащих этому кластеру
4. Проверка сходимости: если центры не изменились — алгоритм завершается, иначе переход к шагу 2

Евклидово расстояние между точками \((x_1, y_1)\) и \((x_2, y_2)\)вычисляется по формуле: \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)

Реализуйте алгоритм K-Means и выведите результат его работы.

Формат входных данных

- Первая строка содержит два целых числа n и k (1 <= n <= 1000, 1 <= k <= 10, k <= n) — количество точек и количество кластеров.
- Следующие n строк содержат по два вещественных числа x_i и y_i (-10⁶ <= x_i, y_i <= 10⁶) — координаты точек.
- Следующие k строк содержат по два вещественных числа cx_j и cy_j (-10⁶ <= cx_j, cy_j <= 10⁶) — начальные координаты центров кластеров.


Формат выходных данных

- Первая строка должна содержать одно целое число — количество итераций, выполненных до сходимости.
- Следующие k строк должны содержать по два вещественных числа — финальные координаты центров кластеров (в том же порядке, что и во входных данных). Координаты выводить с точностью до 2 знаков после запятой.
- Следующие n строк должны содержать по одному целому числу — номер кластера для каждой точки (нумерация с 0, в том же порядке, что и точки во входных данных).
 

Примечания

- Сходимость достигается, когда координаты всех центров не изменяются между итерациями (с точностью до вычислительной погрешности 1e-9)
- При сравнении расстояний, если точка равноудалена от нескольких центров, она относится к кластеру с меньшим номером
- Если кластер оказался пустым (ни одна точка не была к нему отнесена), его центр остаётся на прежнем месте
- Гарантируется, что алгоритм сойдётся не более чем за 100 итераций