\documentclass[12pt,a4paper,russian]{article}

\usepackage[koi8-r]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsmath,amssymb}
\usepackage{enumerate,url}

\topmargin -0.4cm
\headsep=0.0cm
\headheight=0.0cm
\textheight 24.6cm
\oddsidemargin -0.3cm
\evensidemargin -0.3cm
\textwidth 15.9cm
\sloppy

\begin{document}
\thispagestyle{empty}
\begin{flushright}
\it Задачи к экзамену по курсу \\
``Численные методы'' для 443 группы\\
кафедры физики частиц и космологии\\
весенний семестр 2011-2012 уч. г.
\end{flushright}

%\renewcommand{\labelenumi}{{\bf \lnum.\arabic{enumi}}}
\begin{enumerate}

\item {\it Карта неба по данным Fermi LAT}

  Спутник Fermi LAT регистрирует фотоны с энергиями выше 100~МэВ,
  приходящие с различных направлений. Данные представляют собой
  упорядоченный по времени список зарегистированных
  фотонов~\cite{fermigamma}.

\begin{itemize}
\item Разбить небо на пиксели одинаковой площади одним из существующих
  методов~\cite{projection}.
\item Построить карты интенсивностей излучения на небе для диапазонов
  энергий $E~>~100$~МэВ, $E~>~1$~ГэВ и $E~>~10$~ГэВ. 
\item Построить отдельные карты для событий с различным типом конверсии. 
\end{itemize}

\item {\it Происхождение галактических космических лучей}

 В недавней работе А.~Неронова и Д.~Семикоза~\cite{Neronov:2012kz}
обнаружены протяженные источники гамма-лучей с энергией выше
100~ГэВ и показано, что эти источники могут производить
галактические космические лучи.

Используя фотоны с энергией выше 100 ГэВ, принадлежащие классу
ULTRACLEAN~(cls=4)~\cite{fermigamma}:
\begin{itemize}
\item Разработать алгоритм поиска пространственных кластеров (групп
фотонов) с характериным масштабом $1^\circ$.
\item Для каждого из обнаруженных кластеров, учитывая функцию
рассеяния точки (PSF) для класса событий ULTRACLEAN~\cite{fermipsf},
определить могут ли все фотоны группы принадлежать точечному источнику. 
\item Проверить утверждение работы~\cite{Neronov:2012kz} о том, что все
точечные источники соответсвуют внегалактическим объектам, а все
протяженные -- галактическим остаткам сверхновых возрастом не
более 30 тысяч лет, содержащих в центре пульсар.
\end{itemize}


\item {\it Быстрый поиск событий Fermi LAT}

 При заданных галактических
  координатах $l,b$ и угле $\alpha$ требуется получить выборку фотонов
  Fermi LAT, удаленных от заданных координат на угловое расстояние не
  более $\alpha$. Практически интересные значения $\alpha$ от 0.2 до
  10 градусов, что соответствует ширине функции рассеяния точки для
  различных энергий.
\begin{itemize}
\item Реализовать алгоритм выборки путем последовательного чтения
  файла с жесткого диска.
\item Загрузить все данные в оперативную память и производить выборку
  путем последовательного чтения массива в памяти.
\item Загрузить данные в оперативную память в форме дерева,
  упорядоченного по b (например, std::map или другая реализация) и
  производить сканирование только части дерева от $b - \alpha$ до $b +
  \alpha$. 
\item Предложить алгоритм хранения и выборки обеспечивающий более
  высокую производительность.
\item Сравнить скорость работы различных алгоритмов. Для этого
  требуется выполнять последовательно выборки со случайно заданными
  координатами и угловым размером. Время первичной загрузки данных в
  оперативную память не учитывать.
\end{itemize}


\item {\it Угловое разрешение Fermi LAT по наблюдению пульсара Краба}

Среди фотонов, зарегистрированных Fermi LAT~\cite{fermigamma}, выделить
пришедшие из окрестности пульсара Краба.
\begin{itemize}
\item Построить график зависимости плотности числа фотонов от углового расстояния
  до источника для нескольких энергетических диапазонов ($100~\mbox{МэВ} < E
  < 200 \mbox{МэВ}$, $200~\mbox{МэВ} < E
  < 400 \mbox{МэВ}$ и т.д.). Построить отдельные графики для фотонов с
  различным типом конверсии~\cite{fermigamma}.
