Теорія мультимножин та її застосування

Размещено на http://www.allbest.ru/

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

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

УДК 004.655

Автореферат

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

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

ТЕОРІЯ МУЛЬТИМНОЖИН ТА ЇЇ ЗАСТОСУВАННЯ

Богатирьова Юлія Олександрівна

Київ 2011

Дисертацією є рукопис.

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

Науковий керівник: доктор фізико-математичних наук, старший науковий співробітник Буй Дмитро Борисович, Київський національний університет імені Тараса Шевченка, професор кафедри теорії та технології програмування факультету кібернетики.

Офіційні опоненти:

доктор фізико-математичних наук, професор Штефан Гудак, Технічний університет м. Кошице (Словацька республіка), професор кафедри комп'ютерів та інформатики факультету електротехніки та інформатики;

кандидат фізико-математичних наук, доцент Гороховський Семен Самуїлович, Національний університет “Києво-Могилянська академія” Міністерства освіти і науки, молоді та спорту України, доцент кафедри інформатики факультету інформатики.

Захист відбудеться 7 квітня 2011 р. о 14 год. на засіданні спеціалізованої вченої ради Д 26.001.09 Київського національного університету імені Тараса Шевченка за адресою: 03680, м. Київ, проспект академіка Глушкова, 4д, ауд. 40.

З дисертацією можна ознайомитись у науковій бібліотеці Київського національного університету імені Тараса Шевченка за адресою: 01601, м. Київ, вул. Володимирська, 58.

Автореферат розісланий 2 березня 2011 р.

Вчений секретар спеціалізованої вченої ради Шевченко В.П.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

мультимножина інформатика табличний

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

Репрезентативними прикладами таких задач є:

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

· уточнення обчислень на ДНК;

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

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

· соціологічні опитування різних груп населення стосовно певних проблем.

Зручною моделлю для подання й дослідження багатокритеріальних об'єктів є мультимножини - змістовно кажучи, сукупності з повтореннями.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота є складовою частиною наукових робіт, які ведуться на кафедрі теорії та технології програмування факультету кібернетики Київського національного університету імені Тараса Шевченка при виконанні фундаментальної та прикладної тем: “Розробка конструктивних математичних формалізмів для інтелектуальних систем прийняття рішень, обробки знань, еталонування мов сучасних СУБД та CASE-засобів” (№ 0106U005856, 2006-2010 рр.), “Формальні специфікації програмних систем” (№ 08U002463, 2008-2009 рр.).

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

З огляду на мету в роботі ставляться такі задачі:

- побудова та дослідження алгебри мультимножин;

- встановлення структури сім'ї мультимножин, впорядкованої за природним відношення включення;

- розгляд обчислюваності на мультимножинах;

- застосування отриманих результатів в табличних базах даних та обчисленнях на ДНК.

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

У роботі використовуються теоретико-множинні методи, методи теорії решіток, теорії алгоритмів та теорії програмних алгебр композиційного типу.

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

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

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

Отримані результати застосовані для: уточнення таблиць з дублікатами рядків в сучасних СУБД та маніпуляцій над такими таблицями; побудови денотаційної семантики рекурсивної форми CTE-виразів (Common Table Expressions) сучасних SQL-подібних мов; уточнень обчислень на ДНК у біоінформатиці.

Теоретичне і практичне значення одержаних результатів. Дисертація має теоретико-прикладну спрямованість. Теоретичне значення роботи полягає у розвиненні розділів теорії мультимножин відносно властивостей операцій, устрою частково впорядкованої сім'ї мультимножин, обчислюваності на мультимножинах.

Отримані результати були впроваджені у навчальний процес за спеціальністю “Інформатика” на факультеті кібернетики Київського національного університету імені Тараса Шевченка (нормативні курси “Прикладна логіка”, “Композиційна семантика SQL-подібних мов”, “Теорія обчислень”; спеціальний курс “Вступ до реляційних баз даних”).

Практичне значення роботи полягає в застосування отриманих результатів до табличних баз даних та обчислень на ДНК.

Особистий внесок здобувача. Основні результати роботи отримані здобувачем самостійно. Статті [2, 3, 5] написані у співавторстві з науковим керівником, якому належить постановка задачі дослідження, вибір методів дослідження та обговорення результатів. Здобувачем у статтях [6-10] у систематизованому вигляді подано література з теорії мультимножин станом на 2008 р., досліджено устрій частково впорядкованої сім'ї мультимножин, побудовано системи породжуючих множинної та мультимножинної примітивних програмних алгебр.

