Математика

О надежности неветвящихся программ в базисе, содержащем штрих Шеффера

С. М. Грабовская

Пензенский государственный университет, Пенза

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

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

УДК: 519.718

DOI: 10.21685/2072-3040-2018-4-3