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

• Автор: Корольков, Юрий Дмитриевич
• Шифр специальности: 05.13.16
• Научная степень: Докторская
• Год защиты: 1997
• Место защиты: Иркутск
• Количество страниц: 216 с.

Министерство общего и профессионального образования Российской Федерации
Иркутский государственный университет
КОРОЛЬКОВ Юрий Дмитриевич
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ АЛГЕБРАИЧЕСКИХ И АНАЛИТИЧЕСКИХ ПРЕОБРАЗОВАНИИ НА ВЕТВЯЩИХСЯ СТРУКТУРАХ
05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях
Диссертация на соискание ученой степени доктора физико - математических наук
Иркутск
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. АЛГЕБРАИЧЕСКИЕ МОДЕЛИ И МЕТОД
КОНЕЧНЫХ ЧАСТИЧНЫХ ИЗОМОРФИЗМОВ
1.1. Методика определения истинности формул
на конечных деревьях
1.2. Частичные изоморфизмы на линейных порядках
1.3. Изоморфизм полурешеток вычислимых нумераций
1.4. Применение частичных морфизмов для
некоторых приближенных вычислений
ГЛАВА 2. ЛОКАЛЬНЫЕ АНАЛИТИЧЕСКИЕ ПРЕОБРАЗОВАНИЯ
И ОЦЕНКИ СЛОЖНОСТИ СИСТЕМ ВЫЧИСЛЕНИИ
2.1. Локальные аналитические преобразования и
система аналитических преобразований
2. 2. Локальные арифметические преобразования
2.3. Оценки сложности всюду определенных вычислений
в арифметической иерархии
2. 4. Рекурсивно перечислимые индексные множества
ГЛАВА 3. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
КАЧЕСТВА ПРОГРАММНЫХ СРЕДСТВ
3.1. Методика моделирования качества на этапах жизненного цикла программных средств
3. 2. Моделирование внешних спецификаций программ
функциями алгебры логики для построения тестов
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ВВЕДЕНИЕ
В математическом моделировании заметные успехи связаны в первую очередь с непрерывными моделями, но в последние десятилетия, особенно в связи с развитием вычислительной техники, все больше внимания уделяется дискретным моделям. Возникла потребность в развитии методов построения и исследования дискретных моделей и их преобразований с учетом возможной их автоматизации.
Успехи теории алгоритмов, математической кибернетики и теоретического программирования не в последнюю очередь связаны с алгебро-лотическим подходом. Здесь можно оттстить работы
А.Н.Колмогорова и В.А.Успенского по вычислимым функциям и исчислениям; А. И. Мальцева, Ю. Л. Ершова и С. С. Гончарова по теории нумераций и конструктивным моделям; А. А. Ляпунова,
С. В. Яблонского и В. М. Глушкова по математической кибернетике; Ю. И. Янова и А. П. Ершова по схемам программ; О. Б. Лупанова по синтезу и сложности управляющих систем; А. Н. Тихонова по регулярным моделям и многие другие у нас и за рубежом.
В последние годы ведутся исследования по изучению алгоритмов над дискретными моделями, алгоритмических свойств моделей. К этому направлению также относятся работы по базам данных, логическому программированию, экспертным системам.
Локальные методы в математике используются практически во всех ее разделах. Там, где возможно применение локальных методов, они обычно приводят к новым и эффективным решениям. В алгебре особенно известны локальные теоремы А. И. Мальцева.
На важность связей между непрерывными и дискретными моделями неоднократно указывал H.H. Яненко.

ет такая последовательность Зд з 3 з ... 5 Зп 5 8'п+ з ... непустых множеств (конечных) частичных изоморфизмов из И в ®, что для любого п е (о, любого ф € и любых а е А и Ь є В
существуют 7 , X Є Зп такие, ЧТО ф £ 7, А И а Є 5т, Ь Є рг
Путем некоторой факторизации этих множеств частичных изоморфизмов с продолжениями из множеств Зп получим конечные деревья для определения истинности формул. Наряду с подходом Ю. Л. Ершова [30] или А. Т. Нуртазина 11231 точно так же получаются критерии элементарной эквивалентности и разрешимости, поскольку наши преобразования основываются в конечном итоге на разработанном А. Д. Таймановым [ 147, 148] методе перекидки.
Пусть для каждого п « со последовательность ф0 , . , ФеСп:, состоит из всех атомных формул Сто есть бескванторных и содержащих не более одного предикатного символа! сигнатуры а от переменных х, . , хГ). Ясно, что функция зСпО = иСп, а! рекурсивна. Введем формулы
Схі Vе Д чД13
где ф* = ф, ф° = т ф, ГПЄ З2
Если а, . , - элементы А, то истинна в точности одна
из формул А Со, . , , О 2 т < З2.
Построим индуктивно систему вложенных помеченных деревьев Тп = ТПСЮ. Элементами деревьев являются элементы А, ребра помечены формулами А , 1 і 1 < п. Общий фиктивный корень, лежащий на уровне О, обозначим 0, Т0 <Д>.
Пусть построено Тп_. С каждой вершиной j уровня
Сп-11 - последнего в Тп_ - свяжем ребрами свой комплект вершин ‘СоП2_}> представляющий все элементы А по одному. Будем называть такой комплект подуровнем. Если Ьп - элемент этого