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

  Скачати повний текст

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

  Скачати повний текст

  Скачати повний текст

  Скачати повний текст

  Скачати повний текст

Запропоновано узагальнену математичну модель, сформульовану у вигляді векторної задачі покриття графа типовими підграфами. Обгрунтовано оцінки обчислювальної складності різних класів досліджуваної задачі покриття графа типовими підграфами, знайдено новий P-важкий клас в оптимізаційній постановці, установлено важкорозв'язуваність усіх класів однорідних векторних задач покриття графа типовими підграфами у випадку наявності у векторній цільовій функції (ВЦФ) двох критеріїв вигляду MAXSUM. Виділено нові поліноміально розв'язувані підкласи одно- та двокритеріальних задач у класах P-важких та важкорозв'язуваних задач покриття графа зірками та ланцюгами. Розроблено відповідні алгоритми їх розв'язання, обгрунтовано поліноміальні оцінки їх обчислювальної складності. Розвинуто теорію алгоритмів з оцінками стосовно одно- та багатокритеріальних задач покриття графа ланцюгами. Для багатокритеріальної задачі покриття графа ланцюгами двох типів побудовано малотрудомісткий алгоритм та доведено теореми, що встановлюють достатні умови, за яких цей алгоритм майже завжди гарантує знаходження розв'язку, точного за критеріями вагового вигляду та асимптотично точного за критерієм кількості ланцюгів у покритті. У однокритеріальному випадку доведено статистичну ефективність алгоритмів. Побудовано малотрудомісткий алгоритм градієнтного типу для оптимізаційної задачі покриття графа скінченою множиною ланцюгів та доведено теореми про достатні умови його асимптотичної точності. Досліджено випадок задачі покриття зірками з інтервальними даними. Здійснено зведення інтервальної задачі до двокритеріальної з обгрунтуванням оцінки обчислювальної складності. Доведено, що розглянуті задачі покриття графа ланцюгами й зірками з інтервальними вагами не можуть бути розв'язуваними за допомогою алгоритмів лінійної згортки критеріїв.

  Скачати повний текст

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

  Скачати повний текст

Встановлено умови, за яких схеми на абелевих групах і графи струмів, асоційовані з цими схемами, породжують неізоморфні вкладення повного графа. Знайдено точну нижню межу для мінімальної ненульової відстані між двома трикутними вкладеннями повного графа та знайдено нетривіальну нижню межу для максимальної відстані між двома трикутними вкладеннями деяких повних графів. Застосовано систему трійок Штейнера, побудовано неорієнтовані трикутні вкладення повних графів з необмеженою великою нещільністю. Цим дано негативну відповідь на відкриту проблему Негамі. Доведено, що існує нескінченно багато мінімальних графів, що не мають 1-занурення у площину. Знайдено з точністю до 10-ти 1-хроматичне число кожної поверхні, орієнтованої чи неорієнтованої. Знайдено 1-хроматичне число нескінченної кількості неорієнтованих поверхонь.

  Скачати повний текст

Обгрунтовано процес редукції ребер розв'язуючих дерев (РД) з використанням імовірнісного підходу до оцінювання емпіричних закономірностей як невипадковостей. Одержано оцінки випадкового виявлення в стандартних навчальних таблицях кон'юктивних закономірностей як ребер РД заданого рангу й у цілому - оцінки можливості "випадкового" виявлення РД-структури заданої складності. Запропоновано новий алгоритм синтезу сукупності РД з обмеженням на ранг ребер. Розв'язано проблему синтезу емпіричного розв'язуючого лісу як розв'язуючого правила, у якому дотримується обмеження на ранг ребер (кон'юнкцій) РД, і зберігається можливість правильної класифікації всіх об'єктів навчальної вибірки. З урахуванням ємнісної характеристики Вапніка - Червоненкіса досліджено складність і одержано оцінку I/CD класу розв'язуючих правил, породжуваних емпіричним розв'язуючим лісом. З використанням алгебричного підходу до розпізнавання побудовано модель алгебричної корекції r - некоректного емпіричного лісу.

  Скачати повний текст

  Скачати повний текст

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

  Скачати повний текст

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

  Скачати повний текст

  Скачати повний текст

  Скачати повний текст

Визначено необхідні умови існування розв'язку узагальненої задачі Ферма, яка стала прототипом задачі Штейнера, у вигляді тригонометричних рівнянь. Виведено загальну формулу довжини мінімального дерева Штейнера для конструкцій типу "драбин". Доведено, що такі фрагменти мінімального остовного дерева, як спіралі, можна трансформувати у піддерева меншої довжини. Формалізовано постановку зваженої задачі Штейнера, яка відрізняється від класичної тим, що в ній ділянки мінімального дерева мають певну вагу. Виведено необхідні умови оптимальності її розв'язку. Побудовано три моделі зваженої задачі Штейнера, наближені до практичних задач. Запропоновано та теоретично обгрунтовано новий параметричний підхід до розв'язання класичної теорії Штейнера, на базі якого розроблено метод обгрунтування гіпотези Гільберта - Поллака, що зводить проблему до розв'язання задач нелінійного програмування. Наведено загальну схему для побудови трьохетапного алгоритму обгрунтування гіпотези Гільберта - Поллака.

  Скачати повний текст

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

  Скачати повний текст

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

  Скачати повний текст