\item Определить угловой размер, в пределах которого содержится 68\%
  всех фотонов от источника. Сравнить зависимость полученного углового
  размера от энергии и типа конверсии с результатом, полученным
  коллаборацией Fermi LAT Монте-Карло моделированием~\cite{fermipsf}
 (данные на диске соответствуют классу событий \url{P7SOURCE_V6}).
\end{itemize}

\item {\it Поиск гамма-всплесков в данных Fermi LAT}

\begin{itemize}
\item Реализовать метод скользящего окна для поиска групп фотонов,
пришедших за короткий интервал времени ($\sim 100$ сек) с небольшого
участка неба (в пределах углового разрешения $\lesssim
10^\circ$)~\cite{fermigrb}. Один из примеров, который должен быть
обнаружен данным методом - гамма-всплеск \url{GRB 090902B} с
координатами $l = 51.5^\circ,~b=26.9^\circ$ и временем $t =
273582308.313$~\cite{fermigamma,fermipsf}.
\item Для координат обнаруженных всплесков рассчитать средний поток
  фотонов за весь период наблюдений. Оценить вероятность случайной
  флуктуации такого же размера, как обнаруженный всплеск. Учесть, что
  каждая точка неба находится в поле зрения спутника примерно 1/6 от
  общего времени наблюдения.
\end{itemize}

Замечание: поток гамма-лучей из Галактики $|b| \lesssim 20^\circ$
значительно выше, чем извне, поэтому поиск галактических и
внегалактических всплесков удобно разделить, используя различные
параметры алгоритма.


\item  {\it Спектральный анализ данных на неравномерной решетке }

Быстрое преобразование Фурье требует набор данных на равномерной
решетке. Условия эксперимента могут приводить к тому, что реальная
решетка будет неравномерной. Так, в методе ``photon echo'', широко
применяемом в фемтосекундной спектроскопии, отклик исследуемого
образца измеряется как функция относительных задержек между
несколькими короткими лазерными импульсами, пересекающимися в
образце. Изменение задержки произходит за счет изменения оптического
пути луча посредством механического перемещения зеркала. Техническая
особенность механики состоит в том, что позицию не удается выставить с
пренебрежимо малой ошибкой. С другой стороны, точная позиция зеркала
измеряется интерференционным методом независимым прибором.

В файле \url{photon_echo.dat}~\cite{CD} приведены результаты измерения
интенсивности сигнала в зависимости от временной задержки. Формат
файла (первая колонка -- положение зеркала в мкм, вторая колонка --
интенсивность сигнала в произвольных единицах). Временная задержка
определяется как $t = \frac{2 l}{c}$, так как положение зеркала входит
в оптический путь дважды. Для данной задачи измерены около 30 точек на
период сигнала основной частоты. В реальном эксперименте измеряют не
более 2.5 точек на период (так чтобы частота сигнала была несколько
ниже частоты Найквиста), так как время выполнения эксперимента имеет
критическое значение.

\begin{itemize}
\item Выполнить интерполяцию сплайнам и привести данные к равномерной
  решетке. Вычислить спектр методом FFT.
\item Равномерно проредить данные, уменьшая число точек на период
 оставляя только каждую k-ую из экспериментальных точек. Построить
 спектр для различных k вплоть до предельно возможных значений, при
 которых основная частота превышает частоту Найквиста.
\item Реализовать метод преобразования Фурье для данных на
  неравномерной решетке без интерполяции, согласно алгоритму
  Ломба~\cite{NR,Lomb}. Построить спектр для различных k.
\item Сравнить точность спектров полученных с интерполяцией и без для
  различных значений k. Какой метод позволяет лучше работать с
  наиболее разреженными данными? При сравнении, в качестве
  референс-спектра использовать спектр, полученный с полным набором
  данных. 
\item Можно ли, корректно учитывая эффект наложения, получить спектр
при значениях k, при которых основная частота сигнала превышает
частоту Найквиста?
\end{itemize}


\item {\it Статистическая проверка гипотез о химическом составе
космических лучей }

