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

рг6 од

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

I "

Корольков Юрий Дмитриевич

Математическое моделирование

алгебраических и аналитических преобразований на ветвящихся структурах

05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Иркутск -1997

Рабата выполнена в Иркутском государственном университете.

Официальные оппоненты: доктор физико-матеттических наук,

профессор Г. П. Егорычев,

Ведущая организация: Уральский государственный университет.

Защита состоится 20 июня 199Г7г. ь 4Н.00 ЧйСОЬ на заседании диссертационного совета Д 063.32.04 в Иркутском государственном университете по адресу: 664003, г. Иркутск, 6. Гагарина, 20.

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (б. Гагарина, 24).

Автореферат разослан " мая 1997г.' Ученый секретарь диссертационного

доктор физико-математических наук В. И. Мартьянов

доктор физико-матештических наук Д. И. Свмрвденко.

совета, доцент

Н. Б. Бельтюков

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

Успехи теории алгоритмов, математической кибернетики и теоретического программирования не в последнюю очередь связаны с алгебро-логическим подходом. Здесь мсжно отметить работы А. Н. Колмогорова и В. А. Успенского по вычислимые функциям и исчислениям; А. И. Мальцева, Ю. Л. Ершова и С. С. Гончарова " по теории нумераций и конструктивным моделям: А. А. Ляпунова, С. В. Яблонского и В. М. Глушкова по математической кибернетике; Ю. И. Янова и А. П. Ершова по схемам программ; О. Б. Лупанова по синтезу и сложности управляющих систем; А. Н. Тихонова по регулярным моделям и многие другие у нас и за рубежом.

В последние годы ведутся многочисленные исследования по изучению алгоритмов над дискретными моделями, алгоритмических свойств моделей. К этому направлению также относятся работы по базам данных, логическому программированию, экспертным системам.

Локальные методы в математике используются практически во всех ее разделах. Там, где возможно применение локальных методов, они обычно приводят к новым и эффективным решениям. В алгебре особенно известны локальные теоремы А. И. Мальцева.

На важность связей между непрерывными и дискретными моделями неоднократно указывал Н. Н. Яненко.

Вьщелим 1ри типа дискретных моделей.

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

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

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

Первой методической характеристикой работы является систематическое выявление и использование ветвящихся структур.

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

Третья методическая особенность работы - использование конструктивных обьектов и алгоритмических методов при моделировании для автоматизированного использования результатов.

Диссертация имеет прикладной характер.

Целью работа является разработка и применение дискретных моделей и локальных методов на ветвящихся структурах с алгебро-логическим обоснованием.

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

С их применением получены новые результаты:

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

- на основе этих результатов предложен новый модельный подход к ранению задачи идентификации геологических разрезов на деревьях уравнений в свободных полугруппах (совместно с Э. Г. Бернгардтом);

- разработан метод рекурсивных пределов конечных частичных гомеоморфизмов в общей теории вычислимости. Базисы бэровской

топологии семейств скЗцерекурсивных функций являются деревьями по отношению включения, как правило, неизоморфными. Метод заключается в том, что, ослабляя стандартную топологию, можно добиться изоморфизма деревьев базисов новых топологий. Отсюда следует рекурсивный гомеоморфизм самих семейств. Этим методом получены новые результаты . по проблеме Ю. Л. Ершова об изоморфизме полурэшегок вычислишх нумераций для семейств общерекурсивных функций;

- разработан метод нерекурсивных: пределов частичных изоморфизмов палурешеток вычислимых нумераций на базе изоморфных нумераций. Получена классификация типоз изоморфизма полурешеток вычислимых нумераций с наименьшим элементом семейств общерекурсивных функций с конечным числом предельных точек (последний результат невозможно получить рекурсивный пределом, так что этот метод не сводится к предыдущему);

- сочетанием методов конечных проективных морфизмов, статистических и численных предложен новый подход к решению задачи аппроксимации функций, измеренных в произвольном конечном множестве точек и представленных сходящимся радом заданных вычислимых функций. Этот подход был успешно использован для решения задачи выбора оптимального епегара гармоник в сферическом гармоническом анализе, что нашло применение в модели переменного геомагнитного поля для расчета ионосферных токов, индуцирующих вариации поля. Практическая важность задачи и попытки с отрицательным результатом применения известных методов потребовали разработки этого математического аппарата и его программного обеспечения (совместно с А. Д. Базаржаповым);

- разработаны обоснование и методика использования локальных аналитических преобразований. На основе выделенных

преобразований и систешттаческого их применения была разработана и внедрена система аналитических преобразований. Расширенная численными мзтодами, она нашла применение при решении модельных и технологических задач в ЦНИИ комплексной автоматизации (г. Москва) (совместно с В. Н. Хомичем):

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

- на основе разработанных теоретических положений предложены новью модельные подходы к проблеме качества программных средств с целью сертификации и управления качеством на этапах жизненного никла программных средств. Разработана схема построения иерархических моделей качества. На ее базе разработана и внедрена в НИИ высшей школы (г. Москва) учениками автора автоматизированная методика оценки качества компьютерных средств обучения;

- разработана методика моделирования иерархических баз данных инфориационно-расчетньк систем на этапе проектирования специальными деревьями (совместно с В. И. Болдоновым);

- на основе предыдущих разработок проведено моделирование внешних спецификаций программ формулами алгебры логики для автоматизированного построения.некоторых тестов (совместно с Г. С. Курганской и В. И. Курганским).

Все основные результаты диссертации, а также часть методов их доказательства являются новыми.

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

задачах. Ряд таких задач рассмотрен в диссертации. Разработки, предложенные в работе, использовались в ходе выполнения научно-исследовательских работ в Иркутском госуниверситете. Материалы диссертации используются при чтении специальных курсов на математическом факультете ИГУ.

Математические модели', вычислительные методы и программное обеспечение для решения задачи выбора оптимального спектра в сферическом гармоническом анализе внедрены в Институте солнечно-земной физики 00 РАН и используются при моделировании переменного геомагнитного поля. Повыиена точность расчетов, что позволило впервые приступить к расчетам новых типов вариаций поля, выполнять ежедневные расчеты ионосферных токов, ответственных за вариации геомагнитного поля. Новые модели переменного геомагнитного поля ИСЗФ СО РАН получили определенное международное признание.

