Search academic texts

Information × Registration Number 0400U001302, Candidate dissertation Status к.ф.-м.н. Date 27-04-2000 popup.evolution o Title Research Local Algorithm for Decision of Boolean Programming Block Problems. Author KANAYeVA Nataliya Mykolayivna, popup.head ЩЕРБИНА Олег Олександрович popup.opponent ЄМЕЦЬ Олег Олексійович popup.opponent ГРЕБЕННIК Ігор Валерійович Description Об'єктом дослідження є обчислювальна складність локальних алгоритмів розв'язання блочних і квазіблочних задач булевого програмування. Мета дослідження - візначення середніх оцінок обчис-лювальної складності локального алгоритму, визна-чення найкращих та найгірших структур задач. Методи дослідження - методи комбінаторного аналізу, теория мажоризації, теорія обчіслювальної складності, обчислювальний експерімент. Показано, що локаль-ний алгоритм є особистім випадком метода послідовного аналізу варіантів В.С.Михалевича-Н.З.Шора. Показано, що локальний алгоритм є алго-ритмом з квазіекспоненційною оцінкою обчислюваль-ної складності. Визначені блочна і квазіблочна струк-тури, відповідні найкращому і найгіршому застосуван-ню ЛА. Registration Date 2000-04-27 popup.nrat_date 2020-04-04 Close