Одна из величин, измеряемая в эксперименте Telescope Array -- глубина
максимума широких атмосферных ливней (XMAX), вызванных частицами
сверхвысоких энергий. По данной величине можно судить о типе первичной
частицы (в рамках двух крайних гипотез - протон или ядро железа). В
докладе~\cite{tameda} на слайдах 21-25 приведены распределения XMAX
в различных диапазонах энергий в сравнении с Монте-Карло
моделированием, выполненном в предположении первичных протонов и
железа. Из графиков видно, что данные лучше согласуются с гипотезой
протонов, чем с гипотезой первичного железа, что согласуется с
результатом эксперимента HiRes~\cite{Abbasi:2009nf}, но 
противоречит
результату эксперимента Pierre Auger~\cite{Abraham:2010yv}.

\begin{itemize}
\item Проверить статистическим тестом согласие данных с гипотезами
  первичных протонов и железа в каждом из энергетических диапазонов. Использовать
  тесты Колмогорова-Смирнова, Купера и Смирнова-Крамера-фон
  Мизеса. Количество степеней свободы в данных приведено на слайде 27,
  количество степеней свободы на графике Монте-Карло считать
  бесконечным.
\item Выполнить предыдущий пункт для объединенного набора событий (слайд~20).
\item Пусть гипотеза заключается в том, что некая доля $\alpha$ всех
  событий -- железо, а остальные -- протоны. Теоретическое предсказание
  для такой гипотезы можно получить взвешенным сложением Монте-Карло
  распределений для протонов и железа. При каких $\alpha$ гипотеза исключена
  в каждом из энергетических диапазонов, включая $E~>~10^{19}$~эВ с
  уровнем достоверности не менее 95\%.
\end{itemize}

\item {\it Поиск максимального равномерно распределенного подмножества
  событий}

В эксперименте Telescope array производится измерение некой величины
$\mathcal C$ с целью обнаружить присутствие в наборе событий,
вызванных фотонами сверхвысоких энергий~\cite{tagamma}. Файл
\url{Cvalue.dat}~\cite{CD} содержит значение данной величины для 335
событий с энергиями выше $10^{19}$~эВ. Известно, что для фотонных
событий величина $\mathcal C$ распределена равномерно, принимая
значения от 0 до 1. В то же время распределение величины $\mathcal C$
для нефотонных событий неизвестно, так как неизвестен химический
состав космических лучей. Распределение величины $\mathcal C$ для
данных сильно отличается от равномерного, что исключает возможность
фотонного происхождения всех событий. Задача состоит в том, чтобы
поставить ограничение на число фотонов в данном наборе событий. Пусть
в наборе k событий фотоны. В этом случае существует по крайней мере
один набор из k событий, являющийся поднабором исходного,
распределение которых совместно с равномерным.

\begin{itemize}
\item Гипотезу, что в наборе 1 или 2 фотона исключить невозможно.
\item Выбрать три события, для которых распределение значений
  $\mathcal C$ наиболее близко к равномерному. Убедиться, что такая
  гиотеза также не исключена.
\item Увеличивая k искать наиболее совместный с равномерным
  распределением поднабор исходного набора. Найти k при котором все
  побнаборы из k элементов несовместны с равномерным распределением на
  уровне не менее 95\%.
\end{itemize}

Замечание: для решения задачи можно использовать любой статистический
тест, но перебор всех подмножеств --- ресурсоемкая процедура. При
использовании дискретной версии теста Смирнова-Крамера-фон Мизеса
(омега-квадрат) минимизация по поднаборам может быть упрощена.


%\item {\it Нелинейный генератор случайных чисел}
%
%Придумать и реализовать генератор псевдослучайных 32-битных
%   целых чисел, основанный на нелинейной функции и проходящий все
%   тесты пакета DieHard~\cite{diehard}. Результат не должен
%   достигаться за счет смешивания со случайной величиной, полученной
%   одним из линейных методов~\cite{NR}.

%\item {\it Параллельный алгоритм}
%
%Распараллелить вычисления в одной из задач с помощью MPI или
%  openmp. Оценить эффективность алгоритма при росте числа используемых
%  процессорных ядер (можно использовать два 24-ядерных вычислительных
%  сервера в составе кластера теоротдела ИЯИ РАН). Должна быть
%  предусмотрена возможность проверить работу алгоритма в условиях
%  экзамена на машине с двумя процессорными ядрами.

%\item thin and it's fluctuation (estimate)