Созданная на основе локальных аналитических преобразований и алгоритмов численных методов система САТУШ внедрена в ЦНИИ комплексной автоматизации (г. Москва) и используется для построения, тестирования и исследования моделей, выполнения расчетов динамических характеристик объектов управления с распределенными параметрами, в частности, теплообменников, котлоагрегатов и ядерных реакторов. Пакет обеспечивает сокращение трудозатрат цри выполнении исследований, позволяет увеличивать размерность и точность моделей. Межведомственной комиссией проведены испытания пакета, который рекомендован для распространения через Отраслевой фонд алгоритмов и щхярамм.

Результаты диссертационной работы по номенклатурам показателей качества программных средств, принципам построения регионального ФАЛ, математическим моделям технологических

процессов на этапах жизненного цикла ПС, методов построения математических моделей качества ПС внедрены в СНПО Алгоритм (г.Москва) и использовались в работах по Государственной целевой научно-технической программе повышения качества ПС, в работе государственных и региональных ФАЛ и в работах по сертификации программных продуктов.

Полученные результаты нашли применение при моделировании и создании информационно-расчетных систем и решения практических задач большой размерности локальными методами в Центральном вычислительном центре Ткла Вооруженных Сил и используются в Центральном вещевом управлении Министерства обороны РФ.

Результаты внедрения подтверждены актами и справками о внедрении Института солнечно-земной физики СО РАН (г. Иркутск), ЦНИИ комплексной автоматизации (г. Москва) , СНПО " Алгоритм" (г. Москва), Штаба Тыла Вооруженных Сил РФ (г. Москва), НИИ высшей школы (г. Москва).

Результаты диссертации докладывались на ряде международных и всесоюзных конференций и семинаров в Алма-Ате, Барнауле, Владивостоке, Гомеле, Екатеринбурге (УрГУ, ИМИ УО РАН), Ереване, Иркутске (ИГУ, ИГНИ, ИрЕЦ СО РАН), Караганде, Киеве (КГУ, ИК УАН), Кишиневе, Красноярске, Минске, Москве (МГУ, ВЦ РАН, Алгоритм, ЦНШКА), Н. Новгороде, Новосибирске (НГУ, ГОШ, ИМ СО РАН, ВЦ 00 РАН), С. -Петербурге (ЛЖ РАН), Ташкенте, Тбилиси, Твери, Улан-Баторе, Ярославле, в том числе в виде пленарных докладов.

В 1997 г. диссертационная работа рассматривалась в Институте математики и механики УВД РАН и УрГУ (г. Екатеринбург), НГУ (г. Новосибирск), на городских семинарах по дискретной математике в Красноярском государственном техническом

университете, по алгебре и математической логике в Красноярском госуниверсигете (г. Красноярск), на объединенном семинаре математического факультета ИГУ (г. Иркутск).

Основные результаты диссертации опубликованы в С1 - 321.

Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 187 наименований. Объем работы 216 страниц.

Первая глава посвящена развитию и применению метода частичных конечных изоморфизмов Ю. Л. Ершова для постановки и ранения конкретных задач на алгебраических моделях с выявлением и использованием ветвящихся структур. Идея использования конечных изоморфизмов для получения "бесконечных" результатов неоднократно используется автором в диссертации.

В §1.1 ([2, 32]) некоторой факторизацией введенных Ю. Л. Ершовым' 3 множеств частичных изоморфизмов с продолжениями заданы конечные деревья Рп СК^ для определения истинности формул. Наряду с подходами Ю. Л. Ершова или А. Т. Нургазина, на этом пути тоже получены критерии элементарной эквивалентности и разрешимости, поскольку наши подходы основывается в конечном итоге на разработанном А. Д. Таймановым методе перекидки.

Под алгебраической системой как обычно понимаем множество элементов с заданными на нем операциями и отношениями и обозначаем как и = <А, а>, где А - множество, а с - сигнатура. Теорией первого порядка ТЬ СЮ алгебраической системы И называется множество всех замкнутых формул узкого исчисления предикатов сигнатуры и, истинных на и.

Пусть ни®- алгебраические системы одной сигнатуры.

13 Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. М.: Наука, 1®. 416 с.

ТЕОРЕМА 1.1. ТЪСЮ = ПпС®} (или И элементарно эквивалентна тогда и только тогда, когда для любого п е ш помеченные деревья К^Ю и ^СЖЭ изоморфны.

ТЕОРЕМА 1.2. ТЪСЮ разрешима тогда и только тогда, когда существует эффективная процедура построения по любому п е и дерева ^СЮ.

ТЕОРЕМА 1.3. Если и - подсистема то система м является элементарной подсистемой системы ® тогда и только тогда, когда каждое дерево РПСЮ является деревом РПС®3.

ПРЕДЛОЖЕНИЕ 3. Если и - подсистема то всякое Рп-дерево из и можно пополнить до Рп~дерева в

ПРЕДЛОЖЕНИЕ 6. Для любого эпиморфизма а: V -> % и любого п существуют такие конечные полные деревья ЬпОО и М^®}, что аЬ^СЮ = 1уЖ).

ПРЕДЛОЖЕНИЕ 7. Произведение Рп~деревьев систем и и ¡в дает полное дерево прямого произведения и х ¡в.

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

Рассмотрим отдельно случай, когда изучается не вся теория ТЪСЮ, а ее ограничение -замкнутыми формулами без кванторов всеобщности (3 - теория модели и).

ОПРЕДЕЛЕНИЕ. Назовем п - универсальным словом модели и = (А, о) такую последовательность а^, с^, ... , а^ элементов из А, что в нее изоморфно вкладывается любая последовательность из п элементов множества А.

Очевидно, что универсальнш слова всегда существуют и что разрешимость В - теории модели и эквивалентна существованию алгоритма, дающего по каждому neu некоторое п - универсальное слово. В то же время наименьшая длина п - универсальных слов как функция от п может служить определением сложности разрешимой 3 - теории.

Сформулируем постановку задачи. Даны помеченные линейные порядки. Требуется найти минимальное универсальное слово, то есть такой помеченный линейный порядок Р минимальной мощности, в который данные помеченные порядки изоморфно вкладываются.

Бели отождествлять помеченные линейные порядки со словами в алфавите S, составленными из меток на элементах, то можно получить уравнения в свободной полугруппе со свободными образующими из S для поиска Р :

Р = Xq н XJ. .. Qk Xk = У0 bjL у±. . . b^ ym =... , CID

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

В геологии известна задача идентификации С сопоставления} геологических разрезав. Разрез рассматривается как последовательность типов однородности пород Сосадочных, геохимических и т. п.}, а задача идентификации разрезав заключается в таком сопоставлении однотипных элементов разных разрезов, которое соответствует реальному прохождению геологических тел на данной территории2 ^.

