Различия

Здесь показаны различия между двумя версиями данной страницы.

Ссылка на это сравнение

Предыдущая версия справа и слева Предыдущая версия
research:prob_median_petya [2018/09/09 15:00]
nikita [Баллы]
research:prob_median_petya [2018/09/15 00:03] (текущий)
nikita
Строка 1: Строка 1:
 ====== Вычисление взвешенной медианы для Пети, фотографирующего филинов ====== ====== Вычисление взвешенной медианы для Пети, фотографирующего филинов ======
- + <note warning>​Обратите внимание:​ это задание больше не принимается,​ так как его решение описано в книге Т. Кормена и пр. "​Алгоритмы:​ построение и анализ"​. 
 + 
 +Тому, кто уже успел его сдать, баллы зачтены.</​note>​
 ===== Задание 1 ===== ===== Задание 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$ раз, после чего на каждой фотографии провёл измерение $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}$. Порядок трудоемкости метода надо обосновать.
research/prob_median_petya.txt · Последние изменения: 2018/09/15 00:03 — nikita
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0