WWW.UK.X-PDF.RU

БЕЗКОШТОВНА ЕЛЕКТРОННА БІБЛІОТЕКА - Книги, видання, автореферати

 
<< HOME
CONTACTS




Продажа зелёных и сухих саженцев столовых сортов Винограда (по Украине)
Тел.: (050)697-98-00, (067)176-69-25, (063)846-28-10
Розовые сорта
Белые сорта
Чёрные сорта
Вегетирующие зелёные саженцы

Продажа зелёных и сухих саженцев столовых сортов Винограда (по Украине)
Тел.: (050)697-98-00, (067)176-69-25, (063)846-28-10
Розовые сорта
Белые сорта
Чёрные сорта
Вегетирующие зелёные саженцы
Pages:   || 2 | 3 | 4 | 5 |   ...   | 26 |

«На правах рукопису Буй Дмитро Борисович УДК 681.3.06 ТЕОРІЯ ПРОГРАМНИХ АЛГЕБР КОМПОЗИЦІЙНОГО ТИПУ ТА ЇЇ ЗАСТОСУВАННЯ 01.05.03 – Математичне та програмне забезпечення обчислювальних ...»

-- [ Страница 1 ] --

Київський національний університет імені Тараса Шевченка

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

Буй Дмитро Борисович

УДК 681.3.06

ТЕОРІЯ ПРОГРАМНИХ АЛГЕБР КОМПОЗИЦІЙНОГО ТИПУ

ТА ЇЇ ЗАСТОСУВАННЯ

01.05.03 – Математичне та програмне забезпечення обчислювальних машин

та систем

Дисертація на здобуття наукового ступеня

доктора фізико-математичних наук

Науковий консультант

Редько Володимир Никифорович,

доктор фіз.-мат. наук, професор, академік НАНУ

Київ – 2002

ЗМІСТ

Перелік умовних позначень

Вступ Розділ 1. Нерухомі точки монотонної функції на частково впорядкованій множині 33

1.1. Основні поняття

1.2. Основні властивості та еквівалентні завдання монотонних функцій.......... 36 1.2.1. Ланцюги елемента відносно функції

1.2.2. Ланцюги елементів і нерухомі точки

1.2.3. Структура нерухомих точок монотонної функції на індуктивній множині 55 1.2.4. Монотонні та зростаючі функції, конструкція Тарського

1.2.5. Ординальні зображення нерухомих точок

1.2.6. Нерухомі точки неперервної функції на індуктивній множині

1.2.7. Обернення теорем про нерухомі точки

Розділ 2. Композиція суперпозиції

2.1. Допоміжні результати

2.2. Неперервність суперпозиції та суміжні факти

2.2.1. Зображення суперпозиції, колекція та добуток

1.3.1. Неперервність суперпозиції

2.3. Часткові функції: підстановка та інші програмологічні операції................ 84 2.3.1. Частково впорядкована множина часткових функції

2.3.2. Неперервність операцій на часткових функціях

2.3.3. Підстановка, добуток та колекція часткових функцій

2.3.4. Вкладення часткових функцій у тотальні

2.3.5. Розгалуження часткових функцій за предикатом

Розділ 3. Композиція рекурсії

3.1. Рекурсія, індукована рівнянням

3.1.1. Теореми про нерухомі точки монотонних та неперервних функцій......... 103 3.1.2. Означення та зображення рекурсії

3.1.3. Монотонність рекурсії, замкненість класу монотонних функцій відносно рекурсії

3.1.4. Неперервність обмежень рекурсії, замкненість класу неперервних функцій відносно рекурсії

3.1.5. Інші означення рекурсії

3.2. Рекурсія, індукована системами рівнянь

3.2.1. Розв’язки систем рівнянь з монотонними (неперервними) функціями правих частин

3.2.2. Розв'язки систем рівнянь з параметром, багатомісна композиція рекурсії та її зображення

3.2.3. Властивості багатомісної рекурсії

3.2.4. Випадок декількох параметрів

3.3. Розв’язування систем рівнянь в індуктивних множинах

3.3.1. Допоміжні леми

3.3.2. Розв’язки систем спеціального вигляду, метод Гаусса

3.3.3. Розв’язки систем з суперпозиціями та рекурсіями у правих частинах..... 139 3.3.4. Підстановка значень функцій замість параметрів

3.3.5. Перетворення, що зберігають найменші розв’язки

3.3.6. Взаємозв’язок між операціями суперпозиції та рекурсії

3.3.7. Похідність багатомісної рекурсії

3.3.8. Оцінки найменших розв‘язків

Розділ 4. Маніпулювання даними