Важность данной задачи обусловлена тем, что базой теоретических построений в геологии является физическое просгран-азСатт Ю. С. Стратиграфическая корреляция. М.: Наука, 1983. 277 с.

ство геологических тел. Его структура и определяется результатом решения задачи идентификации.

Предложен новый модельный подход к решению этой задачи, полученный автором совместно с Э. Г. Бернгардтом 12., 17].

Разрезы являются разномесгныии реализациями единого процесса осадконакопления Р. Обычно считают, что осадконакоп-ление носило устойчивый характер. Это предположение позволяет сформулировать задачу идентификации для комплекса разрезов ■СА^> как задачу выделения систем слоев (модельных аналогов геологических пластов) с максимальным числом слоев, что равносильно построению по разрезам <А^У процесса Р как минимального универсального слова для <А^>.

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

ТЕОРЕМА 1.4. Решение 13 уравнения С13 с минимальной длиной Рр порождает корректную систему слоев Тр с максимальным

значением суммы £ С1-13 М^, где обозначает число слоев

1=г

мощности 1 в системе Т^.

Задача систематического изучения вычислимых нумераций была поставлена А. Н. Колмогоровым в 50-х годах. Следующий шаг был сделан трудами А. И. Мальцева в 6СНх годах. Из зарубежных авторов следует отметить Э. Поста, С. Клини, X. Райса, А. Лахлана.

Начало новому этапу положили статьи и книги Ю. Л. Ершова3^ , интересные результаты получили И. А. Лавров, С. С. Марченков,' С.Д.Денисов, С.С.Гончаров, В.Л.Селиванов, Л. Хэй. Как отметил Ю. Л. Ершов, результаты теории нумераций оказались важными для прояснения трудностей современного программирования.

з;> Ершов Ю. Л. Теория нумераций. М. : Наука, 1977. 416 с.

Изучение полурешеток вычислимых нумераций семейств общерекурсивных функций было начато Ю. Л. Ершовый, он же обратил внимание на важную роль предельных точек в этих вопросах.

Нумерация а: N —> и семейства рекурсивно перечислимых множеств (функций) называется вычислимой, если цредикат РСх, уЭ » х е ау СРСх, у, 2} » х = ауСгЭ) ренурсивно перечислим. Нумерация а: N —♦ и семейства конечных множеств называется сильно вычислимой, если функция ГС 13 = "число элементов множества ал." общерекурсивна.

Нумерация а сводится к нумерации р, а < р, если существует такая общерекурсивная функция Г, что а = рГ.

Совокупность всех вычислимых нумераций семейства и обозначаем Н°(И), а полурешетку (классов эквивалентности) вычислимых нумераций и с отношением сводимости через Ь°( и).

На вычислимую нумерацию можно смотреть как на рекурсивный язык програмглирования. Тогда сводимость языков означает существование эффективного транслятора, а классы эквивалентности полурешетки Ь°(И) представляют сложности языков. Главная вычислимая нумерация выделяет универсальный язык.

Базис открытых множеств для бэровской топологии на классе всех (рекурсивно перечислимых) множеств состоит из семейств -СА I £ А), N. где Б^ есть 1-ое конечное множество.

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

В §1.3 получены новые результаты в рамках поставленной Ю. Л. Ершовым проблемы об изоморфизме полурешеток вычислимых нумераций. В п. 1.3.1 доказано, в частности, что любые два

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

В п. 1.3.2. дана характеризация полурсшетак вычислимых нумераций семейств с конечным числом предельных точек (полу-решегок с наименьшим элементом). Здесь изоморфизм полурешеток получается как нерекурсивный предел частичных изоморфизмов. Существование дискретных не эффективно дискретных вычислимых семейств общерекурсивных Функций свидетельствует о невозможности получения этого изоморфизма через рекурсивный предел как в предыдущем разделе.

