Различия

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

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

Предыдущая версия справа и слева Предыдущая версия
Следующая версия
Предыдущая версия
Последняя версия Следующая версия справа и слева
research:prob_median_petya [2018/09/09 01:36]
nikita [Задание 1]
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}$. Порядок трудоемкости метода надо обосновать.
Строка 10: Строка 12:
 Трудоемкость (по порядку) не больше $N^2$:  2 курс – 15 баллов, 1 курс – 30 баллов. \\ Трудоемкость (по порядку) не больше $N^2$:  2 курс – 15 баллов, 1 курс – 30 баллов. \\
 Трудоемкость (по порядку) не больше $N \log N$: 2 курс – 20 баллов, 1 курс – 40 баллов. \\ Трудоемкость (по порядку) не больше $N \log N$: 2 курс – 20 баллов, 1 курс – 40 баллов. \\
-Трудоемкость (по порядку) в среднем линейная по $N$, с объяснением: 2 курс – 40 баллов, 1 курс – 80 баллов. +Трудоемкость (по порядку) в среднем линейная по $N$ или детерминированная $O(N)$, с объяснением: 2 курс – 40 баллов, 1 курс – 80 баллов. 
  
 ==== Подготовка ==== ==== Подготовка ====
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