12.2017 - том 21 выпуск 4 (PDF)

Куриленко Н.В. Формальная постановка Тезиса М

Рассматривается Тезис М и освещаются основные проблемы с формальным доказательством корректности или ложности данного тезиса. Предложена математическая постановка вопроса и рассмотрены простейшие свойства введённой модели. Описан пример одномерной непрерывной однородной стриктуры, в которой может быть реализована машина с оракулом.

Ключевые слова: тезис Тьюринга-Чёрча, Тезис М, клеточные автоматы, непрерывные однородные структуры.

Кутянин А.Р. Рекомендательные системы: обзор основных постановок и результатов

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

Ключевые слова: Рекомендательная система, рекомендации, коллаборативная фильтрация, item-based, user-based, фильтрация на основе содержания, фильтрация на основе знаний, гибридные рекомендательные системы.

Миронов А.М. Верификация программ методом инвариантов

Излагается метод инвариантов для доказательства правильности компьютерных программ. Основные концепции, связанные с этим методом, иллюстрированы примерами верификации последовательных и параллельных программ.

Ключевые слова: верификация программ, метод Флойда, инварианты.

Рыжов А.П., Ильин И.Ю. Об одной модели влияния в социальных сетях

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

Ключевые слова: анализ социальных сетей, модели влияния.

Д.В. Алексеев К вопросу о восстановлении трехмерного тела по его плоским проекциям

В работе рассматривается задачи восстановления трехмерного изображения по его плоским проекций с точностью до аффинной и метрической эквивалентности. Найдено необходимое и достаточное условие разрешимости этих задач.

Ключевые слова: аффинные преобразования, изометрические преобразования, распознавание изображений, восстановление трехмерных изображений, стереозрение.

Носов М.В. Персептронный алгоритм и линейное программирование

В работе персептронный алгоритм применён для решения задачи линейного программирования с непустой внутренной областью.

Ключевые слова: персептронный алгоритм, линейное программирование.

А.П. Рыжов, П.А. Новиков Об одной модели цифровых привычек

В работе предложена формализация способов использования человеком информационно-коммуникационных технологий на основе анализа логов смартфона. Полученная модель взаимодействия человека с другими людьми и информационными ресурсами (цифровым миром) может быть использована для персонализации такого цифрового окружения и, соответственно, оптимизации такого взаимодействия. Предложен сценарий использования модели дляперсонализации новостной ленты.

Ключевые слова: персонализация, цифровой след, нечеткая кластеризация.

Гасанов Э.Э. О функциональной сложности двумерной задачи о доминировании

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

Ключевые слова: информационно-графовая модель данных, двумерная задача о доминировании, функциональная сложность, метод сеток.

Дергач П. С. О максимальном накрытии начала натурального ряда с ограничениями

В статье рассматривается следующая задача: необходимо определить, какое максимальное по длине начало натурального ряда можно накрыть арифметическими прогрессиями, не накрыв при этом весь ряд. При этом может вводиться ряд ограничений на начало и разность(шаг) этих прогрессий, а также на их общее количество. В зависимости от того, какие из ограничений имеют место, возникает класс различных задач, часть из которых успешно решается в данной статье. Самыми интересными случаями оказываются ограничения типа "начало+шаг", "количество".

Ключевые слова: натуральный ряд, арифметическая прогрессия, максимальное накрытие.

М. Ж. Жолбарысов, Ю. С. Шуткин Проблема стабилизации в булевых сетях

В данной работе рассматривается проблема стабилизации булевых сетей, а именно, вопрос наличия точечных аттракторов в асинхронной булевой сети. Найден критерий стабилизации в зависимости от выбора компонент булевой сети: граф, булевы функции, начальное состояние, порядок обновления.

Ключевые слова: булевы сети, стабилизация. Проблема стабилизации в булевых сетях

Ронжин Д.В. Линейные автоматы над полем рациональных чисел

Исследуется класс линейных автоматов над полем рациональных чисел. В указанном классе доказано отсутствие конечной $K$-полной системы, отсутствие конечных $\Sigma$ полных с добавкой определенного вида систем, выделен бесконечный $K$-базис и бесконечный $\Sigma$-базис, а так же бесконечная $\Sigma$-полная система не содержащая $\Sigma$-базиса.

Ключевые слова: линейные автоматы, поле рациональных чисел, операции композиции, операции суперпозиции, $K$-замыкание, $\Sigma$-замыкание.