Результаты gl. 3 опубликованы в [1, 6, 7, 8L

В §1.4 разработаны новые подходы к решению задачи оптимального выбора спектра в сферическом гармоническом анализе через решение конечномерной дискретной задачи сочетанием методов конечных проективных морфизмов, статистических и численных. Получено приложение к задаче солнечно-земной физики о вычислении ионосферных токов по измеримым на наземных магнитометрических станциях вариациям геомагнитного поля.

Рассмотрим часто встречающуюся ситуацию, приводящую к появлению систем линейных алгебраических уравнений. Уравнение FCxD = S dfc G^CxD, (23

где F(x3 - измеряемая функция, G^Cx)- некоторые стандартные функции и d^ - искомые коэффициента, сводится к системе уравнений в точках измерения х^ функции F

fcxjd = £ с^ g^cxp, isn. с 33

Встает вопрос о выборе количества R и спектре функций G^ для сведения к системе линейных алгебраических уравнений:

R

FCx,3 = £ d, G, Cx,3, i s N, R i N. С 43

1 1=1 K1 4L x

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

Предлагается следующий подход к решению задачи С 23 - С 43. Аппроксимируем F таким конечным спектром функций G^, чтобы достаточно хорошо были выявлены локальные экстремумы F. При этом, как выяснилось, важную роль играет ортогональность функций G^ в функциональном пространстве.

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

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

Метод проверялся на модельных примерах, на спутниковых и ракетных данных, но результирующий вывод о пригодности метода и его преимуществах был сделан лишь после его апробации применительно к задачам, где известные методы не дали хороших результатов. Последнее относится црежде всего к анализу полей магнитных возмущений, вариаций типа Sfj и б. Расчеты ИСЗФ 00 РАН показали, что в большинстве названных случаев единственно приемлемым оказался новый метод. Полученные результаты вместе с соответствующим программным

обеспечением использованы в [23, 31], опубликованы в [2, 4, 5] (совместно с А. Д. Базаржаповым).

Вторая глава посвящена исследованиям и применению локальных аналитических и арифметических преобразований.

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

Из-за этих отличий лучше говорить о системах аналитических преобразований, в состав которых включаем кроме класса функций входной язык, внутреннее представление данных, класс задач (набор макрокоманд системы), алгоритмы решения задач.

В §2.1 введены локальные аналитичесие преобразования как алгоритмический язык промежуточного уровня, относящийся к эквивалентным преобразованиям тернов. В нем имеется важное расширение языка символьных преобразований: допускаются косвенные ссылки на подтермы. Локальность заключается в том, что разрешаются ссылки только на "близкие" подтермы.

Предложена реализация языка локальных аналитических преобразований на абстрактной машине, доказаны утверждения о свойствах введенных понятий, которые можно рассматривать как обоснования для практического применения. Эти. результаты из §2.1 опубликованы в 11, 13, 16, 22].

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

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

Следующим важным моментом при разработке систем является обеспечение всюду определенности вычислений. Предложена абстрактная система программирования D с этим свойством. Следует понимать нащу систему в смысле В. М. Глушкова как некоторое исчисление текстов программ.

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

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

ТЕОРЕМА 2.1. Примитивно рекурсивные функции D-вычислтиы.

ТЕОРЕМА 2.2. Существует D-программа, которая по операторному терму формирует текст D-программы, вычисляющей функцию, являющуюся значением этого терла.

Далее в §2.1 приведено краткое описание системы аналитических преобразований САТУРН ЕС [2, 12-143. Разработанные модели и метода с .программным обеспечением использованы в [24-27, 29]. Эти результаты получены совместно с В. Н. Хомичем.

Функции системы не ограничены аналитическими преобразованиями. На практике нередко аналитические преобразования реализуют подштовигельную часть обработки моделей с последующим проведением численных расчетов. Наша система плани-

ровалась как автоматизированное рабочее место инженера-технолога теплообменников, котлоахрегатов и ядерных реакторов. Кроме того, сна включена в более крупную систему. Систола САТУРН ЕС содержит свыие восьмидесяти подпрограмм общим обьемом свыие 10 тысяч операторов процедурных языков.

В §2.2 введены рекурсивные операторы в качестве локальных арифметических преобразований. Получено обоснование локальных методов, использованных для доказательств изоморфизма полу-решегок вычислимых нумераций и харакггеризации индексных множеств семейств схЗцерекурсивных функций.

ОПРЕДЕЛЕНИЕ. Отображение ф: <и —> в семейств рекурсивно перечислимых множеств называется рекурсивным оператором, если существуют такие сильно вычислимые нумерации а: N —► , р: N —» С>2 некоторых семейств конечных множеств что

при любом А е и выполняется ФА = и <р1 | а1 2 А> е ¡8.

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

ТЕОРЕМА 2.4. Пусть Ни®- вычислимые семейства, и существует рекурсивный биективный оператор ш: М°(И) —> Н°(В) такой, что для любых е^, е^ е Н°(Ш) и общерекурсивной функции Г равенство е^ = е-р Г выполняется тогда и только тогда, когда ш(е^) = э(б2)Г. При этих условиях существует рекурсивный обратимый оператор ф: и —> эз.

Результаты параграфа 2.2 отубликованы в [ 1, 8, 9].

В §2.3. с использованием рекурсивных операторов получены результаты о харакгеризации индексных множеств семейств общерекурсивных функций, опубликованные в [1, 11, 19, 20].

Индексное множество вычислимого семейства А определяется

как я (А) для семейств функций или как (А) для семейств множеств, где ж и % есть главные вычислимые нумерации соответственно семейства всех одноместных частично-рекурсивных функций R и семейства всех рекурсивно перечислимых множеств П.

Оценка сложности индексных множеств проведена в арифметической иерархии Клини-Мостовского. Принадлежность множества к классу СппЭ этой иерархии означает возможность выделения его формулой с п переменами кванторов над рекурсивны,! предикатом, причем первый квантор есть 3 CVO. Класс дп определяется как 2п л пл. Отношение частичного порядка задается 1-сводимостью множеств.

Обозначим через ^ индексное множество одноэлементного семейства, а через М, - вычислимого семейства общерекурсивных функций ( о. р. ф. ) без изолированных точек.

ТЕОРЕМА 2. 7. Пусть даны вычислимые семейства о. р. ф.

A, В, С, где семейство А одноэлементно, семейство В произвольно, а семейство С содержит вычислимое подсемейство без изолированных точек. Тогда аГ*(А) аГ*(В) <f аГ'(С).

ТЕОРША 2.8. Множество является пг - полным, множество Mf лежит в классе д3 и к нему сводятся п2 - и ï2 - полные множества. Таким образом, неравенство Mf - строгое.

ТЕЮРЕМА 2.9. Существует вычислимое дискретное семейство о. р. ф. с индексным множеством типа М^.

В п. 2.4. с помощью рекурсивных операторов исследуются вполне перечислимые подсемейства для вычислимых семейств рекурсивно перечислимых множеств и общерекурсивных функций. Их в вычислимом случае начали изучать X. Райе, А.И.Мальцев,

B. А. Успенский, Ю. Л. Ершов, И. А. Лавров, а в случае нумерованных топологических пространств - Е. Ю. Ногина. Но в работах этих

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

Если <й , а>— нумерованное множество, то подмножество вед

-1

называют вполне перечислимым, если индексное множество а (®) рекурсивно перечислимо. Это понятие существенно зависит от заданной нумерации а. Для вычислимого семейства а рекурсивно перечислимых множеств Ю.Л.Ершов предложил называть вполне перечислимыми такие подсемейства в е д, что а (в) рекурсивно перечислимо при любой вычислимой нумерации а е Н°( а ). Если семейство А обладает главной вычислимой нумерацией а, то такое определение вполне перечислимости совпадает с определением относительна а. В то же время определение Ю. Д. Ершова годится для семейств, не имеющих главной вычислимой нумерации, а среди вычислимых нумераций таких семейств трудно разумным образом выделить какую-нибудь единственную.

Вполне перечислимые подсемейства являются наиболее естественный распространением понятия рекурсивно перечислимого подмножества на класс вычислимых семейств. Первая половина параграфа посвящена таким семействам, у которых система вполне перечислимых подсемейств совпадает с системой эффективно открытых подсемейств (такие семейства мы назвали райсовыми. Например, семейства всех рекурсивно перечислимых множеств или всех одноместных частично-рекурсивных Функций райсовы). Теорема 2.11 дает достаточные для райсовости условия на языке введенных рекурсивных э-операторов, что позволило единообразно получить ряд известных и новых результатов о райсовости

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

Из других результатов параграфа 2.4 отметим следующие.

ПРЕДЛОЖЕНИЕ 1. а) Вполне перечислимое подсемейство рай-сова семейства райсово.

б) Вполне перечислимое подсемейство главно нумерованного семейства обладает главной вычислимой нумерацией.

ПРЩЦЮЖЕНИЕ 3. Если вычислимое семейство Д содержит сильно вычислимое семейство конечных множеств г, удовлетворяющего условию *), то л - райсово.

* ) Для всякого множества А <= л и любого его конечного подмножества М £ А найдется Е е г такое, что М £ Г £ А.

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

ТЕОРЕМА 2.11. Если д - райсово семейство и Ф - б-опера-тор, то семейство ФСДЭ - райсово.

