Головна Головна -> Реферати українською -> Дисертації та автореферати -> РОЗВ’ЯЗАННЯ ЗАДАЧ Ізоморфізму та знаходження хроматичного числа на числових графах

РОЗВ’ЯЗАННЯ ЗАДАЧ Ізоморфізму та знаходження хроматичного числа на числових графах

Назва:
РОЗВ’ЯЗАННЯ ЗАДАЧ Ізоморфізму та знаходження хроматичного числа на числових графах
Тип:
Реферат
Мова:
Українська
Розмiр:
15,43 KB
Завантажень:
418
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10 
Національна академія наук України
Інститут кібернетики імені В.М. Глушкова
ШУЛІНОК Георгій Олександрович
УДК 519.1
РОЗВ’ЯЗАННЯ ЗАДАЧ Ізоморфізму та знаходження хроматичного числа на числових графах
 
01.05.01 - теоретичні основи інформатики та кібернетики
Автореферат
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
Київ – 2006
Дисертацією є рукопис.
Робота виконана в Інституті кібернетики ім. В.М. Глушкова НАН України.
Науковий керівник : доктор фізико-математичних наук,
Донець Георгій Панасович,
Інститут кібернетики ім. В.М. Глушкова
НАН України, завідувач відділу.
Офіційні опоненти: доктор фізико-математичних наук, професор,
Асельдеров Зайнутдін Макашаріпович,
Національний технічний університет України
“КПІ”, кафедра автоматизованих систем обробки інформації та управління,
кандидат фізико-математичних наук,
Журбенко Микола Георгійович,
Інститут кібернетики ім. В.М. Глушкова
НАН України, старший науковий співробітник.
Провідна установа: Київський національний університет
імені Тараса Шевченка, факультет кібернетики, кафедра математичних методів
еколого-економічних досліджень.
Захист відбудеться "____"_____________ 2006 р. о(об) годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики імені В.М. Глушкова НАН України за адресою:
03680, МСП Київ-187, проспект Академіка Глушкова, 40.
З дисертацією можна ознайомитися в науково-технічному архіві інституту.
Автореферат розісланий "____"____________2006 р.
Учений секретар
спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.


ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми. Дисертаційна робота присвячена розв’язанню на числових графах задач, що не мають ефективних алгоритмів розв’язку у загальному випадку, таких як пошук хроматичного числа графа та ізоморфізм графів. Дослідження велися у таких напрямках: а) дослідження структури числових графів та розробка методів визначення інваріантів; б) знаходження необхідних та достатніх умов ізоморфізму для певних підкласів числових графів; в) розробка методів пошуку ізоморфізму для однорідних та довільних числових графів; г) знаходження хроматичного числа для певних підкласів числових графів; д) дослідження наявних методів пошуку хроматичного числа числових графів; е) розробка методів, що дозволяють ефективно вирішувати задачу розфарбування довільних числових графів довільним числом кольорів; ж) розробка програмного забезпечення для деяких з напрямків.
Проблема ефективності алгоритмів (у тому числі не тільки на графах) за останні півстоліття породила величезну масу робіт. Разом з тим пошук ефективних алгоритмів на числових графах почався зовсім недавно. Дослідження почалося з базових для теорії графів алгоритмів, таких як пошук в ширину та глибину, проте ці алгоритми і так мали ефективні (поліноміальні) алгоритми розв’язку. З іншого боку, найбільш цікавими для практичного застосування є задачі на графах, що не мають відомих поліноміальних алгоритмів розв’язку.
Останнім часом дуже багато досліджень в галузі розпізнавання образів, структурного та системного аналізу, в розробці програмних комплексів, у конструюванні обчислювальної техніки та багатьох інших галузях як об’єкт початкових даних використовують графи, які мають специфічну структуру. Деякі користуються при цьому традиційним представленням графів, що вимагає величезної пам’яті та приводить до громіздких обчислень з великими витратами часу. В більшості випадків ці графи мають ієрархічну або симетричну структури, які складаються з однотипних частин або таких, що повторюються. А саме числові графи дозволяють з максимальним ефектом використовувати ці особливості. Необхідно тільки знайти підходящу функцію, яка адекватно описує суміжність вершин графа. Внаслідок вдалого підбору такої функції представлення заданого графу може зменшитися за обсягом пам’яті в декілька разів, а операції пошуку у величезних масивах пам’яті для отримання необхідної інформації замінюються невеликою кількістю елементарних обчислень.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4  5  6  7  8  9  10 



Реферат на тему: РОЗВ’ЯЗАННЯ ЗАДАЧ Ізоморфізму та знаходження хроматичного числа на числових графах

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок