Алгебраическое программирование В.М.Глушкова.

Введение

Актуальность темы. Жизнь всякого человека наполнена программированием. Ежедневно каждый из нас ставит будильник на телефоне, задает программу стиральной машине или мультиварке – все это наглядные примеры человеческого программирования.
Существует разные виды программирования, но суть каждого заключается в выполнении действий, записанных в коде.
При программировании очень важно понять, насколько мощным является то, что вы знаете. В принципе любой интересный алгоритм/программу можно написать, основываясь на тех знаниях, которые вы получили в самом начале обучения программирования. Все мощные способности современных языков не обязательны для построения интересных вещей – они нужны только для того, чтобы построить их более четко и удобно. Говоря другими словами, хорошим писателем становится не тот, кто выучил много слов из словаря, а тот, кто нашел, о чем рассказать.
Для написания качественных программ, можно дать несколько простых советов [1,с.5]:
Пишите сначала комментарии. Начинайте ваши программы и процедуры с нескольких предложений, которые объясняют то, что они должны делать. Это важно, потому что если вы не сможете с легкостью написать эти комментарии, то, вероятнее всего, вы не понимаете, что делает программа. Редактировать комментарии гораздо проще, чем редактировать программу , поэтому время, потраченное на дополнительное печатание, потрачено с большой выгодой. Конечно из-за того, что на соревнованиях обычно поджимает время, появляется привычка быть небрежным, но в этом нет ничего хорошего.
Документируйте каждую переменную. Напишите одну строку комментария для каждой переменной, чтобы бы вы знали, что она делает. И снова, если вы не можете четко это написать, то вы не понимаете, что она тут делает. Вы будете общаться с программой, по крайней мере, несколько циклов отладки, и вы оцените это скромное вложение в ее читабельность.
Используйте символьные константы. Когда бы вам ни потребовалась константа в вашей программе (размер входных данных, математическая константа, размер структуры данных и т.д.), объявляйте ее в самом начале программы. Использование противоречивых констант может привести к очень сложным и трудно обнаруживаемым ошибкам. Конечно, символьное имя нужно только тогда, когда вы собираетесь его использовать в том месте, где должна быть константа.
Используйте подпрограммы, чтобы избежать излишнего кода. Гораздо безопаснее написать одну подпрограмму и вызывать ее с соответствующими параметрами, чем повторять одно и тоже с разными переменными.
Объект исследования – программирование.
Предмет исследования - алгебраическое программирование В.М. Глушкова.
Целью данной работы является изучение принципов алгебраического программирования В.М. Глушкова.
Для достижения поставленной цели необходимо решить следующие задачи:
Ознакомиться с понятием теоретическое программирование;
Ознакомиться с понятием алгебраическое программирование;
Изучить алгебраическое программирование В.М. Глушкова;
Изучить теории алгоритмики программ.

1.Теоритическое программирование
Первые школы программирования шли по пути создания теории схем программ, синтеза, композиции и сборки программ, а также алгоритмических и алгебраических методов программирования. В рамках этих школ определены и теоретически обоснованы формальные подходы к конструированию логических схем программ, методов их описания и реализации на ЭВМ [1,с.5].
Теоретически и практически программисты с математическим образованием развивали отдельные направления в программировании, объясняя некоторые закономерности в структуре программ и их определении с различных точек зрения[2,с.11]:
аппарата функций (функциональное программирование);
композиций (композиционное программирование и др.);
теории модульного программирования и сборки программ.
Первые работы в области теории программирования связаны с понятием схем программ, синтаксиса и семантики ЯП, моделей вычислений последовательных программ (операторных программ) и рекурсивных программ, которые строились в рамках некоторой абстрактной алгебраической системы.
При этом использовался алгебраический математический аппарат для объяснения действий над элементами программ, выполнения математических операций над этими элементами и принципов обработки, исходя из базовых основ алгебры – алгебраическое программирование, алгоритмика, композиции и др. Существуют следующие теоретические методы программирования[2,с.13]:
Логическое;
Алгебраическое;
Композиционное;
Экспликативное;
алгебраическое и др.
Данные методы основаны на математических, алгебраических и логико-алгоритмических подходах построения и доказательства программ, в том числе определения интеллектуальных агентов.


