Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Исследование некоторых задач в алгебрах и пространствах программ

Название: Исследование некоторых задач в алгебрах и пространствах программ
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 10:14:21 21 марта 2005 Похожие работы
Просмотров: 82 Комментариев: 3 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

КазиевВ.М.

Рассмотрим пару алгебр (A,B): алгебру X=<X,&,a (+),a {},{}a > событий - алгоритмических процедур (программ) заданную над алфавитом X={x1 ,x2 ,...,xn } и В-трехзначную алгебру логики (0,1,2 - неопределенность). В алгебре А определим двухместные операции конъюнкции и условной дизъюнкции и одноместную операцию итерации следующим образом: конъюнкция s1 &s2 событий s1 , s2 состоит из всех слов вида pq, pÎ s1 , qÎ s2 ; a - дизъюнкция a (s1 +s2 ) совпадает с s1 (s2 ), если условие a истинно (ложно); итерация с постусловием {s}a состоит из пустого события s0 =e и всевозможных слов вида p1 p2 ...pk т.е. , {s}a =sm , где sm - последний из степеней s, для которого условие a выполнено; итерация с предусловием a {s} определяется аналогично. В алгебре А задается событие называемое неопределенным и обозначаемое символом Æ. Элементарные события в А - события е, x1 , x2 ,..., xn . Аксиомы алгебры А ниже рассмотрены. Все аксиомы алгебры B и правила вывода в ней сохраняются. Правила вывода, используемые в алгебре А включают правила вывода, принятые в программировании - см., например, [1]. Событие, получаемое применением конечного числа операций алгебры А над элементарными, называется регулярным.

Имеет место важная теорема Клини [2]: регулярные события и только они представимы в конечных автоматах.

Рассмотрим задачу построения алгоритма регуляризации во введенной паре алгебр (А,B). Алгоритм в укрупненных шагах состоит в следующем.

Шаг 1. Задается произвольное событие s=s0 s1 s2 ...sn+1 , где si - событие номер i, начальное событие - s0 , конечное - sn+1 , остальные события - преобразователи и/или события - распознаватели.

Шаг 2. Составляется система уравнений алгебры событий А: записывается функция F события, его дерево D и дерево состояний определяющее все к путей выполнения : , где Fi - функция ветви дерева состояний. Функция ветви дерева - композиция всех функций (событий) данной ветви; программная функция F - объединение всех функций ветвей дерева.

Шаг 3. Система уравнений с помощью подстановок и операций дизъюнкции и конъюнкции представляется в виде : X=XA+B, где X - событие, представленное заключительным состоянием sn+1 , .

Шаг 4. Находим решение системы. Используется теорема [3]: если характеристический граф матрицы А (орграф соединяющий ребрами вершины i и j только тогда, когда eÎaij ) не содержит ни одного цикла, то система X=XA+B имеет единственное решение X=B{A}, которое регулярно при регулярных A, B. При решении системы эффективно преобразовывать уравнения, - как и при решении линейных алгебраических уравнений, например, брать дизъюнкцию событий, изменять порядок исключения событий и др.

Шаг 5. По условиям выполнимости событий находим регулярную форму этого решения. Используются аксиомы алгебры логики В и соотношения алгебры событий А, например, следующие (AB=A&B, ab=a&b,a(A) - условие выполнимости события А, Aa - проверка условия a после события А и для этого условия верны все аксиомы алгебры В, - отрицание условия a):

Ae=eA=A,

ea=a(e)=a,

AÆ=ÆA=Æ,

2 (A+B)=Æ,

a(b(A))=b,

A(BC)=(AB)C,

b (A+B)=(a(A)+ (B)),

a(b (A+B))=(ba(A))+( (B)),

a (A+B)C=a (AC+BC),

Aa (B+C)=a (AB+AC),

a(AB)=a(A)Ba(B),

(AB)a=A(Ba),

A{B}a ={BA a }A,

a({A}b )={Ab }b,

{A}a =a (e+A{A}a ),

{a(A)}(B)={A} B,

a {A}a {A}=a {A},

{a a {A}}=a {A},

{A}a {A}a ={A}a ,

{{A}aa }={A}a ,

{a(A)}={A} ,

{A}a +e=a {A},

Aa {A}=a {A}A={A}a .

Пример 1. Регуляризуем микропрограмму А деления с фиксированной запятой. Для простоты считаем, что числа неотрицательны, а операция не приводит к переполнению разрядной сетки компьютера фон - Неймановского типа, операционный автомат которого состоит из регистров R1 , R2 сумматора R3 и счетчика сдвигов R4 . Делимое храниться на R1 , делитель - на R2 , частное накапливается на R3 . Введем обозначения: li - микрооперация сдвига регистра Ri влево (i=1,2,3); s-1 ij - микрокоманда вычитания из содержимого регистра Rj содержимого регистра Ri ; ai - условие заполненности регистра Ri ; gi - условие отрицательности содержимого регистра Ri ; pi - микрооперация занесения единицы в младший разряд Ri ; si,j - микрокоманда добавления содержимого регистра Ri к содержимому Rj .

Выпишем систему уравнений, обозначив через xi - событие соответствующее каждому из 11 пунктов алгоритма деления (см., например, [3]):

Решим эту систему. После очевидных подстановок, вводя обозначения:

x=x3 +x7 +x10 ,

B=el3 s-1 13 ,

