English language
12.2017 - том 21 выпуск 4 (PDF)
Рассматривается Тезис М и освещаются основные проблемы с формальным доказательством корректности или ложности данного тезиса. Предложена математическая постановка вопроса и рассмотрены простейшие свойства введённой модели. Описан пример одномерной непрерывной однородной стриктуры, в которой может быть реализована машина с оракулом.
Ключевые слова: тезис Тьюринга-Чёрча, Тезис М, клеточные автоматы, непрерывные однородные структуры.
В работе описываются основные алгоритмы рекомендательных систем. Приводится содержательная постановка задачи нахождения N лучших рекомендаций, описываются преимущества и недостатки каждого из названных методов. Приводится обзор работ и результатов, начиная с возникновения первых рекомендательных систем и до настоящего времени.
Ключевые слова: Рекомендательная система, рекомендации, коллаборативная фильтрация, item-based, user-based, фильтрация на основе содержания, фильтрация на основе знаний, гибридные рекомендательные системы.
Излагается метод инвариантов для доказательства правильности компьютерных программ. Основные концепции, связанные с этим методом, иллюстрированы примерами верификации последовательных и параллельных программ.
Ключевые слова: верификация программ, метод Флойда, инварианты.
В работе приводится модель влияния в социальных сетях и изучаются некоторые ее свойства. Основное внимание уделяется изучению матрицы влияния. Влияние рассматривается как величина, зависящая от времени, а также состояния и мнений других агентов. Для рассмотрения подобного влияния интерпретируется противоположность мнений агентов. Приведены примеры социальных сетей, основанных на данной модели. Рассмотрены несколько простых случаев сходимости матрицы влияния. Показаны отличия в структуре модели социальной сети с предельной матрицей влияния от некоторых существующих моделей.
Ключевые слова: анализ социальных сетей, модели влияния.
В работе рассматривается задачи восстановления трехмерного изображения по его плоским проекций с точностью до аффинной и метрической эквивалентности. Найдено необходимое и достаточное условие разрешимости этих задач.
Ключевые слова: аффинные преобразования, изометрические преобразования, распознавание изображений, восстановление трехмерных изображений, стереозрение.
В работе персептронный алгоритм применён для решения задачи линейного программирования с непустой внутренной областью.
Ключевые слова: персептронный алгоритм, линейное программирование.
В работе предложена формализация способов использования человеком информационно-коммуникационных технологий на основе анализа логов смартфона. Полученная модель взаимодействия человека с другими людьми и информационными ресурсами (цифровым миром) может быть использована для персонализации такого цифрового окружения и, соответственно, оптимизации такого взаимодействия. Предложен сценарий использования модели дляперсонализации новостной ленты.
Ключевые слова: персонализация, цифровой след, нечеткая кластеризация.
В работе исследуются двумерная задача о доминировании, в которой база данных представляет собой множество точек на плоскости, и надо для произвольной точки плоскости, интерпретируемой как запрос на поиск, найти все точки из базы данных, которые по обоим координатам превосходят запрос. Под функциональной сложностью понимается функция зависимости времени поиска от объема памяти, которую можно выделить под структуры данных. В работе показано, как, используя метод Бентли-Маурера, можно получить алгоритмы с разными соотношениями времени поиска и объема памяти.
Ключевые слова: информационно-графовая модель данных, двумерная задача о доминировании, функциональная сложность, метод сеток.
В статье рассматривается следующая задача: необходимо определить, какое максимальное по длине начало натурального ряда можно накрыть арифметическими прогрессиями, не накрыв при этом весь ряд. При этом может вводиться ряд ограничений на начало и разность(шаг) этих прогрессий, а также на их общее количество. В зависимости от того, какие из ограничений имеют место, возникает класс различных задач, часть из которых успешно решается в данной статье. Самыми интересными случаями оказываются ограничения типа "начало+шаг", "количество".
Ключевые слова: натуральный ряд, арифметическая прогрессия, максимальное накрытие.
В данной работе рассматривается проблема стабилизации булевых сетей, а именно, вопрос наличия точечных аттракторов в асинхронной булевой сети. Найден критерий стабилизации в зависимости от выбора компонент булевой сети: граф, булевы функции, начальное состояние, порядок обновления.
Ключевые слова: булевы сети, стабилизация. Проблема стабилизации в булевых сетях
Исследуется класс линейных автоматов над полем рациональных чисел. В указанном классе доказано отсутствие конечной \[K\]-полной системы, отсутствие конечных \[\Sigma\] полных с добавкой определенного вида систем, выделен бесконечный \[K\]-базис и бесконечный \[\Sigma\]-базис, а так же бесконечная \[\Sigma\]-полная система не содержащая \[\Sigma\]-базиса.
Ключевые слова: линейные автоматы, поле рациональных чисел, операции композиции, операции суперпозиции, \[K\]-замыкание, \[\Sigma\]-замыкание.
Том 21 выпуск 3(PDF)
В данной работе приведен обзор некоторых результатов о вычислительной сложности алгебр, в частности, результатов, полученных на кафедре математической кибернетики МГУ им. М.В. Ломоносова автором и его учениками: Поспеловым А.Д., Чокаевым Б.В., Лысиковым В.В.
Ключевые слова: алгебраическая сложность, алгебра, ранг алгебры, билинейная сложность, мультипликативная сложность, сложность умножения матриц.
Для моделирования фазовых переходов в многокомпонентных растворах часто используется обобщенная модель «черной нефти». При изучении численных неустойчивостей модели было обнаружено, что они могут возникать из-за термодинамического рассогласования функций в окрестности критической точки раствора, которая, как известно, физически неустойчива по своей природе. Все измеряемые величины из-за флуктуаций, происходящих в этой об- ласти, имеют значительные погрешности измерений, что приводит к существенному рассогласованию параметров модели и соответственно к численным неустойчивостям. Предлагается физический подход к моделированию таких областей. Объяснены некоторые причины неточности моделей «черной нефти».
Ключевые слова:
В работе исследована задача о цепочках. Приведены результаты об области существования цепочек, полученных из данной переводом конца цепочки в заданную точку; оценки минимума евклидова расстояния между цепочками, получаемыми друг из друга переводом конца в заданную точку; возможное количество цепочек, полученных переводом конца в заданную точку и отличающихся минимальным количеством звеньев от данной цепочки; возможное количество цепочек, находящихся на минимальном расстоянии от данной и полученных переводом конца цепочки в заданную точку, для n = 2 и n = 3. Описаны алгоритмы перевода конца цепочки в заданную точку: экспоненциальный алгоритм, перебирающий все возможные цепочки с шагом ε, линейный алгоритм, дающий примерное решение для евклидова расстояния, и линейный алгоритм, дающий точный ответ для расстояния Хэмминга и примерный для евклидова расстояния.
Ключевые слова: цепочка, алгоритм, верхние оценки, нижние оценки, евклидово расстояние, расстояние Хэмминга.
Излагаются основные криптографические примитивы, используемые в протоколах безопасности (симметричные и асимметричные системы шифрования, хэш-функции, схемы разделения секрета), протоколы аутентификации, и алгоритмы цифровой подписи.
Ключевые слова: протоколы, безопасность, криптография, хэш-функции, аутентификация, цифровая подпись.
В работе представлены алгоритмы построения проверочных матриц для LDPC - кодов на основе графа Таннера с обхватом 8. Также, в качестве параметров графа выступают разбиение степеней символьных вершин: отношение вершин степени 3 и степени 4 к общему числу символьных вершин, и скорость полученного кода. Код строится для произвольной скорости и произвольного разбиения за линейное, относительно количество элементов матрицы, время.
Ключевые слова: LDPC - коды, граф Таннера, двудольные графы, распределение степеней вершин.
В кандидатской диссертации [1] была поставлена и решена задача о нахождении верхней оценки на минимальную длину слов из регулярного языка, склеивающихся (то есть имеющих совпадающий образ) при алфавитном кодировании (если такая склейка вообще существует). В данной статье исследуется задача о нахождении соответствующих нижних оценок на длину склейки для случая, когда регулярные языки имеют линейную функцию роста, а схема кодирования преобразует все буквы входного алфавита в один и тот же символ. Для такого кодирования образ слова однозначно определяется по его длине. Приводятся нижние оценки, совпадающие по порядку с верхними оценками из [1] для таких языков и такого кодирования. Кроме того, для этого подслучая приводится более точная верхняя оценка.
Ключевые слова: алфавитное кодирование, регулярный язык, склейка.
В работе формулируется и доказывается критерий полиномиальной полноты квазигрупп в терминах предполных классов k-значной логики.
Ключевые слова: квазигруппа, полиномиальная полнота, квазилинейность.
Том 21 выпуск 2(PDF)
Исследуется изоморфизм алгебр на k-булеанах множеств в аксиоматике \[\textit{ZFU}\] и соответствующего им \[\textit{k}\]-гиперпространства индикаторов над \[\textit{GF}\][2]. Оценивается сложность решения задач поиска в \[\textit{k}\]-булеанах множеств. Полученные результаты проецируются на модель \[\textit{k}\]-гиперпространства семиотико-хроматических гипертопографов в аксиоматической системе \[[G]^{1}\]. Последняя положена в основу вычислительной архитектуры ёмкостного паракомпьютера управления знаниями интеллектуальной системы
Ключевые слова: алгебр морфизмы, алгоритмов сложность ёмкостная, алгоритмов сложность операционная, гипертопографы семиотико-хроматические, графов теории обобщения, графов теории однообъектная парадигма, знаниями управление, множеств индикаторы, множеств (- носителей) \[\textit{k}\]-топологизация, множеств \[\textit{k}\]-булеан, множеств \[\textit{k}\]-булеанов индикаторы, паракомпьютер ёмкостной, поиск на множествах, системы интеллектуальные, топологии дискретные с конечным носителем, \[\textit{k}\]-гиперпространство булево
В статье приводится результат об описании структуры непосредственного вложения для семейства \[\mathbb P_2\]прогрессивных множеств сложности не выше \[2.\] Приводится полная неизбыточная классификация ребер структуры. При этом возникают 12 типов классификации, для описания которых водятся понятия согласованности, асинхронности, слабой и сильной синхронности пар арифметических прогрессий в натуральных рядах. Такая постановка задачи является новой и ранее никем не исследовалась.
Ключевые слова: прогрессивное множество, арифметическая прогрессия, структура непосредственного вложения.
В работе вводится понятие граф автомата. Рассматривается задача определения принадлежности автомата к классу групповых автоматов по его графу. Приводится свойство графов групповых автоматов. Доказана теорема о существовании группового автомата с графом заданного вида.
Ключевые слова: автомат, граф, групповой автомат.
В работе доказаны универсальные нижние оценки функции Шеннона мощности плоских схем, а также найден порядок роста функции Шеннона мощности схем, реализующих монотонные функции. В качестве меры мощности рассматривается максимальный потенциал, он равен максимальному количеству выходов элементов, выдающих единицу на заданном входном наборе схемы, где максимум берётся по всем входным наборам. В работе показано, что порядок роста функции Шеннона максимального потенциала для монотонных функций равен \[2^{n/2}/\sqrt[4]{n}\], а порядок среднего потенциала равен \[2^{n/2}/\sqrt[4]{n^3}\].
Ключевые слова: Cхемы из функциональных элементов, плоские схемы, клеточные схемы, потенциал, мощность, функция Шеннона, верхние оценки, нижние оценки, монотонные булевы функции.
В статье рассматривается класс всех двуместных кусочно-линейных непрерывных функций. Доказывается что данный класс лежит в классе согласованных функций. Найден критерый полноты в этом классе.
Ключевые слова: Класс кусочно-линейных функций, класс кусочно-линейных непрерывных функций, класс согласованных функций, класс финитно-параллельных непрерывных функций, функция Хэвисайда, операции суперпозиции, вектор сигнатуры.
В данной работе рассматриваются матрицы самосравнения одномерного сигнала (в частности, речевого). Предлагается метод нелинейного растяжения этих симметричных матриц для нахождения оптимального расстояния между ними в смысле похожести сигналов.
Ключевые слова: одномерный сигнал, матрица самосравнения, нелинейное растяжение.
В работе представлены формулы промежуточного типа, задающие сложность минимальной схемы, в базисе из штриха Шеффера.
Ключевые слова: сложность минимальной схемы, штрих Шеффера.
В данной работе предложена модель цифрового изображения как динамической системы взаимодействующих частиц. На основе этой модели построен алгоритм анализа цифровых изображений. Исследован характер преобразования изображений в зависимости от типа потенциала взаимодействия и выбора основных параметров модели.
Ключевые слова: цифровое изображение, потенциал взаимодействия, теория многих частиц, визуальная разборчивость изображений.
В данной работе предложен алгоритм кластеризации последовательностей изображений, идея которого заключается в формировании кластеров на основе минимальных трёхточечных симплексов, образованных классифицируемыми данными в многомерном пространстве признаков. Рассмотрены варианты кластеризации в отложенном и псевдореальном масштабе времени.
Ключевые слова: кластеризация изображений, определение смены сюжета, анализ видео, опорные кадры, кластеризация в реальном времени.
Вариационный автокодировщик (ВАК) - вероятностный метод обучения без учителя, использующий глубинное обучение. В статье предлагается устойчивый к шуму метод обучения ВАК, основанный на модификации функции правдоподобия. Предлагаются и анализируются две нижние оценки в качестве целевых функций для ВАК. Эффективность метода продемонстрирована в экспериментах с искусственно добавленными шумовыми объектами.
Ключевые слова: обучение без учителя, генеративное моделирование, вариационный автокодировщик, важностно взвешенный автокодировщик, робастность, устойчивость к шуму
В работе рассмотривается модификация быстрого градиентного метода (БГМ). Показана его прямо-двойственность как способность восстановить решение прямой задачи по решению двойственной. Получены теоретические результаты о его сходимости как для задач безусловной минимизации, так и для задач условной минимизации с линейными ограничениями-равенствами и ограничениями-неравенствами на примере задачи энтропийно-линейного программирования (задача ЭЛП). Доказаны строгая и сильная выпуклость двойственного функционала последней, а также показано, что градиент двойственного функционала удовлетворяет условию Липшица.
Ключевые слова: быстрый градиентый метод, задача энтропийно-линейного программирования, условная минимизация, безусловная минимизация, прямо-двойственные методы.
03.2017 - том 20 выпуск 1 (PDF)
В статье исследуется представление упорядоченности возможностей элементарных событий, с точностью до изоморфизма задающее меру возможности, матрицами и функциями попарных сравнений значений возможностей, его свойства и операции над такими представлениями, в частности маргинализация совместного распределения, расчет условного распределения по совместному, экспертное восстановление распределения и принятие оптимальных решений.
Ключевые слова: мера возможности, упорядоченность, представление распределения
В статье приводится результат о нахождении минимального количества L(n) арифметических прогрессий, необходимых для того, чтобы получить в объединении все натуральные числа, не сравнимые по модулю n с 0 и −2. Здесь n - произвольное натуральное число. При этом прогрессии могут пересекаться. Приводится точное значение для функции L(n), а также конструктивное разбиение этого подмножества натурального ряда на L(n) арифметических прогрессий.
Ключевые слова: натуральный ряд, арифметическая прогрессия, декомпозиция
Ранее автор доказал, что автоматные функции с магазинной памятью сохраняют множество периодических последовательностей и привел экспоненциальную оценку удлинения периода при этом. Для автоматов с унарным магазином эту оценку удалось понизить до квадратичной.
Ключевые слова: автомат с магазинной памятью с однобуквенным магазином, детерминированная функция, периодические последовательности.
В работе исследуется функция Шеннона мощности плоских схем, которые реализуют функции от \[n\] переменных с ограниченным числом единиц. В качестве меры мощности рассматривается максимальный потенциал. Потенциал схемы на входном наборе равен количеству выходов элементов, выдающих единицу на этом входном наборе. В частности, в работе показано, что если количество единиц функции ограничено числом \[N\], причём \[\log_2 N\asymp n\], то порядок функции Шеннона равен \[N(n-\log_2 N)\]. Также было исследовано поведение функции Шеннона в зависимости от ограничений на расположение входов схемы.
Ключевые слова: схемы из функциональных элементов, плоские схемы, клеточные схемы, потенциал, мощность, функция Шеннона, верхние оценки, нижние оценки, булевы функции.
В данной работе решена задача построения сверточной нейронной сети, способной распознавать рукописные символы на сильно зашумленных изображениях с точностью, сопоставимой с человеческой. При этом обучение классификатора происходит по размеченной базе сильно зашумленных изображений, в которой 5\[\%\] обучающих примеров размечено неправильно.
Ключевые слова: сверточные нейронные сети, распознавание изображений, машинное обучение, обучение с учителем.
В данной статье представлен протокол шифрования, в котором биометрические данные пользователя используются для генерации открытого ключа посредством нечеткого экстрактора. Это схема устойчива к адаптивной атаке с выбранным открытым текстом и обладает шифртекстом постоянного размера. Определена модель безопасности и показано, что безопасность протокола основана на билинейной задаче принятия решения Диффи-Хеллмана. Сравнительный анализ показывает большую устойчивость и безопасность предложенной схемы перед аналогами.
Ключевые слова: криптография, биометрия, личностное шифрование, схема разделения секрета Шамира, нечеткие экстракторы
Изучается сложность реализации автоматов посредством кодирований его состояний. Рассматриваются всевозможные равномерные кодирования, т.е. кодирования состояний наборами одинаковой длины. На длину кода не накладывается ограничение сверху. Получена верхняя оценка сложности реализации автомата. Получена верхняя оценка длины кода, при котором достигается линейная реализуемость автомата.
Ключевые слова: теория автоматов, переходные системы, кодирование, сложность
В работе описаны нетривиальные примеры моделирования сложных задач динамики и геометрии.
Ключевые слова: