Добірка наукової літератури з теми "Алгебра алгоритмів"

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

У статті розглядається управління процесами, що є складовою логістичного забезпечення ЗС України. Як правило, вони частково структуровані, без чіткої взаємодії з іншими складовими та потребують прийняття складних рішень. Відповідно, на сьогодні розробка математичного забезпечення (моделей, методів, алгоритмів) системи підтримки прийняття рішень у логістичному забезпеченні потреб ЗС України, що враховують відповідні завдання та особливості ведення операцій, є потрібною, а їх впровадження – актуальним завданням. Матеріали статті передбачають можливість удосконалення системи логістичного забезпечення ЗС України шляхом розробки та впровадження логістично-інформаційних моделей системи підтримки прийняття рішень на основі алгебри предикатів. Проаналізовано наукові досягнення у галузі логістики, стан та сучасні погляди на питання логістичного забезпечення збройних сил в Україні та країн-членів НАТО. Запропоновано для розробки логістично-інформаційної моделі системи підтримки прийняття рішень використовувати функціонально-структурний підхід та метод компараторної ідентифікації, що дозволить перейти до єдиної математичної моделі ефективного інформаційного забезпечення особі, що приймає рішення. Рекомендовано застосування багатовимірної моделі зберігання та представлення інформації під час роботи з логістично-інформаційними системами, що дозволить забезпечити визначення всіх ієрархічних складових кожної з підсистем єдиної системи логістики Збройних Сил України. У результаті роботи таких моделей формується раціональний, обґрунтовано визначений вектор логістичного стану до конкретного об'єкта, процесів логістичного забезпечення чи ситуації, що склалась з врахуванням усіх впливів факторів зовнішньої й внутрішньої дії на кожний окремий елемент об’єкта спостереження і надається інформація особам, що приймають рішення. Здійснення інформаційно-аналітичної підтримки особам, які приймають рішення у галузі логістики має відбуватись завдяки наданню таким особам всебічної, необхідної та достатньої інформації для прийняття ефективного управлінського рішення щодо перебігу процесів у системі логістичного забезпечення, впливу внутрішніх і зовнішніх факторів, зворотних зв’язків системи логістично-інформаційних моделей. Представлення даних на основі логістично-інформаційних систем стає перспективним підходом щодо оптимізації управлінського рішення урегулювання відносин між різноплановими процесами логістичного забезпечення.

Дана робота є продовженням досліджень, розпочатих в [1], у яких теорія булевих функцій розглядається з точки зору універсальних алгебр. У цій роботі описано клас функціонально неповних алгебр, проведено дослідження основних типів алгебр і розташування їх по ярусах сигнатурного кубу. У даних дослідженнях універсальні булеві алгебри утворюють 11-мірний сигнатурний куб, до складу якого входять 2048 алгебр. Запропоновано нумерацію (кодифікацію) цих алгебр. Вводиться поняття суміжних, граничних, внутрішніх класів функціонально повних і функціонально неповних алгебр. Булеві алгебри досліджуваного класу поділяють на чотири підкласи: клас внутрішніх функціонально неповних алгебр, клас граничних функціонально неповних алгебр, клас граничних функціонально повних алгебр, клас внутрішніх функціонально повних алгебр. У даній роботі пропонується алгоритм знаходження граничних функціонально повних алгебр на основі розширення сигнатури функціонально неповних алгебр булевими операціями. Побудовані підкласи граничних алгебр для кожної з одинадцяти операцій. Вказано ізоморфізм графів деяких класів граничних алгебр. На основі об’єднання графів отримали -граф граничних функціонально повних алгебр.

Розглядаються особливості розроблення надійного алгоритму для генерування ключів переставляння, робота якого базується на класичному шифрі Кардано "квадратні ґратки" у його сучасному математичному формулюванні, що загалом дає змогу генерувати послідовності випадкових чисел у заданому діапазоні без повторення. Встановлено, що алгоритм "квадратні ґратки", будучи алгоритмом маршрутного переставляння, в якому правило розміщення символів у блоці задається квадратним трафаретом, можна використовувати не тільки для шифрування блоку вхідного повідомлення, але й для генерування відповідної множини ключів переставляння. З використанням основних положень матричної алгебри розроблено математичне формулювання алгоритму "квадратні ґратки" для генерування ключів переставляння, а також математичне формулювання алгоритму переставляння рядків матриці вхідного повідомлення, кількість стовпців якої може бути довільною.