4.1. Функції, що зберігають денотати

4.1.1. Основні поняття та властивості

4.1.2. Характеристики функцій та програмологічних операцій

4.1.3. Функції, що зберігають денотати, та обчислювані функції

4.2. Примітивні програмні алгебри функцій та предикатів на оціненому універсумі

4.2.1. Основні означення

4.2.2. Необхідні умови повноти

4.2.3. Повнота класів обчислюваних функцій, що зберігають денотати............ 191 4.2.4. {true, false}-Породжуючі ППА

4.3. Програмні алгебри іменних функцій, що зберігають денотати, та предикатів

4.3.1. Оцінений універсум іменних даних

4.3.2. Програмні алгебри іменних функцій та предикатів

4.3.3. Необхідні умови повноти

4.3.4. Сильне збереження денотатів

4.3.5. Проблеми повноти в класах іменних функцій, що зберігають денотати.. 219 Розділ 5. Програмні алгебри та реляційні бази даних

5.1. Загальнозначні семантичні структури реляційних баз даних, змістовна семантика мови SQL

5.1.1. Загальна характеристика мови SQL

5.1.2. Моделі реляційних структур

5.2. Табличні алгебри

5.2.1. Основні означення

Розділ 6. Взаємна похідність та виразна сила сигнатурних операцій

6.1. SQL-орієнтовані програмні алгебри

6.1.1. Операції на таблицях

6.1.2. Композиції фільтрації та повного образу

6.1.3. Композиції для випадку мультимножин

6.1.4. Впорядковані таблиці

6.1.5. Агрегатні функції, композиція агрегування

6.1.6. Групування

6.1.7. Оновлення даних

Розділ 7. Визначення семантики операторів маніпулювання даними.................. 305 Висновки

Список використаних джерел

Додаток А. Доведення деяких лем та тверджень; означення агрегатних функцій мови SQL

ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ

–  –  –

*( n 1) (n 1) -арна композиція циклування n функцій арності n за n -арним предикатом, n 1,2,...

клас всіх функцій на оціненому універсумі, що сиF, <

–  –  –

денотати, та частково рекурсивних предикатів A pr ППА частково рекурсивних функцій та предикатів pr ППА частково рекурсивних функцій, що сильно збеA, <

–  –  –

N* множина векторів натуральних чисел F( L) клас всіх функцій, які зберігають множину L P ( L) клас всіх предикатів, які у випадку визначеності на

–  –  –

GrW параметрична функція групування БНФ Бекуса-Наура форма ПА програмна алгебра ППА примітивна програмна алгебра п. ч. в. м. повна частково впорядкована множина СУБД система управління базою даних у-таблиця “упорядкована” таблиця УЗЛ умова обриву зростаючих ланцюгів т. д. і. топологія додатньої інформації ц. у. м. цілком упорядкована множина ч. в. м. частково впорядкована множина чр-предикат частково рекурсивний предикат чр-функція частково рекурсивна функція

ВСТУП

Актуальність теми. Об’єктивна тенденція розвитку сучасного суспільства характеризується застосуванням інформаційних технологій у різноманітних сферах. Розробка, впровадження та супровід програмних систем, що реалізують інформаційні технології, наштовхуються на значні труднощі, які носять принциповий характер. Вимоги надійності, ефективності, відкритості, передбачуваності до програмних систем потребують формальних моделей на всіх етапах життєдіяльності програмного забезпечення. Труднощі застосування формальних моделей пов‘язані, по-перше, з абсолютизацією інтуїтивної основи при уточненні визначальних категорій (програм та програмування як процесу синтезу програм) та, подруге, з використанням формальних моделей, неадекватних у повному обсязі предметній області. Сам факт наявності багатьох стилів програмування (наприклад, структурного [84, 117]; функціонального чи, за іншою термінологією, денотаційного [64, 168, 208]; логічного [101, 118, 171]; об‘єктно-орієнтованого [63]; візуального [83]; модульного чи, за сучасною термінологією, компонентноорієнтованого [80]) свідчить не лише про безсумнівні досягнення сучасної комп‘ютерної науки, а й про відсутність загальноприйнятої концептуальної платформи. Спроби виходу з такого незадовільного становища робилися В. М. Глушковим, К. Л. Ющенко, А. П. Єршовим, В. Н. Редьком та їх учнями.

