В данной работе рассматривается задача об охране картинной галереи в случае, когда план галереи представляет собой ортогональный многоугольник с вершинами в узлах целочисленной решетки. Проводится точная оценка на число охранников, а также разрабатывается жадный алгоритм расстановки охранников. Для реализации алгоритма выбран язык программирования Python.
Идентификаторы и классификаторы
На сегодняшний день задача об охране картинной галереи является одной из хорошо изученных задач в области вычислительной геометрии [1], она возникает в реальном мире как задача охраны художественной галереи минимальным числом охранников, которые могут наблюдать за всей галереей. В вычислительной геометрии галерея представлена в виде простого многоугольника, а охранник — точкой внутри него. Существует теорема о картинной галерее, которая принадлежит Вацлаву Хваталу, которая утверждает, что для охраны многоугольника из n вершин всегда достаточно n 3 охранников [2]. Позднее той же оценки добился Стив Фиск, значительно упростив доказательство Хватала. Для этого он использовал раскраску вершин многоугольника в три цвета [3].
Список литературы
1. O’Rourke J. Art Gallery Theorems and Algorithms. - New York: Oxford University Press, 1987. - 282 p.
2. Chvatal V. A combinatorial theorem in plane geometry // Journal of Combinatorial Theory, Series B. - 1975. - Vol. 18. - P. 39-41.
3. Fisk S. A short proof of Chvatal’s watchman theorem // Journal of Combinatorial Theory, Series B. - 1978. - Vol. 24, no. 3. - P. 374.
4. Берг М., Чеонг О., Кревельд М., Овермарс М. Вычислительная геометрия. Алгоритмы и приложения. - М.: ДМК Пресс, 2017. - 438 с.
Выпуск
Другие статьи выпуска
Рассматривается однородная задача Дирихле для p(x)-эллиптического уравнения анизотропной диффузии-абсорбции с ограничением значений диффузионного потока. Изучается семейство приближённых решений, получаемых с помощью метода штрафа с применением интегрального оператора штрафа А. Каплана. Устанавливается, что семейство приближённых решений при стремлении малого параметра регуляризации к нулю слабо сходится к решению исходной задачи в пространстве Соболева первого порядка с переменным показателем и что имеет место свойство равномерной аппроксимации в классах функций, непрерывных по Гёльдеру.
В статье рассматривается методы для построения оптимального пути с учетом специфики окружающей обстановки. Начиная от создания графа и заканчивая самим поиском пути. Все действия будут производиться на подробной карте местности, т. е. на карте, на которой изображены все различимые объекты местности.
В современном мире ведутся активные исследования в области анализа пространственных данных. Под пространственными данными в нашем случае понимаются спутниковые изображения, которые составляют основу информационного обеспечения геоинформационных систем. В статье описывается корреляционный метод поиска объектов на спутниковых изображениях.
В статье приводится детальное доказательство единственности меры длины отрезка в евклидовой геометрии, основанной на системе аксиом Гильберта [1]. Обоснования, представленные в учебной литературе [2–5] сжаты и существенно опираются на единственность меры на классе отрезков, являющихся рациональными частями эталона, о чём умалчивается как о само собой разумеющемся факте. Игнорируется сама возможность зависимости меры от точки отсчёта, в частности, от выбора конца отрезка, с которого начинается измерение. Но если для отрезков, кратных эталону при измерении с одного конца, кажется прозрачным, что укладывание эталона с другого конца даст то же самое целое число, то в остальных случаях это совсем не очевидно.
В настоящее время можно наблюдать взрывной рост в использовании сети Интернет и мобильных телефонов, а сближение двух этих технологий открывает широкий диапазон новых возможностей на уже процветающем рынке мультимедиа. Эти возможности побуждают к проведению исследований, которые могут и должны выявить недостатки существующих методов обработки цифровых данных и показать пути их (методов) оптимизации для удовлетворения современных нужд рынка.
В данной работе рассмотрена проблема необходимости проведения экспертизы при реализации инвестиционных проектов. В разработанной математической модели эффективность проекта оценивается показателем NPV. В модели используются априорные оценки дополнительной информации, снижающей неопределенность при принятии решений.
Задача оценки причинных эффектов представляет собой сравнение состояния объекта с учетом и без учета вмешательства и оценки ожидаемой величины полученных различий целевого признака. В работе рассматривается сравнительный анализ методов оценки причинных эффектов на примере производства продукции растениеводства в Алтайском крае. Оценке подлежит причинный эффект от применения интенсивной технологии, предполагающей внесение удобрений и применение средств защиты растений. Тестировались следующие методы: парное сравнение средних, линейная регрессия и матчинг методы (Propensity Score Matching), позволяющие сбалансировать выборку по основным индикативным признакам. Результаты показали, что согласно всем рассматриваемым методам интенсификация производства, даже в засушливых условиях 2012 года привела в ожидаемому росту продуктивности пшеницы, средний ожидаемый эффект от применения интенсивной технологии варьируется от 3,12 ц/га до 3,71 ц/га. Полученные результаты демонстрируют возможность получения более корректных оценок причинных эффектов на основе сбалансированных выборок, использование простого сравнения средних приводит к недооценке или переоценке получаемого эффекта. Также в статье проанализированы ограничения и особенности применения метода Propensity Score Matching в социально-экономических исследованиях.
Проведен анализ способов сбора информации о пользователях на различных площадках в сети интернет. Рассмотрен способ извлечения информации из социальной сети “ВКонтакте”. Для создания информационной базы исследования было выбрано наиболее информативный, на наш взгляд, раздел - список групп, в которых состоит пользователь. В процессе исследования был разработан алгоритм разбора текста до уровня понимания компьютером. С помощь наивного байесовского классификатора реализована классификация социального положения пользователя. Этот же алгоритм без каких-либо изменений можно адаптировать к классификации интересов пользователя.
Предложен вариант оценки самообразовательной компетентности выпускника вуза, разработанный методами нечеткого моделирования. Итоговый показатель развития самообразовательной компетентности выпускника моделируется из показателей развития универсальных и обще профессиональных самообразовательных компетенций студента, сформированных в процессе обучения.
В работе освящен вопрос использования систем компьютерной математики при исследовании гладких регулярных кривых. В системах прикладных программ Maxima и SageMath разработаны алгоритмы, позволяющие вычислять кривизну и кручение кривой по заданным входным параметрам - векторному уравнению кривой.
Данная работа направлена на определение конформно-киллинговых векторных полей на неразложимом эйнштейновом симметрическом четырехмерном лоренцевом многообразии. Для вычисления конформно киллинговых полей используется система координат Бринкмана.
Среди свободно распространяемых универсальных математических систем особое место занимают Maxima и SageMath. В статье приводится авторская реализация компьютерных моделей в среде данных пакетов прикладных программ, позволяющая определять первую и вторую квадратичные формы поверхности.
В работе на данных модельной задачи рассматривается процесс оптимизации стоимости выполнения проекта при заданном (директивном) сроке его выполнения, то есть рассматриваются вопросы оптимального согласования стоимости реализации проекта и интенсивности его реализации. При этом речь идёт об использовании трудовых ресурсов различного уровня квалификации и различного уровня технической оснащённости, что выражается в различной стоимости, как оплаты труда, так и стоимости прочей оснащённости проекта. На основе модельной задачи разработан программный продукт на языке программирования C++ для численных расчётов временных характеристик комплексов работ.
Издательство
- Издательство
- АлтГУ
- Регион
- Россия, Барнаул
- Почтовый адрес
- 656049, Алтайский край, город Барнаул, проспект Ленина, дом 61
- Юр. адрес
- 656049, Алтайский край, город Барнаул, проспект Ленина, дом 61
- ФИО
- Бочаров Сергей Николаевич (Руководитель)
- E-mail адрес
- rector@asu.ru
- Контактный телефон
- +7 (385) 2291291
- Сайт
- https://www.asu.ru/