A=g3 p2 l2 p4 l3 s-1 13 +g3 l2 p4 l3 s-1 13

получим уравнение X=XA+B, решение которого будет X=B{A} и после упрощений с помощью приведенных аксиом, заключительное событие S равно

s=x11 l3 s-1 13 {g 3 (l2 p4 l3 s13 +p2 l2 p4 l3 s13 -1 )}a 4

2. Рассмотрим задачу нахождения оптимальных (например, в смысле операции, длины и т.д.) структурированных программ из заданного набора базовых процедур (некоторые из них - см. в [5]), а также построения грамматик для анализа структур из программных единиц. При решении этой задачи используются аксиомы алгебры А.

Пример 2. Дана программа Р, где А,В,С - процедуры, a,b - предикаты:

P=a (BA+CA)b (Ab {A}+e)=a (B+С)Ab (Ab {A}+e)=a (B+С)Ab ({A}b +e)=a (B+С)Ab {A}=a (B+C){A}b =T.

Программа Т - более оптимальна и ее правильность доказываема формально.

Доказана теорема (доказательство не приводим из-за объема).

Теорема 1. Если R,A,S Î A, a,b,gÎB, A и S - коммутативны, то:

а)AX=Aa (R+SX)ÛAX=A{S}a R, б)Ag=Aa (b+Sg)ÛAg=A{S}a b,

в)Ag=Aa (b+S )ÞAg=A{S2 }t a (b+S ),t=a+Sa,

г)Ag=A{S2 }t gÞAg=At (e+S2 )g, g=a (b+S), t=a+Sa.

Рассмотрим задачу исследования разрешимости в пространствах программ.

Пусть x=<X, Y, M, S> - программа, определенная на входном алфавите Х, выходном алфавите Y и состоящая из подпрограмм (процедур) М с логической схемой (структурой) S. Структуре S поставим в соответствие орграф: Вершины - подпрограммы, ребра - в соответствии со структурой их взаимодействий. Метрика r(x,y) в этом пространстве - сумма всех весов ребер орграфов программ не совпадающих при заданной структуре S или отклоняющихся от оптимальной структуры, т.е. Аксиомы метрики проверяемы.

Отметим метризуемость пространства и по некоторым характеристикам качества программ Холстеда [6], а также с помощью понятия интеллектуальной работы программы, оцениваемой как разность энтропии до работы (статической формы программы) и после работы (динамической формы). У идеальной программы энтропия равна нулю. Отметим, что если ds/dt - общее изменение энтропии программного комплекса при отладке, ds1 /dt - изменение энтропии за счет необратимых изменений структуры, потоков внутри комплекса (рассматриваемую как открытую систему), ds2 /dt - изменение энтропии за счет усилий по отладке и тестированию, то справедливо уравнение Пригожина: ds/dt = ds1 /dt + ds2 /dt. Последовательность программ {xi }, сходится по схеме (структуре) к программе х (обозначим ), если r(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:U®V, U,V - линейные нормированные пространства D(L) ÍU, R(L)ÍV.

Теорема 2. Если R(L)=V и для каждого uÎD(L) существует постоянная c такая, что , то Lu+Tu=f имеет единственное решение uÎU.

Доказательство. Условия теоремы гарантируют существование непрерывного обратного оператора L-1 , причем . Тогда u=L-1 (f-Tu). Для однородного уравнения: . Отсюда следует, что , т.е. u=0. Следовательно, неоднородное уравнение имеет единственное решение.

Пример 3. Пусть umax - максимальный уровень синтаксических ошибок в программе Р, u(t) - их оставшееся количество к моменту времени t. Исходя из модели du/dt+lumax =0, u(t0 )=u0 можно заключить, что уровень ошибок убывает при l(c-t0 ) ¹ -1 (t0 <c<T) по закону: u(t) = u0 (1+ l(c-t))/(1+l(c-t0 )).

Если задать дополнительно u(t* )=u* , (umax - неизвестная величина), то закон изменения уровня ошибок находится однозначно, так как: с=(u* t0 -u0 t* )/(lu* -lu0 )-1/l.

Вопросы разрешимости некоторых уравнений Lx=y, где х - неизвестная программа, y - заданная программа, L - оператор, например, оптимизации, будут изложены в другой работе.

Список литературы

1. Алагич С., Арбиб М. Проектирование корректных структурированных программ. - М., Радио и связь, 1984.

2. Клини С.К. Представление событий в нервных сетях и конечных автоматах. - Автоматы, ИЛ, М., 1956.

3. Бондарчук В.Г. Системы уравнений в алгебре событий. - Журнал вычислительной математики и математической физики, N6, т.3, 1963.

4. Глушков В.М. О применении абстрактной теории автоматов для минимизации микропрограмм. - Изв. АН СССР, Технич. кибернетика, N1, 1964.

5. Казиев В.М. Дидактические алгоритмические единицы. - Информатика и образование, N5, 1991.

6. Холстед М. Начала науки о программах. - М., Финансы и статистика, 1981.

7. Казиев В.М. Один класс математических моделей переработки информации и некоторые его приложения. - Нелинейные эволюционные уравнения в прикладных задачах, Киев, 1991.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений21:59:39 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
15:32:48 24 ноября 2015
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
08:53:20 24 ноября 2015

Работы, похожие на Реферат: Исследование некоторых задач в алгебрах и пространствах программ

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(151079)
Комментарии (1843)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru