Search academic texts

Information × Registration Number 0496U000781, Candidate dissertation Status к.ф.-м.н. Date 26-04-1996 popup.evolution o Title Author Павлова Людмила Александровна, popup.head Асельдеров З.М. popup.opponent Шор Н.З. popup.opponent Белецкий П.М. Description Объект исследования: Труднорешаемые задачи комбинаторной оптимизации. Цель исследования: Создание нового подхода к разработке точных алгоритмов для труднорешаемых комбинаторных задач и исследование его эффективности. Методы исследования и аппаратура: Базируются на понятиях и результатах теории алгоритмов, теории графов. теории расписаний и методов дискретной оптимизации. Теоретические результаты и новизна: 1.Введено понятие ПДС-алгоритма для труднорешаемой комбинаторной задачи и предложена оценка его эффективности. 2.Разработаны ПДС-алгоритмы для задач "Максимальное независимое множество" и "Минимизация суммарного взвешеного момента окончания работ". Практические результаты и новизна: Определены ограничения на параметры задач "Максимальное независимое множество" и "Минимизация суммарного взвешенного момента окончания работ", при выполнении которых полиномиальная составляющая их ПДС-алгоритмов является эффективной. Предмет и степень внедрения: ПДС-алгоритмы на этапе создания опытных образцов. Эффективность внедрения: Разработанные ПДС-алгоритмы могут быть использованыдля получения точного решения задач Максимальное независимое множество, Минимизация суммарного взвешенного момента окончания работ, Выполнимость, Клика, вершинное Покрытие, Разбиение на клики, Хроматическое число, Гамильтонов цикл, Гамильтонов путь. Сфера (область) использования: Информатика, исследование операций, современная теория управления, экономическая кибернетика, прикладная и вычислительная математика. Registration Date 1996-04-26 popup.nrat_date 2020-05-17 Close