№ 5 (2023)

В статье рассматриваются различные числовые функции, определяющие степень “похожести” двух заданных конечных последовательностей. Эти меры подобия основаны на определяемом нами понятии вложения в последовательность. Частным случаем такого вложения является обычная подпоследовательность (subsequence). Другие случаи дополнительно требуют равенства расстояний между соседними символами подпоследовательности в обеих последовательностях. Это является обобщением понятия отрезка последовательности (substring), в котором эти расстояния единичны. Дополнительно может требоваться равенство расстояний от начала последовательностей до первого символа вложения или от последнего символа вложения до конца последовательностей. Кроме этих двух последних случаев, вложение может входить в последовательность несколько раз. В литературе используются такие функции как число общих вложений или числа пар вхождений вложений в последовательности. Кроме них, мы вводим еще три функции: сумма длин общих вложений, сумма минимумов числа вхождений общего вложения в обе последовательности и функция подобия на основе наибольшего по числу символов общего вложения. Всего рассматриваются 20 числовых функций, для 17 из которых предложены алгоритмы (в том числе новые) полиномиальной сложности, еще для двух функций алгоритмы имеют экспоненциальную сложность с уменьшенным показателем степени. В Заключении дается краткая сравнительная характеристика этих вложений и функций.

Представлена вторая часть исследования, посвященного тематике автоматизированного обезличивания персональных данных. Обзор и анализ перспектив для исследований, выполненный ранее, здесь дополнен практическим результатом. Предложена модель процесса обезличивания, сводящая задачу обеспечения анонимности персональных данных к манипулированию выборками разнотипных случайных элементов. Соответственно, ключевой идеей преобразования данных для обеспечения их анонимности при условии сохранения полезности является применение метода синтеза, т.е. полной замены всех необезличенных данных синтетическими значениями. В предлагаемой модели выделен набор типов элементов, для которых предложены шаблоны синтеза. Совокупность шаблонов составляет алгоритм обезличивания методом синтеза. Методически каждый шаблон опирается на типовой статистический инструмент – частотные оценки вероятностей, ядерные оценки плотностей Розенблатта–Парзена, статистические средние и ковариации. Применение алгоритма иллюстрируется простым примером из области гражданских авиаперевозок.

Рассматриваются системы линейных обыкновенных дифференциальных уравнений с бесконечными формальными степенными рядами в роли коэффициентов. Ряды задаются в усеченном виде, при этом степени усечения могут различаться для разных коэффициентов. В качестве средства исследования таких систем привлекаются индуцированные рекуррентные системы и литеральные обозначения незаданных коэффициентов рядов. Для случая, когда определитель ведущей матрицы индуцированной системы отличен от нуля и не содержит литералов, предлагается алгоритм построения лорановых решений системы. Ряды, входящие в решения, вновь являются усеченными. Алгоритм находит для них максимально возможное число членов, инвариантных относительно любых продолжений усеченных коэффициентов исходной системы. Представлены реализация алгоритма в виде Maple-процедуры и примеры ее использования.

Математическая формулировка принципа дополнительности Бора приводит к понятиям взаимно несмещенных базисов в гильбертовых пространствах и комплементарных квантовых наблюдаемых. Мы рассматриваем связанные с этими понятиями алгебраические структуры и их приложения к конструктивной квантовой механике. Кратко обсуждаются компьютерно-алгебраические подходы к рассматриваемым задачам и приводится алгоритм для решения одной из них.

Предложена эффективно проверяемая нижняя граница для ранга разреженной вполне неразложимой квадратной матрицы, содержащей по два ненулевых элемента в каждой строке и каждом столбце. Ранг такой матрицы равен порядку или отличается на единицу. Построены базисы специального вида в пространствах квадратичных форм от фиксированного числа переменных. Существование таких базисов позволило нам обосновать эвристический алгоритм для решения задачи распознавания, проходит ли данное аффинное подпространство через вершину многомерного единичного куба. В худшем случае этот алгоритм может вернуть уведомление о неопределенности результата вычисления, но для общего подпространства достаточно малой размерности корректно отвергает вход. Алгоритм реализован на языке Python. В ходе тестирования получены оценки времени работы этой реализации алгоритма.