Перераховані стилі виділяють певний (звичайно, дуже важливий, але один з багатьох) аспект та уточнюють саме його. Так, у структурному програмуванні це каталогізація методів побудови програм, у функціональному – опис програм системами функціональних рівнянь, у логічному – визначення програм специфікаціями певних формальних мов, як правило, першого порядку, в об‘єктноорієнтованому (модульному) – трактування розмаїтості даних, функцій та керуючих структур як об‘єктів (модулів). Тим самим моделі програм, що лежать в основі названих стилів, не є повністю адекватними інтуїтивному змісту основних категорій програмування.

Труднощі застосування існуючих моделей до реального програмування, пов‘язані в першу чергу з нехтуванням вимоги експлікативності моделей предметній області (експлікативність у розумінні Р. Карнапа: по-перше, формальність моделей у загальноприйнятому розумінні та, по-друге, їх адекватність предметній області, що моделюється), добре усвідомлюються та здійснюються спроби їх подолання: створюються нові стилі програмування об‘єднанням існуючих (функціонального з логічним, алгебраїчного з логічним та ін.

Купить саженцы и черенки винограда

Более 140 сортов столового винограда.


), розробляються нові формалізми. Аналіз причин сучасного критичного стану в застосуванні формальних моделей до створення складних промислових програмних систем дозволяє сформулювати наступні вимоги, яким повинні задовольняти сучасні моделі програм:

експлікативність;

– композиційність (уточнення семантичних структур програм у вигляді композицій – спеціальних алгебраїчних операцій у класах функцій, що виступають семантиками програм);

інтенсіональність (зміст понять, їхня структура);

– явне використання структур іменування;

– чітка витримка рівнів абстракції моделей.

– Серед потенційно можливих моделей, які задовольняють наведеним вимогам, у дисертації обрані програмні алгебри композиційного типу, які базуються на композиційному програмуванні, закладеному в працях академіка В. Н. Редька у 70-х роках минулого століття [135, 140, 145, 146]. За поставленими задачами та методами їх вирішення робота розвиває експлікативне програмування [133, 136, 138, 141, 142, 143, 151, 152]. Реальні теоретико-практичні досягнення побудованій у дисертації теорії програмних алгебр композиційного типу і можливість застосування цієї теорії до нагальних потреб практичного програмування і визначають актуальність дисертаційного дослідження.

Зв‘язок роботи з науковими програмами, планами, темами. Дисертаційна робота є складовою частиною наукових робіт, які ведуться на кафедрі теорії програмування факультету кібернетики Київського національного університету імені Тараса Шевченка (КНУ) при виконанні фундаментальних та прикладних тем: “Дослідження універсальних та спеціалізованих програмних логік” (№ 0197U003444, 1997-2000 рр.), “Побудова і дослідження програмних логік, що лежать в основі сучасних CASE-технологій” (№ 0101U002163, 2001-2005 рр.), “Дескриптивні CASE-технології генерації професійних систем програмування” (№ 0195U016803, 1995-1997 рр.), “Дослідження програмних алгебр композиційного типу” (№ 0198U002032, 1998-2000 рр.), “Еталонування семантичних структур мов CASE-середовищ програмологічними засобами” (№ 0101U005770, 2001рр.), “Розробка та реалізація підсистеми віддаленої актуалізації даних в засобах обліку державних службовців” (№ 0198U007174, 1998 р.).

Мета і задачі дослідження. Метою дисертаційної роботи є конструювання формальних моделей програмних систем засобами програмних алгебр композиційного типу на абстрактному та іменному рівнях абстракції:

побудова програмних алгебр, які виступають моделями загальнозначних

– дескриптивних та декларативних структур програм, моделями маніпуляційних дій у базах даних, зокрема, в реляційних базах даних;

математичні дослідження таких алгебр, орієнтовані на їх подальше застосування до потреб практичного програмування;

застосування отриманих результатів до опису повної семантики підмов маніпулювання даними (DML мов) у SQL-подібних мовах.

Відповідно до цієї мети в роботі ставляться такі задачі:

– побудувати та дослідити на абстрактному рівні програмні алгебри суперпозицій та рекурсій, які виступають моделями загальнозначних дескриптивних (суперпозиція) та декларативних (рекурсія) структур програм;

побудувати та дослідити на абстрактному та іменному рівнях абстракції

– програмні алгебри зберігаючих денотати функцій, які виступають моделями маніпуляційних дій в базах даних; абстрактному рівню відповідають примітивні програмні алгебри, іменному – програмні алгебри іменних функцій;

побудувати та дослідити табличні алгебри, які уточнюють маніпуляції коддовського типу;

побудувати програмну алгебру іменних функцій та застосувати її до визначення повної формальної семантики DML мов у SQL-подібних мовах.

Наукова новизна одержаних результатів. Побудована узагальнююча теорія розв‘язування систем рівнянь, асоційованих з рекурсіями, і отримані такі нові результати цієї теорії:

