Реєстраційний номер
0400U001302, Кандидатська дисертація
На здобуття
к.ф.-м.н.
Дата захисту
27-04-2000
Статус
Захищена
Назва роботи
Дослідження локальних алгоритмів розв'язання блочних задач булевого програмування.
Здобувач
КАНАЄВА Наталія Миколаївна,
Керівник ЩЕРБИНА Олег Олександрович
Опонент ЄМЕЦЬ Олег Олексійович
Опонент ГРЕБЕННIК Ігор Валерійович
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Дніпропетровський державний університет
Опис
Об'єктом дослідження є обчислювальна складність локальних алгоритмів розв'язання блочних і квазіблочних задач булевого програмування. Мета дослідження - візначення середніх оцінок обчис-лювальної складності локального алгоритму, визна-чення найкращих та найгірших структур задач. Методи дослідження - методи комбінаторного аналізу, теория мажоризації, теорія обчіслювальної складності, обчислювальний експерімент. Показано, що локаль-ний алгоритм є особистім випадком метода послідовного аналізу варіантів В.С.Михалевича-Н.З.Шора. Показано, що локальний алгоритм є алго-ритмом з квазіекспоненційною оцінкою обчислюваль-ної складності. Визначені блочна і квазіблочна струк-тури, відповідні найкращому і найгіршому застосуван-ню ЛА.
Дата реєстрації
2000-05-23
Додано/оновлено в НРАТ
2020-04-05 / 2026-06-30