Статья
Hardness of Approximation for H-free Edge Modification Problems
В работе рассмотрена модификация алгоритмов динамического программирования(АДП), называемых графическими алгоритмами (ГА). Для задачи РАНЕЦ показано, что временная сложность ГА ниже, чем у стандартных АДП. Средняя продолжительность работы ГА также зачастую существенно меньше. ГА также могут решать примеры большой размерности и примеры с нецелочисленными параметрами. В статье представлены параллельные реализации алгоритма для 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 -гладкой фазовой функции.
Настоящая книга представляет собой своеобразный расширенный учебник по математической статистике. Данный учебник не ограничен рамками учебного стандарта или вузовской программы --- он предназначен всем, кто интересуется математикой вообще и, в частности, хочет узнать, что такое современная математическая статистика, какие задачи и какими методами она решает, какие результаты в ней уже накоплены, какие проблемы в ней сегодня актуальны; наконец, каковы ее истоки, какой путь она прошла и какие ученые были ее творцами. По замыслу авторов, книга простым и доступным языком рассказывает о математической статистике и одновременно обучает ей. Вся теория объясняется и иллюстрируется на интересных и тщательно подобранных примерах. Книга может служить и задачником, так как содержит большой список упражнений для самостоятельного решения, а также справочным пособием по математической статистике, а в некоторых аспектах --- и по теории вероятностей.
Книга будет интересна преподавателям, аспирантам и студентам естественных и технических вузов, в которых изучается математическая статистика, научным работникам, использующим в своей деятельности методы математической статистики, а также самому широкому кругу любителей математики.
В данной работе рассматривается пятое уравнение Пенлеве, которое имеет 4 комплексных параметра. Методами степенной геометрии ищутся асимптотические разложения его решений в окрестности его неособой точки z=z0, z0≠0, z0≠∞, при любых значениях параметров уравнения. Показано, что имеется ровно 10 семейств разложений решений уравнения. Все они - по целым степеням локальной переменной z - z0. Из них одно новое; у него произвольный коэффициент при четвертой степени локальной переменной. Одно из семейств однопараметрическое, остальные - двухпараметрические. Доказано, что все разложения сходятся в окрестности (а являющиеся полюсами - в проколотой окрестности) точки z=z0.
В учебном пособии рассматриваются базовые вопросы компьютерной лингвистики: от теории лингвистического и математического моделирования до вариантов технологических решений. Дается лингвистическая интерпретация основных лингвистических объектов и единиц анализа. Приведены сведения, необходимые для создания отдельных подсистем, отвечающих за анализ текстов на естественном языке. Рассматриваются вопросы построения систем классификации и кластеризации текстовых данных, основы фрактальной теории текстовой информации.
Предназначено для студентов и аспирантов высших учебных заведений, работающих в области обработки текстов на естественном языке.
В данной работе рассматривается пятое уравнение Пенлеве, которое имеет 4 комплексных параметра α, β, γ, δ. Методами степенной геометрии ищутся асимптотические разложения его решений при x → ∞. При α≠0 найдено 10 степенных разложений с двумя экспоненциальными добавками каждое. Шесть из них - по целым степеням x (они были известны), и четыре по полуцелым (они новые). При α=0 найдено 4 однопараметрических семейства экспоненциальных асимптотик y(x) и 3 однопараметрических семейства сложных разложений x=x(y). Все экспоненциальные добавки, экспоненциальные асимптотики и сложные разложения найдены впервые. Также уточнена техника вычисления экспоненциальных добавок.
В данной работе рассматривается пятое уравнение Пенлеве. Методами степенной геометрии ищутся асимптотические разложения его решений при x → 0. Получено 27 семейств разложений решений уравнения. 19 из них получены из разложений решений шестого уравнения Пенлеве. Среди остальных 8 семейств одно было известно раньше, ещё одно может быть получено из разложения решения третьего уравнения Пенлеве. Новыми являются 3 семейства полуэкзотических разложений, 2 семейства сложных разложений и семейство степенно-логарифмических разложений.