Modeling and Analysis of Information Systems / Моделирование и анализ информационных систем (МАИС)
Not a member yet
782 research outputs found
Sort by
Методы преобразования параллелизма в процессе высокоуровневого синтеза СБИС
Get PDFIn this paper methods for increasing the efficiency of VLSI development based on the method of architecture-independent design are proposed. The route of high-level VLSI synthesis is considered. The principle of constructing a VLSI hardware model based on the functional-flow programming paradigm is stated.The results of the development of methods and algorithms for transformation functional-parallel programs into programs in HDL languages that support the design process of digital chips are presented. The principles of assessment are considered and the classes of resources required for the analysis of design solutions are identified. Reduction coefficients and methods of their calculation for each resource class have been introduced. An algorithm for calculating the reduction coefficients and estimating the required resources is proposed. An algorithm for converting parallelism is proposed, taking into account the specified constraints of the target platform. A mechanism for the exchange of metrics with an architecture-dependent level has been developed. Examples of parallelism reduction for the FPGA platform and practical implementation of FFT algorithms in the Virtex® UltraScale FPGA basis are given. The developed methods and algorithms make it possible to use the method of architecture-independent synthesis for transferring VLSI projects to various architectures by changing the parallelism of the circuit and equivalent transformations of parallel programs. The proposed approach provides many options for hardware solutions for implementation on various target platforms.Предложены методы повышения эффективности разработки СБИС на основе метода архитектурно-независимого проектирования. Рассмотрен маршрут высокоуровневого синтеза СБИС. Изложен принцип построения аппаратной модели СБИС на основе функционально-потоковой парадигмы программирования.Представлены результаты разработки методов и алгоритмов трансформации, функционально-потоковых параллельных программ в программы на языках описания аппаратуры, обеспечивающих поддержку процесса проектирования цифровых однокристальных систем. Рассмотрены принципы оценки и выделены классы ресурсов, требуемых для анализа проектных решений. Введены коэффициенты редукции и методики их расчета по каждому классу ресурсов. Предложен алгоритм расчета коэффициентов редукции и оценки требуемых ресурсов. Предложен алгоритм преобразования параллелизма с учетом заданных ограничений целевой платформы. Разработан механизм обмена метриками с архитектурно-зависимым уровнем. Приведены примеры редукции параллелизма для платформы ПЛИС и практическая реализация тестовых алгоритмов БПФ в базисе ПЛИС Virtex® UltraScale. Разработанные методы и алгоритмы позволяют использовать метод архитектурно-независимого синтеза для переноса проектов СБИС на различные архитектуры с помощью изменения параллелизма схемы и эквивалентных преобразований параллельных программ. Предложенный подход обеспечивает множество вариантов аппаратных решений для реализации на различных целевых платформах
Модель текста для автоматической оценки делового письма на заданную тему
Get PDFThis study is aimed at building an automated model for business writing assessment, based on 14 rubrics that integrate EFL teacher assessment frameworks and identify expected performance against various criteria (including language, task fulfillment, content knowledge, register, format, and cohesion). We developed algorithms for determining the corresponding numerical features using methods and tools for automatic text analysis. The algorithms are based on a syntactic analysis with the use of dictionaries. The model performance was subsequently evaluated on a corpus of 20 teacher-assessed business letters. Heat maps and UMAP results represent comparison between teachers’ and automated score reports. Results showed no significant discrepancies between teachers’ and automated score reports, yet detected bias in teachers’ reports. Findings suggest that the developed model has proved to be an efficient tool for natural language processing with high interpretability of the results, the roadmap for further improvement and a valid and unbiased alternative to teachers’ assessment. The results may lay the groundwork for developing an automatic students’ language profile. Although the model was specifically designed for business letter assessment, it can be easily adapted for assessing other writing tasks, e.g. by replacing dictionaries.В статье описана модель текста, предназначенная для автоматической оценки связного текста в виде письма на заданную тему. Параметры оценки сформулированы и формализованы в виде 14 критериев при помощи экспертов в области обучения английскому языку. Критерии включают параметры, относящиеся к анализу лексики, включая особенности предметной области, тематики текста, стилю и формату письма, средствам логической связи предложений. Авторами разработаны алгоритмы определения соответствующих числовых характеристик с использованием методов и инструментов автоматического анализа текстов. Алгоритмы основаны на анализе состава и структуры предложений, для чего используются, в том числе данные специализированных словарей. Характеристики ориентированы на проверку электронного делового письма, но могут быть адаптированы к анализу других письменных текстов, например, с помощью замены словарей. На основе разработанных алгоритмов создана система автоматической оценки текстов. Проведён эксперимент по анализу результатов работы этой системы на корпусе из 20 текстов, предварительно размеченных преподавателями английского языка. Автоматическая оценка и оценка экспертов сравнивались с помощью тепловых карт и технологии двумерного представления векторов UMAP, применённой к характеристическим векторам текстов. В большинстве случаев не было выявлено значимых различий между этими оценками, кроме того, автоматическая оценка оказалась более объективной. Таким образом, разработанная модель успешно справилась с поставленной задачей и может применяться для оценки текстов, написанных человеком. Результаты будут использованы в проекте автоматического построения языкового профиля учащегося. Достоинствами модели являются хорошая интерпретируемость получаемых результатов, объективность, перспективы развития
Рекурсивно-параллельный алгоритм решения задачи об изоморфизме граф-подграф
Get PDFThe paper proposes a parallel algorithm for solving the Graph-Subgraph Isomorphism Problem and makes an experimental study of its efficiency. The problem is one of the most famous NP-complete problems. Its solution may be required when solving many practical problems associated with the study of complex structures. We solve the problem in a formulation that requires finding all existing isomorphic substitutions or proving their absence. In view of the high complexity of the problem, it is natural to want to speed up its solution by parallelizing the algorithm.We used the RPM ParLib library, developed by the author, as the main tool to program the algorithm. This library allows us to develop effective applications for parallel computing on a local network under the control of the runtime environment .NET Framework. Thanks to this library, applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. Any language with support of the .NET Framework can be used as a programming language in conjunction with this library. For the numerical experiment, an open database from the Internet was used, which was specially developed to study algorithms for searching for isomorphic substitutions. Also, the author has developed a special application in C# for generating additional sets of initial data with specified characteristics. The aim of the experiment was to study the speedup achieved due to the recursively parallel organization of computations. The paper provides a detailed description of the proposed algorithm, as well as the results obtained during the experiment.В работе предложен параллельный алгоритм решения задачи об изоморфизме граф-подграф и произведено экспериментальное исследование его эффективности. Задача является одной из самых известных NP-полных задач. Ее решение может потребоваться при решении многих практических задач, связанных с исследованием сложных структур. Мы решаем ее в постановке, в которой требуется найти все возможные изоморфизмы или доказать отсутствие таковых. Ввиду высокой трудоемкости задачи естественным является желание ускорить ее решение за счет распараллеливания алгоритма.Для организации параллельных вычислений автором использовалась библиотека RPM_ParLib, которая позволяет создавать параллельные приложения, работающие в локальной вычислительной сети под управлением среды исполнения .NET Framework. Библиотека поддерживает рекурсивно-параллельный стиль программирования и обеспечивает эффективное распределение работы и динамическую балансировку загрузки вычислительных модулей в процессе исполнения программы. Она может быть использована для приложений, написанных на любом языке программирования, поддерживаемом .NET Framework. Для проведения численного эксперимента использовалась открытая база данных из сети Интернет, специально разработанная для исследования алгоритмов поиска изоморфизмов. Также автором было разработано специальное приложение на языке C# для генерации собственных дополнительных наборов исходных данных с заданными характеристиками. Целью эксперимента было исследование ускорения, достигаемого за счет рекурсивно-параллельной организации вычислений. В работе приводится подробное описание предлагаемого алгоритма, а также полученных в ходе эксперимента результатов
Применение функций голосования для оценки числа монотонных самодвойственных булевых функций
Get PDFOne of the problems of modern discrete mathematics is R. Dedekind problem on the number of monotone boolean functions. For other precomplete classes, general formulas for the number of functions of the classes had been found, but it has not been found so far for the class of monotone boolean functions. Within the framework of this problem, there are problems of a lower level. One of them is the absence of a general formula for the number of boolean functions of intersection of two classes --- the class of monotone functions and the class of self-dual functions. In the paper, new lower bounds are proposed for estimating the cardinality of the intersection for both an even and an odd number of variables. It is shown that the election function of an odd number of variables is monotone and self-dual. The election function of an even number of variables is determined. Free election functions, which are functions with fictitious variables similar in properties to election functions, are introduced. Then the union of a set of election functions and a set of free election functions is considered, and the cardinality of this union is calculated. The resulting value of the cardinality is proposed as a lower bound for . For the class of monotone self-dual functions of an even number of variables, the lower bound is improved over the bounds proposed earlier, and for functions of an odd number of variables, the lower bound for is presented for the first time.Одной из проблем современной дискретной математики является проблема Р. Дедекинда о числе монотонных булевых функций. Если для прочих предполных классов были найдены общие формулы числа функций этих классов, то для класса монотонных булевых функций этого сделать пока не удалось. В рамках этой проблемы существуют проблемы меньшего уровня, одной из которых является отсутствие общей формулы числа булевых функций пересечения двух классов --- класса монотонных функций и класса самодвойственных функций. В данной работе предлагаются новые нижние границы для оценки мощности этого пересечения как для чётного, так и для нечётного количества переменных. Показывается, что функция голосования от нечётного числа переменных является монотонной и самодвойственной. Определяется функция голосования от чётного числа переменных. Вводятся функции свободного голосования --- функции с фиктивными переменными, близкие по свойствам к функциям голосования. Рассматривается объединение множества функций голосования и множества функций свободного голосования. Вычисляется мощность этого объединения. Полученное значение мощности предлагается в качестве нижней границы для . Для класса монотонных самодвойственных функций от чётного числа переменных нижняя граница была улучшена по сравнению с границами, предложенными ранее, а для функций от нечётного числа переменных нижняя граница для представлена впервые
LTL-спецификация ограниченных счётчиковых машин
Get PDFThe article revises the results of the work devoted to the problem of representing the behaviour of a program system as a set of formulas of the linear temporal logic LTL, followed by the use of this representation to verify the satisfiability of the program system properties through the procedure of proving the validity of logical inferences, expressed in terms of the LTL logic. The LTL logic is applied to bounded Minsky counter machines that are considered as program systems of which we need to get the specification of its behaviour. Earlier, when working with the temporal logic LTL as a program logic, a special pseudo-operator was actually introduced to refer to the previous values of variables involved in elementary propositions. Despite the fact that this pseudo-operator is easily implemented in the Cadence SMV verifier when proving the validity of logical LTL-inferences, the classical definition of the LTL logic does not imply its presence. In this article, only binary variables will be used to build an LTL-specification for the behaviour of a bounded counter machine, and tracking of previous values of these variables will be carried out exclusively within the LTL logic itself through the appropriate formulas.В статье пересматриваются результаты работы, посвящённой задаче представления поведения программной системы в виде набора формул линейной темпоральной логики LTL с последующим использованием этого представления для проверки выполнимости программных свойств системы через процедуру доказательства справедливости логических выводов, выраженных в терминах логики LTL. В качестве программных систем, для спецификации поведения которых применяется логика LTL, рассматриваются счётчиковые машины Минского с ограничениями. Ранее при работе с темпоральной логикой LTL как с программной логикой фактически был введён специальный псевдооператор обращения к предыдущим значениям переменных, задействованных в элементарных высказываниях. Несмотря на то что этот псевдооператор легко реализуется в верификаторе Cadence SMV при доказательстве справедливости логических LTL-выводов, классическое определение логики LTL не предполагает его наличия. В данной статье для построения LTL-спецификации поведения ограниченной счётчиковой машины будут использоваться только бинарные переменные, а отслеживание их предыдущих значений будет осуществляться исключительно в рамках самой логики LTL посредством соответствующих формул
Нейросетевая классификация русскоязычных предложений по тональности на четыре класса
Get PDFThe paper is devoted to the classification of Russian sentences into four classes: positive, negative, mixed, and neutral. Unlike the majority of modern study in this area, the mixed sentiment class is introduced. Mixed sentiment sentences contain positive and negative sentiments simultaneously.To solve the problem, the following tools were applied: the attention-based LSTM neural network, the dual attention-based GRU neural network, the BERT neural network with several modifications of the output layer to provide classification into four classes. The experimental comparison of the efficiency of various neural networks were performed on three corpora of Russian sentences. Two of them consist of users’ reviews: one with wear reviews and another with hotel reviews. The third corpus contains news from Russian media. The highest weighted F-measure in experiments (0.90) was achieved when using BERT on the wear reviews corpus, as well as the highest weighted F-measure for positive and negative sentences (0.92 and 0.93, respectively). The best classification results for neutral and mixed sentences were achieved on the news corpus. For them F-measure was 0.72 and 0.58, respectively. As a result of experiments, the significant superiority of the BERT transfer network was demonstrated in comparison with older neural networks LTSM and GRU, especially for classification of sentences with weakly expressed sentiments. The error analysis showed that “adjacent” (positive/negative and mixed) classes are worse classified with BERT than “opposite” classes (positive and negative, neutral and mixed).Работа посвящена классификации русскоязычных предложений по тональности на четыре класса: положительный, отрицательный, смешанный и нейтральный. В отличие от большинства современных работ в этой области, вводится в рассмотрение класс предложений смешанной тональности. Предложения со смешанной тональностью содержат в себе одновременно и положительно, и отрицательно окрашенную речь. Для решения данной задачи были применены: нейронная сеть LSTM с механизмом внимания, нейронная сеть GRU с двойным механизмом внимания, нейронная сеть BERT с несколькими модификациями выходного слоя для обеспечения классификации на четыре класса. Эксперименты по сравнению эффективности различных нейронных сетей производилось на трёх корпусах русскоязычных предложений. Два корпуса составлены из пользовательских отзывов: один с отзывами на одежду, другой с отзывами на отели. Третий корпус составлен из новостных статей российских изданий. Лучшая средняя взвешенная F-мера в экспериментах, составляющая 0.90, была достигнута моделью BERT на корпусе отзывов на одежду. На этом же корпусе были отмечены лучшие F-меры для положительных и отрицательных предложений, составившие 0.92 и 0.93 соответственно. Наилучшие показатели классификации нейтральных и смешанных предложений достигаются на корпусе новостных статей. Для них F-мера составляет 0.72 и 0.58 соответственно. В результате экспериментов было продемонстрировано значительное превосходство трансферных нейронных сетей BERT над нейронными сетями предыдущего поколения LSTM и GRU, наиболее ярко выражающееся при классификации текстов со слабо выраженной эмоциональной окраской. Анализ ошибок показал, что на «смежные» классы тональности (положительный/отрицательный и смешанный) приходится большая доля ошибок при классификации с помощью BERT, чем в случае «противоположных» классов (положительный и отрицательный, нейтральный и смешанный)
Двухшаговая раскраска графов решетки различных типов
Get PDFIn this article, we consider the NP-hard problem of the two-step colouring of a graph. It is required to colour the graph in a given number of colours in a way, when no pair of vertices has the same colour, if these vertices are at a distance of 1 or 2 between each other. The optimum two-step colouring is one that uses the minimum possible number of colours.The two-step colouring problem is studied in application to grid graphs. We consider four types of grids: triangular, square, hexagonal, and octogonal. We show that the optimum two-step colouring of hexagonal and octogonal grid graphs requires 4 colours in the general case. We formulate the polynomial algorithms for such a colouring. A square grid graph with the maximum vertex degree equal to 3 requires 4 or 5 colours for a two-step colouring. In the paper, we suggest the backtracking algorithm for this case. Also, we present the algorithm, which works in linear time relative to the number of vertices, for the two-step colouring in 7 colours of a triangular grid graph and show that this colouring is always correct. If the maximum vertex degree equals 6, the solution is optimum.В данной статье рассматривается NP-трудная задача о двухшаговой раскраске графа. Она состоит в нахождении такой раскраски в заданное число цветов, при которой ни одна пара вершин на расстоянии 1 или 2 друг от друга не будет окрашена в одинаковый цвет. Оптимальной считается двухшаговая раскраска в минимально возможное количество цветов.Задача о двухшаговой раскраске исследуется применительно к графам решетки. Рассмотрены четыре типа решеток: треугольная, квадратная, шестиугольная и восьмиугольная. Показано, что в общем случае для оптимальной двухшаговой раскраски графов шестиугольной и восьмиугольной решетки требуется 4 цвета, приводятся полиномиальные алгоритмы получения такой раскраски. Для графа квадратной решетки, в котором максимальная степень вершины равна 3, может потребоваться 4 или 5 цветов для двухшаговой раскраски. В данной работе предложен алгоритм поиска с возвратом для этого случая. Для графов треугольной решетки представлен линейный относительно количества вершин алгоритм двухшаговой раскраски в 7 цветов, показано, что раскраска будет всегда корректной. Если максимальная степень вершины равна 6, решение будет оптимальным
Поиск упоминаний экологических практик в социальных сетях с помощью методов классификации текстов
Get PDFThe paper is devoted to the task of searching for mentions of green practices in social media texts. The relevance of this task is dictated by the need to expand existing knowledge about the use of green practices in society and the spread of existing green practices. This paper uses a text corpus consisting of the texts published on the environmental communities of the VKontakte social network. The corpus is equipped with an expert markup of the mention of nine types of green practices. As part of this work, a semi-automatic approach is proposed to the collection of additional texts to reduce the class imbalance in the corpus. The approach includes the following steps: detecting the most frequent words for each practice type; automatic collecting texts in social media that contain the detected frequent words; expert verification and filtering of collected texts. The four machine learning models are compared to find the mentions of green practices on the two variants of the corpus: original and augmented using the proposed approach. Among the listed models, the highest averaged F1-score (81.32%) was achieved by Conversational RuBERT fine-tuned on the augmented corpus. Conversational RuBERT model was chosen for the implementation of the application prototype. The main function of the prototype is to detect the presence of the mention of nine types of green practices in the text. The prototype is implemented in the form of the Telegram chatbot.Работа посвящена решению задачи поиска упоминаний экологических практик в текстах социальных сетей. Авторами составлен корпус текстов экологических сообществ социальной сети ВКонтакте, снабженный экспертной разметкой упоминаний девяти видов экологических практик. Предложен полуавтоматический подход к сбору дополнительных текстов для уменьшения несбалансированности видов экологических практик, представленных в корпусе. Подход включает в себя следующие этапы: определение наиболее частотных слов, характеризующих упоминания практик; автоматический сбор текстов, включающих в себя найденные частотные слова; экспертная проверка и фильтрация собранных текстов. Проведено сравнение четырех моделей машинного обучения для поиска упоминаний практик на двух вариантах корпуса: исходном и дополненном. Лучший усредненный показатель F-меры (81.32%) достигнут моделью Conversational RuBERT, дообученной на текстах дополненного корпуса. Данная модель выбрана в качестве основы для реализации прототипа приложения для поиска упоминаний экологических практик, реализованного в форме чат-бота Telegram
Об одной оценке для нормы интерполяционного проектора
Get PDFLet be the unit cube in and let be a space of continuous functions with the norm By denote a set of polynomials in variables of degree , i. e., a set of linear functions on . The interpolation projector with the nodes is defined by the equalities , . Let be the norm of as an operator from to . If is an Hadamard number, then there exists a non-degenerate regular simplex having the vertices at vertices of . We discuss some approaches to get inequalities of the form for the norm of the corresponding projector .Пусть - единичный куб в , - пространство непрерывных функций с нормой Через обозначим совокупность многочленов от переменных степени , т. е. линейных функций на . Интерполяционный проектор с узлами определяется равенствами , . Пусть - норма как оператора из в . Если - число Адамара, то существует невырожденный правильный симплекс, вершины которого находятся в вершинах куба В статье обсуждаются различные подходы к получению оценок вида для нормы соответствующего интерполяционного проектора
На пути к нейросетевой маршрутизации с верифицированными границами эффективности
Get PDFWhen data-driven algorithms, especially the ones based on deep neural networks (DNNs), replace classical ones, their superior performance often comes with difficulty in their analysis. On the way to compensate for this drawback, formal verification techniques, which can provide reliable guarantees on program behavior, were developed for DNNs. These techniques, however, usually consider DNNs alone, excluding real-world environments in which they operate, and the applicability of techniques that do account for such environments is often limited. In this work, we consider the problem of formally verifying a neural controller for the routing problem in a conveyor network. Unlike in known problem statements, our DNNs are executed in a distributed context, and the performance of the routing algorithm, which we measure as the mean delivery time, depends on multiple executions of these DNNs. Under several assumptions, we reduce the problem to a number of DNN output reachability problems, which can be solved with existing tools. Our experiments indicate that sound-and-complete formal verification in such cases is feasible, although it is notably slower than the gradient-based search of adversarial examples.The paper is structured as follows. Section 1 introduces basic concepts. Then, Section 2 introduces the routing problem and DQN-Routing, the DNN-based algorithm that solves it. Section 3 proposes the contribution of this paper: a novel sound and complete approach to formally check an upper bound on the mean delivery time of DNN-based routing. This approach is experimentally evaluated in Section 4. The paper is concluded with some discussion of the results and outline of possible future work.Когда алгоритмы на основе данных, особенно основанные на глубоких нейронных сетях (ГНС), заменяют классические, их более высокая производительность часто сопряжена с трудностями при анализе. Чтобы компенсировать этот недостаток, для ГНС были разработаны методы формальной верификации, которые могут предоставить надежные гарантии поведения программы. Эти методы, однако, обычно рассматривают только саму ГНС, исключая среду, в которой она работает, и применимость методов, учитывающих такие среды, часто ограничена. В данной работе рассматривается задача формальной верификации нейросетевого контроллера для задачи маршрутизации в конвейерной сети. В отличие от известных постановок задачи, рассматриваемые ГНС выполняются в распределенной среде, и производительность алгоритма маршрутизации, которая измеряется как среднее время доставки, зависит от многократного выполнения этих ГНС. При некоторых предположениях, проблема верификации сводится к ряду проблем достижимости выходов ГНС, которые можно решить с помощью существующих программных средств. Эксперименты показывают, что в таких случаях возможна строгая и полная формальная верификация, хотя она заметно медленнее, чем градиентный поиск состязательных примеров.Статья построена следующим образом. Раздел 1 вводит основные понятия. Затем в Разделе 2 представлена проблема маршрутизации и алгоритм DQN-маршрутизации на основе ГНС, который ее решает. В Разделе 3 описывается вклад данной статьи: новый надежный и полный подход к формальной проверке верхней границы среднего времени доставки маршрутизации на основе ГНС. Этот подход экспериментально оценивается в Разделе 4. Статья завершается обсуждением результатов и описанием возможной будущей работы