автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы и средства автоматического проектирования программ по операторным термам

РГ6 он

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИ?: ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ 1 ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ '

На правах рукописи

ЧИЧИКОВ АЛЕКСАНДР ВИКТОРОВИЧ

"МЕЮДЫ И СРЭДСТВА АВТОМАТИЧЕСКОГО ПРОЕКТИРОВАНИЯ ПРОГОШМ

ПО ОПЕРАТОРНЫМ ТЕРМАМ"

05-13.11 - матемзтичесг.ое и программное обеопечеш1е вы-гкслителышх маетш, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание учрной степени кандидата технических наук

Минск - 1994

Работа вилслнена в Белорусском государственном университете.на кафедре Ичгомашчеекого обеспечения САШ5

Научный рукогодм елъ кандидат £из.-ш)т. каук, доцент Мсчценскнй В.А.

Официальные оппоненты: доктор мяничесчах наук, профессор ШПИКОВ В.А.

кандидат флз.-к.ат. наук, дсцгнт Бородач Л.И.

Ведущая организация - БЦ ь'шшстерства образования

Задета состоится "_£!_" апреля 1994 г. в 14 чао на заседаем специализироЕашюго совета К 056.05.01 Белорусского государственного университета информатики и радиоэлектроники по адресу: 220027, Минск, ул. П. Броыи, б.

С диссертацией мс;шо ознакомиться в библиотеке университета

Автореферат разослан "24 марта 1994 г.

Ученый секретарь специа.'шзпровашюго

совета К 056.05.01, доцент А"П' Пашкевич

ВВЕДЕНИЕ.

Актуальность теми В настоящее время получает приоритет создание тагах систем программирования, которые оперировали бы математическими моделям объектов. Эти модели долим содержать метода иг анализа и преобразования. Желательно, чтобы пользователь, обращаясь в рекше диалога к такой системе, задавал лишь конечный результат, а его получение обеспечивалось бы самой системой на основе описанных в модели методов. Ясно, что такие система позволяют значительно повысить производительность труда прогрямягатов и пользователей, облегчаит работу на ЭЕМ. Однако самим вакным является то, что при нспользовагаш таких скате!.« работа ЭЕМ заметно "илтеллектуализируется". Это позволяет ей стать еще более гибким шгструментом в различных исследованиях п вкспериментах. Создание таких енотом нуждается в новцх подходах к технологии программировать. Такими подходашг являвтея логическое и функциональное програилфованин, а Taic:e концептуальное или объектно-ориентирозазшее программирование ( ООП ), которое в последнее время получает все большее распространение и становится одной из ведудих концепция современного программирования. С другой сторонн эти подходы вызывают повызэшшй интерес к моделям и методам дискретной математики и математической лога-га.

Работы по донным научгаг.» направлениям имеются у белорycc:sts ученых Петровского A.A., Беликова В.А., Склярова В.А., Сородича Ю.С., Вальвачева А.Н. и др., а такта у зарубеггшх учетггх -Тиугу Э.Х., Ченя Ч., Ли Р., Калклэроэ А., Фуги К., Судзука И., Mairaa 3., Флойда Р. н др.

ШУШ работы. Разработать алгоритмы, методы, а такга осуществить программу» реализации автоматического проектировали программ то операторным термам. Операторные термы выбраны потому, что к.я более окономно задается вычислишь функции, чем, скажем, логкчесгагми выводами.

Для достижения втоЛ целя необходимо решить следзпгдпэ оснсз-гше задачи:

разработать математические методы для синтеза nperpaws по операторным термам;

разработать модель синтеза программ по операторным термам, которая при проектировашв! использует

дедуктивный подход к автоматическому синтезу программ,

объектно-ориентированный подход; разработать структуру и осуществить программную реализацию системы автоматического проектирования программ по операторным термам ( САППОТ );

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

Используемые в данной диссертации операторные термы являются термами в смысле, А.И.Мальцева и представляют собой выражения, состоящие из функциональных символов примитивной рекурсии й, минимизации М, суперпозиции Бп+1 , а также символов простейших функций о, в, Т™.

Методы исследования. При решении втих задач использовались следующие методы: логических выводов в формальных теориях, теории алгоритмов, комбинаторного анализа, дедуктивного подхода к автоматическому синтезу программ, объектно-ориентированного подхода к проектированию программ.

Научная новизна. Основные результаты, выносимые на защиту, заключаются в следующем.

1. Разработаны математические метода для синтеза программ по операторным термам.

2. Разработана математическая модель автоматического проектирования программ по операторным термам, которая работает следующим образом.

а. вычисляет по терму, задающему вычислимую функцию Г, значение етой функции I при указанных значениях аргументов;