Апробація результатів дослідження. Основні положення та висновки дисертаційного дослідження обговорювалися на наукових семінарах кафедри теорії та технології програмування Київського національного університету імені Тараса Шевченка, а також на республіканському семінарі “Програмологія та її застосування”.

Результати дисертаційного дослідження оприлюднені у доповідях і повідомленнях на Міжнародних та Всеукраїнських наукових конференціях, семінарах: VI Всеукраїнській конференції молодих науковців “Інформаційні технології в освіті, науці і техніці” (ІТОНТ-2008, Черкаси, Україна, 2008 р.), V Міжнародній конференції “Theoretical and Applied Aspects of Program Systems Development” (TAAPSD'2008, Київ, Україна, 2008 р.), Міжнародній конференції “Современные направления теоретических и прикладных исследований” (SWORD'2009, Одеса, Україна, 2009 р.), V Міжнародній науково-практичній конференції “Интегрированные модели и мягкие вычисления в искусственном интеллекте” (Коломна, Росія, 2009 р.), VI Міжнародній конференції “Theoretical and Applied Aspects of Program Systems Development” (TAAPSD'2009, Київ, Україна, 2009 р.), ІІІ Всеукраїнській науково-практичній конференції “Моделювання та прогнозування економічних процесів” (Київський національний технічний університет “КПІ”, Київ, Україна, 2009 р.), 9-th International Conference on Applied Mathematics (APPLIMAT-2010, Братислава, Словаччина, 2010 р.), IX Міжнародному науково-практичному семінарі “Комбінаторні конфігурації та їх застосування” (Кіровоград, Україна, 2010 р.), International Conference “Dependable Systems, Services & Technologies” (DESSERT'2010, Кіровоград, Україна, 2010 р.), ХІІІ Міжнародній науковій конференції ім. акад. М. Кравчука (Київський національний технічний університет “КПІ”, Київ, Україна, 2010 р.), I З'їзді “Медична та біологічна інформатика і кібернетика” (Київ, Україна, 2010 р.), VII Міжнародній конференції “Theoretical and Applied Aspects of Program Systems Development” (TAAPSD'2010, Київ, Україна, 2010 р.), XVI Міжнародній конференції “Problems of Decision Making under Uncertainties” (PDMU-2010, Ялта, Україна, 2010 р.), Науково-практичній конференції, присвяченій 80-річчю фізико-математичного факультету (Кіровоградський державний педагогічний університет ім. В. Винниченка, Кіровоград, Україна, 2010), X Міжнародному семінарі “Дискретная математика и ее приложения” (Московський державний університет ім. М.В. Ломоносова, Москва, Росія, 2010 р.), VII Міжнародній науково-практичній конференції з програмування (УкрПРОГ 2010, Київ, Україна, 2010 р.), Міжнародній науковій конференції “Computer Science and Engineering” (CSE'2010, Кошице, Стара Любовна, Словаччина, 2010 р.), XVI-th International Conference “Knowledge-Dialogue-Solution” (KDS 2010, Київ, Україна, 2010 р.), V-th International Conference “Modern (electronic) Learning” (MeL 2010 Київ, Україна, 2010 р.) [5-22].

Публікації. Основні результати дисертаційного дослідження опубліковано у 22 працях. Серед них - 10 статей у наукових журналах і збірниках наукових праць, з них 5 статей опубліковано у фахових виданнях, затверджених ВАК України [1-5], 5 статей опубліковано у наукових фахових іноземних журналах [6-10]; 12 тез та праць конференцій.

Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, списку використаних джерел (79 найменувань). Загальний обсяг дисертації становить 113 с., основний зміст викладено на 105 с. Праця містить 4 рис. та 2 табл.

ОСНОВНИЙ ЗМІСТ

У вступі обґрунтовується актуальність теми дисертації, визначається об'єкт, мета та завдання дисертаційної роботи, методи дослідження, наукова новизна одержаних результатів та їх теоретико-практичне значення, відображаються апробації та публікації результатів дисертаційного дослідження.

У першому розділі “Сучасний стан теорії мультимножин” у систематизованому вигляді подано огляд існуючої літератури з теорії та застосування мультимножин. Усі розглянуті роботи умовно розділено на чотири частини: абстрактна теорія мультимножин, оглядові роботи по мультимножинам, застосування мультимножин у табличних базах даних та інші застосування мультимножин. Бібліографія кожної частини представлена у хронологічному порядку, по кожній роботі наводиться перелік головних результатів. Основні роботи розглянуто більш детально.

Другий розділ “Основи теорії мультимножин” присвячено побудові алгебри мультимножин. У підрозділі 2.1 “Основні означення” наведені основні означення, які стосуються теорії мультимножин. А саме, означення мультимножини, її характеристичної функції, характеристик мультимножин (потужність, розмірність, піковий елемент, пікове значення), відношення включення мультимножин.

Наведемо основні визначення. Нехай - деяка множина (в класичному канторівському розумінні). Тоді мультимножина з основою - це функція вигляду:

,

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

Мультимножина називається порожньою (), якщо її основа - порожня множина.

Мультимножини, областю значень яких є одноелементна множина вигляду {1}, будемо називати 1-мультимножинами.

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

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

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

для всіх . Тут і далі - універсум елементів основ мультимножин.

Потужністю скінченної мультимножини , де - попарно різні елементи основи, називається сума дублікатів усіх елементів основи.

Мультимножини такого вигляду позначаються .

Розмірністю мультимножини називається потужність її основи .

Піковим значенням скінченної мультимножини називається найбільше значення цієї функції . Це значення завжди існує, оскільки область значень скінченної функції також скінченна.

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

,

Твердження 2.1. Із рівності характеристичних функцій мультимножин випливає рівність цих мультимножин і навпаки:

.?

Мультимножина включається у мультимножину (), якщо:

.

Твердження 2.2. Виконується еквівалентність:

.?

Мультимножина строго включається у мультимножину (), якщо:

.

Твердження 2.3. Якщо мультимножина строго включається у мультимножину , то існує хоча б один елемент , для якого виконується нерівність , тобто маємо імплікацію:

.

До особливих мультимножин належать порожня мультимножина та постійна мультимножина (мультимножина, яка приймає постійне значення на своїй основі: ).

У підрозділі 2.2. “Операції над мультимножинами” визначено аналоги стандартних операцій над множинами: об'єднання, перетин, різниця, симетрична різниця, доповнення, пряме з'єднання. Крім того, над мультимножинами визначені операції, що незастосовні для абстрактних множин: додавання, добуток, множення числа на мультимножину. Окремо наводяться означення операцій, які враховують кількість екземплярів, та операцій, що нехтують цією властивістю та будують 1-мультимножини - аналоги класичних множин (кількість екземплярів кожного елементу основи одинична).

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

Наведемо означення основних операцій.

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

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

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

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

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

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

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

,

де операція зрізаної різниці визначається традиційно.

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

Операція прямого з'єднання мультимножин мультимножинам і з основами і відповідно зіставляє мультимножину, основою якої є множина , а характеристична функція задається рівністю

.

У підрозділі 2.3 “Властивості операцій над мультимножинами” систематично встановлюються властивості введених операцій:

· характеристика відношення включення мультимножин в термінах операцій перетину та об'єднання мультимножин: , ;

· аналог закону подвійного заперечення для мультимножин при природній достатній умові ; тут доповнення розглядається до мультимножини (параметра) : ;

· комутативність операцій симетричної різниці, додавання та добутку, а також асоціативність операції додавання та добутку;

· низка тверджень щодо взаємної дистрибутивності операцій об'єднання, перетину, додавання, різниці, добутку, множення числа на мультимножину:

,

,

,

,

,

,

,

,

, ,

,

,

, ,

, .

Усі твердження обґрунтовані формальними доведеннями. Ці співвідношення можуть бути покладені в основу оптимізаційних блоків процесорів мов запитів сучасних табличних баз даних.

Третій розділ “Структура частково впорядкованого сімейства мультимножин” присвячено побудові решітки та двох повних решіток мультимножин.

У підрозділі 3.1 “Побудова решітки мультимножин” будується решітка мультимножин, починаючи з побудови верхньої та нижньої піврешіток.

Лема 3.1 (ідемпотентність, комутативність та асоціативність операцій об'єднання та перетину ). Операції та ідемпотентні (, ), комутативні та асоціативні.?

Лема 3.2 (закони поглинання для операцій об'єднання та перетину ). Для довільних мультимножин і виконуються закони поглинання , .

Виходячи з леми 3.1, розглядаються дві комутативні ідемпотентні напівгрупи та , де - сімейство мультимножин (відповідного універсума ).

Напівгрупа по об'єднанню перетворюється у верхню піврешітку, а напівгрупа по перетину - в нижню. Часткові порядки верхньої та нижньої піврешіток задаються відповідно наступними означеннями:

, ,

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

Теорема 3.1. Частково впорядкована множина є решіткою, причому

, .

Так як такий метод побудови явно не використовував законів поглинання, то далі, в загальному випадку, показано роль законів поглинання у побудові решітки за двома комутативними ідемпотентними напівгрупами з однаковим носієм, сигнатурні операції яких зв'язані законами поглинання.

Теорема 3.2 (критерій співпадіння порядків верхньої та нижньої піврешіток). Часткові порядки верхньої та нижньої піврешіток співпадають тоді і тільки тоді, коли виконуються закони поглинання.

У підрозділі 3.2 “Побудова повної решітки мультимножин” наводяться більш інформативні результати про структуру частково впорядкованої множини (ч.в.м.) мультимножин.

Твердження 3.1 (структура ч.в.м. мультимножин). Виконуються наступні твердження:

1) порожня мультимножина (її характеристична функція є константною функцією, усюди рівною нулю) ? найменший елемент в ;

2) для довільної непорожньої множини мультимножин ; тут характеристична функція точної нижньої грані (інфімуму) задається виразом

3) ;

