Статья
Граничные классы графов для некоторых задач распознавания
Рассматриваются класс всех графов, у которых каждая компонента связности является деревом с не более чем 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.
Дается новое определение граничного класса графов и доказывается критерий граничности. В качестве примера его применения рассматривается класс, состоящий из графов, у которых каждая компонента связности является деревом с не более чем тремя листьями. Известен ряд задач, для которых этот класс является граничным. Получены достаточные условия его граничности и доказано, что он является граничным для задач о наибольшем двудольном подграфе и наибольшем планарном подграфе.
Исследована задача решения линейных уравнений над множеством подстановок первого порядка. Получена полная классификация вычислительной сложности этой задачи в зависимости от вида уравнений.
В ситуациях, когда коллективу требуется принять решение на основе множества индивидуальных предпочтений, применяется тот или иной метод агрегирования, в частности, голосование. Одной из главных проблем для любой недиктаторской процедуры выбора является манипулирование - возможность у избирателей добиться более выгодного для себя исхода голосования при помощи искажения своих предпочтений. Один из подходов, используемых для сравнения процедур по степени манипулируемости, – выявление класса сложности задачи манипулирования при том или ином методе агрегирования. В настоящей работе представлен обзор литературы по исследованию классов сложности задач манипулирования при различных предположениях и ограничениях в модели.
В первой части пособия рассмотрены дополнительные вопросы теории вероятностей, необходимые для изучения математической статистики, и начальные сведения по математической статистике.
Во второй части пособия подробно изложены вопросы, связанные с решением одной из основных задач математической статистики - параметрической задачи. Приведено много примеров.
Рекомендуется всем студентам МИЭМа, изучающим математическую статистику.
Центр конъюнктурных исследований Института статистических исследований и экономики знаний НИУ ВШЭ представляет информационно-аналитический материал «Деловой климат в оптовой торговле в I квартале 2012 года», подготовленный в рамках Программы фундаментальных исследований НИУ ВШЭ на основе ежеквартальных конъюнктурных опросов руководителей около 3 тыс. торговых компаний, проводимых Федеральной службой государственной статистики.
Конъюнктурные обследования направлены на оперативное получение от предпринимателей в дополнение к официальным статистическим данным краткосрочных качественных оценок о состоянии бизнеса и основных тенденциях его динамики, особенностях функционирования хозяйствующих субъектов, их намерениях, степени адаптации к механизмам хозяйствования, сложившемся деловом климате, а также о важнейших факторах, лимитирующих их деятельность.
Программа обследования гармонизирована с соответствующими подходами, принятыми в странах ОЭСР, и базируется на Гармонизированной Европейской Системе обследований деловых тенденций.
Структура выборочной совокупности идентична структуре генеральной статистической совокупности. При этом объем выборки достаточен для получения необходимой точности оценок показателей на всех уровнях разработки по разделу ОКВЭД (раздел G).
Настоящая книга представляет собой своеобразный расширенный учебник по математической статистике. Данный учебник не ограничен рамками учебного стандарта или вузовской программы --- он предназначен всем, кто интересуется математикой вообще и, в частности, хочет узнать, что такое современная математическая статистика, какие задачи и какими методами она решает, какие результаты в ней уже накоплены, какие проблемы в ней сегодня актуальны; наконец, каковы ее истоки, какой путь она прошла и какие ученые были ее творцами. По замыслу авторов, книга простым и доступным языком рассказывает о математической статистике и одновременно обучает ей. Вся теория объясняется и иллюстрируется на интересных и тщательно подобранных примерах. Книга может служить и задачником, так как содержит большой список упражнений для самостоятельного решения, а также справочным пособием по математической статистике, а в некоторых аспектах --- и по теории вероятностей.
Книга будет интересна преподавателям, аспирантам и студентам естественных и технических вузов, в которых изучается математическая статистика, научным работникам, использующим в своей деятельности методы математической статистики, а также самому широкому кругу любителей математики.
В данной работе рассматривается пятое уравнение Пенлеве, которое имеет 4 комплексных параметра α, β, γ, δ. Методами степенной геометрии ищутся асимптотические разложения его решений при x → ∞. При α≠0 найдено 10 степенных разложений с двумя экспоненциальными добавками каждое. Шесть из них - по целым степеням x (они были известны), и четыре по полуцелым (они новые). При α=0 найдено 4 однопараметрических семейства экспоненциальных асимптотик y(x) и 3 однопараметрических семейства сложных разложений x=x(y). Все экспоненциальные добавки, экспоненциальные асимптотики и сложные разложения найдены впервые. Также уточнена техника вычисления экспоненциальных добавок.
Эта публикация представляет собой сборник отдельных статей "Третьей Международной конференции по динамике информационных систем», которая состоялась в университете Флориды, 16-18 февраля 2011 года. Цель данной конференции заключалась в том, чтобы собрать вместе ученых и инженеров из промышленности, правительства и научных кругов, чтобы они смогли обменяться новыми открытиями и результатами в вопросах, имеющих отношение к теории и практике динамики информационных систем. Динамика информационных систем: математическое открытие представляет собой современное исследование и предназначается студентам – аспирантам и исследователям, которые интересуются самыми последними открытиями в информационной теории и динамичных системах. Ученые других дисциплин могут также получить пользу от применения новых разработок в своих областях исследований.
Статьи данного сборника написаны на основе докладов, сделанных в 2011 г. на социологическом факультете МГУ им. М.В. Ломоносова на заседании XIV Междисциплинарного ежегодного научного семинара "Математическое моделирование социальных процессов" им. Героя Социалистического труда академика А.А. Самарского.
Издание предназначено для научных сотрудников, преподавателей, учащихся вузов и научных учреждений РАН, интересующихся проблемами, разработкой и внедрением методологии математического моделирования социальных процессов.