?
Разработка эффективного алгоритма масштабирования изображений .
С. 63–64.
Егоров И. В.
В статье описывается разработка эффективного алгоритма масштабирования изображений.
Язык:
русский
В книге
М.: Московский государственный институт электроники и математики, 2012.
Каймаков К. В., Малышев Д. С., Математические заметки 2025 Т. 117 № 5 С. 672–679
В данной работе рассматривается задача о минимальном остовном дереве (кратко, ЗМОД) на произвольном множестве $n$ точек $d$-мерного пространства в $l_1$-норме. Для этой задачи при каждом фиксированном $d\geq 2$ известен алгоритм сложности $O\big(n\cdot (\log\,n + \log^{r_d}\,n\cdot \log\log\,n)\big)$, где $r_d\in \{0,1,2,4\}$ при $d\in \{2,3,4,5\}$ и $r_d=d$ при $d\geq 6$. Для $d=3$ известно улучшение этого результата до сложности ...
Добавлено: 18 января 2025 г.
Каймаков К. В., Малышев Д. С., Математические заметки 2024 Т. 116 № 4 С. 504–509
Для заданных $P=(p_1,\ldots,p_n)$ --- набора точек единичного квадрата и числа $1\leq k\leq \binom{n}{2}$ в данной работе рассматривается задача поиска $k$-ого порядкового расстояния между элементами $P$ в $l_s$-норме, где $s\in \{1,\infty\}$. Иными словами, рассматривается задача поиска такого минимального $d_k$, что выполнено $\sum\limits_{i<j}\indicator(\|p_i,p_j\|_{s} \leq d_k)\geq k$, где $\indicator$ --- индикаторная функция и $s\in \{1,\infty\}$. В настоящей работе ...
Добавлено: 31 мая 2024 г.
Круглов В. Е., Починка О. В., Современная математика. Фундаментальные направления 2022 Т. 68 № 3 С. 467–487
Градиентно-подобные потоки на поверхностях имеют простую динамику, что вдохновляло многих математиков на поиски инвариантов их топологической эквивалентности. В предположениях различной общности на рассматриваемый класс градиентно-подобных потоков, были
получены такие классические инварианты, как схема Леонтович—Майера, граф Пейшото, оснащенный граф Пейшото, двуцветный граф Вонга, трехцветный граф Ошемкова—Шарко, круговая схема Флейтас и др. Таким образом, проблема классификации градиентно-подобных потоков ...
Добавлено: 17 октября 2022 г.
Развенская О. О., Журнал Средневолжского математического общества 2020 Т. 22 № 4 С. 442–448
Классическая NP-трудная задача о взвешенной вершинной раскраске состоит в минимизации количества цветов в раскрасках вершин задаваемого графа так, что для каждой вершины назначаются цвета, количество которых равно задаваемому весу вершины, причем смежным вершинам назначаются различные цвета. Соответствующее наименьшее количество цветов называется взвешенным хроматическим числом графа. Известно несколько полиномиальных алгоритмических приемов для построения эффективных алгоритмов для ...
Добавлено: 16 декабря 2020 г.
Изучение динамики потока на поверхностях путем разбиения фазового пространства на ячейки с одинаковым предельным поведением траекторий внутри ячейки восходит к классическим работам А.А. Андронова, Л.С. Понтрягина, Е.А. Леонтович, А. Г. Майера. Типы ячеек, которых конечное число, и их примыкание друг к другу полностью определяют класс топологической эквивалентности потока с конечным числом особых траекторий. Если в ...
Добавлено: 11 сентября 2017 г.
Малышев Д. С., Сироткин Д. В., Дискретный анализ и исследование операций 2017 Т. 24 № 3 С. 35–60
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. В данной работе доказываем полиномиальную разрешимость этой задачи для субкубических планарных графов, не содержащих порождённого дерева, получаемого отождествлением концов трёх путей длины 3, 3 и 2 соответственно. ...
Добавлено: 31 августа 2017 г.
М.: Горная книга, 2017.
Разработаны модель управления предприятием и последующая реализация программного обеспечения, позволяющего смоделировать варианты развития предприятия в долгосрочном периоде, комплекс программ на MATLAB, реализующих метод авторегрессии, спектрального и корреляционного анализа, программа на языке программирования Python для оценки платежеспособности заемщиков банка на основе модели с использованием нейронных сетей, исследованы характеристики стохастического временного ряда, предложены программы реализации алгоритмов масштабирования ...
Добавлено: 21 августа 2017 г.
Малышев Д. С., Дискретный анализ и исследование операций 2017 Т. 24 № 1 С. 81–96
Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До ...
Добавлено: 27 февраля 2017 г.
Грибанов Д. В., Малышев Д. С., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 19–31
Мы рассматриваем естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования и доказываем полиномиальную разрешимость этих задач для классов графов, имеющих ограниченные по абсолютному значению миноры (расширенных) матриц ограничений. ...
Добавлено: 20 октября 2016 г.
Малышев Д. С., Дискретная математика 2016 Т. 28 № 2 С. 44–50
Класс графов называется монотонным, если он замкнут относительно удалений вершин и рёбер. Любой такой класс может быть задан запрещёнными подграфами. Хроматическим индексом графа называется наименьшее количество цветов, необходимое для такого раскрашивания его рёбер, что любые два соседних ребра имеют разные цвета. В статье получена полная классификация сложности задачи о хроматическом индексе для всех монотонных классов, ...
Добавлено: 5 июля 2016 г.
Круглов В. Е., Починка О. В., Журнал Средневолжского математического общества 2016 Т. 18 № 3 С. 41–48
Изучение динамики потока на поверхностях путем разбиения фазового пространства на ячейки с одинаковым предельным поведением траекторий внутри ячейки восходит к классическим работам А.А. Андронова, Л.С. Понтрягина, Е.А. Леонтович, А. Г. Майера. Типы ячеек (которых конечное число) и их примыкание друг к другу полностью определяют класс топологической эквивалентности потока с конечным числом особых траекторий. Если в ...
Добавлено: 11 июня 2016 г.
Внуков А. А., Егоров И. В., Горный информационно-аналитический бюллетень (научно-технический журнал) 2014 № 9 С. 264–271
Проведен сравнительный анализ эффективности последовательного и параллельного подхода к масштабированию цифровых изображений при программной реализации. Для исследования за образец был выбран метод билинейной интерполяции. В целях исследования была написана тестовая программа на языке С#. Тестирование проводилось путём сравнения времени работы при последовательной и параллельной обработки одних и тех же изображений. Для получения более полной картины, ...
Добавлено: 26 июля 2014 г.
Внуков А. А., Егоров И. В., Горный информационно-аналитический бюллетень (научно-технический журнал) 2014 № 1 С. 238–241
Рассмотрены вопросы, связанные с масштабированием цифровых изображений, оптимизации проводимых вычислений путем использования параллельной обработки. В качестве наиболее подходящей структуры планируется применение многоступенчатого конвейера. Внесено предложение использовать современные ПЛИС в качестве аппаратной основы. ...
Добавлено: 27 мая 2014 г.
Малышев Д. С., Пардалос П. О., Доклады Академии Наук. Информатика 2014 Т. 455 № 5 С. 529–532
Понятие допуска элемента оптимального решения часто используется для анализа устойчивости оптимального решения в задачах комбинаторной оптимизации и служит основой для разработки переборных алгоритмов, решающих эти задачи. В данной работе показывается, что для задачи о взвешенном независимом множестве и двудольного графа с n вершинами и m рёбрами оптимальное решение вычисляется за время O(nm), а все допуски ...
Добавлено: 27 марта 2014 г.
Алексеев В. Е., Замараев В. А., Захарова Д. В. и др., Вестник Нижегородского университета им. Н.И. Лобачевского 2013 № 6(1) С. 165–172
Рассматриваются вопросы асимптотического перечисления наследственных классов графов и их структурного описания, исследуется сложность некоторых задач на таких классах. ...
Добавлено: 3 февраля 2014 г.
Малышев Д. С., Дискретная математика 2013 Т. 25 № 2 С. 63–67
В статье изучается влияние предельного роста упаковочного числа графов (как функции от числа вершин) на сложностной статус задачи о независимом множестве. Доказывается, что при некоторых естественных предположениях эта задача полиномиально разрешима тогда и только тогда, когда упаковочное число растет по порядку не быстрее логарифма числа вершин. ...
Добавлено: 15 января 2014 г.
Малышев Д. С., Дискретный анализ и исследование операций 2013 Т. 20 № 3 С. 26–44
Доказывается полиномиальная разрешимость задачи о независимом множестве для некоторого семейства классов планарных субкубических графов. ...
Добавлено: 23 июня 2013 г.
Гольденгорин Б. И., Малышев Д. С., Пардалос П. О., Doklady Mathematics 2013 Vol. 87 No. 3 P. 368–371
The notion of a tolerance of an element of a combinatorial optimization problem is often used for stability analysis of an optimal solution and it is a base for design branch-and-bound algorithms solving such problems. In this paper we show that for the weighted independent set problem on trees with n vertices all upper and ...
Добавлено: 23 июня 2013 г.
Внуков А. А., Егоров И. В., В кн.: Инновационные информационные технологии. Материалы международной научно-практической конференции, Прага, 22-26 апреля 2013г. Том 2 // Innovative information technologies: Materials of The International Scientific-Practical Conference, Prague, 2013, April 22-26. Part 2Т. 2.: М.: МИЭМ НИУ ВШЭ, 2013. С. 213–218.
В докладе рассматривается вопросы, связанные с масштабированием цифровых изображений, оптимизацией проводимых вычислений путём использования параллельной обработки на основе конвейера. Данный подход предполагает постепенную обработку изображения на нескольких параллельно работающих ступенях. Предложена модель блока масштабирования. ...
Добавлено: 20 мая 2013 г.
Гольденгорин Б. И., Малышев Д. С., Пардалос П. О., Доклады Академии Наук. Информатика 2013 Т. 450 № 4 С. 393–396
Понятие допуска элемента оптимального решения часто используется для анализа устойчивости оптимального решения в задачах комбинаторной оптимизации и служит основой для разработки переборных алгоритмов, решающих эти задачи. В данной работе показывается, что для задачи о взвешенном независимом множестве на деревьях с n вершинами все верхние и нижние допуски вершин могут быть вычислены за время O(n). ...
Добавлено: 17 мая 2013 г.
Малышев Д. С., Дискретный анализ и исследование операций 2013 Т. 20 № 2 С. 75–87
Введено понятие расширяющего оператора для задачи о независимом множестве, являющееся полезным инструментом конструктивного формирования новых случаев эффективной разрешимости этой задачи в семействе наследственных классов графов. Данное понятие применяется к наследственным частям множества Free({P5,C5}). Доказано, что если для связного графа G задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого p она остается таковой в классе ...
Добавлено: 17 мая 2013 г.