English
03.2015 - том 19 выпуск 1 (PDF)
В работе описывается технология оценки и мониторинга сложных процессов, разрабатываемая на кафедре МАТИС с начала 90-х годов. Приводится содержательная постановка проблемы информационного мониторинга, описываются технологические и математические аспекты разработки систем информационного мониторинга. Приводится обзор основных результатов.
Ключевые слова: системы оценки и мониторинга, нечеткие множества, оценка нечеткости, поиск в нечетких базах данных.
В статье обобщаются результаты работы [1] на случай kзначных логик. Вводится понятие прогнозирующего автомата, который для каждого поданного ему на вход сверхслова из заданного множества, начиная с некоторого шага в каждый момент t выдает значение входного слова в момент t + 1, то есть предугадывает входное сверхслово. Получен критерий прогнозируемости множеств сверхслов. Приведен наилучший по порядку метод построения прогнозирующего автомата для произвольного прогнозируемого множества сверхслов.
Ключевые слова: конечный автомат, прогнозирующий автомат, прогнозирование событий.
Рассматривается класс P L кусочно-линейных функций вместе с операциями суперпозиции [1]. В настоящей работе показано, что в P L существуют три предполных класса, содержащих класс L всех линейных функций: класс финитных функций, класс непрерывных функций и класс согласованных функций. Получен критерий позволяющий по конечному множеству M ∈ P L проверить полноту множества M ∪ L.
Ключевые слова: класс кусочно-линейных функций, класс финитных функций, класс непрерывных функций, класс согласованных функций, функция Хэвисайда, операции суперпозиции, существенный разврыв.
В работе представлен алгоритм построения множества по заданным параметрам, для которого фактическое число шагов достигает половину верхней оценки числа шагов для данного множества в теореме Новикова. Дополнительно доказывается, что для множества, состоящего из двух точек, фактическое число шагов не более чем \(({D^2}/{2*r^2})+2\).
Ключевые слова: нейронные сети, теорема Новикова.
В работе рассматриваются две задачи — классификация музыкальных файлов по жанрам и классификация изображений. В первом случае требуется реализовать веб-приложение, которое определяет жанры загружаемых в него музыкальных файлов (джаз, классика, диско, метал, блюз). Во втором случае требуется реализовать веб-приложение с возможностью загрузки картинок-эталонов. При последующей загрузке картинок система должна определять, на какой из эталонов наиболее похожа загруженная картинка, и определять ее в соответствующий класс.
Ключевые слова: классификация, музыкальные файлы, mfcc, hog, php.
Ставится задача построения поисковой системы вебстраниц. Основной задачей системы является выдача отсортированного списка результатов, удовлетворяющий заданному поисковому запросу пользователя. Система разделена на несколько частей: кроулер, индексер, ранжирование и поисковый интерфейс. Статья содержит детальное описание каждой из этих частей. Кроме того, по каждой части предоставлена реализация.
Ключевые слова: интернет, поисковая система, кроулер, индексер, ранжирование, HITS, PageRank, TF-IDF.
Рассматриваемая в работе задача состоит в следующем: пусть дано множество слов; требуется для произвольного подслова найти все вхождения этого подслова в слова из этого множества. В данной работе приведена нижняя оценка времени работы алгоритмов, позволяющих осуществлять такой поиск, а также получен порядок объёма памяти для алгоритмов, осуществляющих поиск за минимальное по порядку время.
Ключевые слова: поиск вхождения подслов, нижняя оценка, верхняя оценка.
В данной работе рассматривается решение динамической задачи поиска идентичного объекта для произвольного потока запросов. Сложность параллельной обработки запросов над общей структурой данных заключается в избежании конфликтов, которые возникают при изменении одного и того же участка памяти. При этом считаем, что считывать из одного участка памяти нескольким процессам допустимо. Решение получено с помощью динамического информационного графа [1], [2], который в свою очередь является обобщением информационного графа [3] на случаи вставки и удаления записи.
Ключевые слова: динамические базы данных, информационный граф, конечный автомат, потоки запросов, параллельная обработка данных.
Ранее автор доказал, что автоматные функции с магазинной памятью сохраняют множество периодических последовательностей и привел экспоненциальную оценку удлинения периода при этом. Для автоматов с унарным магазином эту оценку удалось понизить до квадратичной.
Ключевые слова: автомат с магазинной памятью с однобуквенным магазином, детерминированная функция, периодические последовательности.
Доказана алгоритмическая разрешимость задачи выразимости линейных автоматов через произвольную конечную систему автоматов относительно расширенной суперпозиции.
Ключевые слова: автомат, линейный автомат, выразимость, суперпозиция, алгоритмическая разрешимость.
В данной работе рассматривается решение динамической задачи поиска идентичных объектов для произвольного потока запросов с логарифмической сложностью. Сложность параллельной обработки запросов над общей структурой данных заключается в избежании конфликтов, которые возникают при изменении одного и того же участка памяти. При этом считаем, что считывать из одного участка памяти нескольким процессам допустимо. Решение получено с помощью многоавтоматного динамического информационного графа [1].
Ключевые слова: динамические базы данных, информационный граф, автомат, потоки запросов, параллельная обработка данных, сбалансированные деревья.
В работе рассматривается задача расшифровки полиномиальных функций ранжирования. В случае когда функция ранжирования зависит от известной переменной линейно предложен алгоритм расшифровки с точностью до мультипликативного множителя с известной погрешностью, а так же его оценка сложности. Представлен класс функций, для которых существует алгоритм, определяющий для какой из переменных соответствующий моном имеет наименьшую степень и наименьший по модулю старший коэффициент. Дана оценка сложности данного алгоритма.
Ключевые слова: расшифровка функций, функции ранжирования, продвижение веб-сайтов.