Статья
Вычисление длиннейшей общей подстроки с одной ошибкой
Описан алгоритм, решающий задачу нахождения приближенной максимальной общей подстроки двух строк $\alpha_1$ и $\alpha_2$ за время $O(\abs{\alpha_1} \abs{\alpha_2})$ с использованием $O(\abs{\alpha_1})$ дополнительной памяти. При обращении к строке $\alpha_2$ алгоритм читает ее только \emph{слева направо, начиная с первого символа}. Используется RAM-модель вычислений.
We revisit two variants of the problem of computing minimal discriminating words studied in [5]. Given a pattern P and a threshold d, we want to report (i) all shortest extensions of P which occur in less than d documents, and (ii) all shortest extensions of P which occur only in d selected documents. For the rst problem, we give an optimal solution with constant time per output word. For the second problem, we propose an algorithm with running time O(jPj + d (1 + output)) improving the solution of [5].
Эта публикация представляет собой сборник отдельных статей "Третьей Международной конференции по динамике информационных систем», которая состоялась в университете Флориды, 16-18 февраля 2011 года. Цель данной конференции заключалась в том, чтобы собрать вместе ученых и инженеров из промышленности, правительства и научных кругов, чтобы они смогли обменяться новыми открытиями и результатами в вопросах, имеющих отношение к теории и практике динамики информационных систем. Динамика информационных систем: математическое открытие представляет собой современное исследование и предназначается студентам – аспирантам и исследователям, которые интересуются самыми последними открытиями в информационной теории и динамичных системах. Ученые других дисциплин могут также получить пользу от применения новых разработок в своих областях исследований.
We study a new variant of the pattern matching problem called cross-document pattern matching, which is the problem of indexing a collection of documents to support an efficient search for a pattern in a selected document, where the pattern itself is a substring of another document. Several variants of this problem are considered, and efficient linear space solutions are proposed with query time bounds that either do not depend at all on the pattern size or depend on it in a very limited way (doubly logarithmic). As a side result, we propose an improved solution to the weighted ancestor problem.
We study the following three problems of computing generic or discriminating words for a given collection of documents. Given a pattern $P$ and a threshold $d$, we want to report (i) all longest extensions of $P$ which occur in at least $d$ documents, (ii) all shortest extensions of $P$ which occur in less than $d$ documents, and (iii) all shortest extensions of $P$ which occur only in $d$ selected documents. For these problems, we propose efficient algorithms based on suffix trees and using advanced data structure techniques. For problem (i), we propose an optimal solution with constant running time per output word.
We study a new variant of the string matching problem called {\em cross-document string matching}, which is the problem of indexing a collection of documents to support an efficient search for a pattern in a selected document, where the pattern itself is a substring of another document. Several variants of this problem are considered, and efficient linear-space solutions are proposed with query time bounds that either do not depend at all on the pattern size or depend on it in a very limited way (doubly logarithmic). As a side result, we propose an improved solution to the {\em weighted level ancestor} problem.
Рассмотрена динамика мнений в сетевых структурах специального вида: каждый узел состоит из двух взаимодействующих между собой агентов. При помощи модели де Гроота исследованы свойства консенсуса, возникающего в таких структурах.
В данной работе рассматривается пятое уравнение Пенлеве, которое имеет 4 комплексных параметра α, β, γ, δ. Методами степенной геометрии ищутся асимптотические разложения его решений при x → ∞. При α≠0 найдено 10 степенных разложений с двумя экспоненциальными добавками каждое. Шесть из них - по целым степеням x (они были известны), и четыре по полуцелым (они новые). При α=0 найдено 4 однопараметрических семейства экспоненциальных асимптотик y(x) и 3 однопараметрических семейства сложных разложений x=x(y). Все экспоненциальные добавки, экспоненциальные асимптотики и сложные разложения найдены впервые. Также уточнена техника вычисления экспоненциальных добавок.
Российские ученые разработали модельный суперкомплекс для долгосрочного прогнозирования развития мировой экономики
Статьи данного сборника написаны на основе докладов, сделанных в 2011 г. на социологическом факультете МГУ им. М.В. Ломоносова на заседании XIV Междисциплинарного ежегодного научного семинара "Математическое моделирование социальных процессов" им. Героя Социалистического труда академика А.А. Самарского.
Издание предназначено для научных сотрудников, преподавателей, учащихся вузов и научных учреждений РАН, интересующихся проблемами, разработкой и внедрением методологии математического моделирования социальных процессов.
Получена форма несмещенной оценки коэффициента детерминации для линейного уравнения регрессии, вычисляемая по выборочным данным из многомерного нормального распределения. Эту оценку предлагается применять как альтернативный критерий выбора факторов в регрессии.