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

Інформація × Реєстраційний номер 0212U000142, 0107U000797 , Науково-дослідна робота Назва роботи Розробити теоретичні основи для створення паралельних ефективних алгоритмів розв'язання задач на графах великого об'єму Назва етапу роботи Керівник роботи Донець Георгій Панасович, Дата реєстрації 18-01-2012 Організація виконавець Iнститут кібернетики ім. В. М. Глушкова НАНУ Опис етапу Розроблені теоретичні основи для створення типових паралельних алгоритмів на графах різної природи, які забезпечують високий рівень швидкодії. Уперше запропонована така нумерація вершин графів, яка призводить до нового представлення графів у вигляді спеціального математичного об'єкту під назвою числовий граф. Створена математична модель для комбінаторної побудови на площині малюнка графа і розроблений на її основі обчислювальний алгоритм. Для довільних числових графів розроблений поліноміальний алгоритм визначення хроматичного числа. Розглянуті способи паралельної реалізації алгоритмів на графах на прикладі задачі пошуку найкоротших шляхів між усіма парами пунктів призначення і задачі виділення мінімального дерева (остову графа), що охоплює. Запропоновані алгоритми можуть бути використані при створенні автоматизованих систем проектування великих інтегральних схем, систем синтезу машинобудівних деталей, в системах управління різними галузями народного господарства, в економіці, в автоматизованих системах банківського обліку. Опис продукції Розроблені теоретичні основи для створення нових паралельних алгоритмів на графах великого об'єму. Створені нові математичні графові моделі та нові алгоритми оптимізації на графах з паралельним виконанням розрахунків. Автори роботи Білецький В.І. Богданюк В.М. Вовк Л.Б. Гуленко О.В. Давиденко С.О. Желіховський О.А. Кікоть Г.Ф. Карпець Е.П. Кузьменко В.М. Лазебна Т.О. Ненахов Е.І. Омельченко Т.П. Панасенко С.В. Петренюк Д.А. Чикрій Г.Ц. Чоломбитько В.І. Чоломбитько Н.П. Шулінок І.Е. Яценко М.В. Додано в НРАТ 2020-04-02 Закрити