Книга
Lecture Notes in Computer Science
This volume constitutes the refereed proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, MFCS 2012, held in Bratislava, Slovakia, in August 2012. The 63 revised full papers presented together with 8 invited talks were carefully reviewed and selected from 162 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, databases and knowledge-based systems, foundations of computing, logic in computer science, models of computation, semantics and verification of programs, and theoretical issues in artificial intelligence.
We present an algorithm which computes the Lempel-Ziv factorization of a word $W$ of length $n$ on an alphabet $\Sigma$ of size $\sigma$ online in the following sense: it reads $W$ starting from the left, and, after reading each $r = O(\log_{\sigma}{n})$ characters of $W$, updates the Lempel-Ziv factorization. The algorithm requires $O(n\log\sigma)$ bits of space and $O(n \log^2{n})$ time. The basis of the algorithm is a sparse suffix tree combined with wavelet trees.
В статье рассматривается феномен увлеченности онлайн-играми, в частности массовыми многопользовательскими ролевыми онлайн-играми, предлагается разграничить понятия увлеченности и зависимости. Ставится вопрос о характере влияния увлеченности онлайн- играми на социальные навыки и интенсивность коммуникации игроков. На основе обзора зарубежной литературы анализируются такие концепты, как игра, игровая зависимость, игровая увлеченность, социальный капитал, социальные навыки, интенсивность коммуникаций игроков. Во второй части статьи представлены результаты эмпирического исследования, основанного на онлайн анкетировании 479 игроков многопользовательских онлайн-игр. Для анализа данных применялись логистическая и парная линейная регрессии. Результаты исследования показали, что увлеченность играми негативно влияет на интенсивность коммуникаций, однако было обнаружено и некоторое позитивное ее влияние на развитие социальных навыков. Эти выводы расходятся с теми, что были получены зарубежными коллегами, фиксирующими исключительно пагубное влияние увлеченности онлайн-играми. Авторы статьи переосмысливают десоциализирующий эффект увлеченности онлайн- игр, предполагая, что он выражен в гораздо меньшей степени, чем это утверждается многими другими исследователями.
В статье рассказывается об экспедиции менеджеров из постсоветских государств в Западную Африку (Бенин, Того и Гану), проведенной в октябре – ноябре 2012 г. Институтом Африки РАН и научно-консалтинговой группой «ДиБиЭй-концепт» под руководством ученых-авторов статьи. Экспедиция имела одновременно обучающий и исследовательский характер: погружаясь в миры африканских культур, ее участники искали и находили в них параллели с собственным профессиональным и жизненным опытом, призванные помочь их дальнейшему карьерному и личностному росту. В том, какие основные «открытия» сделали для себя эти образованные, успешные, но впервые побывавшие в Африке люди, чем оказалась важна для них Африка, по мнению авторов статьи, содержится много поучительного относительно значимости культур народов этого континента в общем контексте современной мировой культуры.
This book constitutes the proceedings of the 35th International Conference on Application and Theory of Petri Nets and Concurrency, PETRI NETS 2014, held in Tunis, Tunisia, in June 2014. The 15 regular papers and 4 tool papers presented in this volume were carefully reviewed and selected from 48 submissions. In addition the book contains 3 invited talks in full paper length. The papers cover various topics in the field of Petri nets and related models of concurrency.
Характерная особенность моделей Крипке и большинства темпоральных логик (PLTL, CTL, PDL, mu-исчисление и др.), используемых в качестве формальных языков спецификации, состоит в том, что элементарные свойства вычислений зависят только от состояний модели, но не от вычислений, которыми достигаются состояния. Однако для стороннего наблюдателя поведение реагирующей системы проявляется в соответствии между последовательностями стимулов (сигналов), которыми внешняя среда воздействует на систему, и откликов (действий), которые вырабатывает или исполняет система в ответ на внешние воздействия. Поэтому при верификации некоторых видов реагирующих систем элементарными свойствами становятся множества конечных последовательностей действий. Это обстоятельство должно быть также учтено при разработке формального языка спецификаций поведения таких систем. В данной статье рассмотрена задача формальной верификации реагирующих систем, моделируемых конечными автоматами-преоб\-разователями. Для спецификации их поведения предложен новый вариант темпоральной логики линейного времени LTL-FL (LTL with Formal Languages). Формальные языки (множества конечных слов фиксированных алфавитов) в формулах LTL-FL используются для представления элементарных свойств вычислений, а также для параметризации темпоральных операторов. Установлено, что задача проверки выполнимости формул регулярного фрагмента FL-LTL на конечных автоматах преобразователях разрешима.
This paper regards problems of analysis and verification of complex modern operating systems, which should take into account variability and configurability of those systems. The main problems of current interest are related with conditional compilation as variability mechanism widely used in system software domain. It makes impossible fruitful analysis of separate pieces of code combined into system variants, because most of these pieces of code has no interface and behavior. From the other side, analysis of all separate variants is also impossible due to their enormous number. The paper provides an overview of analysis methods that are able to cope with the stated problems, distinguishing two classes of such approaches: analysis of variants sampling based on some variants coverage criteria and variation-aware analysis processing many variants simultaneously and using similarities between them to minimize resources required. For future development we choose the most scalable technics, sampling analysis based on code coverage and on coverage of feature combinations and variation-aware analysis using counterexample guided abstraction refinement approach.
Обсуждаются подходы к моделированию взаимозависимостей в экономике, показаны сложности, которые возникают при анализе такого рода моделей. Представлен ряд полученных автором результатов, относящихся к зависимости состояния экономики от структуры экономической системы. Внимание уделяется таким технологическим характеристикам, как степень дополняемости факторов или усилий агентов, и сетевых характеристик системы. Мы прослеживаем это отличие на примерах моделей с промежуточными товарами и сетевых игр. Показана также роль взаимозависимости в формировании поведения потребителя.
Изучается задача минимизации среднеквадратичного отклонения однородной струны с закрепленными концами от положения равновесия. Управлением служит плотность внешних сил, действующих на струну. Предполагается, что заданы начальные условия и концы струны закреплены. Используется метод Фурье, который позволяет задачу управления уравнением в частных производных свести к задаче управления счетной системой обыкновенных дифференциальных уравнений. Для полученной задачи оптимального управления в пространстве l2 доказано, что оптимальный синтез содержит особые траектории и траектории с учащающимися переключениями. Для исходной задачи оптимального управления колебаниями струны доказано, что существует единственное решение, при этом оптимальное управление имеет счетное число переключений на конечном интервале времени.
Изучаются класс задач оптимального управления и порожденные ими гамильтоновы системы в пространстве l 2. Доказывается существование экстремалей со счетным числом переключений на конечном интервале времени. Построен оптимальный синтез в пространстве l 2, образующий расслоение с кусочно-гладкими двумерными слоями, состоящими из экстремалей со счетным числом переключений, над бесконечномерной базой особых экстремалей.
В данной работе рассматривается пятое уравнение Пенлеве, которое имеет 4 комплексных параметра α, β, γ, δ. Методами степенной геометрии ищутся асимптотические разложения его решений при x → ∞. При α≠0 найдено 10 степенных разложений с двумя экспоненциальными добавками каждое. Шесть из них - по целым степеням x (они были известны), и четыре по полуцелым (они новые). При α=0 найдено 4 однопараметрических семейства экспоненциальных асимптотик y(x) и 3 однопараметрических семейства сложных разложений x=x(y). Все экспоненциальные добавки, экспоненциальные асимптотики и сложные разложения найдены впервые. Также уточнена техника вычисления экспоненциальных добавок.
Эта публикация представляет собой сборник отдельных статей "Третьей Международной конференции по динамике информационных систем», которая состоялась в университете Флориды, 16-18 февраля 2011 года. Цель данной конференции заключалась в том, чтобы собрать вместе ученых и инженеров из промышленности, правительства и научных кругов, чтобы они смогли обменяться новыми открытиями и результатами в вопросах, имеющих отношение к теории и практике динамики информационных систем. Динамика информационных систем: математическое открытие представляет собой современное исследование и предназначается студентам – аспирантам и исследователям, которые интересуются самыми последними открытиями в информационной теории и динамичных системах. Ученые других дисциплин могут также получить пользу от применения новых разработок в своих областях исследований.
В работе построено новое распределение, отвечающее реальному благородному газу, а также уравнение состояний для него.
Статьи данного сборника написаны на основе докладов, сделанных в 2011 г. на социологическом факультете МГУ им. М.В. Ломоносова на заседании XIV Междисциплинарного ежегодного научного семинара "Математическое моделирование социальных процессов" им. Героя Социалистического труда академика А.А. Самарского.
Издание предназначено для научных сотрудников, преподавателей, учащихся вузов и научных учреждений РАН, интересующихся проблемами, разработкой и внедрением методологии математического моделирования социальных процессов.