Informatics (E-Journal) / Информатика
Not a member yet
963 research outputs found
Sort by
ПОЛУМАРКОВСКАЯ МОДЕЛЬ НАДЕЖНОСТИ ВЫЧИСЛИТЕЛЬНОГО ПОЛЯ КЛАСТЕРНОЙ СИСТЕМЫ
Get PDFПриводится математическая модель надежности кластерной вычислительной системы, в которой состояния вычислительного поля описываются полумарковской моделью, а также формулы расчета показателей надежности вычислительного поля при различных стратегиях его восстановления. Даются примеры расчета показателей надежности вычислительного поля кластерной вычислительной системы
Об оценке результатов классификации несбалансированных данных по матрице ошибок1
Get PDFWhen applying classifiers in real applications, the data imbalance often occurs when the number of elements of one class is greater than another. The article examines the estimates of the classification results for this type of data. The paper provides answers to three questions: which term is a more accurate translation of the phrase "confusion matrix", how preferable to represent data in this matrix, and what functions to be better used to evaluate the results of classification by such a matrix. The paper demonstrates on real data that the popular accuracy function cannot correctly estimate the classification errors for imbalanced data. It is also impossible to compare the values of this function, calculated by matrices with absolute quantitative results of classification and normalized by classes. If the data is imbalanced, the accuracy calculated from the confusion matrix with normalized values will usually have lower values, since it is calculated by a different formula. The same conclusion is made for most of the classification accuracy functions used in the literature for estimation of classification results. It is shown that to represent confusion matrices it is better to use absolute values of object distribution by classes instead of relative ones, since they give an idea of the amount of data tested for each class and their imbalance. When constructing classifiers, it is recommended to evaluate errors by functions that do not depend on the data imbalance, that allows to hope for more correct classification results for real data.При применении классификаторов в реальных приложениях часто число элементов одного класса больше числа элементов другого, т. е. имеет место дисбаланс данных. В статье исследуются оценки результатов классификации данных такого типа. Рассматривается, какой из переводов термина confusion matrix более точен, как предпочтительнее представлять данные в такой матрице и какими функциями лучше оценивать результаты классификации по ней.На реальных данных демонстрируется, что с помощью популярной функции точности accuracy не всегда корректно оцениваются ошибки классификации несбалансированных данных. Нельзя также сравнивать значения функции accuracy, вычисленные по матрицам с абсолютными количественными и нормализованными по классам результатами классификации. При дисбалансе данных точность, вычисленная по матрице ошибок с нормализованными значениями, как правило, будет иметь меньшие значения, поскольку она определяется по иной формуле. Такой же вывод сделан относительно большинства функций, используемых в литературе для нахождения оценок результатов классификации. Показывается, что для представления матриц ошибок лучше использовать абсолютные значения распределения объектов по классам вместо относительных, так как они описывают количество протестированных данных каждого класса и их дисбаланс.При построении классификаторов рекомендуется оценивать ошибки функциями, не зависящими от дисбаланса данных, что позволяет надеяться на получение более корректных результатов классификации реальных данных
Подход к оптимизации зарядной инфраструктуры автономных троллейбусов для городских маршрутов
Get PDFP u r p o s e s. When designing a system of urban electric transport that charges while driving, including autonomous trolleybuses with batteries of increased capacity, it is important to optimize the charging infrastructure for a fleet of such vehicles. The charging infrastructure of the dedicated routes consists of overhead wire sections along the routes and stationary charging stations of a given type at the terminal stops of the routes. It is designed to ensure the movement of trolleybuses and restore the charge of their batteries, consumed in the sections of autonomous running.The aim of the study is to create models and methods for developing cost-effective solutions for charging infrastructure, ensuring the functioning of the autonomous trolleybus fleet, respecting a number of specific conditions. Conditions include ensuring a specified range of autonomous trolleybus running at a given rate of energy consumption on routes, a guaranteed service life of their batteries, as well as preventing the discharge of batteries below a critical level under various operating modes during their service life.M e t ho d s. Methods of set theory, graph theory and linear approximation are used.Re s u l t s. A mathematical model has been developed for the optimization problem of the charging infrastructure of the autonomous trolleybus fleet. The total reduced annual costs for the charging infrastructure are selected as the objective function. The model is formulated as a mathematical programming problem with a quadratic objective function and linear constraints.Co n c l u s i o n. To solve the formulated problem of mathematical programming, standard solvers such as IBM ILOG CPLEX can be used, as well as, taking into account its computational complexity, the heuristic method of "swarm of particles". The solution to the problem is to select the configuration of the location of the overhead wire sections on the routes and the durations of charging the trolleybuses at the terminal stops, which determine the corresponding number of stationary charging stations at these stops.Ц е л и. При проектировании системы городского электротранспорта, заряжающегося во время движения, в том числе автономных троллейбусов с батареями увеличенной емкости, актуальной является оптимизация зарядной инфраструктуры для парка такого транспорта. Зарядная инфраструктура выделенных маршрутов состоит из секций контактной сети вдоль маршрутов и стационарных зарядных станций заданного типа на конечных остановках маршрутов. Она предназначена для обеспечения движения троллейбусов и восстановления заряда их батарей, израсходованного на участках автономного хода.Цель исследования заключается в создании моделей и методов выработки экономически эффективных решений по зарядной инфраструктуре, обеспечивающих функционирование парка автономных троллейбусов с учетом ряда специфических условий. Условия включают обеспечение заданного диапазона автономного хода троллейбусов при заданной скорости расхода энергии на маршрутах и гарантийного срока эксплуатации их батарей, а также предотвращение разряда батарей ниже критического уровня при различных режимах эксплуатации в течение срока их службы.М е то д ы. Используются методы теории множеств, теории графов и линейной аппроксимации.Р е з у л ь т а т ы. Разработана математическая модель задачи оптимизации зарядной инфраструктуры парка автономных троллейбусов. В качестве целевой функции выбраны суммарные приведенные годовые затраты на зарядную инфраструктуру. Модель сформулирована в виде задачи математического программирования с квадратичной целевой функцией и линейными ограничениями.З а к л ю ч е н и е. Для решения сформулированной задачи математического программирования могут использоваться стандартные решатели типа IBM ILOG CPLEX, а также, с учетом ее вычислительной сложности, эвристический метод «роя частиц». Решение задачи заключается в выборе конфигурации расположения секций контактной сети на маршрутах и длительностей зарядки троллейбусов на конечных остановках, определяющих соответствующие количества стационарных зарядных станций на этих остановках
О научной деятельности Николая Романовича Торопова
Get PDF50 лет тому назад - 26 ноября 1971 г. - в Институте технической кибернетики АН БССР по инициативе доктора технических наук А. Д. Закревского и его учеников была создана лаборатория системного программирования и логического синтеза, впоследствии переименованная в лабораторию логического проектирования ОИПИ НАН Беларуси. Николай Романович Торопов (13.06.1935-15.04.2021) возглавлял сектор системного программирования с момента основания лаборатории, в которой он проработал до 2009 г.
Контроль надежности защиты интегральных схем от троянов: кодирование и декодирование комбинационных структур
Get PDFIntegrated circuits, systems on a chip are the key links in various industrial systems and state defense systems. The emergence of counterfeit integrated circuits, problems of piracy, overproduction, unauthorized interference in the design of microcircuit, hardware Trojans require the development of methods and means of their timely detection. Trojans can be introduced into the integrated circuits structure both on the development stage and during the production process, including the stages of specification, design, verification and manufacturing. The inclusion of additional elements in the integrated circuits structure jeopardizes the functional suitability and reliability of the system as a whole. For the purpose of hardware protection of projects, the methods of hardware coding are currently used.The paper discusses the features and reliability of logical coding of combinational circuits. An algorithm for cracking the code of combinational circuits is proposed, based on the description of encoded structure by the resolution function and reducing the problem to SAT CNF. The initial data for decoding the structure of a digital device is the structural implementation of encoded circuit, obtained, for example, by reverse engineering (prototype design), as well as an activated physical sample of an integrated circuit, when into protected from unauthorized access memory the correct key value is loaded. This sample can be used as a black box model. The main idea of breaking a key is to solve a problem without research on a large interval of values of input and output variables.Интегральные схемы и системы на кристалле являются ключевыми звеньями различных промышленных систем и систем обороноспособности государства. Появление контрафактных интегральных схем, проблемы пиратства, перепроизводства, несанкционированное вмешательство в проект микросхемы, аппаратные трояны требуют развития методов и средств их своевременного обнаружения. Трояны могут быть внесены в структуру интегральных схем при разработке и в процессе производства на этапах спецификации, проектирования, верификации и изготовления. Включение в структуру интегральных схем дополнительных элементов ставит под угрозу функциональную пригодность и надежность системы в целом. С целью аппаратной защиты проектов в настоящее время применяются методы аппаратного кодирования.В работе рассматриваются особенности и надежность логического кодирования комбинационных схем. Предлагается алгоритм взлома кода комбинационных схем, основанный на описании закодированной структуры функцией разрешения и сведении задачи к КНФ-выполнимости. Исходными данными для декодирования структуры цифрового устройства являются структурная реализация закодированной схемы, полученная, например, методом обратного проектирования (проектирования по прототипу), а также активированный физический образец интегральной схемы, в защищенную от несанкционированного доступа память которой загружено правильное значение ключа. Этот образец может использоваться в виде модели черного ящика. Основная идея взлома ключа состоит в том, чтобы решить задачу, не прибегая к исследованиям на большом интервале значений входных и выходных переменных
Применение логики первого порядка для выявления организаторов и исполнителей противоправных действий в преступных группах
Get PDFThere are three main families of inference algorithms in first-order logic: direct inference and its application to deductive databases and production systems; backward inference procedures and logic programming systems; theorem proving systems based on the resolution method. When solving specific problems, the most effective algorithms are those that allow you to cover all the facts and axioms and must be taken into account in the process of inference. An example is considered in which it is necessary to prove the guilt of a person in murder. On the basis of statements, a knowledge base is formed from expressions, with the help of which an expression of first-order logic is compiled and proved using direct logical inference. The proof of the reasoning obtained in direct inference using the proof tree is given. However, direct inference provides for the implementation of all admissible stages of logical inference based on all known facts. The article also considers a method based on the resolution when implementing the reverse inference, taking into account the expression obtained in the direct inference. This expression is converted into a conjunctive normal formula using the laws of Boolean algebra and is proved by the elimination of events using the conjunction operation.Известны три основных семейства алгоритмов вывода в логике первого порядка: прямой логический вывод и его применение к дедуктивным базам данных и продукционным системам; процедуры обратного логического вывода и системы логического программирования; системы доказательства теорем на основе метода резолюции. При решении конкретных проблем наиболее эффективными являются алгоритмы, позволяющие охватить все факты и аксиомы, которые должны быть учтены в процессе логического вывода. Рассматривается пример применения логики первого порядка с целью выявления виновных в противоправных действиях. На основании высказываний формируется база знаний из выражений, с помощью которых составляется выражение логики первого порядка. Приводятся доказательства рассуждений, полученных в прямом логическом выводе с помощью дерева доказательств. Прямой логический вывод предусматривает выполнение допустимых этапов логического вывода на основе всех известных фактов, поэтому также рассматривается метод на основе резолюции при реализации обратного логического вывода с учетом выражения, полученного при прямом логическом выводе. Данное выражение преобразуется в конъюнктивную нормальную формулу с помощью законов булевой алгебры и доказывается методом исключения событий с помощью операции конъюнкции
Автоматическое обнаружение и отслеживание движущихся объектов, наблюдаемых видеокамерой беспилотного летательного аппарата
Get PDFAn algorithm of automatic detection and tracking the moving objects for the use in equipment on board of unmanned aerial vehicles is considered. The developed algorithm is based on a tracking specially selected points for a certain period. Tracked points are selected from the areas on the current frame, where the pixel intensity differs from the intensities of the same pixels in previous frames, aligned with the current frame using projective transformation. If the displacement of the tracked points is not fixed on several adjacent frames, they are being deleted, and new points from the areas presumably belonging to moving objects in the current frame are added instead. On each frame the points similar by the location and shape of trajectories of movement are combined into groups that presumably correspond to moving objects. Objects are tracked by comparing the groups of moving points with the points of neighboring frames. Groups of moving points from neighboring frames are matched if they contain a large number of common tracked points. The algorithm allows simultaneous tracking of more than 20 objects in real time. The indication of objects as moving occurs only if during the time of its tracking it has shifted a considerable distance. The algorithm has a low percentage of false detections of moving objects, it detects well small objects and is capable reliably to accompany moving objects.Предлагается алгоритм автоматического обнаружения и отслеживания движущихся объектов, предназначенный для использования на борту беспилотного летательного аппарата. Разработанный алгоритм основан на отслеживании на протяжении определенного времени выбранных точек изображения. Отслеживаемые точки выбираются из областей на текущем кадре, в которых интенсивность пикселов отличается от интенсивностей тех же пикселов в предыдущих кадрах, совмещенных с текущим кадром при помощи проективного преобразования. Если на нескольких соседних кадрах не фиксируется смещение отслеживаемых точек, они удаляются и на их место добавляются новые точки из областей, предположительно принадлежащих движущимся объектам на текущем кадре. На каждом кадре близкие по расположению и форме траекторий движения точки объединяются в группы, которые соответствуют движущимся объектам. Отслеживание объектов осуществляется путем сопоставления групп движущихся точек соседних кадров. Группы движущихся точек соседних кадров сопоставляются, когда они содержат большое число общих отслеживаемых точек. Алгоритм позволяет одновременно отслеживать более 20 объектов в реальном времени. Индикация объекта как движущегося происходит только в том случае, если за время его сопровождения он сместился на значительное расстояние. Рассматриваемый алгоритм имеет низкий процент ложных обнаружений объектов, хорошо обнаруживает объекты малого размера и надежно сопровождает объекты
Праектаванне беларуска- і рускамоўных натуральна-маўленчых інтэрфейсаў для даведкавых сістэм
Get PDFМ э т ы. Галоўнай мэтай працы з’яўляецца даследаванне натуральна-маўленчых карыстальніцкіх інтэрфейсаў, а таксама стварэнне прататыпу такога інтэрфейсу на прыкладзе двухмоўнай пытальна-адказнайдыялогавай сістэмы з выкарыстаннем рускай і беларускай моў. Натуральна-маўленчыя інтэрфейсы даследуюцца з пункту гледжання выкарыстання натуральнай мовы для арганізацыі дыялогу карыстальніка з камп’ютарнай сістэмай. Пры гэтым абмяркоўваюцца асноўныя складанасці, звязаныя з неадназначнасцю натуральнай мовы і неадпаведнасцю магчымасцей рэалізацыі натуральна-маўленчага інтэрфейсу спадзяванням карыстальніка.М е та д ы. Прыводзяцца асноўныя прынцыпы мадэлявання натуральна-маўленчага карыстальніцкага інтэрфейсу. Будучы інтэлектуальнай сістэмай, у якасці асноўных сваіх кампанентаў ѐн мае базу ведаў, машыну апрацоўкі ведаў і карыстальніцкі інтэрфейс. Кампаненты сістэмы распазнавання і сінтэзу маўлення па тэксце робяць натуральна-маўленчы інтэрфейс яшчэ больш зручным для карыстальніка.В ы н ік і. Прадстаўлена апісанне прататыпа інтэрфейсу натуральнай мовы для інтэлектуальнай пытальна-адказнай сістэмы. Мадэль прататыпа ўключае ў сябе беларускую і рускую версіі падсістэмы («маўленне ў тэкст» і «тэкст у маўленне»), генерацыю адказаў у выглядзе натуральнай мовы і фармальнага тэксту. Дадатковы кампанент – падача на ўваход сістэмы чалавечага маўлення. Некаторыя дадзеныя, неабходныя для распазнавання натуральнага маўлення, захоўваюцца ў базе ведаў альбо ствараюцца на аснове існуючых ведаў. Сінтэз беларускага і рускага маўлення з'яўляецца неабходным для таго, каб зрабіць інтэрфейс на натуральнай мове больш зручным для карыстальнікаў.З а к л ю ч э н н е. Прадстаўлена паслядоўнасць даследавання і праектавання натуральна-маўленчых карыстальніцкіх інтэрфейсаў. Прыводзіцца апісанне прататыпа інтэрфейсу натуральнай мовы для інтэлектуальнай пытальна-адказнай сістэмы.O b j e c t i v e s. The main goal of the work is a research of the natural language user interfaces and the developmentof a prototype of such an interface. The prototype is a bilingual Russian and Belarusian question-and-answer dialogue system. The research of the natural language interfaces was conducted in terms of the use of natural language for interaction between a user and a computer system. The main problems here are the ambiguity of natural language and the difficulties in the design of natural language interfaces that meet user expectations.M e t ho d s. The main principles of modelling the natural language user interfaces are considered. As an intelligent system, it consists of a database, knowledge machine and a user interface. Speech recognition and speech synthesis components make natural language interfaces more convenient from the point of view of usability.R e s u l t s. The description of the prototype of a natural language interface for a question-and-answer intelligent system is presented. The model of the prototype includes speech-to-text and text-to-speech Belarusian and Russian subsystems, generation of responses in the form of the natural language and formal text.An additional component is natural Belarusian and Russian voice input. Some of the data, required for human voice recognition, are stored as knowledge in the knowledge base or created on the basis of existing knowledge. Another important component is Belarusian and Russian voice output. This component is the top required for making the natural language interface more user-friendly.Co n c l u s i o n. The article presents the research of natural language user interfaces, the result of which provides the development and description of the prototype of the natural language interface for the intelligent question- and-answer system.М э т ы. Галоўнай мэтай працы з’яўляецца даследаванне натуральна-маўленчых карыстальніцкіх інтэрфейсаў, а таксама стварэнне прататыпу такога інтэрфейсу на прыкладзе двухмоўнай пытальна-адказнайдыялогавай сістэмы з выкарыстаннем рускай і беларускай моў. Натуральна-маўленчыя інтэрфейсы даследуюцца з пункту гледжання выкарыстання натуральнай мовы для арганізацыі дыялогу карыстальніка з камп’ютарнай сістэмай. Пры гэтым абмяркоўваюцца асноўныя складанасці, звязаныя з неадназначнасцю натуральнай мовы і неадпаведнасцю магчымасцей рэалізацыі натуральна-маўленчага інтэрфейсу спадзяванням карыстальніка.М е та д ы. Прыводзяцца асноўныя прынцыпы мадэлявання натуральна-маўленчага карыстальніцкага інтэрфейсу. Будучы інтэлектуальнай сістэмай, у якасці асноўных сваіх кампанентаў ѐн мае базу ведаў, машыну апрацоўкі ведаў і карыстальніцкі інтэрфейс. Кампаненты сістэмы распазнавання і сінтэзу маўлення па тэксце робяць натуральна-маўленчы інтэрфейс яшчэ больш зручным для карыстальніка.В ы н ік і. Прадстаўлена апісанне прататыпа інтэрфейсу натуральнай мовы для інтэлектуальнай пытальна-адказнай сістэмы. Мадэль прататыпа ўключае ў сябе беларускую і рускую версіі падсістэмы («маўленне ў тэкст» і «тэкст у маўленне»), генерацыю адказаў у выглядзе натуральнай мовы і фармальнага тэксту. Дадатковы кампанент – падача на ўваход сістэмы чалавечага маўлення. Некаторыя дадзеныя, неабходныя для распазнавання натуральнага маўлення, захоўваюцца ў базе ведаў альбо ствараюцца на аснове існуючых ведаў. Сінтэз беларускага і рускага маўлення з'яўляецца неабходным для таго, каб зрабіць інтэрфейс на натуральнай мове больш зручным для карыстальнікаў.З а к л ю ч э н н е. Прадстаўлена паслядоўнасць даследавання і праектавання натуральна-маўленчых карыстальніцкіх інтэрфейсаў. Прыводзіцца апісанне прататыпа інтэрфейсу натуральнай мовы для інтэлектуальнай пытальна-адказнай сістэмы
Нормализация данных в машинном обучении
Get PDFIn machine learning, the input data is often given in different dimensions. As a result of the scientific papers review, it is shown that the initial data described in different types of scales and units of measurement should be converted into a single representation by normalization or standardization. The difference between these operations is shown. The paper systematizes the basic operations presented in these scales, as well as the main variants of the function normalization. A new scale of parts is suggested and examples of the data normalization for correct analysis are given. Analysis of publications has shown that there is no universal method of data normalization, but normalization of the initial data makes it possible to increase the accuracy of their classification. It is better to perform data clustering by methods using distance functions after converting all features into a single scale. The results of classification and clustering by different methods can be compared with different scoring functions, which often have different ranges of values. To select the most accurate function, it is reasonable to normalize several functions and to compare their estimates on a single scale. The rules for separating features of tree-like classifiers are invariant to scales of quantitative features. Only comparison operation is used. Perhaps due to this property, the random forest classifier, as a result of numerous experiments, is recognized as one of the best classifiers in the analysis of data of different nature.В задачах машинного обучения исходные данные часто заданы в разных единицах измерения и типах шкал. Такие данные следует преобразовывать в единое представление путем их нормализации или стандартизации. В работе показана разница между этими операциями. Систематизированы основные типы шкал, операции над данными, представленными в этих шкалах, и основные варианты нормализации функций. Предложена новая шкала частей и приведены примеры использования нормализации данных для их более корректного анализа.На сегодняшний день универсального метода нормализации данных, превосходящего другие методы, не существует, но нормализация исходных данных позволяет повысить точность их классификации. Кластеризацию данных методами, использующими функции расстояния, лучше выполнять после преобразования всех признаков в единую шкалу.Результаты классификации и кластеризации разными методами можно сравнивать различными оценочными функциями, которые зачастую имеют разные диапазоны значений. Для выбора наиболее точной функции можно выполнить нормализацию нескольких из них и сравнить оценки в единой шкале.Правила разделения признаков древовидных классификаторов инвариантны к шкалам количественных признаков. Они используют только операцию сравнения. Возможно, благодаря этому свойству классификатор типа «случайный лес» в результате многочисленных экспериментов признан одним из лучших при анализе данных разной природы
Минимизация многоуровневых представлений систем полностью определенных булевых функций с использованием разложений Шеннона и алгебраических представлений кофакторов
Get PDFIn the systems of digital VLSI design (Very Large Integrated Circuits), the BDD (Binary Decision Diagram) is used for VLSI verification, as well as for technologically independent optimization as the first stage in the synthesis of logic circuits in various technological bases. The BDD is an acyclic graph defining a Boolean function or a system of Boolean functions. Each vertex of this graph corresponds to the complete or reduced Shannon expansion formula. When BDD representation for systems of Boolean functions is constructed, it is possible to perform additional logical optimization based on the proposed method of searching for algebraic representations of cofactors (subfunctions) of the same BDD level in the form of a disjunction, conjunction either exclusive-or of cofactors of the same level or lower levels of BDD. A directed BDD graph for a system of functions is constructed on the basis of Shannon expansion of all component functions of the system by the same permutation of variables. The method allows to reduce the number of literals by replacing the Shannon expansion formulas with simpler formulas that are disjunctions or conjunctions of cofactors, and to reduce the number of literals in specifying a system of Boolean functions. The number of literals in algebraic multilevel representations of systems of fully defined Boolean functions is the main optimization criterion in the synthesis of combinational circuits from librarian logic elements.В системах проектирования цифровых СБИС (сверхбольших интегральных схем) графовый аппарат BDD (Binary Decision Diagram - бинарная диаграмма решений) применяется при верификации СБИС, а также при технологически независимой оптимизации, выполняемой как первый этап синтеза логических схем в различных технологических базисах. BDD представляет собой ациклический граф, задающий булеву функцию либо систему булевых функций. Каждой вершине этого графа соответствует полная или редуцированная формула разложения Шеннона. После получения BDD-представлений систем булевых функций предлагается выполнять дополнительные логические оптимизации на основе описываемого в статье метода поиска алгебраических представлений кофакторов (подфункций разложения Шеннона) одного уровня BDD в виде дизъюнкции, конъюнкции либо суммы по модулю два подфункций того же уровня либо нижних уровней BDD. Ориентированный граф BDD для системы функций строится на основе разложений Шеннона всех компонентных функций системы по одной и той же перестановке переменных. Метод позволяет уменьшать число литералов путем замены формул разложений Шеннона более простыми логическими формулами и сокращать число литералов в описании системы булевых функций. Число литералов в алгебраических многоуровневых представлениях систем полностью определенных булевых функций является основным критерием логической оптимизации при синтезе комбинационных схем из библиотечных логических элементов