Статья
Исследование граничных классов графов для задач о раскраске
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту задачи о раскраске. Оказывается, что любой класс, граничный для задачи о реберной 3-раскраске, является граничным для задачи о хроматическом индексе. Вместе с тем, при любом k > 3 существует континуум классов графов, граничных для задачи о реберной k-раскраске, каждый из которых не является граничным для задачи о хроматическом числе. Формулируется необходимое условие существования граничных классов графов для задачи о вершинной 3-раскраске, не являющихся граничными для задачи о хроматическом числе. По мнению автора, заключение этого условия никогда не выполняется, поэтому таковых классов вовсе не существует.
Сборник содержит доклады, представленные на XVI Международной конференции «Проблемы теоретической кибернетики» (Нижний Новгород, 20–25 июня 2011 г.), организованной при поддержке Российского фонда фундаментальных исследований (проект №11-01-06036-г). Для научных работников и специалистов в области математической кибернетики, дискретной математики, информатики и их приложений.
Proceedings include extended abstracts of reports presented at the III International Conference on Optimization Methods and Applications “Optimization and application” (OPTIMA-2012) held in Costa da Caparica, Portugal, September 23—30, 2012.
Эта публикация представляет собой сборник отдельных статей "Третьей Международной конференции по динамике информационных систем», которая состоялась в университете Флориды, 16-18 февраля 2011 года. Цель данной конференции заключалась в том, чтобы собрать вместе ученых и инженеров из промышленности, правительства и научных кругов, чтобы они смогли обменяться новыми открытиями и результатами в вопросах, имеющих отношение к теории и практике динамики информационных систем. Динамика информационных систем: математическое открытие представляет собой современное исследование и предназначается студентам – аспирантам и исследователям, которые интересуются самыми последними открытиями в информационной теории и динамичных системах. Ученые других дисциплин могут также получить пользу от применения новых разработок в своих областях исследований.
Рассматривается понятие граничного класса, которое является полезным инструментом для анализа вычислительной сложности задач на графах. Исследуются два конкретных класса графов, и приводятся задачи, для которых эти классы являются граничными.
Исследована задача решения линейных уравнений над множеством подстановок первого порядка. Получена полная классификация вычислительной сложности этой задачи в зависимости от вида уравнений.
Рассматриваются класс всех графов, у которых каждая компонента связности является деревом с не более чем 3 листьями, и класс рёберных графов к графам этого класса. Известен ряд задач, для которых эти классы являются граничными. В работе исследуются общие свойства таких задач. Именно, доказывается достаточное условие граничности рассматриваемых классов. При помощи полученного инструмента к известным случаям граничности данных классов добавляется восемь новых.
Для задач о вершинной 3-раскраске и о реберной 3-раскраске указываются континуальные множества граничных классов графов. Это первые примеры задач на графах с множествами граничных классов такой мощности.
В ситуациях, когда коллективу требуется принять решение на основе множества индивидуальных предпочтений, применяется тот или иной метод агрегирования, в частности, голосование. Одной из главных проблем для любой недиктаторской процедуры выбора является манипулирование - возможность у избирателей добиться более выгодного для себя исхода голосования при помощи искажения своих предпочтений. Один из подходов, используемых для сравнения процедур по степени манипулируемости, – выявление класса сложности задачи манипулирования при том или ином методе агрегирования. В настоящей работе представлен обзор литературы по исследованию классов сложности задач манипулирования при различных предположениях и ограничениях в модели.
Сборник составлен по результатам исследований молодых ученых, аспирантов и студентов МЭСИ, а также ряда вузов Москвы, Йошкар-Олы, Магнитогорска, Махачкалы, Пензы, Саранска, Саратова, Улан-Удэ. Рассмотренные на конференции (июнь 2011 г.) результаты исследований посвящены вопросам статистической методологии, применению математико-статистических и эконометрических методов в различных отраслях экономики и социальной сфере. Обобщается зарубежный опыт статистического анализа ряда проблем экономической и социальной жизни. Сравнивается эффективность различных методов, формулируются рекомендации по их выбору в зависимости от специфики решаемой задачи.
В данной работе рассматривается пятое уравнение Пенлеве, которое имеет 4 комплексных параметра α, β, γ, δ. Методами степенной геометрии ищутся асимптотические разложения его решений при x → ∞. При α≠0 найдено 10 степенных разложений с двумя экспоненциальными добавками каждое. Шесть из них - по целым степеням x (они были известны), и четыре по полуцелым (они новые). При α=0 найдено 4 однопараметрических семейства экспоненциальных асимптотик y(x) и 3 однопараметрических семейства сложных разложений x=x(y). Все экспоненциальные добавки, экспоненциальные асимптотики и сложные разложения найдены впервые. Также уточнена техника вычисления экспоненциальных добавок.
Российские ученые разработали модельный суперкомплекс для долгосрочного прогнозирования развития мировой экономики
Статьи данного сборника написаны на основе докладов, сделанных в 2011 г. на социологическом факультете МГУ им. М.В. Ломоносова на заседании XIV Междисциплинарного ежегодного научного семинара "Математическое моделирование социальных процессов" им. Героя Социалистического труда академика А.А. Самарского.
Издание предназначено для научных сотрудников, преподавателей, учащихся вузов и научных учреждений РАН, интересующихся проблемами, разработкой и внедрением методологии математического моделирования социальных процессов.
Получена форма несмещенной оценки коэффициента детерминации для линейного уравнения регрессии, вычисляемая по выборочным данным из многомерного нормального распределения. Эту оценку предлагается применять как альтернативный критерий выбора факторов в регрессии.