Статья
Polynomial-time approximation algorithms for the coloring problem in some cases
В работе рассмотрена модификация алгоритмов динамического программирования(АДП), называемых графическими алгоритмами (ГА). Для задачи РАНЕЦ показано, что временная сложность ГА ниже, чем у стандартных АДП. Средняя продолжительность работы ГА также зачастую существенно меньше. ГА также могут решать примеры большой размерности и примеры с нецелочисленными параметрами. В статье представлены параллельные реализации алгоритма для OpenCL и MPI. В ходе экспериментов было замечено, что "сложные" примеры задачи РАНЕЦ имеют параметры p_j = k w_j, где p_j и w_j - ценность и вес предметов.
In this paper, we deal with single machine scheduling problems with a non-renewable resource, such problems are also referred to as financial scheduling problems.
Рассматривается задача построения расписания проекта с учётом ограничений на ресурсы (RCPSP) и её частные случаи. Проведён сравнительный анализ известных нижних оценок целевой функции - минимизации общего времени выполнения проекта. Выдвинута гипотеза, что для задачи RCPSP без прерываний в обслуживании требований оптимальное значение целевой функции не более чем в два раза больше оптимального значения целевой функции соответствующей задачи с прерываниями. Представлены доказательства гипотезы для случаев задачи с параллельными машинами и без отношений предшествования.
Рассматривается задача теории расписаний минимизации суммарного взвешенного момента окончания для одного прибора с возможностью прерывания обслуживания требований. Продолжительности обслуживания всех требований одинаковы. На текущий момент данная задача является открытой, т.е. не известен полиномиальный алгоритм ее решения и не доказано, что она является NP-трудной. Приводятся свойства оптимальных расписаний данной задачи.
Рассматривается графическая реализация метода динамического программирования. Идея метода показана на примерах решения задач разбиение и рюкзака. Проведен сравнительный анализ предлагаемого метода с известными алгоритмами решения этих задач.
We study the scheduling problem for single machine with preemptions of jobs. On a machine it is necessary to process a set of n jobs. Simultaneous processing is prohibited, but interrupts in processing jobs is possible. Each job j of the set is characterize by it's weight w_j, release date r_j = j - 1 and processing time p_j = 2. The only restriction is that weights w_j are non-decreasing. The objective function can be expressed as the sum of weighted completion times. We suggest the polynomial algorithm with complexity O(n^4) operations which gives us the Pareto-optimal schedules for each set of jobs. In the algorithm we use generalized Smith's rule, to obtain particular schedules after moment r_n and to prove some important lemmas for reduction of search of suitable schedules.
Рассматриваются пространства функций на окружности, естественным образом возникающие в гармоническом анализе, и операторы замены переменной (суперпозиции с гомеоморфизмами окружности) в этих пространствах. В работе рассматривается вопрос о том, какие функции обладают тем свойством, что любая их суперпозиция с гомеоморфизмом принадлежит заданному пространству. Рассмотрен также многомерный случай.
Рассматриваются пространства функций на m -мерном торе, преобразование Фурье которых p -суммируемо. Получены оценки норм экспонент деформированных посреством C1 -гладкой фазовой функции. Результаты являются распространением на многомерный случай оценок, полученных автором ранее для одномерного случая в работе «Количественные оценки в теоремах типа теоремы Берлинга--Хелсона» Математический сборник, 201:12 (2010), 103-130.
Рассматриваются пространства функций на окружности таких, что их преобразование Фурье является p-суммируемым. Получены оценки норм экспонент, деформированных посредством C1 -гладкой фазовой функции.
Труды содержат доклады, представленные учеными из России, Украины, Белоруссии, Казахстана, Эстонии, Узбекистана, Германии, Польши, посвященные актуальным проблемам радиационной физики твердого тела (влияние радиации на физико-химические свойства и структуру металлических, полупроводниковых и диэлектрических материалов, влияние факторов космического пространства на свойства конструкционных и функциональных материалов и покрытий космических аппаратов, радиационно-технологические методы получения материалов, в частности наноматериалов, модифицирования и обработки материалов с целью улучшения их эксплуатационных свойств, создание и получение экологически чистых материалов с низкой наведенной радиоактивностью и др.).
Труды содержат доклады, представленные специалистами из России, Украины, Белорусии, Казахстана, Узбекистана, Германии, Великобритании, Польши по направлениям:«Радиационная физика металлов», «Радиационная физика неметаллических материалов», «Физические основы радиационной технологии» и посвященные разнообразным проблемам радиационной физики твердого тела (процессы прохождения заряженных и нейтральных частиц, рентгеновского и гамма-излучений через вещество, электрон-атомные, атом-атомные, ион-атомные и др. столкновения в твердых телах, ориентационные явления при взаимодействии высокоэнергетических частиц с твердым телом, радиационно-индуцированные и радиационно-стимулированные явления в твердых телах и др.).
Настоящая книга представляет собой своеобразный расширенный учебник по математической статистике. Данный учебник не ограничен рамками учебного стандарта или вузовской программы --- он предназначен всем, кто интересуется математикой вообще и, в частности, хочет узнать, что такое современная математическая статистика, какие задачи и какими методами она решает, какие результаты в ней уже накоплены, какие проблемы в ней сегодня актуальны; наконец, каковы ее истоки, какой путь она прошла и какие ученые были ее творцами. По замыслу авторов, книга простым и доступным языком рассказывает о математической статистике и одновременно обучает ей. Вся теория объясняется и иллюстрируется на интересных и тщательно подобранных примерах. Книга может служить и задачником, так как содержит большой список упражнений для самостоятельного решения, а также справочным пособием по математической статистике, а в некоторых аспектах --- и по теории вероятностей.
Книга будет интересна преподавателям, аспирантам и студентам естественных и технических вузов, в которых изучается математическая статистика, научным работникам, использующим в своей деятельности методы математической статистики, а также самому широкому кругу любителей математики.
Эта публикация представляет собой сборник отдельных статей "Третьей Международной конференции по динамике информационных систем», которая состоялась в университете Флориды, 16-18 февраля 2011 года. Цель данной конференции заключалась в том, чтобы собрать вместе ученых и инженеров из промышленности, правительства и научных кругов, чтобы они смогли обменяться новыми открытиями и результатами в вопросах, имеющих отношение к теории и практике динамики информационных систем. Динамика информационных систем: математическое открытие представляет собой современное исследование и предназначается студентам – аспирантам и исследователям, которые интересуются самыми последними открытиями в информационной теории и динамичных системах. Ученые других дисциплин могут также получить пользу от применения новых разработок в своих областях исследований.
В данной работе рассматривается пятое уравнение Пенлеве, которое имеет 4 комплексных параметра α, β, γ, δ. Методами степенной геометрии ищутся асимптотические разложения его решений при x → ∞. При α≠0 найдено 10 степенных разложений с двумя экспоненциальными добавками каждое. Шесть из них - по целым степеням x (они были известны), и четыре по полуцелым (они новые). При α=0 найдено 4 однопараметрических семейства экспоненциальных асимптотик y(x) и 3 однопараметрических семейства сложных разложений x=x(y). Все экспоненциальные добавки, экспоненциальные асимптотики и сложные разложения найдены впервые. Также уточнена техника вычисления экспоненциальных добавок.
Статьи данного сборника написаны на основе докладов, сделанных в 2011 г. на социологическом факультете МГУ им. М.В. Ломоносова на заседании XIV Междисциплинарного ежегодного научного семинара "Математическое моделирование социальных процессов" им. Героя Социалистического труда академика А.А. Самарского.
Издание предназначено для научных сотрудников, преподавателей, учащихся вузов и научных учреждений РАН, интересующихся проблемами, разработкой и внедрением методологии математического моделирования социальных процессов.