О. проектирует и выдает по введенному терму программу на языке Паскаль для функции, заданной втим термом, следуя при етом одному из подходов логического программирования - дедуктивному подходу к автоматическому синтезу программ;

в. применяет один из операторов примитивной рекурсии, минимизации или суперпозиции к программам, спроектированным и выданным как самой САЛЮТ, так и написанным на языке Паскаль для вычислимой функции человеком , для проектирования и выдачи новых программ для соответствующих вычислимых функций, следуя при атом объектно-ориентированному подходу к проектированию программ,

3. Дана оценка шшиу и сверху числа различных вичислишх

'"yniiríí, пгэдотазлешж через тертя! :: нзгвдп^ася из ¿стях р:о-отсянт от ^:с:опрсЕ02гогэ г":с"'.сстЕа порсоиачэ-тази Это

«стало рез::о возрастав? с увагэтеяясч пспельзуе!пс в тер-'« сгасо-лзз операторов прздптпгпсП p2::ype;si, мажятояаг, супоргозетргт. 2гот >JaRT гсЕорг? о тс-.;, рпснич тор ¡г?! охпгП тс.'1, по

лпгп! iío,:;ct б:гть паяг.сгпо газго разягшщс прогрг-'.гл, «отерта етп:слл:с? рззхтопгз E-re-сл йтаспя.

Eco прсгрл":":! СЛОЮ? nsnrcsna пз язкпз Псе:шль.

Псзз:пгг!?с:.:.оя norasc::. рэ5стц ссг?сп? s сл.гпгк"--'''

1. Ссзд-;гп:а:'1 С/.КП0Г :.гс"ст пепользевзтьел п глугго-зкрз.':?:!-4ic:ziz ггсохэдоазшгял. Hps сяз с^зепечгззст:

- nrscrscir.» зпггогз:." с^пл:*™ Çjzzzz'Si, птздсггзлзг-лг™ чорзз терм;

- Ерсаетзтрсвзплэ гггсгт^'"': дла птгепслг^п срз'з-ггг:." •:•'!•;": ;

- прсс?гглгсг.оп::о г.гогрг*ч длл пггптасг'лг -Г-угла:-:?: ггггг пр~.'эт?ггЕ:л слер^тсрсз иргутп-г-зЛ рзкурозя, гггг—гз.'лг:::, cyn-jv-r.osnrnt; iíí„t ere:: г.гдодьзусг i.tr*. rrvsrp?'-'::, спрззггпгрспгл^э i: котли» nr-yî Ci! ЛОТ, тш: it протр":"-.- ллл srmtc.rra.'nr ¡'угаягЛ, аглягепп*? пп ,тз::«:э Паепзль

Слоте".} г-сг:? хгрл-тллгьел в ;г;есгг=-'г цо-,:л:-: гг.'.: ::?;•-^гс:—:т ::урзсз "Зекрз'птгл '•тгл'зтдкп'' "Тгср"т ?jErey::.,:cr.*'f з