ТЕОРЕМА 2.12. Если л - вычислимое семзйсгво общерекур-сивнык функций без изолированных точек, а в £ д - вполне перечислимое подсемейство семейства а , то в также не содержит изолированных точек.

Результаты параграфа 2.4 оцубликованы в [ 1, 8, 9].

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

программных средств с целью их сертификации.

Efe основе разработанных теоретических положений глав 1 и 2 предложены новые модельные подходы к проблеме качества программных средств на этапах их жизненного цикла.

В параграфе 3.1 предложен подход к определению и выбору системы показателей качества программных средств для построения иерархических моделей качества программных средств.

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

Но произведение деревьев уже необязательно дерево. Если на произведение деревьев смотреть как на диаграмму, то следует потребовать дополнительно наличия свойства коммутативности этой диаграммы. Свойство коммутативности диаграмм использовано далее в §3.2.

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

Результаты §3.1 опубликованы в [3, 10, 211 и использованы в С28, 30, 323.

Методика получения сценок качества на древовидных структурах использовалась также в других НИР.

В параграфе 3.2 построена алгебро-логическая модель внешних спецификаций программ для построения тестов. На

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

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

Предлагаемая здесь более общая модель программной единицы и ее внешних спецификаций в виде функции трехзначной логики позволила не только получить новые интерпретации и алгоритмы решения задачи построения тестов, но и формально поставить, а также ранить новую задачу анализа внешних спецификаций. Эти результаты были получены в совместной работе [ 18] с Г. С. Курганской и В. И. Курганским, ( см. также [ 3] ).

' Программная единица рассматривается как управляющая система. Носители х1.....хг - ее входные полюса, а уг , . .. , ys -

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

Задача тестирования в рамках классификации основных задач кибернетики, предложенной А.А.Ляпуновым и С.В.Яблонским4"1, рассматривается как задача выявления функции управляющей системы. Исходными данными для ранения этой задачи служат внешние спецификации, рассматриваемые как результат ранения задачи выявления потоков внешней информации.

4уЛяпунов A.A. , Яблонский C.B. Теоретические проблемы кибернетики// Проблемы кибернетики. 1963. Вып. 9. С. 5-22.

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

Обозначим Р: 11х -» и Б : Ц, Ку отображения 11х на и иу на Иу, полученные с помсщыо предикатов Р, , ... , Рп и

условий Б,.....соответственно, а Г : ^ - цро-

извольное отображение на .

Обозначим через Б СЕ, Р, Б, БЭ диаграмму отображений:

и —Е—» Ц

у

Р

Полагаем, что при условии ЗСГСцрз = ГСРСихЗЗ коммутативности этой диаграммы отображение Е моделирует отображение Г.

ТЕОРЕМА 3.1. Существует алгоритм построения для коммутативной диаграммы Б СЕ, Р, 8, Ю формулы трехзначной логики оСР/ , .... Рп, ....., представляющей характеристическую функцию графика функции Е.

Тест, диагностирующий ошибки при обработке условий Р£ = ai Са£ е <0, 1>, 1 < гО, обозначим Т,. Состав теста Тг определяется перебором представителей всех классов эквивалентности в их, определенных предикатами Pí , ..., Рп.

УТВЕРЖДЕНИЕ 1. Если диаграмма Э СЕ, Р, 8, Е) коммутативна, тоТ, ^ 0, Т, £ Тг и Тг ^ й : ФСО = 1>.

Цель обработки построенной логической модели программной единицы и ее внешних спецификаций заключается в проверке свойств этой модели и выделении тестов Т, и Т2.

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

Основньми результатами диссертации являются:

1. Предложена методика определения истинности формул на конечных деревьях. Разработанньк методы рекурсивных и нерекурсивных пределов конечных частичных изоморфизмов на деревьях позволили получить новые результаты по проблеме Ю. Л. Ершова об изоморфизма полурешеток вычислимых нумераций.

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

3. На языке локальных аналитических преобразований разработана автоматизированая система, используемая для преобразования математических моделей технологических процессов в ядерной энергетике. Методом локальных арифметических преобразований доказан ряд теорем о характеризации индексных множеств вычислимых семейств общерекурсивных функций в иерархии Клини- Ростовского.

4. На основе предложенных теоретических положений разработана и внедрена автоматизированная методика построения иерархических моделей качества программных средств. Получены модельные подходы к решению некоторых технологических задач на этапах жизненного цикла программных средств, в частности для проектирования иерархических баз данных и построения тестов. Разработки части прикладных задач пп. 2, 3, А подтверждены актами и справками о внедрении.

ав

Автор вьражает благодарность Ю.Л.Ершову, О.Б.Лупанову, С.В.Яблонскому, С.С.Гончарову за плодотворные обсуждения и постоянное внимание к работе автора.

Основные результаты диссертации оцубликованы в следующих работах:

а) монографиях:

1. Корольков Ю. Д. Вычислимте семейства общерекурсивных функций. Иркутск: Изд-во Мркут. ун-та, 1902. 72 с.

2. Корольков Ю. Д. Математические модели и алгоритмы на ветвящихся структурах. Иркутск: Изд-во Иркут. ун-та, 1994. 80с.

3. Корольков Ю. Д. Математические модели качества программных средств. Иркутск: Изд-во Иркут. ун-^га, 1996. 160 с.

б) статьях:

4. Корольков Ю. Д. Метод решения недоопределенных систем линейных алгебраических уравнений// Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1973. Вып. 23. С. 8-10.

3. Базаржапов А.Д. , Корольков Ю. Д. Апостериорный метод выбора спектра гармоник в сферическом гармоническом анализе // Исследования по геомагнетизму, аэрономии и физике Солнца. М.: Наука, 1973. Вып. 33. С. 18-20.

6. Корольков Ю. Д. 0 семействах общерекурсивных функций с конечным, числом предельных точек // Алгебра и логика. 1978. Т. 17. № 2. С. 169-177.

7. Корольков Ю.Д. 0 семействах общерекурсивных функций без изолированных точек // Матам, заметки. 1979. Т. 2В. Шп. 3. С. 747-735.

8. Корольков Ю.Д. 0 вычислимых нумерациях классов рекурсивно перечислимых множеств// Алгоритмические вопросы ал-

гебраических систем иЭЕМ/ Межвуз. сб. Иркутск, 1979. С. 45-52.

9. Корольков Ю. Д. Об эффективных операторах// Прикладная математика и пакеты прикл. программ/ Сб. тр. Иркутск, 1980. С. 48-52.