У данiй роботi проведенi дослiдження над булевими унiверсальними алгебрами, в сигнатуру яких входять нульарнi, унарнi та частина бiнарних булевих операцiй. Побудованi еквацiональнi та сигнатурнi решiтки класу тривiальних алгебр. Елементи решiток представляються у виглядi квадрата. Клас унiверсальних булевих алгебр складається з восьми алгебр, в сигнатуру яких входять операцiї кон’юнкцiї, диз’юнкцiї та заперечення. Вони утворюють сигнатурнi i еквацiональнi куби. Для тривiальних алгебр i всiх алгебр булевого кубу знайденi повнi системи тотожностей. Повнота систем тотожностей доводиться за допомогою алгоритмiв, якi дозволяють привести формули вiдповiдних алгебр до стандартних канонiчних виглядiв. Куб Жегалкiна складається з восьми алгебр, в сигнатуру яких входять операцiї одиниця, сума та множення за модулем два. Для алгебр кубу Жегалкiна побудована еквацiональна решiтка

Задачу маршрутизации можно сформулировать следующим образом: учитывая сеть G , необходимо найти наилучший путь между узлами i и j из сети. Однако понятие «лучшее» расплывчато, и оно зависит от того, какие параметры в составной метрике сетевые операторы пытаются оптимизировать. Для разделения проблем была введена алгебра маршрутизации для моделирования того, что пытается решить протокол маршрутизации, сохраняя при этом общий алгоритм маршрутизации. Тем не менее все протоколы маршрутизации должны решать проблему свободы от циклов. Цель этой статьи - представить теорию бесцикловой маршрутизации с произвольной метрикой. Показано, что выбор базовой алгебры может повлиять на производительность самого алгоритма, как в представленном примере для протокола маршрутизации (EIGRP). Кроме того, модификация алгебры маршрутизации может помочь во внедрении новых алгоритмов маршрутизации. Примером может служить протокол DSN (Распределенный порядковый номер), который использует гибридный алгоритм состояния каналов и дистанционно-векторный. В метрику DSN добавлены новые компоненты, которые представляют собой порядковый номер и бит флага для запроса увеличения порядкового номера. Это помогло, как показано в этой статье, решить проблему бесцикловой маршрутизации с незначительными изменениями в исходном дистанционно-векторном алгоритме. В данной работе решены следующие задачи. Условия для бесцикловой маршрутизации и отношения между ними были представлены алгебраически и доказаны. Введена концепция монотонной маршрутизации. Была исследована бесцикловая маршрутизация при наличии и отсутствии монотонности. На основании сформулированных теорем разработана алгебраическая модель и валидация бесциклового алгоритма, используемого в протоколе DSN The routing problem can be formulated as follows: given a network, it is necessary to find the best path between nodes and from the network. However, the concept of “best” is obscure, and it depends on which parameters in the composite metric network operators are trying to optimize. For separation of concerns, routing algebras were introduced to model what the routing protocol is trying to solve while maintaining a generic routing algorithm. However, all routing protocols must address the problem of loop-freedom. The purpose of this article is to present a theory of loop-free routing with an arbitrary metric. It is shown that the choice of the basic algebra can affect the performance of the algorithm itself, as in the presented example for the routing protocol (EIGRP). In addition, the modification of the routing algebra can help in the introduction of new routing algorithms. An example is the DSN protocol (Distributed Sequence Number), which uses a hybrid link-state and distance vector algorithm. New components are added to the DSN metric, which are the sequence number and a flag bit denoting a request to increase the sequence number. This helped, as shown in this article, to solve the problem of loop-free routing with minor changes in the original distance vector algorithm. In this paper, the following tasks have been solved. The conditions for loop-free routing and the relations between them were presented algebraically and proved. The concept of monotonous routing is introduced. Loop-free routing was investigated in the presence and absence of monotony. Based on the formulated theorems, an algebraic model and validation of a loop-free algorithm used in the DSN protocol have been developed