2.Алгебраическое программирование
Алгебраическое программирование (АП) - это конструирование программ с алгебраическими преобразованиями и функциями интеллектуальных агентов[3,с.23]. В основе математического аппарата АП лежит алгебра языка действий АL (Action Language) и понятие транзитивной системы в качестве механизма определения поведения систем и механизмов ее эквивалентности. В качестве понятий в общем случае могут быть компоненты, программы и их спецификации, объекты, взаимодействующие друг с другом и со средой их существования.
Основу АП составляет математическая модель, которая включает в себя следующие понятия[3,с.27]:
агент как транзитивная система с поведением и его завершением;
поведение агентов, задаваемое в языке АL с помощью операций a,u,u+v, констант ∆, ┴, 0, граничных условий и рекурсий;
среда, состоящая из агентов и функций погружения, которая обозначается env и имеет в качестве параметров состояние среды и агентное выражение;
функция развертывания функциональных выражений в простые агентные выражения;
транзитивная система, представленная в виде композиции среды и системы взаимодействующих агентов, погруженных в эту среду.
Всякая транзитивная система имеет историю функционирования, которая включает последовательность действий и состояний - конечных или бесконечных. История функционирования хранит одно из соответствующих состояний: успешное завершение вычислений в среде транзитивной системы; тупиковое состояние, когда каждая из параллельно выполняющихся частей системы находятся в состоянии ожидания; неопределенное состояние, возникающее при выполнении алгоритма с бесконечными циклами.
Расширение понятия транзитивных систем – это множество заключительных состояний с успешным завершением функционирования системы и без неопределенных состояний[3,с.35]. Главный инвариант состояния транзитивной системы - поведение системы, задаваемое выражениями алгебры поведения F(A) на множестве операций алгебры действий – префиксинг a*u, недетерминированный выбор u+v одного из двух поведений u и v со свойством ассоциативности и коммутативности. Конечное поведение системы задается константами ∆, ┴, 0, которые обозначают соответственно состояние успешного завершения, неопределенного и тупикового

. Алгебра поведения включает отношение ≤, элемент ┴ как наименьший и операции поведения, являющиеся монотонными. Средствами алгебры поведения F(A) доказана теорема про наименьшую неподвижную точку[3,с.37].
Транзитивные системы называют бисимуляцийно эквивалентными, если каждое состояние эквивалентно состоянию другой системы. На множестве поведений определяются новые операции, которые используются для построения программ агентов. К ним относятся следующие операции: последовательная композиция (u;v) и параллельная композиция u||v [3,с.40].
Среда E, где находится объект, определяется как агент в алгебре действий АL и функции погружения от двух аргументов Ins(e,u)=e[u]. Первый аргумент - это поведение среды, второй - поведение агента, который погружается в эту среду с заданным состоянием. Значения функций погружения - это новое состояние одной и той же среды. Базовым понятием является «действие», которое трансформирует состояние агентов, поведение которых, в конце концов, изменяется.
Поведение агентов характеризуется состоянием с точностью до слабой эквивалентности. Каждый агент рассматривается как транзитивная система с действиями, определяющими не детерминированный выбор и последовательную композицию (т.е. примитивные и сложные действия). Последовательная композиция - ассоциативная, а параллельная композиция - ассоциативная и коммутативная. Параллельная композиция раскладывается на комбинацию действий компонентов[3,с.40].
Взаимодействие агентов может быть двух типов. Первый тип выражается через параллельную композицию агентов над той же самой областью действий и соответствующей комбинацией действий. Другой тип выражается через функцию погружения агента в некоторую среду, результат трансформации - новая среда.
Язык действий АL имеет синтаксис и семантику. Синтаксис языка задает правила описания действий, семантика - функции, которые определяются средствами и выражениями языка и ставят в соответствие заданным выражениям значения в некоторой семантической области. Разные семантические функции могут давать равные абстракции и свойства программ. Семантика может быть вычислительной и интерактивной. Каждая алгебра действий - это гомоморфный образ алгебры примитивных действий, когда все слагаемые разные, а их представление однозначно с точностью до ассоциативности и коммутативности при детерминированном выборе[3,с.42].
Агенты рассматриваются как значения транзитивных систем с точностью до бисимиляционной эквивалентности, которая характеризуется непрерывной алгеброй с аппроксимацией и двумя операциями: недетерминированным выбором и префиксингом. Среда вводится как агент, в нее погружается функция, которая имеет поведение (агент и среда). Произвольные непрерывные функции могут быть использованы как функции погружения в эти функции. Трансформации поведения среды, которые определяются функциями погружения, составляют новый тип эквивалентности - эквивалентность погружения.
Создание новых методов программирования с введением агентов и сред позволяет интерпретировать элементы сложных программ как самостоятельно взаимодействующие объекты[4,с.7].
В АП интегрируется процедурное, функциональное и логическое программирование, используются специальные структуры данных - граф термов, который разрешает использовать разные средства представления данных и знаний о ПрО в виде выражений многоосновной алгебры данных.
Наибольшую актуальность имеют системы символьных вычислений, которые дают возможность работать с математическими объектами сложной иерархической структуры - группы, кольца, поля. Теория АП обеспечивает создание математической информационной среды с универсальными математическими конструкциями, вычислительными механизмами, учитывающими особенности разработки ПС и функционирования.
Алгебраическое программирование концентрирует внимание на проблемах интеллектуализации и аспектах поведения агентов в распределенной среде, куда они погружаются. Оно постепенно перешло в инсерционное программирование путем вставки, погружения агентов в разнообразные среды для преобразования поведения агентов на основе модели поведения, соответствующей размеченной транзитивной системы и бисимуляционной эквивалентности. Данное программирование обобщает алгебраическое преобразование множества состояний информационной среды на объекты, обладающие поведением [5,с.11]. Схема создания агентных программ представлена на рис.2.1.
Главное действующее лицо инсерционного программирования - агент, обладающий поведением при его погружении в среду, которую он также меняет. Характерной особенностью является недетерминированное поведение агентов и сред, как это происходит в реальных системах. При этом программа агента требует не интерпретации, а моделирования, поскольку она представляется транзитивной системой в виде композиции среды и системы взаимодействующих агентов, погруженных в эту среду. Язык действий - порождающий, в нем задается синтаксис действий, агентных функциональных выражений и внутренних состояний среды. Кроме того, в этом языке описывается семантика функций развертывания агентных функциональных выражений и погружений агентов в среду.
Программа - набор параметров и начальных агентных выражений. Параметры могут быть фиксированные и переменные, изменяющиеся при переходе от одной среды в другую. Особенно это касается параметров развертывания.

