КАНАЄВА Н. М. Дослідження локальних алгоритмів розв'язання блочних задач булевого програмування.

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