%\item $phi -> 3 phi, lambda phi^2, E^2 = m^2 + p^4 / M^2, m<<M, p^4/M^2 ~
%   m^2$
%secondary particle distribution 

\end{enumerate}

\begin{thebibliography}{100}
\bibitem{CD} Прилагаемый DVD-диск.

\bibitem{NR}   W.~H.~Press, S.~A.~Teukolsky, W.~T.~Vetterling, B.~P.~Flannery,
  ``Numerical Recipes: The Art of Scientific Computing,'' 3rd edition,
  Cambridge University Press. 2007.

\bibitem{fermigamma} Файл \url{fermi_100M.dat} на прилагаемом
  DVD-диске содержит фотоны с энергией выше 100 МэВ,
 зарегистрированные спутником  Fermi LAT в период с 4 августа
2008 г. по 26 марта 2012 г. В каждой строке файла информация об одном
  зарегистрированном фотоне в формате: t,E,l,b,c,cls, где t -- время в
  секундах с 1 января 2001 года, E -- энергия в МэВ, l,b --
  галактические координаты в градусах, c - тип конверсии (0 -
  зарегистрировано фронтальной частью детектора, 1 - не зарегистрировано
  фронтальной частью), cls -- класс события (2 - SOURCE, 3 - CLEAN, 
4 - ULTRACLEAN). Файл содержит более 52 миллионов фотонов.

\bibitem{projection} M.~R.~Calabretta and E.~W.~Greisen,
 ``Representations of celestial coordinates in FITS,'' Astron.\
 Astrophys.\ {\bf 395}, 1077 (2002) [arXiv:astro-ph/0207413].
 %%CITATION = AAEJA,395,1077;%%

\bibitem{Neronov:2012kz} 
  A.~Neronov and D.~V.~Semikoz,
  ``Origin of TeV Galactic Cosmic Rays,''
  arXiv:1201.1660 [astro-ph.HE].
  %%CITATION = ARXIV:1201.1660;%%

\bibitem{fermipsf}
  \url{http://fermi.gsfc.nasa.gov/ssc/data/analysis/documentation/Cicerone/Cicerone_LAT_IRFs/IRF_PSF.html}

\bibitem{fermigrb}
A. Bouvier, ``Gamma-Ray Burst Observations at High Energy with the
Fermi Large Area Telescope'', PhD thesis,  \url{http://arxiv.org/abs/1012.0558}

\bibitem{Lomb} Lomb, N.R., ``Least-squares frequency analysis of
unequally spaced data,'' Astrophysics and Space Science 39:447-462
1976.

\bibitem{tameda} Y.Tameda, ``HiRes and TA Composition Measurements'', 
International Symposium on Future Directions in Ultra-high Energy Cosmic Ray
 Physics. CERN Feb.13-16, 2012,
\url{http://indico.cern.ch/contributionDisplay.py?contribId=75&confId=152124};
также файл \url{xmax_tameda.pdf} на прилагаемом DVD.

\bibitem{Abbasi:2009nf}
  R.~U.~Abbasi {\it et al.}  [HiRes Collaboration],
  \emph{Indications of Proton-Dominated Cosmic Ray Composition above 1.6 EeV},
  \emph{Phys.\ Rev.\ Lett.}  {\bf 104} (2010) 161101
  [{\tt arXiv:0910.4184}].
  %%CITATION = PRLTA,104,161101;%%

\bibitem{Abraham:2010yv}
  J.~Abraham {\it et al.}  [Pierre Auger Observatory Collaboration],
  \emph{Measurement of the Depth of Maximum of Extensive
    Air Showers above $10^{18}$ eV},
  \emph{Phys.\ Rev.\ Lett.}  {\bf 104} (2010) 091101
  [{\tt arXiv:1002.0699}].
  %%CITATION = PRLTA,104,091101;%%

\bibitem{tagamma} G.Rubtsov, ``Search for ultra-high energy photons
using Telescope Array surface detector'', International Symposium on
the Recent Progress of Ultra-high Energy Cosmic Ray
Observation. Nagoya, JAPAN Dec.10-12, 2010, файл \url{rubtsov_uh10.pdf} на прилагаемом DVD.


%\bibitem{diehard} \url{http://www.stat.fsu.edu/pub/diehard/}



\end{thebibliography}


\end{document}