4) для довільної, зокрема порожньої, сім'ї мультимножин :

точна верхня грань (супремум) існує обмежено зверху;

5) , де ? довільна сім'я мультимножин, яка має точну верхню грань, а характеристична функція мультимножини задається виразом

6) .

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

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

Для цього поповнимо частково впорядковану множину найбільшим елементом . Отриману ч.в.м. позначимо через .

Наслідок 3.1. Ч.в.м. є повною решіткою з найменшим елементом та найбільшим елементом .?

Для вкладення ч.в.м. мультимножин в іншу повну решітку розширюємо поняття мультимножини. Поповнимо множину натуральних чисел без нуля з стандартним порядком найбільшим елементом та покладемо . У такому випадку під мультимножиною будемо розуміти функцію вигляду , сімейство усіх таких мультимножин позначимо через . Порядок на множині позначимо через , тоді порядок на мультимножинах розширимо наступним чином: , . Зауважимо, що порядки , по суті будуються прямим добутком ч.в.м. та відповідно.

Теорема 3.4. Ч.в.м. є повною решіткою з найменшим елементом та найбільшим елементом , де , для усіх . Точні нижні грані знаходяться за формулами твердження 3.1, для точних верхніх граней виконується формула , де характеристична функція мультимножини є такою: .?

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