Рис.2.1.Технологическая схема в АП
На следующем уровне описания программы находятся функции, которые преобразуют любое агентное выражение в AL-программу действий. Например, функция U развертывания функциональных выражений может быть представлена в виде простых агентных выражений[5,с.15]:
U(u+v)=U(u)+U(v), U(u)=u,
где u, v - параметры агентных выражений.
Функция развертывания агентных функциональных выражений задает семантику AL-программы в виде программы функционирования агента в любой среде. Если функция развертывания обрабатывается за конечное число шагов, то она содержит конечное выражение. Множество всех переходов, заключительных и тупиковых состояний - перечислимое, даже если функция развертывания имеет бесконечное множество нетривиальных итераций. Состоянием транзитивной системы являются ограниченные выражения, определяемые операцией выбора +, соотношением x+0=a и отношением перехода с правилом u→U(u) [6,с.23].
Третий уровень программы - это функция развертывания погружений, задаваемых в алгебре действий. Эти функции определяются на объектах среды и агентов, т.е. агентных выражениях. Для корректности функций погружения необходимо, чтобы она зависела только от поведения агента и среды и была непрерывной функцией. Следующим шагом разработки программ является ее реализация в ЯП, например в С++, когда уточняются типы данных и параметры. Затем проводится верификация полученной программы для проверки правильности выполнения ее поведения в заданной модели.

3.АП в.м.глушкова
Примером применения алгебраических методов может служить проблема эквивалентности дискретных преобразователей теории Глушкова, в которую естественно вкладываются операторные схемы программ.
Пусть χ – конечный автомат Мили с входным алфавитом X и выходным алфавитом Y и с заданными начальным и заключительным состояниями [6,с.3].
Пусть G – полугруппа с множеством образующих Y единицей е и рассматривается автомат Мура Gm (бесконечный) с множествами состояний G, входов Y, выходов X, начальным состоянием е, функцией выхода m(g) и функцией перехода q(g, y) = gy[6,с.3].
Автомат χ, работающий совместно с Gm, называется дискретным преобразователем