10. Бодцонав В. И., Корольков Ю. Д. Некоторые моменты разработки интеллектуальных ' инфор-еционно-програмных банков данных //Разработка инфорюдионного обеспечения прогнозов науч. -технич. прогресса. Иркутск, 1990. С. 13-17.

11. Корольков Ю. Д. О сводимости индексных множеств семейств общерекурсивных функций// Сиб. матам, журнал. 1582. 1. С. 190-193.

12. Корольков Ю. Д. , Хомич В. Н. Сатурн ЕЕ: система для аналитических преобразований //Тр. Вс. конф. "Системы для аналитических вычислений в механике". Горький, 1984. С. 33-25.

13. Корольков Ю. Д. , Хомич В. Н. Система аналитических преобразований в ОС ЕЕ// Пакеты прикладных программ. Технология разработки. Новосибирск: Наука, 1984. С. 171-173.

14. Корольков Ю. Д., Хомич В. Н. 0 построении системы аналитических преобразований на ЭВМ// Алгоритмические вопросы алгебраических систем и ЭВМ. Иркутск, 1985. С. 37-42.

13. Корольков Ш. Д. Вычисления на термах// Междуиар. конф. по алгебре/ Прикладная и компьютерная алгебра. Новосибирск, 1989. С. 76-77.

16. Корольков Ю. Д. Технология аналитических вычислений на ЭВМ^/ Алгоритмические и комбинаторные вопросы дискретных систем и ЭВМ/ Межвуз. сб. Иркутск, 1990. С. 67-70.

17. Бернгардг Э. Г. , Корольков Ю. Д. Моделирование задачи идентификации геологических разрезов уравнениями в свободной полугруппе// Алгоритмические и комбинаторные вопросы дискрег-

ных систем и ЭВМ/ Межвуз. сб. Иркутск. 1990. С. 16-36.

18. Корольков Ю. Д., Курганская Г. С. , Курганский В. И. Моделирование внешних спецификаций программ формулами алгебры логики для построения тестов// Интеллектуализация программных средств. Новосибирск: Наука, 1990. С. 76-80.

19. Корольков Ю. Д. Индексные множества семейств оЗщере-курсивных функций// Мездунар. конф. по матем. логике. Новосибирск, 1994. С. 58-39.

20. Корольков Ю. Д. Оценка сложности семейств общерекурсивных функций // Компьютерная логика, алгебра и интеллектное управление. Проблемы анализа устойчивости развития и стратегической стабильности. Иркутск, 1995. Т. 3. С. 191-197.

21. Корольков Ю. Д. Сводная оценка качества компьютерных обучающих систем // Материалы междунар. науч. -методич. конф. "Новые информационные технологии в университетском образовании"/Сб. тр. Новосибирск, 1996. С. 14-15.

22. Корольков Ю. Д. Локальные преобразования дискретных моделей на ветвящихся структурах. Иркутск, 1997. 19 с. (Препринт/Иркут. гос. ун-т).

в) отчетах о НИР:

23. Построение и исследование математических моделей мезосферы и нижней термосферы. Отчет о НИР/ Иркутский гос. ун-т. Руководитель темы Ю. Д. Корольков. № ГР 81008475. Инв. №8382003566. 112 с.

24. Система автоматизированного преобразования математических моделей технологических процессов. Отчет о НИР/ Иркутский гос. ун-т. Руководитель темы Ю. Д. Корольков. № ГР 81093466. Инв. № СеВЭЭСе06С7. 44 с.

23. Система аналитических преобразований уравнений САТУРН

ВС. Отчет о НИР/ Иркутский тсс. ун-т. Руководитель тема Ю. Л- Корольков. № ГР 81053331. Инв. № 02840027193. 242 с.

2В. Система автоштизированного преобразования разностных аналогов моделей технологических процессов. Отчет о НИР/ Иркутский гос. ун-т. Руководитель темы Ю. Д. Корольков. № ГР 01840041499. Инв. № 03Э33013335. 76 с.

27. Развитие системы преобразования моделей ТОУ. Отчет о НИР/ Иркут. гос. ун-т. Руководитель темы Ю. Д. Корольков. № ГР 01860103906. Инв. № 028700С6813. 88 с.

28. Моделирование сисюлы создания и использования программных средств в Восточно-Сибирском регионе. Отчет о НИР/ Иркутский гос. ун-т. Руководитель темы Ю. Д. Корольков. № ГР 01860061355. Инв. № 02870002812. 96 с.

23. Опытная эксплуатация и развитие системы преобразований моделей ТОУ. Отчет о НИР/ Иркут. гос. ун-т. Руководитель темы Ю. Д. Корольков. № ГР 01860103906. Инв. W СЕ380033В54. 63с.

ЗЭ. Разработка информационной модели функционирования системы производства и использования программных средств. Отчет о НИР/ Иркутский гос. ун^г. Руководитель темы Ю. Д. Корольков. IÍIP 01860061263. Инв. № 02880013930. 91с.

31. Моделирование и автоматизация обработки данных обратных задач геофизики. Отчет о НИР/ Иркутский гос. ун-т. Руководитель темы Ю. Д. Корольков. № ГР 01890042228. Инв. № 0239006S535. 136 с.

32. Оценка качества программного обеспечения автоматизированных обучающих систем при их внедрении, эксплуатации и сопровождении. Отчет о НИР/ Иркутский гос. ун-т. Руководитель темы И. Д. Корольков. № ГР 01900063К7. Инв. № 02910029181. 83 с.

¡'1 ч

№

ъу

ц »

puf..-

NJ У

"У,/ - /? ■? Л /-V

Л" -1 у ¿у- г

/

Министерство общего и профессионального образования Российской Федерации

Иркутский государственный университет

КОРОЛЬКОВ Юрий Дмитриевич

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ АЛГЕБРАИЧЕСКИХ И АНАЛИШЧЕСКИХ ПРЕОБРАЗОВАНИИ НА ВЕТВЯЩИХСЯ СТРУКТУРАХ

05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Диссертация на соискание ученой степени доктора физико - математических наук

Иркутск - 1997

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ .............. 3

ГЛАВА 1. АЛГЕБРАИЧЕСКИЕ МОДЕЛИ И МЕТОД

КОНЕЧНЫХ ЧАСТИЧНЫХ ИЗОМОРФИЗМОВ 33

1.1. Методика определения истинности формул

на конечных деревьях ......................33

1.2. Частичные изоморфизмы на линейных порядках 42

1.3. Изоморфизм полурешеток вычислимых нумераций 53

1.4. Применение частичных морфизмов для

некоторых приближенных вычислений .......85

ГЛАВА 2. ЛОКАЛЬНЫЕ АНАЛИПЛЧЕСКИЕ ПРЕОБРАЗОВАНИЯ