Четвертий розділ “Обчислюваність на скінченних множинах та мультимножинах” присвячено обчислюваності на множинах та мультимножинах. Обчислюваність вводиться як нумераційна обчислюваність за А.І. Мальцевим. Апаратом для задання класу обчислюваних функцій виступають примітивні програмні алгебри (ППА), які були введені В.Н. Редьком на початку 80-х років минулого століття.

У підрозділах 4.1-4.2 наводяться основні означення теорії ППА та будується нова система породжуючих арифметичної ППА (більш зручна в технічному плані), яка базується на вже побудованій у роботі В.Н. Редька та Д.Б. Буя системі породжуючих арифметичної ППА.

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

Операція суперпозиції (функції в функцію або в предикат) визначається традиційно як , де у припущенні, що для арностей виконується рівності . Тут і далі? узагальнена рівність (сильна рівність Кліні).

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

Припускаємо, що для арностей виконується рівності

.

Параметрична операція циклування функцій за предикатом має наступне означення:

,

де . Для задання значення задамо послідовностей індукцією по . Базис: , ; індуктивний крок: , , . Значення функції визначимо як , де таке мінімальне значення, для якого (за умови визначення всіх попередніх значень , , , ).

Тобто, використовуючи запис оператора мінімізації класичної теорії рекурсії, маємо узагальнену рівність

,

де .

У цьому розділі розглядаються три ППА: арифметична, множинна, мультимножинна. Універсумами даних для них виступають відповідно: множина натуральних чисел , множина скінченних множин натуральних чисел , множина мультимножин, основи яких скінченні множини натуральних чисел.

Побудована в роботі В.Н. Редька, Д.Б. Буя повна система (система породжуючих) арифметичної ППА складається з предикату , функції слідування , функцій додавання та множення , селекторів , , та константної функції , фіксуючої 0:

.

Будуємо наступну систему породжуючих арифметичної ППА

,

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

Повнота системи буде випливати з того, що всі елементи повної системи можна побудувати з елементів системи .

Далі та - константні предикати, що фіксують і відповідно.

Лема 4.1. Функція слідування та предикати , будуються із елементів системи суперпозиціями.?

Лема 4.2. Функція множення будується із елементів системи у арифметичній ППА.

Лема 4.3. Предикат нерівності будується із елементів системи у арифметичній ППА.

Лема 4.4. Система є системою породжуючих арифметичної ППА та -базисом.

Тобто, без втрати властивості повноти з системи не можна вилучити жодного елемента окрім, можливо, селекторів.

У підрозділі 4.3 “Множинна примітивна програмна алгебра” на основі побудованої системи породжуючих арифметичної ППА будуємо систему породжуючих множинної ППА.