ВВ криптографических системах шифрования информации используются гиперкомплексные числа: кватернионы и октонионы. В качестве ключа применяется кватернион, который производит вращения группы выборок информации. Кватернионы и бикватернионы являются частными случаями геометрической алгебры Клиффорда. Использование векторов и мультивекторов геометрической алгебры для шифрования информации позволяет расширить разнообразие этих векторов. Для шифрования информации, представленной совокупностью векторов геометрической алгебры, эти векторы умножаются на мультивектора, которые осуществляют операцию ротор (rotor). В качестве ключа используется мультивектор (ротор). Для дешифрования информации применяется операция, которая соответствует обратному ротору. Алгоритмы геометрической алгебры повышают безопасность шифрования информации за счет повышения размерности алгебры. Для повышения производительности шифрования предлагается коэффициенты информационного вектора и мультивектора вращения выбирать из поля Z256. Предлагается вектор информации с коэффициентами из Z256 складывать со случайным вектором с коэффициентами из Z256 и считать эти коэффициенты ключами шифрования. Приведены базисные векторы применяемых геометрических алгебр и таблицы геометрических произведений базисных векторов.

Математика розвиває алгоритмічне мислення. До Фалеса математика була рецептурно-догматичною, набором алгоритмів для розв’язання типових задач. Давньогрецька математика виробила систему аксіом й методи логічного виведення з них теорем. Рецептура замінювалася доказовими алгоритмами, одним з яких був алгоритм Евкліда. Знаходження найбільшого спільного дільника, який дає й розвинення звичайного дробу в ланцюговий і побудову двосторонніх наближень.У школі некваліфіковані вчителі не дають чітких алгоритмів розв’язання типових задач, хоча не всі діти здатні до швидких “творчих” знахідок й тому не вміють самі знайти шлях до розв’язку. Але математика засобами алгебри дає змогу узагальнення числової задачі до типової з розробкою алгоритму її розв’язання. Фіксація алгоритму у вигляді послідовності операцій, обумовленої й результатами проміжних дій, веде до необхідності введення операції умовногопереходу й циклічних гілок. Одним з корисних прикладів є знаходження квадратного кореня. На жаль, зараз цей алгоритм не вивчають, бо будують приклади-завдання так, щоби відповідь можна було знайти “в умі”. Це відноситься й до розв’язання квадратних рівнянь. Значно більше, ніж треба, вчителі приділяють увагу вгадуванню коренів за теоремою Вієта, хоча її бажано застосовувати для перевірки знайдених коренів.Вища математика дає змогу широкого використання комп’ютера. Деякі студенти мають комп’ютер або змогу користуватися ним у батьків чи друзів; дехто вже має й деякі навички. Тому можна пропонувати їм використовувати комп’ютер для обчислень і для побудови графіків. Це сприяє кращому розумінню поняття функції та її границі, а далі й дослідженню властивостей функції. Бажано використовувати можливості збірника типових задач (Кузнєцова, Чудесенка та ін.), розробляючи разом із студентами алгоритми розв’язання задач, можливо з доведенням їх до комп’ютерних програм. Ми маємо досвід розробки програми DIFF аналітичного диференціювання у 1978 р., ще до появи сучасних математичних пакетів типу Maple. Вона стала основою програми Lagr для побудови рівнянь Лагранжа електромеханічних систем, а студенти Донецької політехніки І. Кирютенко та В. Карабчевський стали учасниками розробки пакета програм VIBRO для динамічного аналізу вібраційних систем за замовленням проектного інституту в м. Луганську. Один із студентів, який отримав дозвіл працювати над курсом “Диференціальні рівняння” (ДР) за індивідуальним планом, розробив програми для розв’язання 16 типових задач. Реалізація операцій алгебри логіки на контактних схемах із демонстрацією діючих моделей, розроблених студентами минулих років, сприяє виробленню уявлень про корисність абстрактно-математичних теорій. Побудова точкових графіків послідовностей (1+1/n)n та (1–1/n)–n дає уявлення про графік функції y=(1+1/x)x та про вивчення неперервних величин за допомогою їх дискретизацій на ЦЕОМ. Побудова графіка функції y=sin(x)/x пояснює не тільки першу чудову границю, а й усувний характер розриву при х=0 та парність цієї функції.Можливість використання мультімедіа-ефектів та використання варіації параметрів особливо корисні при вивченні розділу ДР, де розв’язок визначається початковими чи граничними умовами; їх зміна дає наочне уявлення про різницю між частинним та загальним розв’язками та ілюструє метод “стрільби” тощо. Теж саме відноситься до курсу “Теорія ймовірностей та математична статистика”. Вивчення методу найменших квадратів знаходження середнього та дисперсії, регресійних рівнянь тощо, дозволяє уяснити можливості прогнозу – екстраполяції. Збільшення числа n у схемі послідовних випробувань з імовірністю Pn(m) показує природність нормального закону розподілу ймовірностей. При цьому багатокутник розподілу наочно перейде у криву густини.Викладання комп’ютерних наук з орієнтацією на міжпредметний комплекс задач. Усі завдання повинні бути складовими частинами основного завдання, яке повинен розв’язати колектив студентів. У свою чергу, завдання для одного чи групи студентів повинне паралельно розвиватися по різним дисциплінам. Наприклад, для спеціальності “Системне програмування” проектування частини графічного редактора, містить підзадачу пакування зображення для архівації, що використовує знання предметів: комп’ютерна графіка, обробка цифрових сигналів, архітектура операційних систем, архітектура ЕОМ тощо. Комплекс завдань з окремого предмета призводить до прогресу у вирішенні завдання в цілому. При цьому виникають труднощі перевірки та контролю якісного виконання завдань, бо результат праці студента є складовою загального проекту і може виникнути ситуація обмеженого самостійного функціонування. Тут виникає потреба в механізмі доведення коректності виконаного завдання, що у свою чергу доповнить знання студентів щодо засобів перевірки та діагностування, розробки тестових прикладів та правила їх складання. Для впровадження комплексу задач необхідно використання централізованого контролю та міжпредметних зв’язків. Централізований контроль можливо автоматизувати, використавши готовий проект, де кожен модуль студент може тимчасово замінити на власний і отримати від системи оцінку ефективності нової розробки. Це може бути використане й до колективних курсових та дипломних робіт.

