Пошук академічних текстів

Інформація × Реєстраційний номер 0413U001553, Кандидатська дисертація На здобуття к.ф.-м.н. Дата захисту 22-02-2013 Статус Запланована Назва роботи Ефективні алгоритми на арифметичних графах Здобувач Гришанович Тетяна Олександрівна, Керівник Провотар Олександр Іванович Опонент Донець Георгій Панасович Опонент Карнаух Тетяна Олександрівна Опонент Лялецький Олександр Вадимович Опис Дисертація присвячена дослідженню числових графів та ефективних алгоритмів на них. Досліджено теоретичні питання складності алгоритмів. Розглянуто такі підкласи числових графів як арифметичні графи. Доведена актуальність розробки алгоритмів на числових графах. Для таких графів було розроблено та реалізовано на мові програмування новий алгоритм декомпозиції графів за їх вершинами - алгоритм розкладання графів за допомогою їхніх кістяків. Показано, що цей алгоритм забезпечує більшу ефективність за часом як для традиційних способів подання графів, так і для натуральних арифметичних графів. У роботі адаптовано наступні алгоритми відшукання гамільтонових циклів у графах для числових графів: алгоритм із поверненням, Approx-TSP(G), алгоритм із поліноміальним часом. Досліджено характеристики таких алгоритмів. Показано, що числові графи дозволяють покращити оцінки часової складності алгоритмів. Побудовано програмне забезпечення у візуальному середовищі програмування, яке дозволяє розкладати граф за розробленим алгоритмом декомпозиції за умови подання графу у вигляді матриці суміжності та натурального арифметичного графу. А також здійснює відшукання гамільтонових циклів на арифметичних графах, використовуючи адаптовані алгоритми. Дата реєстрації 2013-02-22 Додано в НРАТ 2020-04-04 Закрити