До системи породжуючих множинної ППА входить предикат рівності , функція об'єднання множин , функція додавання (скінченних) множин , функція віднімання (скінченних) множин , селекторні функції та константні функції та , що фіксують відповідно сінглтон та порожню множину на довільному аргументі:

.

Наведемо означення функцій та .

.

Також можна визначити цю операцію через повний образ відносно стандартного додавання:

,

тобто,

.

,

де як і раніше операція зрізаної різниці. Аналогічно до операції додавання множин мають місце рівності: , .

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

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

.

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

.

Лема 4.5 (множинні представляючі елементів системи ). Представляючі для елементів системи :

1) предикат представляє предикат ;

2) функція представляє функцію ;

3) множинний селектор представляє арифметичний селектор ;

4) константна функція представляє функцію .?

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

Лема 4.6 (представляюча суперпозиції). Якщо множинні функції , представляють відповідно арифметичні функції , , то суперпозиція представляє суперпозицію .

Аналогічний факт має місце для суперпозиції функцій у предикат.

Лема 4.7 (представляюча розгалуження). Якщо множинні функції представляють відповідно арифметичні функції , а множинний предикат представляє арифметичний предикат , то тоді розгалуження ?⁽³⁾ представляє розгалуження ?⁽³⁾.

Аналогічним чином лема виконується для розгалужень предикатів.

Лема 4.8 (представляюча циклування). Якщо множинні функції представляють відповідно арифметичні функції , а множинний предикат представляє арифметичний предикат , то тоді циклування представляє циклування .

Наслідок 4.1. У множинній ППА з елементів системи можна побудувати множинну представляючу довільної частково рекурсивної арифметичної функції.

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

Нехай , де , - непорожня скінченна множина натуральних чисел. Покладемо, що

,

де , - -те просте число (,,,…). Шукана нумерація задається кусковою схемою:

де - скінченна множина натуральних чисел.

Лема 4.9. Відображення є ін'єктивним, а його область значень -рекурсивна.

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

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

Лема 4.10. Існує рекурсивна арифметична функція така, що , причому - бієкція.

Вводимо означення “кодуючої” та “розкодуючої” функцій. Розглядаються множинні функції, які моделюють нумерацію та : для всіх ; для всіх .

Лема 4.11. Нехай - -арна частково рекурсивна множинна функція, а - -арна множинна функція, що представляє арифметичну частково рекурсивну функцію з означення часткової рекурсивності . Тоді для довільних виконується узагальнена рівність:

.

Лема 4.12 (побудова “кодуючої” функції за “розкодуючою”). Функцію можна побудувати із елементів системи та функції у множинній ППА: .

Лема 4.13. Функцію можна побудувати із елементів системи у множинній ППА: .

Із попередніх лем безпосередньо випливає наступна основна теорема.

Теорема 4.1. Система є системою породжуючих множинної ППА.?

У підрозділі 4.4 “Мультимножинна примітивна програмна алгебра” на основі побудованої системи породжуючих арифметичної ППА будується система породжуючих мультимножинної ППА.

Система породжуючих мультимножинної ППА складається з предикату рівності мультимножин , функцій об'єднання , додавання та віднімання мультимножин, константних функцій та , що фіксують відповідно мультимножину вигляду та порожню мультимножину , специфічної функції над мультимножиною та селекторних функцій :

.

Операція додавання мультимножин визначається через повний образ відносно стандартного бінарного додавання наступним чином: .

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

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

Функція визначається як

.

Функція об'єднання мультимножин визначається стандартно (підрозділ 2.2).

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

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

.

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

.

Лема 4.14 (мультимножинні представляючі елементів системи ). Представляючі для елементів системи :

1) предикат представляє предикат ;

2) функція представляє функцію ;

3) мультимножинний селектор представляє арифметичний селектор ;

4) константна функція представляє функцію .?

Лема 4.15 (представляюча суперпозиції). Якщо мультимножинні функції , представляють відповідно арифметичні функції , , то суперпозиція представляє суперпозицію .

Аналогічний факт має місце для суперпозиції функцій в предикат.

Лема 4.16 (представляюча розгалуження). Якщо мультимножинні функції представляють відповідно арифметичні функції , а мультимножинний предикат представляє арифметичний предикат , то тоді розгалуження ?⁽³⁾ представляє розгалуження ?⁽³⁾.

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

Лема 4.17 (представляюча циклування). Якщо мультимножинні функції представляють відповідно арифметичні функції , а мультимножинний предикат представляє арифметичний предикат , то тоді циклування представляє циклування .

