Том 20, номер 6, 2013 г., Стр. 16-29

УДК 519.8
Великанова Ю. Ю.
Алгоритмы для одной задачи о нахождении максимума унимодальной функции в режиме online

Аннотация:
Рассматривается задача, возникающая при автофокусировке различных оптических систем. Известно, что функция яркости является гладкой на отрезке и имеет единственный максимум. Значения функции априори неизвестны. Существует измерительное устройство, которое может перемещаться по отрезку в любую точку и измерять в ней значение функции яркости. На перемещение измерительного устройства и вычисление значения затрачивается энергия. Требуется локализовать в ε-интервале максимум функции яркости, затратив как можно меньше энергии. В работе исследуется поведение алгоритмов золотого сечения и дихотомии. Предложены три новых алгоритма для решения этой задачи. Для этих алгоритмов вычислены затраты энергии в лучшем и худшем случаях.
Библиогр. 6.

Ключевые слова: онлайн задача, онлайн алгоритм, минимизация энергии.

Великанова Юлия Юрьевна ^1,2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: julia.velikanova@gmail.com

Статья поступила 20 декабря 2012 г.
Исправленный вариант — 18 мая 2013 г.

Литература

[1] Васильев Ф. П. Методы оптимизации. - М.: Факториал Пресс, 2002. - 824 c.

[2] Кельманов А. В., Пяткин А. В. О сложности некоторых задач кластерного анализа векторных последовательностей // Дискрет. анализ и исслед. операций. - 2013. - Т. 20, № 2. - С. 47–57.

[3] Кельманов А. В., Романченко С. М., Хамидуллин С. А. Приближённые алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, № 3. - С. 27–38.

[4] Krotkov E. Focusing // Int. J. Comput. Vision. - 1987. - N 1. - P. 223–237.

[5] Shen Ch.-H. , Chen H. H. Robust focus measure for low-contrast images //
DOI: 10.1109/ICCE.2006.1598314.

[6] Fiat A., Woeginger G. J. Online algorithms. The state of the art. - Berlin: Springer-Verl., 1998. - P. 13–16. (Lect. Notes Comput. Sci.; Vol. 1442.)