встановлена структура множини всіх розв‘язків, залежність розв‘язків від

– початкового наближення, параметрів та функцій правих частин;

отримані нижні та верхні оцінки найменших розв‘язків, які узагальнюють

– оцінки відомих теорем теорії рекурсивних програм – теорем Парка (Park) про індукцію нерухомої точки, Кадью (Cadiou) та Війємана (Vuillemin) про безпечні правила обчислення;

обґрунтована коректність застосування методу Гаусса (послідовного виключення невідомих) до розв‘язування систем;

досліджені загальнозначні перетворення систем типу підстановки, які зберігають найменші розв‘язки; останній результат є узагальненням важливої теореми Війємана про інваріантні перетворення нерухомої точки в теорії рекурсивних програм.

Побудована і досліджена з нових позицій програмна алгебра суперпозицій та рекурсій:

досліджена монотонність і неперервність суперпозиції за окремими аргументами, монотонність рекурсії та неперервність обмежень рекурсії на класи неперервних функцій;

доведена замкненість класів монотонних (неперервних) функцій відносно рекурсії;

встановлений взаємозв‘язок між сигнатурними операціями.

– У дисертаційній роботі узагальнена модель маніпуляційних дій РедькаБасараба шляхом введення поняття функцій, які зберігають денотати відносно оцінок-параметрів універсуму даних. Побудовані і досліджені програмні алгебри функцій, які зберігають денотати. Розв‘язані проблеми повноти для програмних алгебр обчислюваних функцій, що зберігають денотати для основних оцінок універсуму іменних даних.

На основі узагальнення класичних реляційних алгебр Кодда побудована таблична алгебра, яка уточнює інформаційний та маніпуляційний аспект реляційних баз даних. Повністю вирішена проблема взаємної похідності сигнатурних операцій табличної алгебри. Побудована SQL-орієнтована програмна алгебра іменних функцій, засобами якої адекватно задана повна формальна семантика операторів маніпулювання даними SQL-подібних мов.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 26 |
Похожие работы:

«МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ХАРЧОВИХ ТЕХНОЛОГІЙ ЗАТВЕРДЖУЮ Ректор_С.В. Іванов _2012р. ОСНОВИ ФІЗИКО-ХІМІЧНОГО КОНТРОЛЮ СИРОВИНИ І ПРОДУКТІВ ГАЛУЗІ МЕТОДИЧНІ РЕКОМЕНДАЦІЇ до вивчення дисципліни і виконання контрольних робіт напряму 6.051701 „Харчові технології та інженерія” денної, заочної та заочної скороченої форм навчання Реєстраційний номер СХВАЛЕНО Електронних методичних на засіданні кафедри технології рекомендацій у НМВ хлібопекарських та...»

«ВЕРХОВНА РАДА УКРАЇНИ ІНФОРМАЦІЙНЕ УПРАВЛІННЯ ВЕРХОВНА РАДА УКРАЇНИ У Д ЗЕРКАЛІ ЗМІ: За повідомленнями друкованих та інтернет-ЗМІ, телебачення і радіомовлення 15 вересня 2010 р., середа ДРУКОВАНІ ВИДАННЯ Кожен має посадити принаймні три дерева Юліана Шевчук, Голос України.3 Під час робочої поїздки на Рівненщину Голова Верховної Ради В.Литвин взяв участь у відкритті фінальних змагань Всеукраїнської спартакіади працівників лісового господарства у райцентрі Березне, яка відбулася з нагоди Дня...»

«МІЖРЕГІОНАЛЬНА АКАДЕМІЯ УПРАВЛІННЯ ПЕРСОНАЛОМ МЕТОДИЧНІ РЕКОМЕНДАЦІЇ ЩОДО ЗАБЕЗПЕЧЕННЯ САМОСТІЙНОЇ РОБОТИ СТУДЕНТІВ з дисципліни “БІОЛОГІЯ ЛЮДИНИ” (для бакалаврів) Київ ДП «Видавничий дім «Персонал» Підготовлено викладачем кафедри медичної психології та психокорекції Л.Г.Тарасенко Затверджено на засіданні кафедри медичної психології та психокорекції (протокол № 7 від 01.04.08) СхваленоВченоюрадоюМіжрегіональноїАкадеміїуправлінняперсоналом Тарасенко Л. Г. Методичні рекомендації щодо організації...»