Рассматриваются алгебраические, геометрические и информационные аспекты параллельных методов декомпозиции для решения больших систем линейных уравнений с разреженными матрицами, возникающими при аппроксимации многомерных краевых задач на неструктурированных сетках. Алгоритмы базируются на разбиении сеточной расчетной области на подобласти с параметризованной величиной пересечений и различными интерфейсными условиями на смежных границах. Рассматриваются вопросы, возникающие при алгебраической декомпозиции исходной матрицы. Применяются различные двухуровневые итерационные процессы, включающие в себя предобусловленные крыловские методы с использованием грубосеточной коррекции, а также синхронное решение вспомогательных систем в подобластях с помощью прямых или итерационных алгоритмов. Распараллеливание алгоритмов реализуется средствами гибридного программирования с формированием MPI-процессов для каждой подобласти и использованием в них многопотоковых вычислений над общей памятью. Информационные коммуникации между соседними подобластями осуществляются на каждой внешней итерации путем предварительной организации буферов обмена и применения неблокирующих операций с возможностями проведения арифметических действий на фоне передачи данных. Algebraic, geometric, and informational aspects of parallel decomposition methods are considered to solve large systems of linear equations with sparse matrices arising after approximation of multidimensional boundary value problems on unstructured grids. Algorithms are based on partitioning a grid computational domain into its subdomains with a parameterized value of overlapping and various interface conditions on the adjacent boundaries. Some questions arising in algebraic decomposition of the original matrix are discussed. Various two-level iterative processes are used. They include both preconditioned Krylov methods with a coarse grid correction and the parallel solution of auxiliary subsystems in subdomains by direct or iterative algorithms. Parallelization of algorithms is implemented by means of hybrid programming with separate MPI processes for each subdomain and by multithreaded computations over shared memory in each of the subdomains. Communications between adjacent subdomains are performed on each external iteration via the preliminary creation of some exchange buffers and using non-blocking operations, which makes it possible to combine both the arithmetic operations and data transfer.