Наслідок 4.2. У мультимножинній ППА з елементів системи можна побудувати мультимножинну представляючу довільної частково рекурсивної арифметичної функції.

Будується ефективна нумерація скінченних мультимножин натуральних чисел. Спочатку розглядається нумерація скінченних непорожніх мультимножин натуральних чисел.

Нехай

,

де , , - непорожня скінченна мультимножина натуральних чисел. Покладемо, що

.

Шукана нумерація задається кусковою схемою:

де - скінченна мультимножина натуральних чисел. Сім'ю всіх скінченних мультимножин натуральних чисел позначимо .

Лема 4.18. Відображення є ін'єктивним, а його область значень - рекурсивна.

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

Мультимножинну -арну функцію будемо називати частково рекурсивною, якщо існує -арна частково рекурсивна арифметична функція така, що виконується узагальнена рівність:

для всіх .

Лема 4.19. Існує рекурсивна арифметична функція така, що , причому - бієкція.

Вводимо означення “кодуючої” та “розкодуючої” функцій. Розглядаються мультимножинні функції, які моделюють нумерації та :

для всіх ; для всіх .

Лема 4.20. Нехай - -арна частково рекурсивна мультимножинна функція, а - -арна мультимножинна функція, що представляє арифметичну частково рекурсивну функцію з означення часткової рекурсивності . Тоді для довільних виконується узагальнена рівність

.

Лема 4.21 (побудова “кодуючої” функції за “розкодуючою”). Функцію можна побудувати із елементів системи та функції у мультимножинній ППА:

.

Лема 4.22. Функцію можна побудувати із елементів системи у мультимножинній ППА:

.

Із наведених лем безпосередньо випливає наступна теорема.

Теорема 4.2. Система є системою породжуючих мультимножинної ППА.

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

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

ВИСНОВКИ

Головні результати роботи розвивають теорію та застосування мультимножин.

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

Основні результати роботи наступні.

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

2. Досліджено основні властивості операцій над мультимножинами: ідемпотентність, комутативність та асоціативність, закони поглинання, закон подвійного заперечення, взаємна дистрибутивність.

3. Побудовано решітку та дві повні решітки мультимножин.

4. Подано характеристику обчислюваності на скінченних множинах та мультимножинах: побудовано системи породжуючих множинної та мультимножинної ППА.

Застосування отриманих результатів.

1. Співвідношення між мультимножинним операціями можна використовувати в оптимізаційних блоках процесорів мов запитів SQL-подібних мов.

2. Мультимножини рядків виступають формальними моделями таблиць з дублікатами рядків у сучасних СУБД табличного типу. Отже, розглянуті операції над мультимножинами (додавання, перетин, різниця з врахуванням та без врахування кратності) уточнюють маніпуляції над таблицями, представленими ключовими словами UNION ALL, INTERSECT ALL, MINUS ALL (з урахуванням кратності) та DISTINCT UNION, DISTINCT INTERSECT, DISTINCT MINUS (без урахування кратності).

3. Побудована повна решітка мультимножин використовується для задання денотаційної семантики рекурсивних CTE-запитів у сучасних SQL-подібних мовах.

4. Частково рекурсивні мультимножинні функції є моделями так званих обчислень на ДНК в біоінформатиці.

СПИСОК ПРАЦЬ, ОПУБЛІКОВАНИХ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Богатырёва Ю.А. Мультимножества: обзор библиографии, построение решетки мультимножеств / Ю.А. Богатырёва // Проблеми програмування. 2010. - № 2-3. Спеціальний випуск. - C. 68-71.

2. Буй Д.Б. Огляд бібліографії по теорії мультимножин / Д.Б. Буй, Ю.А. Богатырёва // Наукові записки НАУКМА. Сер.: Комп'ютерні науки. 2010. - Том 112. - C. 4-9.

3. Буй Д.Б. Сучасний стан теорії мультимножин / Д.Б. Буй, Ю.О. Богатирьова // Вісник Київського національного університету імені Тараса Шевченка. Сер.: фіз.-мат. науки. - 2010. - №1. - С. 51-58.

4. Богатирьова Ю.О. Обчислюваність на скінченних множинах та мультимножинах / Ю.О. Богатирьова // Вісник Київського національного університету імені Тараса Шевченка. Сер.: фіз.-мат. науки. - 2010. - №4. - С. 88-96.

5. Буй Д.Б. Теория мультимножеств: библиография, применение в табличных базах данных / Д.Б. Буй, Ю.А. Богатырёва // Радіоелектронні і комп'ютерні системи. - № 7(48). - 2010. - С. 56-62.