И ОЦЕНКИ СЛОЖНОСТИ СИСТЕМ ВЫЧИСЛЕНИИ 107

2.1. Локальные аналитические преобразования и

система аналитических преобразований .... 107 2. 2. Локальные арифметические преобразования . . . 120 2.3. Оценки сложности всюду определенных вычислений

в арифметической иерархии ......... 129

2. 4. Рекурсивно перечислимые индексные множества 141

ГЛАВА 3. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ

КАЧЕСТВА ПРОГРАММНЫХ СРЕДСТВ 152

3.1. Методика моделирования качества на этапах

жизненного цикла программных средств..... 153

3. 2. Моделирование внешних спецификаций программ

функциями алгебры логики для построения тестов 176

ЗАКЛЮЧЕНИЕ ................. 196

СПИСОК ЛИТЕРАТУРЫ ................. 199

ВВЕДЕНИЕ

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

Успехи теории алгоритмов, математической кибернетики и теоретического программирования не в последнюю очередь связаны с алгебро-логическим подходом. Здесь можно отметить работы А. Н. Колмогорова и В. А. Успенского по вычислимым функциям и исчислениям; А.И.Мальцева, Ю.Л.Ершова и С.С.Гончарова по теории нумераций и конструктивным моделям; А.А.Ляпунова, С. В. Яблонского и В. М. Глушкова по математической кибернетике; Ю. И. Янова и А. П. Ершова по схемам программ; О. Б. Лупанова по синтезу и сложности управляющих систем; А.Н.Тихонова по регулярным моделям и многие другие у нас и за рубежом.

В последние годы ведутся исследования по изучению алгоритмов над дискретными моделями, алгоритмических свойств моделей. К этому направлению также относятся работы по базам данных, логическому программированию, экспертным системам.

Локальные методы в математике используются праклжчески во всех ее разделах. Там, где возможно применение локальных методов, они обычно приводят к новым и эффективным решениям. В алгебре особенно известны локальные теоремы А. И. Мальцева.

На важность связей между непрерывными и дискретными моделями неоднократно указывал Н. Н. Яненко.

Вьщелим три типа дискретных моделей.

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

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

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

Первой методической характеристикой работы является систематическое выявление и использование ветвящихся структур.

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

Третья методическая особенность работы - использование конструктивных объектов и алгоритмических методов при моделировании для автоматизированного использования результатов.

Диссертация имеет прикладной характер.

Целью работы является разработка и применение дискретных моделей и локальных методов на ветвящихся структурах с алг^ро-логическим обоснованием.

Все основные результаты диссертации, а также часть методов их доказательства являются новыми.

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

Первая глава посвящена развитию и применению метода частичных конечных изоморфизмов Ю. Л. Ершова для постановки и решения конкретных задач на алгебраических моделях с выявлением и использованием ветвящихся структур. Сама идея Ю. Л. Ершова использования конечных изоморфизмов для получения "бесконечных" результатов неоднократно используется в диссертации.

В 01.1 предлагается переложение идей известного метода конечных частичных изоморфизмов Ю. Л. Ершова С 30], разработанного им для получения критерия элементарной эквивалентности моделей, на язык конечных деревьев.

Путем некоторой факторизации множеств частичных изоморфизмов с продолжениями Ю. Л. Ершова получим конечные деревья для

определения истинности формул. Наряду с подходами Ю. Л. Ершова или А. Т. Нургазина [ 1231, здесь точно так же получаются критерии элементарной эквивалентности и разрешимости, поскольку наши преобразования основываются в конечном итоге на разработанном А. Д. Таймановым [ 147, 148] методе перекидал.

Под алгебраической моделью как обычно понимаем алгебраическую систему - множество элементов с заданными на нем операциями и отношениями, и обозначаем как or = <А, а>, где А -множество, а а - сигнатура. Теорией первого порядка Th СЮ алгебраической системы 01 = <А, ст> называется множество всех замкнутых формул узкого исчисления предикатов сигнатуры а, истинных на ot.

Формулы Aj^, m = 1, 2, ..., представляют все возможные конъюнкции всех атомных формул или их отрицаний от п переменных сигнатуры ст. Для любых п элементов А истинна в точности одна из формул А^. Для каждого п для любой алгебраической системы ot существует единственное с точностью до изоморфизма конечное дерево Р . Его элементами являются элементы А, а ребра помечены теми единственными формулами А^, что истинны на элементах корневого пути. Через К^ обозначим дерево, полученное из PR заменой конкретных элементов А в вершинах и формулах А^ символами различных переменных. Эти деревья обладают тем свойством, что любая замкнутая формула с п переменными истинна на 01 тогда и только тогда, когда она истинна на дереве Рп (К^). Кроме того, эти деревья являются формульными объектами для от.

Пусть Ни®- алгебраические системы одной сигнатуры.

ТЕОРЕМА 1.1. ThC01D = ТЬСЮ (или 01 элементарно эквивалентна ж) тогда и только тогда, когда для любого п е со помеченные деревья К^СЮ и К^СЮ изоморфны.

ТЕОРЕМА 1.2. ТЬСЮ разрешима тогда и только тогда, когда существует эффективная процедура построения по любому п е ш дерева К^СЮ.

ТЕОРЕМА 1.3. Если и - подсистема з§, то система и является элементарной подсистемой системы £ тогда и только тогда, когда каждое дерево РПСЮ является деревом РПС®3.

ПРЕДЛОЖЕНИЕ 5. Если гг - подсистема 93, то всякое Рп~дерево из <и можно пополнить до Рп~дерева в 95.

ПРЕДЛОЖЕНИЕ 6. Для любого эпиморфизма а: и —> 95 и любого п существуют такие конечные полные деревья Г^СЮ и Г^СэзЗ, что аЦСЮ = МпСаЮ.

ПРЕДЛОЖЕНИЕ 7. Произведение Рп-деревьев систем и и ® дает полное дерево прямого произведения Их®.

Полученные в 01.1 результаты используются в следующих частях диссертации, опубликованы в [44, 72, 78].

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

Рассмотрим отдельно случай, когда изучается не вся теория ТЪОЮ, а ее ограничение замкнутыми формулами без кванторов всеобщности (3 - теория модели М).

ОПРЕДЕЛЕНИЕ. Назовем п - универсальным словом модели и = (А, ст) такую последовательность а^, а-р, . . . , а^ элементов из А, что в нее изоморфно вкладывается любая последовательность из п элементов множества А.

Очевидно, что универсальные слова всегда существуют и что

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

Сформулируем постановку задачи. Даны помеченные линейные порядки. Требуется найти минимальное универсальное слово, то есть такой помеченный линейный порядок Р минимальной мощности, в который данные помеченные порядки изоморфно вкладываются.

Если отождествлять помеченные линейные порядки со словами в алфавите 8, составленными из меток на элементах, то можно получить уравнения в свободной полугруппе со свободными образующими из 8 для поиска Р :

Р = х0 а1 ХГ ' ' ак хк = У(Э Ь1 У1' ■■ ЪтУт=--- С1'13 причем оказывается, что решения этой системы всегда существуют и минимальным решениям соответствуют минимальные универсальные слова.

Рассмотрим приложение этой модели к практической задаче.

В геологии известна задача идентификации С сопоставления!) геологических разрезов. Разрез рассматривается как последовательность типов однородности пород С осадочных, геохимических и т. п. 3, а задача идентификации разрезов заключается в таком сопоставлении однотипных элементов разных разрезов, которое соответствует реальному прохождению геологических тел на данной территории [ 138, 144].

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

Предложен новый модельный подход к решению этой задачи, полученный автором совместно с Э. Г. Бернгардтом С 73].