Виконане автоматизоване конструювання високорівневих алгебро-алгоритмічних специфікацій програмного забезпечення для розв’язання задачі метеорологічного прогнозування. Виконана генерація програмного коду за побудованими специфікаціями на основі використання розроблених інструментальних засобів автоматизованого проектування та синтезу програм. Проведено експеримент з виконання згенерованої паралельної програми метеорологічного прогнозування на багатоядерній платформі Intel Xeon Phi. Загальний обсяг роботи: 82 c., 5 рис., 29 табл., 30 джерел.
The computer-aided design of high-level algebra-algorithmic specifications of the software for solving the problem of meteorological forecasting is performed. Generation of the program code behind the constructed specifications on the basis of use of the developed tools of computer-aided design and synthesis of programs is executed. An experiment was carried out to implement the generated parallel program of meteorological forecasting on the Intel Xeon Phi multicore platform. Total amount of work: 82 p., pic 5, 29 tables., 30 links.
Выполнено автоматизированное конструирование высокоуровневых алгебро-алгоритмических спецификаций программного обеспечения для решения задачи метеорологического прогнозирования. Выполнена генерация кода по построенным спецификациями на основе использования разработанных инструментальных средств автоматизированного проектирования и синтеза программ. Проведен эксперимент по выполнению сгенерированной параллельной программы метеорологического прогнозирования на многоядерной платформе Intel Xeon Phi.

Коваленко С. С. Розробка методики автоматизації самостійних робіт з алгебри : кваліфікаційна робота магістра спеціальності 122 "Комп'ютерні науки" / наук. керівник С. Ю. Борю. Запоріжжя : ЗНУ, 2020. 60 с.
UA : Робота викладена на 60 сторінках друкованого тексту, містить 1 таблицю, 17 джерел. Об’єкт дослідження – методика автоматизації створення самостійних робіт з алгебри. Мета роботи: розробка методики автоматизації створення самостійних робіт з алгебри за допомогою програмного забезпечення. Методи дослідження – аналітичний, описовий. У кваліфікаційній роботі розглянуто основні проблеми, з якими стикаються вчителі в процесі підготовки завдань до самостійної роботи та їх перевірки. Для вирішення цих проблем запропоновано методику автоматизації створення самостійних робіт з алгебри. Здійснено огляд та порівняння існуючого програмного забезпечення та обрано оптимальне програмне забезпечення для автоматизації генерації завдань та отримання розв’язків. Робота містить алгоритми генерації та розв’язання завдань, практичну інструкцію для педагогів. Практичні результати даної роботи можуть бути використані вчителями математики при проведенні контролю рівня засвоєння матеріалу учнями. Також результати роботи можуть використовуватись для створення методики автоматизації перевірки самостійних робіт з алгебри.
EN : The work is presented on 60 pages of printed text, 1 table, 17 references. The object of study is a technique for the automation creation of independent works on algebra. The goal of the work: development of the technique for automation of creation of the independent works on algebra by means of software. Methods of research − analytical, descriptive. The qualification work deals with the main problems that teachers face in the process of preparing assignments for the independent work and their verification. To solve these problems it is proposed to use the method for automating the creation of independent works on algebra. Existing software is reviewed and compared and the best software is selected to automate task generation and receiving solutions. The work contains algorithms for generating and solving tasks, practical instructions for educators. The practical results of this work can be used by the Maths teachers in controlling the students` level of mastering the material. The results of the work can also be used to create the methodology for the verification automation of independent works on algebra.

Довідник-тренажер містить означення, правила, алгоритми дій, приклади виконання вправ та завдання для тренування з тем шкільного курсу математики, які розкривають змістові лінії «Числа» і «Тотожності». Довідник буде корисний для учнів основної і старшої школи, абітурієнтів, студентів-першокурсників, які вивчають курси «Елементарна математика», «Вища математика», вчителів математики.

Рассматриваются алгоритмическая задачи сравнения строк и приближенного поиска в строке и их взаимосвязь с тропической матричной алгеброй и нестандартной разновидностью классической группы кос. Использование этой взаимосвязи позволяет получить эффективные алгоритмы приближенного поиска для сжатых строк, динамически изменяющихся строк, а также эффективные параллельные алгоритмы для данных задач.