6. Buy D. Multiset Bibliography. Methods of Multiset Lattice Construction / Dmitry Buy, Juliya Bogatyreva // Papers of 9^th International Conference on Applied Mathematics, February 2-5, 2010. - Bratislava. - 2010. - P. 407-413.

7. Buy D. Structure of Partially Ordered Family of Multisets / Dmitry Buy, Juliya Bogatyreva // Proceedings of CSE 2010 International Scientific Conference on Computer Science and Engineering, September 20-22, 2010, Koљice - Starб јubovтa, Slovakia. - P. 40-43.

8. Буй Д.Б. Мультимножества - альтернатива теоретико-множественной платформы в математических обоснованиях информационных технологий / Д.Б. Буй, Ю.А. Богатырёва // Information Model of Knowledge. - ITHEA №19. - P. 377-386.

9. Буй Д.Б. Структура частично упорядоченного семейства мультимножеств / Д.Б. Буй, Ю.А. Богатырёва // Information Model of Knowledge. - ITHEA №19. - P. 387-391.

10. Буй Д.Б. К вопросу о решетке мультимножеств / Д.Б. Буй, Ю.А. Богатырёва // Материалы X международного семинара “Дискретная математика и ее приложения” (Москва, МГУ, 1-6 февраля 2010 г.) / Под. ред. О.М. Касим-Заде. М.: Изд-во мех.-мат. факультета МГУ, 2010. - С. 220-222.

11. Богатирьова Ю.О. Мультимножини: означення, характеристики, операції, властивості операцій / Ю.О. Богатирьова // Матеріали VI Всеукраїнської конференції молодих науковців “Інформаційні технології в освіті, науці і техніці” (ІТОНТ-2008, Черкаси, 5-7 травня, 2008 р.). - Черкаси: ЧНУ, 2008. - C. 140.

12. Буй Д.Б. Мультимножини: означення, операції, основні властивості / Д.Б. Буй, Ю.О. Богатирьова // Матеріали 5-ї Міжнародної конференції “Теоретичні та прикладні аспекти побудови програмних систем” (TAAPSD'2008, Київ, 22-26 вересня 2008 р.). - С. 23-26.

13. Буй Д.Б. Решітка мультимножин / Д.Б. Буй, Ю.О. Богатирьова // Материалы Международной конференция “Современные направления теоретических и прикладных исследований” (SWORD'2009, Одесса, 16-27 марта 2009 г.). - Т. 2. - С. 49-52.

14. Буй Д.Б. Решетка мультимножеств [Електронний ресурс] / Д.Б. Буй, Ю.А. Богатырёва // Материалы Международной конференции “Интегрированные модели и мягкие вычисления в искусственном интеллекте”, 28-30 мая 2009 г. - Режим доступу: raai.org/resurs/papers/kolomna2009/doklad/ Bui_Bogatyreva.doc.

15. Богатырёва Ю.А. Мультимножества: библиография, решетка мультимножеств / Ю.А. Богатырёва // Матеріали 6-ї Міжнародної конференції “Теоретичні та прикладні аспекти побудови програмних систем” (TAAPSD'2009, Київ, 8-10 грудня 2009 р.). - Т. 2. - С. 13-20.

16. Буй Д.Б. Мультимножини як модель експертних оцінок / Д.Б. Буй, Ю.О. Богатирьова // Матеріали ІІІ Всеукраїнської науково-практичної конференції “Моделювання та прогнозування економічних процесів”, (Київ, 9-11 грудня, 2009 р.). - К.: НТУ “КПІ”. - 2009. - С. 44.

17. Буй Д.Б. Побудова (повної) решітки мультимножин / Д.Б. Буй, Ю.О. Богатирьова // Матеріали Дев'ятого Міжнародного науково-практичного семінару “Комбінаторні конфігурації та їх застосування”, (Кіровоград, 16-17 квітня 2010 р.). - С. 18-20.

18. Богатирьова Ю.О. Поняття мультимножини. Структура сімейства мультимножин / Ю.О. Богатирьова // Матеріали Тринадцятої Міжнародної наукової конференції ім. акад. М. Кравчука, (Київ, 13-15 травня 2010 р.). - К.: НТУ “КПІ”. - 2009. - C. 60.

19. Буй Д.Б. Формальная модель ДНК-вычислений / Д.Б. Буй, Ю.А. Богатырёва // Матеріали Першого З'їзду “Медична та біологічна інформатика і кібернетика”, (Київ, 23-26 червня 2010 р.). - C. 221.

20. Буй Д.Б. Структура семейства мультимножеств / Д.Б. Буй, Ю.А. Богатырёва // Матеріали 7-ї Міжнародної конференції “Теоретичні та прикладні аспекти побудови програмних систем” (TAAPSD'2010, 4-8 жовтня 2010 р.). - С. 121-125.

