Вычисление взвешенной медианы для Пети, фотографирующего филинов

Обратите внимание: это задание больше не принимается, так как его решение описано в книге Т. Кормена и пр. «Алгоритмы: построение и анализ».

Тому, кто уже успел его сдать, баллы зачтены.

Задание 1

Петя – любитель живой природы. Он пытается измерить размах крыльев обыкновенного филина. Для этого он сфотографировал филина в полёте $N$ раз, после чего на каждой фотографии провёл измерение $x_i$ требуемого параметра, $1 \le i \le N$. Однако фотографии получились смазанными, некоторые сильно, некоторые нет. Фоторедактор на компьютере Пети умеет для каждой фотографии определять её «вес» $w_i$ в выборке: чем чётче фотография (то есть, «вес» $w_i$ больше), тем вероятнее, что измерение лежит близко к настоящему значению. Петя обратился за помощью к своему научному руководителю ВВ. Тот предложил ему оценить размах крыльев филина с помощью взвешенного метода наименьших абсолютных отклонений: $m_{opt} = \text{argmin}_{m} \sum_{1 \le i \le N} w_i |m - x_i|$. Требуется найти $m_{opt}$. Петю устроит любое $m_{opt}$, на котором достигается минимум. Важна быстрота подсчета $m_{opt}$. Порядок трудоемкости метода надо обосновать.

Баллы

Баллы зависят от трудоемкости по $N$.

Любая трудоемкость: 2 курс - 10 баллов, 1 курс – 20 баллов.
Трудоемкость (по порядку) не больше $N^2$: 2 курс – 15 баллов, 1 курс – 30 баллов.
Трудоемкость (по порядку) не больше $N \log N$: 2 курс – 20 баллов, 1 курс – 40 баллов.
Трудоемкость (по порядку) в среднем линейная по $N$ или детерминированная $O(N)$, с объяснением: 2 курс – 40 баллов, 1 курс – 80 баллов.

Подготовка

Нужно написать программу, где на вход поступает $N$, затем $N$ измерений размаха $x_i$ и положительных весов $w_i$. Можно для простоты считать, что $w_i$ и $x_i$ целочисленные. Результатом программы является найденное $m_{opt}$. Задача на то, чтобы придумать, как можно минимизировать нужную функцию. Чтобы программа работала для большого $N$, нужно воспользоваться свойствами конкретной целевой функции.

Для начала нужно понять, почему при равных весах $w_i=1$ минимум достигается на выборочной медиане.

Руководитель

Никита Звонарев

research/prob_median_petya.txt · Последнее изменение: 2020/10/31 23:22 — nina
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0