Разрезы являются разноместными реализациями единого процесса осадконакопления Р. Обычно считают, что осадконакоп-ление носило устойчивый характер. Это предположение позволяет сформулировать задачу идентификации для комплекса разрезов как задачу выделения систем слоев (модельных аналогов геологических пластов) с максимальным числом слоев, что равносильно построению по разрезам процесса Р как минимального универсального слова для

Для решения уравнения С1.13 удобно использовать дерево уравнения [ 195], дающее все допустимые решения. Нетрудно заметить, что кратчайшим путям дерева соответствуют решения с минимальной длиной Рр, которые и порождают системы с максимальным числом слоев.

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

Путь дерева уравнения С1.13 соответствует максимальной системе, если после каждой вершины Б пути, имеющей среднего сына, он проходит через некоторую вершину О, являющуюся средним сыном, причем между Б и 0 могут бьпъ либо только левые, либо только правые сыновья. Поддерево дерева уравнения С1.13 , состоящее только из таких путей, удовлетворяет требуемому условию.

ОПРЕДЕЖНИЕ 9. Будем говорить, что слой а расположен ниже слоя (3, если для всех 1 таких, "что а п А^ = <п>, |3 п А^ = <ЪУ имеем а < Ь в А^.

Введенное отношение "ниже" на множестве всех слоев не является порядком, но оно отражает наше представление о процессе осадконакопления и существенно используется в следующем определении.

ОПРЕДЕЛЕНИЕ 10. Пусть Т - некоторая система слоев с заданным на ней линейным порядком Систему Т назовем

корректной, если из а р следует, что а ниже р (а, (3 е Т), и каждый элемент разрезов А^, . . . , Ар принадлежит в точности одному слою из Т.

УТВЕРЖДЕНИЕ 5. Система слоев Тр, порожденная допустимым решением корректна.

УТВЕРЖДЕНИЕ 6. Пусть Т - корректная система. Тогда существует допустимое решение 15 уравнения С1.13, такое, что

т = тк.

ТЕОРЕМА 1.4. Решение й уравнения С1.13 с минимальной длиной Рр порождает корректную систему слоев Тр с максимальным

значением суммы ^ С1-13 где обозначает число слоев

1=2

мощности 1 в системе Тр.

Результаты 01. 2 опубликованы в [44, 73, 78]. Задача систематического изучения вычислимых нумераций была поставлена А.Н.Колмогоровым в 50-х годах (см. [150]). Следующий шаг был сделан трудами А.И.Мальцева в 60-х годах [109-111]. Из зарубежных авторов следует отметить Э.Поста, С. Клини, X. Раиса, А. Лахлана (см. [31, 109, 172, 173, 181]).

Начало новому этапу положили статьи и книги Ю. Л. Ершова,

интересные результаты получили И.А.Лавров, С. С. Марченков, С. Д. Денисов, С. С. Гончаров, В. Л. Селиванов, Л. Хэй (см. [20, 31-33, 101, 112, 139, 140, 164]. Как отметал Ю.Л.Ершов, результаты теории нумераций оказались важными для прояснения трудностей современного программирования.

Изучение полурешеток вычислимых нумераций семейств общерекурсивных функций было начато Ю. Л. Ершовым [32], он же обратил внимание на важную роль предельных точек в этих вопросах.

Нумерация а: N —> и семейства рекурсивно перечислимых множеств (функций) называется вычислимой, если предикат РСх, уЗ х е ссу СРСх, у, гЗ х = ауСгЗЗ рекурсивно перечислим. Нумерация а: N —> 01 семейства конечных множеств называется сильно вычислимой, если функция ГС 13 = "число элементов множества а 1" общерекурсивна.

Нумерация а сводится к нумерации р, а < (3, если существует такая общерекурсивная функция Г, что а = рГ.

Совокупность всех вычислимых нумераций семейства 01 обозначаем Н°(и), а полурешетку (классов эквивалентности) вычислимых нумераций 01 с отношением сводимости через Ь°( ох).

На вычислимую нумерацию можно смотреть как на рекурсивный язык программирования. Тогда сводимость языков означает существование эффективного транслятора, а классы эквивалентности полурешетки Ь°(ох) представляют сложности языков. Главная вычислимая нумерация выделяет универсальный язык.

Базис открытых множеств для беровской топологии на классе всех (рекурсивно перечислимых) множеств состоит из семейств <А I В^ £ А>, 1 е где Б^ есть 1-ое конечное множество.

Примерами вычислимых семейств общерекурсивных функций без изолированных точек являются семейства всех одноместных

примитивно рекурсивных функций, характеристических функций всех конечных множеств.

В 01.3 получены новые результаты в рамках поставленной Ю.Л. Ершовым проблемы об изоморфизме полурешеток вычислимых нумераций. В п. 1.3.1 доказано, в частности, что любые два вычислимые семейства общерекурсивных функций без изолированных точек имеют изоморфные полурешетки вычислимых нумераций. Получены новые результаты о строении этих полурешеток.

В п. 1.3. 2. дана характеризация полурешеток вычислимых нумераций семейств с конечным числом предельных точек (полурешеток с наименьшим элементом). Здесь изоморфизм полурешеток получается как нерекурсивный предел частичных изоморфизмов. Существование дискретных не эффективно дискретных вычислимых семейств общерекурсивных функций свидетельствует о невозможности получения этого изоморфизма через рекурсивный предел как в предыдущем разделе.

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