«Міністерство освіти і науки, молоді та спорту України Вінницький національний технічний університет РЕЄСТРАЦІЯ, ОБРОБКА ТА КОНТРОЛЬ БІОМЕДИЧНИХ СИГНАЛІВ Навчальний посібник Вінниця ВНТУ УДК [621.37:57.087.1+615.47](075) ББК 32.811.3:53.4я73 Р33 Автори: В. Г. Абакумов, З. Ю. Готра, С. М. Злепко, С. В. Павлов,. В. Б. Василенко, О. І. Рибін Рекомендовано Міністерством освіти і науки України як навчальний посібник для студентів вищих навчальних закладів, які навчаються за напрямком підготовки...»

«МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ХАРЧОВИХ ТЕХНОЛОГІЙ ЗАТВЕРДЖУЮ В. о. ректора _Іванов С.В._ (Підпис) (Прізвище, ініціали) «_» _2010 р. ОСНОВИ ЕКОЛОГІЇ МЕТОДИЧНІ ВКАЗІВКИ до практичних занять для студентів за напрямами підготовки 6.051701 «Харчові технології та інженерія» денної форми навчання Реєстраційний номер СХВАЛЕНО електронних методичних на засіданні кафедри вказівок у технології функціональних НМУ харчових продуктів Протокол № 3 від 5 жовтня 2010 р. Київ НУХТ...»

«МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ Національний аерокосмічний університет ім. М.Є. Жуковського «Харківський авіаційний інститут» Д.О. Воронович, І.В. Луньов, А.М. Охрімовський, О.В. Подшивалова ЕЛЕКТРИКА Й МАГНЕТИЗМ Навчальний посібник до лабораторного практикуму Харків «ХАІ» 2011 УДК [53 + 537 + 537.6] (076.5) Е45 Рецензенти: д-р фіз.-мат. наук, проф. М.І. Гришанов, доц. В.П. Олефір Воронович, Д. О. E45 Електрика й магнетизм [Текст]: навч. посіб. до лаб. практикуму / Д.О....»

«МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ХАРЧОВИХ ТЕХНОЛОГІЙ ФІЗИЧНА ТА КОЛОЇДНА ХІМІЯ МЕТОДИЧНІ РЕКОМЕНДАЦІЇ до виконання лабораторних робіт для студентів напряму 6.051701 Харчові технології та інженерія та 6.051401 Біотехнологія денної та заочної форм навчання Всі цитати, цифровий та фактичний матеріал, бібліографічні відомості перевірені. Написання одиниць відповідає стандартам Підписи авторів_ 2012 р. СХВАЛЕНО на засіданні кафедри фізичної і колоїдної...»

«Методична комісія природничо-математичних дисциплін Методична розробка уроку Предмет: Фізика Викладач: Присяжнюк А.І. спеціаліст Тема: Експериментальне вивчення будови атома.Мета уроку: з'ясувати будову атома; розглянути шляхи та методи експериментального вивчення будови атома; розвивати логічне мислення; виховувати навички роботи в команді, вміння відстоювати свою думку. Тип уроку: урок засвоєння нових знань. Методи та прийоми уроку: словесний, наочний. Обладнання: демонстрування моделей...»

«ДЕРЖАВНА САНІТАРНО – ЕПІДЕМІОЛОГІЧНА СЛУЖБА УКРАЇНИ МЕТОДИЧНІ ВКАЗІВКИ щодо застосування засобу «Антихлор» з метою дезінфекції, передстерилізаційного очищення та стерилізації виробів медичного призначення Київ2013 р. Організація – розробник: ДУ « Інститут медицини праці НАМН України». Методичні вказівки призначені для закладів охорони здоровя та інших організацій, які виконують роботи з проведення дезінфекції. Місцевим органам охорони здоровя дозволяється тиражування цих методичних вказівок в...»

«Міністерство освіти і науки України Національний технічний університет України “Київський політехнічний інститут” «БІОФІЗИКА» МЕТОДИЧНІ ВКАЗІВКИ до виконання лабораторних робіт Київ «Політехніка»-0Міністерство освіти і науки України Національний технічний університет України “Київський політехнічний інститут” «БІОФІЗИКА» МЕТОДИЧНІ ВКАЗІВКИ до виконання лабораторних робіт для студентів напрямку підготовки 6.0909-«Прилади», 7.090905 «Медичні прилади та системи» приладобудівного факультету...»




Продажа зелёных и сухих саженцев столовых сортов Винограда (по Украине)
Тел.: (050)697-98-00, (067)176-69-25, (063)846-28-10
Розовые сорта
Белые сорта
Чёрные сорта
Вегетирующие зелёные саженцы


 
2013 www.uk.x-pdf.ru - «Безкоштовна електронна бібліотека»