ÏIO^K^ypT ЛЛЛ'." I:: il"/, ' r'~ '' Т'''ЛЛГ '' ¡.■О"""1"*""' , Л ' > ; i.;'^ ;

под «од " ептззу проурлл* t педгед.

3. Оксзигетея, pr.r::.—f» л.з;ч-| и тс" гз лс-^сд^лсЛ д/л::'.» зздг::г иного пплел^дл; ЛуллцлЛ ( focp-чг; 1 и 2 }. Сл?Д"?зт:.лл>-мо, нота? C'iTb nnrercai'o гляго прогрг"м, готоггч лг-г-лтеллггг -

лаздллллз гЛгллл,"^ г.о отлсслтзг.ьг.з ллготп/" M

>гсм евядзтз.гьстэуе? лзл; л; ецзлла ензгу тлгго^сЛ rrsys:«*-

.. ........... . • ..••;•• 'у ;:IV,1V ТОГО, "ГО !----: ЯЗЛЛОТСЛ Д'! "Л ЛЛ

пе.'лпгсЯяеЛ.

Гза.'г.зг-к:'! г^зу.тг^тсгсг; T-j'ctu. ССЗДПТЗЛ чос:*.ого гтрсз!:'лггст,с-:п:л ттрогр-"-'! по ciijpnrcpr..-; гзг"г-м пргз-лтз -'.'rrîuoTepcTPOM сСрззоааглл к пр:г.'опсг:п в учебкчх игляг прл -пзу-ïenô куросз гзге'-эппа'', "Теорхл плгсг::г.:сз" ::

"Прогрч'^сфсззтао". С!стс5:а такг:з сд?На в FT'U! ( сет Я 0/5С9-93

от 23 сентября 1993 г.).

Апробация. Основные принципа и результаты, которые излагаются в работе, рассматривались и обсуждались на следующих конференциях: межреспубликанской научно-практической конференции творческой молодежи "Актуальные проблемы информатики: математическое, программное и информационное обеспечение" ( г. Минск, 1992 г; ), 1-й белорусской конференции "Новые информационные технологии обучения" ( г. Минск, 1992 г. ). Принципы и результаты этой работы также рассматривались, обсуждались и получили одобрение нз международном семинаре в МГУ "Компьютеры в естественнонаучном образовании" ( г. Москва, 24-26 марта 1992 г. ).

Основные результаты работы опубликованы в 3 работах: в 1 статье и 2 тезисах докладов на научных конференциях.

Структура и объем диссертации. Диссертация изложена на 204 листах машинописного текста, содержит 33 рисунка на 45 страницах и состоит из введения, четырех глав, заключения, списка литературы и трех приложений. Библиография включает 48 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении показана актуальность темы диссертации, сформулирована цель и определены задачи работы. Дается ее краткое содержание, положения, выносимые на защиту.

Первая глава посвящена обзору подходов, используемых при автоматическом проектировании программ по операторным термам. Этими подходами являются логическое и объектно-ориентированное программирования. Логическое программирование есть наиболее впечатляющий пример применений идей математической логики в программировании. Суть логического программирования заключается в том, чтобы не указывать ЭВМ последовательность шагов, ведущих к решению задачи, а описать на логическом языке свойства интересующей области. Другие свойства и необходимые объекты ЭВМ должна находить сама путем построения логического вывода. Если функцию рассматривать как особый вид отношения, то тогда языки функционального программирования, которые отроятся на основе понятия функции, есть особый класс языков логического программирования. Приводятся примеры втих языков - Рго1оу, Рефзл,ЛИСП. Затем рассматриваются логические основы автоматического синтеза программ, в частности, дедуктивный подход к автоматическом;' синтезу программ . 6

Далее речь идет об объектно-ориентированном программировании. Основная идея ООП заключается в разработке программ из классов объектов, которыми манипулирует программа. Рассматриваются основные понятия теории ООП - объект, инкапсуляция, наследование, полиморфизм, динамическое связывание. Говорится об истории становления и развития ООП. Приводятся примеры языков программирования, поддерживающих ООП. Это Смолток, последние версии Си и Паскаля, KSP, Eqlog. Среди отечественных объектно-ориентированных систем называются, например, НУТ и пакет структурно-логического синтеза программ.

Во второй главе рассматриваются методы проектирования и доказываются оценки для автоматического проектирования программ по операторным термам.

Определим терм индуктивно.

1. ( Исходные термы ). Термами длины 1 называются однобуквенные олова из предметных символов.

2. ( Правила построения новых термов ). Пусть для некоторого к>1 термы длины, меньшей к, определены. Тогда олово длины к есть терм, если оно имеет вид Г( 81,...,вп). где В1,...,ВП - термы длины, меньшей к, a f - n-местный функциональный символ.

Определим понятие значения терма на JJ. Сопоставим предметному символу некоторый элемент множества Н={0,1,2,...}, который иазовем значением данного предметного символа. Сопоставим n-местному функциональному символу некоторую n-местную частичную операцию на множестве Я, значение которой будет его значением.

Пусть терм имеет вид ГШ.,,.. .¿5П) и значения входящих в терм тредметных и функциональных символов определены на N, т.е. зна-1ения термов В^^,... ,®п равны некоторым элементам з^,...,^ лножества N. Значение n-местноЯ операции, соответствующей Г в сочке ( х.],...,Хд) есть некоторый элемент х из множества N, который есть значение терла Г(В1,...,ВП). Значение терма ЧВ},...,®^) не определено, если значение хотя бы одного из ■ермов ,... ,s>n не определено или, если значения термов Ц,...,ВП определены и равны ' х^,.... а значение п-местной >перации, сопоставленной функциональному символу I в точке х1,...,Хд) не определено.

Следующие функции на N являются исходными.

1. нуль-функция: о(х)=0 при кэзздом х;

2. функция следования: а(х)=х+1 при каждом х; _

3. сункщпг сыбора аргуиентоа при всех

, П21, 1SM1. Рассмотри слодух^пе три ел оратор а.

1. Оператор еупорлозлцкию-ыестная фугпщия h получается при nouons оператора суперпозиции из п-мстлой функции g и пьиестша: Фушодй f^,___,în, если

h(s1,...,«n)=g{î1(st,...,2M),...,în{x1,--.,2jn)). в ëtoîj случае

neneu

h(x1....,sE)=S^1(g,f1,...,in) ( 1 )

2- Оператор примитивной рекурсии: (пИ)-150стЕая функция i возникает из гг-меещой функции g и (гн2)-ыеоткой функции h цркмктив-иой рекурсией, если

i(x1,...,2n,0)=g(51,...,xn>, ( 2 )

i(r1,...,xr),y+1)=h(x1,...,xn,y,f(x1,...,xa,y;) ( 3 ) Если п=0, то

Т(0)=а ( а-кснстанта ) ( 4 )

I<x+1)=h(x,f(*)) ( 5 )

Будеи записывать r=n(g,h), где R - символ s-того оператора. 3.Операция ииш&мзащш. Пусть -дана п-цестная частичная числовая функции Г. Зафиксируем некоторые значения х.,,— >хп-1 Д-*"3 первых (п-1) аргументов фунгсции Г и рассмотрим уравнение

fix,,...,^.,^)^ ( 6 ) Для нахождении рааания етого уравнения будеи последовательно

вычислять зпачешхя ____,xn_1,v) для у=0,1,2.....Наииеньеео

значение а, для которого иолучлгея , — ойозна~

4KJJ

Ру<Г<Х1.....:tn-1'y)=Zn) ( 7 >

и назовем зкачешга уравнения ( б )

Злачепаа куражонля ( 7 ) не определено,-fела

!. сиачекле f(xls___.г^.О) на сдрс-дадс-Ео;

2. гзаченка -для у=0,1,...,а-1 определены, но отечны от , ti сличение X(::,,...»;:..._(,а) на слроделоно;

3. сьспедая ,... сггр:.-дэго:ш ¿¿я ваэх 1,2,...

с..:- ... :: ог-лтчни от z . - к

. " \ S c;ibv:35ii:e a п^бис;:.' or ггт^ьн::^ г.;.:ry-

::,,.-.-¡»^p» и гютс,;у с;:э осы, от к oprjvjîii-

•IC-. сСсзНоЧйу i:f, где i: - с::,:,.а, оаорьтора киздп-еш;--,:.

Сг,г.'..с;:£» углс-рт^нка L'a™ueta /..1!. ч».?та?к$ rcKjTxraiii;:.^;:

являются тв и только те функции, которые являются значениями термов, записываемых о помощью индивидуальных предметных символов о, в, и функциональных символов Я,М,Б2,Б3,... .

Общепринятой является гипотеза, известная как тезис Черча: класс алгоритмически вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций.

Таким образом, любая вычислимая функция может быть представлена соответствующим термом, состоящим из предметных символов о, в, I" простейших функций и операторных символов И, М, Бп+1.

При проектировании программ на основании заданного терма используется дедуктивный подход к автоматическому синтезу программ. Терм, по которому проектируется программа для соответствующей вычислимой функции, есть одновременно описание задачи и теорема существования решения, записанная на логическом языке термов. Далее САППОТ при анализе терма на корректность и определении размерности функции, заданной термом, выделяет и просматривает последовательно отдельные шага доказательства. При этом простейшие функции о, в, рассматриваются как аксиомы, а опе-операторы И, Бп, и М - как правила вывода. Затем на основе втого проектируется программа.

При проектировании программ при помощи операторов используется объектно-ориентированный подход. Служебная метка, размерность функции, набор значений аргументов - суть данные, определяющие свойства объекта. Процедуры для функций о, в, и функций пользователя, для операторов М, Я, Бп+1 оперируют свойствами объекта, то есть задают поведение объекта. Реализация втих процедур осуществлена так, что возможная модификация какой-либо из них не влечет за собой модификацию остальных. Необходимая последовательность вызовов втих процедур, то есть возможность определиться отим процедурам, определяется в ходе выполнения спроектированной программы. Спроектированная программа есть единое целое в неразрывной связи своих свойств и поведения. Поэтому ее можно рассматривать как объект в смысле ООП. САППОТ использует:

- исходный объект в случае выбора оператора М,

- два исходных объекта в случае выбора оператора П,

- п+1 исходных объектов в случае Еыбора оператора в"'1'1

для построения иерархии новых объектов.

Каждый из вновь спроектированных объектов наследует те свойства и поведение, которыми обладал его предшественник в

9

случае выбора оператора М, или обладали aro предшественники в

yiil

случае выбора операторов R и S .При атом на разных уровнях иерархии порожденных объектов процедуры имеют либо одинаковые имена ( в случае, если операторами М, R, Sn+1 используются только функции о, в, ), либо их имена изменяются по строго определенному алгоритму ( возможно в случае, если операторами используются функции пользователя ).

Определим множество Pa={o,s}u{ isnsa }, аа2.

Очевидно, что| 1>аI , где здесь и в дальнейшем | А |

обозначает число елементов конечного множества А. Последовательность частично рекурсивных функций

rrí2....rm (S)

будем называть выводом, если каждая í^ ( Isism ) является либо функцией из множества Р„, либо получается из функций

а

fi .fj етой последовательности, предшествующих функции

íj, т.е. jp.<i ( р=1,2.....k ) о помощью одного из операторов

Sn+1,R и М. Вывод ( 8 ) будем называть выводом функции f .

Функция í из вывода ( 8 ) находится на расстоянии к (каО)

от множества Р , если в выводе ( 8 ) используется ровно.к (каО) 11+1

операторов S ,шш R, или М.

Пусть 1(а,к) - число всех различных частично рекурсивных функций, которые находятся на расстоянии не более к ( каО ) от' функций множества Ро. Тогда L(a,0)=| Р„|.

8 а

Теорема 1. Для любого kaO при фиксированном а ( аа2 ) выполнено неравенство

L(a,k+1) s I(a,k) ( 2+k+a(a+1) )( 2+(1+к+а(а+4) )а).

2 2

Следствие. Для любого таО справедливо неравенство

В диссертации найдены некоторые значения L(a,1) при аа2.

L(a.m) s (2+m+a]a+2)) (2+( 1+m+a£a+4j. )

Вот они! Ь(2,1)=14, а при ааЗ Ь(а,1)=а3 + 11а + 6.

т ~т

Теорема 2. Для любого ааЗ и каждом тг1 выполнено

Ъ ( а, ПН1 ) а ( т+1 )( а3 - а2 + 19а + 4 ).

Г 5~ "Т"

Из следствия теоремы 1 можно получить

Т, ( а, т-Н ) « ( 2 + ( т 4 1+ а(аи1а )2т1 ' )

10 ^

Отсюда, учитывая теорему 2 и то, что а является фиксированным, можно заключить:

lo¿j2(ra+1)+C1slcg2L(a,m+i)s02(m+l)log2(m+1),

где 0^(1=1,2)- подходящие полояаггелыше константы, т.е. в ограничениях снизу и сверху величины log0L(a,m+1) фигурирует функция log2(ni+1) 0 разными сомножителями: 1 и 0?(т+1).

Итак, что Функция L(a,m)-далеко нелинейная. Это свидетельствует о том, что по разным термам одной и той же длины может Оытъ написано много разных программ, вычисляющих различные функции.

Б третьей главе речь идет о структуре и работе системы автоматического проектирования программ по операторным термам.

Структура системы приведена на рис.1.

Рис. 1. Структура САГШОТ

Учитывая, что число аргументов функций, которые использует САГШОТ не должно превышать 99, для вычисления значений исходных функций и реализации операторов выбраны следующие алгоритмы. 1.Значение функции о(х) всегда равно нулю. 2.Значение функции в(х) всегда равно увеличенному на единицу значению аргумента функции. -¡-г

3.Значение функции всегда равно ш-ой координате из вектора аргументов длины п, 1«г\1>99.

4.При определении оператора й были рассмотрены два случая. 4.1.Значения одноместной функции 1 получаются из числа а и двуместной функции Ъ следующим образом:

Г(0)=а, Г(1)=Ь(0,а), х(г)»н(1.г(1)>.

I(m+l)=h(m,f(m)). 4.2.Значения (п+1)-местной функции i получаются из п-меотной функции g и (п+2)-местной функции h следующим образом:

f(x1,...,xn,D=h(x1,...,xn,0,f(x1.....xn>0)),

t(x1.....xn,m+1)=h(x1,...,xn,m,f(x1,...,xn,m)), где 1sns97.

5.Для оператора M последовательно находим значения f (х.,,.. -,xn_î,y) для у=0,1,2,...,32767 ( в программах САППОГ вое переменные -аргументы имеют целочисленный тип ), 1sn«9S. Результат -наименьшее значение а, для которого i(x1,...,xn_1,a)=xn.

Условия, при которых а считается неопределенным:,

а. не определено, 1«ns99;

б. значения I(x1,..;xn_1,y), 1sns99, для у=0,1,...,а-1 определены, но отличны от Xjj, а для у=а значение не определено, as32767;

в. значения r(x1ti,..,хп_1,у), где Isns99, определены для всех у=0,1,...,32767 и отличны от хп.

6.Для оператора Sn+1 сначала вычисляются значения n т-местных функций Х^, 1=1,2 ,...,п; 1 я1^99j 1*ms99. Из етих значений формируется массив из п влеиеитов. Затем, используя значения элементов втого массива в качестве аргументов, находится значение n-местной функции I, которое выдается в качестве результата.

Программы, которые выдает САППОТ по операторному терму, проектируются по следующему алгоритму. Анализируется терм, затем в проектируемую программу копируются соответствующие процедуры только для тех простейших, функций и только для тех функциональных операторов, символы которых встречаются в терме. При етом, если символ какой-либо простейшей функции или какого-либо оператора входят в терм несколько раз, то соответствующая процедура будет входить все равно только один раз.

П;:ое::тиро1!ппно программ путем применения сщюго нп операторов Ц, Я, Sn+1 к программам, выданным САППОТ, происходит по сле-дупи.рму алгоритму. Напрашиваются пути доступа и полные тлена файле.«*, содержащих программы, виданные САППОТ ( один для оператора М, дна - для оператора R, п+1 - для оператора Sn+1 ). Затеи в этих файлах осуществляется поиск необходимых данных -размерности функции и служебной метки, (»формированной на основании терла. После этого для операторов R и Sn+1 идет проверка того, могут л;! функции совместно использоваться виши онерятора-"ели могут, то формируется служебная метка соответствующей функция ( üf - для оператора И, R(í.|,f2) - для оператора R,

SnM(g, Г.,___,í ) - для оператора Sn+1). Далее проектирорвашю

происходит подобно проектированию по терму, с той лишь разницей, что анализируется не терм, а служебная метка. Проектирование, при котором используются как программы, виданные САППОТ, так и програи/л для вычислимых функций, написанные саьгам пользователем, осуществляется аналогично, только для функции из программы, на-соннсЯ пользователем, запрашивается еще и размерность. Программа, написанная пользователем, в процессе проектирования становится процедурой проектируемой программы и должна удовлетворять следуюлт условиям:

1. Значения аргументов должны присвататься целочисленному массиву агпгло сладукшиы сбразсм:

аг-лз{1] - значение 1-го аргумента; агтлз[2] - значение 2-го аргумента;

ni",asín} - значение n-го аргумента. Из прзгру.'ги долгзга сить ясшжчена инициализация массива airas. 2. С'тпение -^унглил долкно присваиваться целочисленной перемен'}. в гге:: г::-."•" ;с,"'гга Сить РЕедопо тхэчкеденяяя переменная о. нсг-'.тг" иг/:: г:'.с? зтченпб 'О', ес.г,н нкхпм спраце-сепо при за; аггумг-птгз, и зпг.чепге ' 11 " "гыньнс.ч случае. . iпг~.лс, перэнзш"1" J^?-"'";" б:;т:> .удален1

т.:-'-.'- rzeveпельгевятелл со¡тргцпдуру па $ym.i9ta, а

"S^cr, zrti ■:>z-ci.'o укг'Эая тот ч:е и&эпсяХяквтср типе, что для Mí>cr-:>r( тт.?.:' в г.лиожгая дарснепЕШ nporpsJ-'.'ii, то п

заголовке этой процедуры или функции идентификатор типа для втого массива должен быть заменен на идентификатор mas. 6. В процессе проектирования из программы пользователя удаляются все операторы writeln, write, readln, read с соответствующими операндами. Поэтому перед тем, как эта программа будет использована САППОТ, надо убедиться, что удаление этих операторов не приведет к зацикливанию программы.

Приводятся блок-схемы подсистем САППОТ.

В четвертой главе говорится об использовании системы. Система может применяться а учебных целях при изучении курсов "Дискретная математика" и "Теория алгоритмов". В частности, проверяется, могут ли обучаемые корректно применять к функциям операторы, представляется возможность проследить пошаговое вычисление Функций и работу операторов. Система может использоваться и в научно-практических исследованиях, обеспечивая нахождение значений вычислимых функций, представленных через терм, и проектирование программ для новых вычислимых функций, используя при етом как терм, так к применяя операторы R, М, Sn+1 к программам, вычисляющим функции.

Речь идет также и о действиях пользователя при работе с САППОТ. Система функционирует под управлением MS-DOS на ПЭВМ типа IBM PC,;XT и AT стандартной конфигурации. Приводятся оценйи

работы САППОТ. Например, проектирование на IBM АТ/386 программы х2

для функции х1 , представленной через терм

R(S2(s,o),'S3(R(o,S3(R(I^,S2(s,l3)),l3tI3))jI3jI3))

длится 4,40 сек.

Программы, спроектированные по терму или посредством ОПера-ni 1

торов М, R, S , использующих программы, выданные системой,' имеют следующие особенности: если терм функции включает некоторые предметные-и функциональные символы более одного разя, то соответствующие им процедуры входят в проектируемую программу все равно только один раз. Поэтому для Функций, термы которых различаются, но составлены из одних и тех же предметных и функциональных символов, объем памяти, занимаемый спроектированной программой, с увеличением размеров терма увеличивается незначительно.

Программы, при проецировании которых, используются программы, написанные пользователем, обладают следующей особенностью: 14

если та или иная программа пользователя указана несколько раз ( для оператора Б,,+' ), то процедура, полученная из втой программы, входит в спроектированную программу такое :ке число раз.

Система САШОТ позволяет быстро и удобно проектировать программы для новых функций по имеющимся программам, используя

Г1+1

операторы И, М, Б . Например, пусть имеются программы, написанные на языке Паскаль для следующих функций:

1^(хгх2); вш(х1,х2)=х1+х2;

Х1

рг(х1,х2)=х1х2; Г1(х1,х2)=х2 '.

Эти программы могут быть написаны как человеком, так и быть спроектированными системой САЛПОГ.

Путем применения оператора минимизации М к программе для функции Г (х^.хр) проектируется программа для функции

Г2(х1,х2)=МГ1(х1,х2)= ✓ х2 . Посредством применения оператора суперпозиции Б3 к соответствующим указанным выше программам для функций проектируются программы для следующих-функций:

2

Гэ(х1,х2)^83(Г1(х1,х2),рг(х1,х2),Г1(х1,х2))=х2х1х2 ;

Х4(х1,х2)=83(Г1(хгх2),Г1(х1,х2),рг(х1,х2))=(х1х2)х2 1;

3 'г,

Г5(хгх2)=8 (Г1(х1,х2),12(х1,х2),рг(х1,х2))=(х1х2) ;

т ? г

Хб(х1,х2)=3-,(Хг(х1,х2)Д^(х1,х2),рг(х1,х2))= / х,х2 .

Будем говорить, что функция / находится на расстоянии 1с

(кгО) от функций Т.если функция Г может быть получена

п+1

из функций Г1РГ2,..,Г путем применения операторов П, М, Б ровно к раз. В приведенных выие примерах функция ?2(х1,х2) находится на расстоянии 1 от функций ^(х^.хд); а фуннкция Г^*-)»^

на расстоянии 1 от функций г^х^хд), В1м(х1,х2), рг(х1,х2).

1

Пусть при проектировании с помощью операторов И, М, Б используется программа, спроектированая системой СЛППОТ, при проекти-

15

ровагаш штороД пспользогалась программа, кгжлоездхзя чахзпег.с.:. Тогда во вновь проег.тпруемук прогршялу будет сйпзателъко на процедура, полученная из программ«, Нйппоаазой челскг:;;:.;. Что иаосагся процедур дяя upossuii^ix фуякциЯ it опзраropes, г.оюриэ пьодят с прогрызи, иопэдьзуилио операторах: для преек-прегизгл, то во вновь щлекгируемую программу спя будут в ляЯсу опу-гаа шиплиезш только одлн раз, нопавис.аю от того, калоЛ спгрлюр выбран длл проектирования и в скольких програ*".:з1, ¡¡слользуслщ для проектирования, они вегрзчгштся.

Пусть для ирсиктирозагая с помойся оп.^ратороз П, S11''1 пеяользумия ля boos, втадлл прогрокз, нашшиннн» чс.г.с2£гкс.,л. То^дз, если шшмгенишо человеком iiporpcteSJ для ?ункц-.;й, к г.гло-puy применяэтея эти оператора, будут компактни, то прэекотрусняя о пемочьм систем»/ САППОТ программа таз~:;е будет пс:^1шг;«юл. С. ростом числа аргумеззтов у функций и с уволлчетки ул рассю-лгли от походных фувкцйЛ число получаемых из них носродгтБо:.« i:j пни операторов Е.', R, ППт 1 пааыг. фушдай резко т-.озрзста??. того, что прл ирзоктировз:з;п: используется обпузй алгоритм п>зэг-•гкрованяя програ:.'.'.*, длл ккгдоС вычислимой функции, прогр спрозктировазкшо системой САППОТ, будут, возноадэ, содержать больше коя'лзотво операторов, чем нрогракш, которлэ псплсал бы для ОООТЕ55 ствола;* фузисцлЧ сам программист. К&пр:"-/эр, для Г-

f-упкции программа на основе метода Ньютона на языке toprpuii оодергшт 10 операторов в теле прографи ( Любимск;:?. 3.3. i: др. Программирование., - M.:Itayi:a, 1920. - С.442 ), а при нрозг.тг.р-о-вгшзш по торлу с помочь» спотош - 59 операторов. Пусть хазпгся проград.-л ко лзипо Паскаль для функций

g1(x)=x5-27x3+69x-95;

С2 (х) =;:"-0 л5-2 л4 - Юх2+9. Прпмэнозшем сперзторз Г.! и каадаЯ из етих прогрг.?.':.: прС'Эз^лрудюя программы для фунзщий I's^x) и !i£2(x> соответэтвошзо. гкёчеш?

функции i'g^tx) в точке 0, т.е. Llg^O), есть костр;:1;з-

тельноа решение уравнения х^-27х3+б9х-95=0. Аналогично знзчэззиэ функции Mg2(x) в точке 0 есть назменькее неотрицательное решение уравнения х^-8х5-2х^-10хг+9=0. Если программы длл функций Kg^(x) и Mg2(x) проектируется по терму, то для этого необходимо по 85 операторов в каядом из случаев. Если :::е программа для 16

функции g.,(x) (g2(x)) написана человеком, то спроектированная

программа для функции Mg1(х) (Mg2(x)) помимо процедуры, полученной из программы для функции g1(х) (g2(x)), будет иметь процедуру для оператора М, которая содержит 14 операторов. В то же время программа на языке бейсик для вычисления корней полинома с действительными коэффициентами anxn+ .+а.|Х+а0 обоб-

щенным методом Ньютона содержит 53 оператора в теле программы ( Дьяконов В.П. Справочник по алгоритмам и программам на языке бейсик для персональных ЭВМ. - М.:Наука, 1989. - С.93-94 ). Следует подчеркнуть еще раз, что важным здесь является то, что эти программы ЭВМ "пишет" сама. Одним из вариантов практического использования системы может быть также использование "решетки" функций. "Решетка" строится из базовых функций, заданных человеком, посредством применения операторов.

В приложениях приведены примеры протоколов работы САППОТ, тексты некоторых программ, спроектированных системой.

ЗАКЛЮЧЕНИЕ

Основные результаты диссертации заключаются з следующем. 1. Создана модель автоматического проектирования программ по операторным термам, которая состоит в следующем.

a.По терму вычисляет значение функции при указанных значениях переменных.

b.По терму проектирует программу для функции на языке Паскаль, используя дедуктивнмЧ подход к автоматическому синтезу программ.

0. Сиитимэ также предоставляет Возможность рмботы с операторами М, в, sn+1, используя при этом объектно-ориентированный подход.

Если выбран оператор М, то запросив программу дли Функции

1, осуществляется проектирование программы на языке Паскаль для функции Vf.

Если выбран оператор R, то запросив программы для функций f1 и f2 осуществляется проектирование программы на языке Паскаль для Функции R(f1,i2), при условии,что функции Г1 и f0 могут быть совместно использованы оператором R.

Если выбран оператор Sn+\ то запросив путь доступа и полные п+1 программ функций g,i1,...,f , осуществляется проектирование программы на языке Паскаль для функции Sn+1( g,tу ...,fn ), при • усломш, что функции g.i^,... ,fn могут быть совместно исполь-

П4-1

soRnmj опоритором S , r«

Модель использует при проектировании с помощью операторов Н,Н,БП+1 как программы, спроектированные СЛШОТ, так и программы, написанные пользователем на.языке Паскаль.

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

3. На основе модели разработана структура и осуществлена программная реализация системы автоматического проектирования программ по операторным термам следующим образом.

a. Подсистема 1огтор обеспечивает по терму вычисление значения функции и проектирование программ.

b. Подсистема ЪегтозЬ применяет операторы к программам, спроектированным системой САППОТ, для проектирования новых программ для соответствующих функций.

о. Подсистема 1егтозЫ применяет операторы к программам, выданным как самой системой САППОТ, так и написанным для вычислимой функции человеком, для проектирования новых программ для соответствующих функций.

Материалы диссертации опубликованы в следующих работах

1-Мощенский В. А., Чичиков А. В. Об автоматическом проектировании программ для вычислимых функций // Экстремальные задачи оптимального планирования и проектирования. Сборник научных трудов. - Минск: ИТК АН РБ, 1991 - С.102 - 104.

2.Чичиков А. В> Автоматическое проектирование программ для вычислимых функций // Межреспубликанская научно-практическая конференция творческой молодели "Актуальные проблемы информатики: математическое, программное и информационное обеспечение": Тез. докл.: Минск - 1992. - С.17В - 179.

Э.Мощенокий В.А., Чичиков А.В. Использование ЭВМ в написании программ // 1-ая Белорусская конференция "Новые информационные технологии обучения": Тез. докл.: Минск - 1992. - С.215 - 216.