Математические основы программирования. Рубрика в журнале - Программные системы: теория и приложения
A picture of common subsequence length for two random strings over an alphabet of 4 symbols
Статья научная
The maximal length of longest common subsequence (LCS) for a couple of random finite sequences over an alphabet of 4 characters was considered as a random function of the sequences lengths and 𝑛; Exact probability distributions tables are presented for all couples of length in a range 2
Бесплатно
Local competing in interpolation problems
Статья научная
A simple example illustrates the insufficiency of the known approaches to interpolation in the problem of recovering a function from a few given specific values that clearly convey the form. A local choice between polynomial and rational local interpolants, which minimizes the local interpolant's errors at the nearest external nodes from one or different sides, complements the known approaches. It combines the extreme computational simplicity of local interpolants with the thorought selection of them. The principles of constructing the algorithm are formulated in general terms for mappings of metric spaces. They provide accurate (with rare exceptions) reconstruction of mappings that locally coincide with some of the given possible interpolants. In the one-dimensional case, the two-stage algorithm guarantees the continuity of the interpolant and accurately reconstructs {[itemindent=1cm] polynomials of small degree, simple rational functions with a linear denominator, broken lines of long links with knots at the ends } when these requirements do not contradict each other. An additional parameter allows you to replace the exact restoration of polylines with the required smoothness of interpolation.
Бесплатно
Robust algorithmic binding to arbitrary fragment of program code
Статья научная
When solving a task, a programmer actively interacts with a finite set of code fragments. The information about their locations is important for quick navigation, for other developers, and as a kind of documentation. Integrated development environments (IDEs) provide tools for marking code fragments with labels, displaying lists of labels, and using these labels for quick navigation. However, they often lose the correspondence between the label and the marked place when the code is edited, in particular when changes are made outside the IDE. In previous works, the authors propose a tool to be integrated into various IDEs for ``binding'' to large syntactic entities of a program and building a~markup that is robust to code editing. The description of the marked element is built on the basis of the abstract syntax tree (AST) of the program. Later it is used to algorithmically search for the element in an edited code. The search has a success rate from 99 to 100.. This article aims at robust algorithmic binding to an~arbitrary section of the code. For binding to a single-line code fragment, we propose an extension of the model describing the marked fragment, and an additional search algorithm. We also propose an algorithm for embedding nodes corresponding to multi-line fragments in an AST. We show that the correctness of the AST is not violated by these embeddings. Bindings to randomly selected lines were made in the code of three large C. projects. Manual check of these lines search results in~the edited code has confirmed that the bindings are robust to code editing.
Бесплатно
Адаптивный анализ надежности паролей при помощи гибридных суперЭВМ
Статья научная
Статья посвящена вопросам безопасности традиционных, широко распространенных схем работы с паролями. Показано как современное широкодоступное высокопроизводительное оборудование позволяет проводить эффективные атаки на базы данных с хэшами паролей, которые последнее время все чаще оказываются в руках хакеров. Корнем этой проблемы является устаревшее, легкомысленное отношение к вопросу создания и хранения паролей как системных администраторов, так и конечных пользователей информационных систем. Авторы статьи не дают полного описания адаптивного алгоритма дешифровки паролей, но делятся некоторыми близкими результатами в надежде на то, что специалисты, отвечающие за хранение и использование паролей, ознакомившись с этой публикацией, смогут сделать свои информационные системы более защищенными. В статье обосновывается, почему широко укоренившиеся в последние десятилетия в сознании людей схемы создания и хранения паролей следует незамедлительно модифицировать в сторону повышения их надежности. В заключении статьи даются некоторые конкретные рекомендации в части противодействия интеллектуальному суперкомпьютерному криптоанализу. Ключевые слова и фразы: T-система, динамическое распараллеливание, язык программирования T++, криптоанализ, информационная безопасность, цепи Маркова, адаптивный подбор паролей
Бесплатно
Аддитивные системы представления чисел: несколько замечаний
Ред. заметка
Фибоначчиева система является общеизвестным примером аддитивных систем представления чисел. В данной работе рассматриваются общие аддитивные системы и устанавливаются некоторые их свойства, в частности, условия, при которых возможно представление натуральных, целых и действительных чисел. Даются вычислительные характеристики действий. Завершается статья совокупностью задач различной трудности.
Бесплатно
Ред. заметка
В работе обосновывается, что, в случае, когда постановка задач верификации рассуждений использует понятие соответствия, можно проверять логическое следование, не применяя логический вывод. При этом удобно использовать исчисление конституентных множеств и постановку задач в логике 𝐿𝑠2 [1]. На примерах показано, что для логики предикатов, верификацию логического следования можно проводить с использованием простых рассуждений с на основе соответствия Галуа
Бесплатно
Высокопроизводительные вычисления с использованием системы остаточных классов
Статья научная
Система остаточных классов (СОК)—это непозиционная система счисления, являющаяся альтернативой двоичному представлению чисел. В СОК большое целое число представляется в виде набора меньших чисел, являющихся остатками от деления исходной величины на выбранные модули. СОК выполняет сложение, вычитание и умножение с каждым остатком по отдельности. Это приводит к параллельной, свободной от переносов и высокоскоростной компьютерной арифметике для высокопроизводительных вычислений. Однако немодульные операции, требующие оценки величины числа по остаткам, являются сложными для реализации в СОК, так как для них не существует параллельной формы. В вопросах практического использования СОК выполнение немодульных операций занимает центральное место. Представлен обзор исследований в области разработки и применения на практике методов высокопроизводительных вычислений на основе СОК: Рассмотрены существующие техники выполнения важнейших немодульных операций, таких как обратное преобразование, сравнение чисел, вычисление знака и деление. Акцент сделан на методы, пригодные для произвольных наборов модулей. Показано, каким образом арифметика на основе СОК находит практическое применение в облачных средах, блокчейн-технологиях, вычислениях многократной точности и глубоких нейронных сетях. Обзор ориентирован на развитие новых направлений исследований, посвященных применению непозиционных систем счисления с параллельной структурой в ресурсоемких приложениях.
Бесплатно
Заметка об автоматическом решении квадратичных уравнений в словах
Статья научная
При анализе программ, оперирующих строками, естественным образом возникает задача решения уравнений в словах. На практике часто встречаются такие уравнения, содержащие, самое большее, два вхождения каждой переменной, –- так называемые квадратичные уравнения. Для их решения Ю. И. Хмелевским в 1971 году предложен интуитивно ясный алгоритм, имеющий экспоненциальную сложность. В 1999 году В. Дьекертом показано, что задача решения квадратичного уравнения является NP-трудной. В данной заметке изложены и показаны на примерах способы упрощения классического алгоритма Хмелевского, позволяющие добиться лучшей его применимости в автоматическом анализе программ.
Бесплатно
Интеллектуальная поддержка процессов контроля и диагностики космических подсистем
Статья научная
В настоящей работе проведено исследование предметной области, выполнен обзор существующих разработок в области построения систем мониторинга, контроля и диагностики подсистем космических аппаратов, в том числе, с использованием нейросетевого подхода. Теоретически исследованы пути реализации математического и алгоритмического обеспечения системы контроля и диагностики подсистем космического аппарата.Разработаны методические подходы, способы и методы решения технических задач по построению нейросетевой системы контроля и диагностики подсистем космического аппарата. Применение технологий искусственных нейронных сетей позволяет обнаруживать, классифицировать и прогнозировать ошибки, осуществлять многоуровневую диагностику подсистем космического аппарата и прогнозировать их дальнейшее поведение, тем самым увеличивая эффективность, скорость принятия решений и надежность работы узлов космического аппарата.Представлен метод графического представления временных последовательностей, позволяющий визуально классифицировать радиотехнический сигнал и обнаружить шум в этом сигнале. Предлагается формировать и ранжировать набор значимых признаков путем применения алгоритмов «Add» и «Del».
Бесплатно
Использование локализации и переполнения для управления параллельными и распределёнными вычислениями
Ред. заметка
Применительно к задачам суперкомпьютинга и сверхбольших баз данных рассматривается абстрактная концепция переполнения и показывается, как её использовать для организации и оптимизации распределённых и параллельных вычислений. Работа является второй в серии, посвящённой методам организации вычислений над локальными системами.
Бесплатно
Исследование эффективности векторизации гнезд циклов с нерегулярным числом итераций
Статья научная
Векторизация вычислений является важной низкоуровневой оптимизацией, используемой для создания высокоэффективного параллельного кода. Особенности набора инструкций AVX-512 позволяют применять векторизацию для сложного программного контекста, в частности для гнезд циклов и циклов с сильно разветвленным управлением. При использовании векторных инструкций для контекста с неизвестным профилем исполнения существует опасность низкой эффективности векторизации. Особенно ярко это проявляется при векторизации гнезд циклов с нерегулярным числом итераций внутреннего цикла.В статье рассматривается практический подход к векторизации гнезд циклов, основанный на предикатном представлении программы. В качестве примера приводится реализация сортировки Шелла, компактная реализация которой состоит из гнезда циклов, в котором количество итераций внутреннего цикла носит нерегулярный характер и зависит от номеров итераций внешних циклов. Такой контекст является крайне неудобным для векторизации.Приводится сравнение теоретической и практической эффективности векторизации сортировки Шелла, рассматриваются особенности этого программного контекста и объясняется их негативное влияние на производительность векторизованного кода. Полученные результаты могут быть использованы исследователями и разработчиками программного обеспечения для обнаружения причин низкой эффективности векторизации программного кода с похожими особенностями.
Бесплатно
Локальная конкурентность в задачах интерполяции
Статья научная
Простой пример иллюстрирует недостаточность известных подходов к интерполяции в задаче восстановления функции по немногим заданным отчётливо передающим форму частным значениям. Известные подходы дополняет локальный выбор между полиномиальной и рациональной локальными интерполянтами, минимизирующий ошибки локальной интерполянты в ближайших внешних узлах c одной или разных сторон. Новый подход сочетает предельную вычислительную простоту локальных интерполянт с тщательностью их подбора. Принципы построения алгоритма сформулированы в общем виде для отображений метрических пространств. Они обеспечивают точное (за редкими исключениями) восстановление отображений, локально совпадающих с какими-то из заданных возможных интерполянт. В одномерном случае двухэтапный алгоритм гарантирует непрерывность интерполянты и точное восстановление одновременно {[itemindent=1cm] полиномов малой степени, несложных рациональных функций с~линейным знаменателем, ломаных из~длинных звеньев с~узлами на~концах } в~типичных ситуациях, когда эти требования не противоречат друг другу. Дополнительный параметр позволяет заменить точное восстановление ломаных требуемой гладкостью интерполяции.
Бесплатно
Методы и модели автоматического синтеза технологических процессов, основанного на знаниях
Статья научная
Рассматриваются методы и модели автоматического построения оптимизированных технологических процессов в различных предметных областях, включая системы автоматизированного проектирования и управления. Наибольшее внимание уделено универсальным решениям синтеза, основанным на знаниях. Приведены примеры практического построения технологических процессов в области САПР вычислительных систем и системах управления беспилотных летательных аппаратов
Бесплатно
Моделирование задачи оптимального выравнивания последовательностей
Статья научная
Выравнивание последовательностей широко используется в различных компьютерных системах для анализа и оценки близости данных, выделения изменений и родственных задач. Интуитивные требования к постановке задачи оптимального выравнивания последовательностей формализованы в приводимых тестах. Тесты показали, что ни один из широко используемых подходов к близости и выравниванию не соответствует этим требованиям. Описана новая модель минимизации конфликтов при слиянии изменений. Модель приводит к простой постановке задачи оптимального выравнивания последовательностей, удовлетворяющей рассмотренным требованиям.
Бесплатно
Моделирование прямоточного сумматора
Ред. заметка
В избыточной системе счисления сложение часто может выполнятся конечным автоматом. В данной статье рассматривается моделирование случая, когда в избыточной системе счисления сложение выполняется прямоточным образом. Показано, что одна и та же схема работает для разных типов данных. Рассмотрено сложение в двоичной, троичной, восьмеричной системах счислений. Показано, что схема работает для сложения двоичных матриц и действительных чисел
Бесплатно
Модель и аксиомы метрик сходства
Ред. заметка
В современных приложения метрики сходства обычно комбинируются с учётом сложности алгоритмов, особенностей восприятия человека, ресурсов и выборок данных. Для оптимизации требуется унифицированное формальное описание основных показателей подобия. Для оптимизации требуется выделить формально и строго описанное абстрактное понимание сходства между объектами.Расширена система аксиом метрики сходства и для неё построена универсальная модель, обощающая известные модели сходства, не сводящиеся к евклидовой метрике. Модель базируется на взвешенном частично упорядоченном множестве.
Бесплатно
О зависимых типах и интуиционизме в программировании математики
Статья научная
Обсуждается практическая возможность доказуемого программирования математики на основе подхода конструктивизма и применения языка с зависимыми типами (dependent types, proof carrying code). Принципы конструктивизма и доказуемого программирования объясняются на примерах. Рассмотрение опирается на опыт реализации на языке \textsys{Agda} небольшой библиотеки вычислительной алгебры, включающей арифметику области остатков $R/(b)$ для евклидова кольца $R$.
Бесплатно
Оптимизация и распараллеливание упрощенного алгоритма Балаша-Кристофидеса для задачи коммивояжера
Статья научная
В работе описывается точный параллельный алгоритм для задачи коммивояжера, основанный на упрощенном алгоритме Балаша/Кристофидеса, его оптимизация и увеличение эффективности распараллеливания. За счет нового метода передачи заданий между параллельными потоками алгоритм способен решать задачи с 3000 вершинами (со случайными весами дуг), в среднем, за минуту, а задачи с 10000 вершинами - за 50 минут. Возможность решать задачи с более чем 3000 вершинами появилась благодаря проведенной автором оптимизации расхода памяти.
Бесплатно
Построение доказательных программ арифметики натуральных чисел в двоичном представлении
Статья научная
Поддержка зависимых типов в функциональном языке программирования Agda создаёт возможность включать в программу машинно-проверяемые доказательства. Рассмотрена задача доказательного включения алгоритмов арифметических действий над натуральными числами в двоичном представлении. Построена библиотека доказательных программ алгоритмов обычных письменных вычислений, действующих над списками двоичных разрядов чисел. Она содержит машинно-проверяемые доказательства необходимых свойств применённых алгоритмов, исправляет и существенно дополняет часть Bin стандартной библиотеки lib-0.16 языка Agda.
Бесплатно
Приближение длины наибольшей общей подпоследовательности пары случайных строк
Ред. заметка
Математическое ожидание длины длиннейшей общей подпоследовательности букв двух случайных слов рассматривается как функция от длин и этих слов и мощности алфавита = A. При этом предполагается, что любая буква независимо и с равной вероятностью оказывается в любой позиции слова. Указан вид приближённой формулы для 𝐸(𝑚, 𝑛, 𝛼), позволяющий вычислять 𝐸(𝑚, 𝑛, 𝛼) с погрешностью в 0.3 процента для 64 6 + 6 65536 и 1
Бесплатно
