Исследование некоторых задач в алгебрах и пространствах программ
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
структуре S или отклоняющихся от оптимальной структуры, т.е. Аксиомы метрики проверяемы.
Отметим метризуемость пространства и по некоторым характеристикам качества программ Холстеда [6], а также с помощью понятия интеллектуальной работы программы, оцениваемой как разность энтропии до работы (статической формы программы) и после работы (динамической формы). У идеальной программы энтропия равна нулю. Отметим, что если ds/dt - общее изменение энтропии программного комплекса при отладке, ds1/dt - изменение энтропии за счет необратимых изменений структуры, потоков внутри комплекса (рассматриваемую как открытую систему), ds2/dt - изменение энтропии за счет усилий по отладке и тестированию, то справедливо уравнение Пригожина: ds/dt = ds1/dt + ds2/dt. Последовательность программ {xi}, сходится по схеме (структуре) к программе х (обозначим ), если (xn,x) 0, при n, т.е. дерево программы xn при n стремится к дереву программы х. Последовательность {xi} сходится функционально к программе х (обозначим ), если F(xn) F(x) при n (программная функция xn стремится к программной функции х). Нетрудно видеть, что из сходимости по схеме следует сходимость функциональная, но обратное неверно.
Пусть M = {x1, x2, ..., xn,...} - последовательность программ с общей функцией (эквивалентных функционально). На этом множестве рассмотрим множество операторов А преобразования (композиции, суперпозиции) программ. Последовательность {An} сходится к А функционально (по схеме, структуре), если верно: xМ:
С точки зрения исследования существования, единственности оптимальной (в каком-то смысле) программы можно рассмотреть: операторы минимизации числа операндов; операторы минимизации числа типов операторов; операторы минимизации числа вызовов процедур; минимизации числа ошибок в программе; минимизации сложности (разных способов определения) и др. При исследовании программных систем важно рассматривать пространства векторов х=(х1,x2,...,xn), где xi - характеристика ошибок в программе или структурной связностипроцедур, ui - количество ошибок в i-ом модуле программного комплекса P(u)=P(u1,u2,...,un).
Пусть u(x,t) - количество ошибок, обнаруженных в программе (системе) в момент времени t, а х - характеристика уровня ошибок. Рассмотрим модель обнаружения ошибок при отладке, представимая уравнением (см. также [7]): Lu+Tu=f, где T - оператор, определяющий первоначальный уровень ошибок в программе или их некоторую характеристику, L - некоторый линейный ограниченный оператор отладки, L:UV, U,V - линейные нормированные пространства D(L) U, R(L)V.
Теорема 2. Если R(L)=V и для каждого uD(L) существует постоянная c такая, что , то Lu+Tu=f имеет единственное решение uU.
Доказательство. Условия теоремы гарантируют существование непрерывного обратного оператора L-1, причем . Тогда u=L-1(f-Tu). Для однородного уравнения: . Отсюда следует, что , т.е. u=0. Следовательно, неоднородное уравнение имеет единственное решение.
Пример 3. Пусть umax - максимальный уровень синтаксических ошибок в программе Р, u(t) - их оставшееся количество к моменту времени t. Исходя из модели du/dt+umax=0, u(t0)=u0 можно заключить, что уровень ошибок убывает при (c-t0) -1 (t0<c<T) по закону: u(t) = u0(1+ (c-t))/(1+(c-t0)).
Если задать дополнительно u(t*)=u*, (umax - неизвестная величина), то закон изменения уровня ошибок находится однозначно, так как: с=(u*t0-u0t*)/(u*-u0)-1/.
Вопросы разрешимости некоторых уравнений Lx=y, где х - неизвестная программа, y - заданная программа, L - оператор, например, оптимизации, будут изложены в другой работе.
Список литературы
1. Алагич С., Арбиб М. Проектирование корректных структурированных программ. - М., Радио и связь, 1984.
2. Клини С.К. Представление событий в нервных сетях и конечных автоматах. - Автоматы, ИЛ, М., 1956.
3. Бондарчук В.Г. Системы уравнений в алгебре событий. - Журнал вычислительной математики и математической физики, N6, т.3, 1963.
4. Глушков В.М. О применении абстрактной теории автоматов для минимизации микропрограмм. - Изв. АН СССР, Технич. кибернетика, N1, 1964.
5. Казиев В.М. Дидактические алгоритмические единицы. - Информатика и образование, N5, 1991.
6. Холстед М. Начала науки о программах. - М., Финансы и статистика, 1981.
7. Казиев В.М. Один класс математических моделей переработки информации и некоторые его приложения. - Нелинейные эволюционные уравнения в прикладных задачах, Киев, 1991.