?
Cross-document Pattern Matching
Kopelowitz T., Kucherov G., Nekrich Y., Стариковская Т. А.
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.
Приоритетные направления:
математика
Язык:
английский
Pham S. K., Antipov D., Sirotkin Alexander и др., Journal of Computational Biology 2013 Vol. 20 No. 4 P. 359-371
Добавлено: 21 марта 2014 г.
CEUR Workshop Proceedings, 2018
Добавлено: 11 декабря 2018 г.
Springer, 2014
This book constitutes the refereed proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014, held in Moscow, Russia, in June 2014. The 28 revised full papers presented together with 5 invited talks were carefully reviewed and selected from 54 submissions. The papers address issues of searching and matching strings and more complicated ...
Добавлено: 24 июня 2014 г.
Найденова К., Игнатов Д. И., Hershey : IGI Global, 2012
The consideration of symbolic machine learning algorithms as an entire class will make it possible, in the future, to generate algorithms, with the aid of some parameters, depending on the initial users’ requirements and the quality of solving targeted problems in domain applications.
Diagnostic Test Approaches to Machine Learning and Commonsense Reasoning Systems surveys, analyzes, and ...
Добавлено: 3 декабря 2012 г.
Бабенко М. А., Стариковская Т. А., Проблемы передачи информации 2011 Т. 47 № 1 С. 28-33
Описан алгоритм, решающий задачу нахождения приближенной максимальной общей подстроки двух строк $\alpha_1$ и $\alpha_2$ за время $O(\abs{\alpha_1} \abs{\alpha_2})$ с использованием $O(\abs{\alpha_1})$ дополнительной памяти. При обращении к строке $\alpha_2$ алгоритм читает ее только \emph{слева направо, начиная с первого символа}. Используется RAM-модель вычислений. ...
Добавлено: 30 октября 2013 г.
Грибанов Д. В., Малышев Д. С., Discrete Applied Mathematics 2017 Vol. 227 P. 13-20
Добавлено: 23 апреля 2017 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Annals of Operations Research 2012 Vol. 196 No. 1 P. 247-261
Добавлено: 24 ноября 2012 г.
Felikson А. A., Натанзон С. М., Differential Geometry and its Application 2012 Vol. 30 No. 5 P. 490-508
We consider (local) parameterizations of Teichmüller space Tg,n (of genus g hyperbolic surfaces with n boundary components) by lengths of 6 g- 6 + 3 n geodesics. We find a large family of suitable sets of 6 g- 6 + 3. n geodesics, each set forming a special structure called "admissible double pants decomposition". For ...
Добавлено: 5 февраля 2013 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 4 С. 66-72
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов Free({P5,C5}). Именно, доказывается, что если эта задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого графа H, который может быть индуктивно получен из G применением к текущему графу сложения с K1 или умножения на K1, эта ...
Добавлено: 31 августа 2012 г.
Бабаш А. В., М. : ИНФРА-М, РИОР, 2013
Пособие предназначено для студентов высших учебных заведений, обучающихся по специальности «Прикладная информатика (в экономике)». Оно также содержит методический материал для ряда инновационных курсов лекций по профилю «Информационная безопасность» и может быть использовано и для блока дисциплин этого профиля. Ряд представленных результатов полезен специалистам и аспирантам, специализирующихся в указанной области. ...
Добавлено: 14 января 2014 г.
Крючков М. В., Русаков С. В., Вестник Ижевского государственного технического университета 2015 № 2(66) С. 110-112
В работе описаны результаты тестирования нейросетевого технического индикатора тренда по данным биржевого курса нефти марки Brent в 2014 году. Апробация модели проводилась на трех временных интервалах, характеризующихся своими особенностями. ...
Добавлено: 31 августа 2015 г.
Alexandrov D. E., Galkin V. V., Zobnin A.I. и др., Journal of Mathematical Sciences 2009 Vol. 163 No. 5 P. 469-486
Добавлено: 1 октября 2014 г.
Малышев Д. С., Дискретный анализ и исследование операций 2020 Т. 27 № 4 С. 104-130
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы соседние рёбра были окрашены в разные цвета. Для всех классов графов, определяемых запрещением подграфов с не более чем 6 рёбрами каждый, известен
сложностной статус этой задачи. В настоящей работе данный результат улучшается и получена полная ...
Добавлено: 25 декабря 2020 г.
Красноярск : ИВМ СО РАН, 2013
Труды Пятой Международной конференции «Системный анализ и информационные технологии» САИТ-2013 (19–25 сентября 2013 г., г.Красноярск, Россия): ...
Добавлено: 18 ноября 2013 г.
Ясницкий Л. Н., Пермь : Пермский государственный национальный исследовательский университет. – Электронные данные. , 2020
В сборнике представлены материалы Международной конференции «Интеллектуальные системы в науке и технике» и Шестой всероссийской научно-практической конференции «Искусственный интеллект в решении актуальных социальных и экономических проблем ХХI века», которая проводилась 12–18 октября 2020 г. в г. Перми в рамках Пермского естественнонаучного форума «Математика и глобальные вызовы XXI века».
Сборник предназначен для научных и педагогических работников, преподавателей, аспирантов, магистрантов, студентов ...
Добавлено: 4 декабря 2020 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706-721
Добавлено: 30 января 2021 г.
Гафаров Е. Р., Лазарев А. А., Information Processing Letters 2012 Т. 112 № 3 С. 72-76
In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number of tardy jobs ...
Добавлено: 24 ноября 2012 г.
Lanham : University Press of America, 2012
The history of logic and analytic philosophy in Central and Eastern Europe is still known to very few people. As an exception to the rule, only two scientific schools became internationally popular: the Vienna Circle and the Lvov-Warsaw School. Nevertheless, the countries included in this region have not only joint history, but also joint cultural ...
Добавлено: 13 февраля 2013 г.
Barcelona : IEEE, 2017
Добавлено: 17 января 2018 г.
Гафаров Е. Р., Лазарев А. А., Вернер Ф., Mathematical Social Sciences 2011 No. 62 P. 7-13
Добавлено: 24 ноября 2012 г.
Литвин Ю. В., Абрамов И. В., Технологии техносферной безопасности 2016 № 66
Расширен подход к оценке случайного времени прибытия пожарных боевых расчётов на объект защиты, времени их занятости и свободного горения. Получены некоторые количественные оценки с использованием рассмотренных аналитических методов и имитации ...
Добавлено: 27 августа 2016 г.
Беклемишев Л. Д., Оноприенко А. А., Математический сборник 2015 Т. 206 № 9 С. 3-20
Формулируются системы преобразований термов, число шагов работы которых на произвольном входе конечно, но не ограничивается никакой вычислимой функцией, доказуемо тотальной в арифметике Пеано PА. Тем самым, утверждение о сходимости таких систем не доказуемо в PA. Эти системы получаются из независимого комбинаторного утверждения, известного как принцип червя; их также можно рассматривать как вариант хорошо известной игры Геракла и гидры, ...
Добавлено: 13 марта 2016 г.
Марширов В. В., Марширова Л. Е., Сибирский журнал индустриальной математики 2013 Т. XVI № 4 С. 111-120
Рассматривается задача определения скорости охлаждения металла в процессе затвердевания при пересечениии температуры ликвидуса при интенсивном теплоотводе с его поверхности. Решение данной задачи необходимо для определения технологических режимов, граничных и начальных условий при которых могут буть получены новые сплавы с микрокристаллическими структурами. Приведены необходимые конечно-разностные уравнения, описан алгоритм, с использованием известных экспериментальных данных проведено тестирование созданной ...
Добавлено: 17 ноября 2013 г.