21. Буй Д.Б. Мультимножества / Д.Б. Буй, Ю.А. Богатырёва // Материалы XVI Международной конференции “Problems of Decision Making under Uncertainties” (PDMU-2010, Ялта, 4-8 октября 2010 г.). - С. 149.

22. Буй Д.Б. Обчислюваність на мультимножинах / Д.Б. Буй, Ю.О. Богатирьова // Матеріали науково-практичної конференції, присвяченої 80-річчю фізико-математичного факультету, (Кіровоград, 26 листопада 2010 р.). - Кіровоград: РВВ КДПУ ім. В. Винниченка, 2010. - С. 28-30.

АНОТАЦІЯ

Богатирьова Ю.О. Теорія мультимножин та її застосування. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03 - математичне та програмне забезпечення обчислювальних машин і систем. - Київський національний університет імені Тараса Шевченка. - Київ, 2011.

Роботу присвячено розвитку теорії мультимножин та її застосуванню.

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

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

Вирішено проблему повноти для мультимножинної примітивної програмної алгебри. Тим самим уточнено обчислюваність на мультимножинах.

Розглянуто можливості застосування теорії мультимножин. Отримані результати можуть бути застосовані для: уточнення таблиць із дублікатами рядків у сучасних СУБД та маніпуляцій над такими таблицями; побудові денотаційної семантики рекурсивної форми CTE-виразів сучасних SQL-подібних мов; уточнені обчислень на ДНК у біоінформатиці.

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

АННОТАЦИЯ

Богатырёва Ю.А. Теория мультимножеств и ее применения. - Рукопись.

Диссертация на соискание учёной степени кандидата физико-математических наук по специальности 01.05.03 - математическое и программное обеспечение вычислительных машин и систем. - Киевский национальный университет имени Тараса Шевченко. - Киев, 2011.

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

Мультимножества (совокупности с повторениями) являются удобной моделью для представления и исследования объектов, особенностью которых является множественность и повторяемость данных.

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

В работе развиваются теория мультимножеств и рассматриваются области ее применения.

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

Исследованы свойства операций над мультимножествами: идемпотентность, коммутативность, ассоциативность, дистрибутивность, законы поглощения, монотонность, аналоги законов де Моргана и двойного отрицания.

Построена решетка мультимножеств и вложена в две полные решетки мультимножеств.

Дана характеристика вычислимости на конечных множествах и мультимножествах: построены системы порождающих множественной и мультимножественной примитивных программных алгебр.

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

1) соотношения между мультимножественными операциями можно использовать в оптимизационных блоках процессоров языков запросов SQL-подобных языков;

2) мультимножества строк выступают формальными моделями таблиц с дубликатами строк в современных СУБД табличного типа, таким образом, рассмотренные операции над мультимножествами уточняют манипуляции над таблицями, представленными ключевыми словами UNION ALL, INTERSECT ALL, MINUS ALL (с учетом кратности) и DISTINCT UNION, DISTINCT INTERSECT, DISTINCT MINUS (без учета кратности);

3) построенная полная решетка мультимножин используется для задания денотационной семантики рекурсивных CTE-запросов в современных SQL-подобных языках;

4) частично рекурсивные мультимножественные функции являются моделями вычислений на ДНК в биоинформатике.

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

ABSTRACT

Bogatyreva J.A. Multisets theory and its applications. - Manuscript.

Candidate's thesis on Physics and Mathematics, speciality 01.05.03 - Mathematical and software support of computers and systems. - Kyiv National Taras Shevchenko University. - Kyiv, 2011.

The thesis is devoted to development of the theory of multisets and its applications. Properties of well-known operations on multisets are investigated: idempotency, commutativity, associativity, distributivity, absorption laws, monotonicity, analogs of de Morgan and double negation laws.

The lattice of multisets is constructed and enclosed in two complete lattices of the multisets. The second complete lattice is obtained by generalization of the multiset concept (by allowing infinite multiplicity of elements) and is used to define denotation semantics of recursive queries of SQL-like languages.

The problem of completeness for multiset primitive program algebra is solved, thereby computability on multisets is specified.

The results obtained in the thesis are applicable for: specifications of tables with duplicate rows in modern databases and manipulations over such tables; defining denotation semantics of the recursive form of CTE-expressions of modern SQL-like languages; specifications of calculations on DNA in biocomputer science.

Key words: multiset, multiset lattice, complete multiset lattice, table database, computability, primitive program algebras.

Размещено на Allbest.ru