ПЕРЕВОД ОЦЕНОК ЭЗАРИ-ПРОШАНА ИЗ КЛАССА NP-ПОЛНЫХ В ИНТЕЛЛЕКТУАЛЬНЫЙ КЛАСС (IN-КЛАСС)
Аннотация
В работах [1-2] показано, что широко известные оценки Эзари-Прошана [3] (ОЭП) являются -полными [4]. В процессе их вычисления происходит взаимное перекрещивание этих оценок, несмотря на то, что процедура перечисления полных множеств простых цепей (ПЦ) и простых разрезов (ПР) выполняется до конца. Эта картина подтверждается и специальными исследованиями этих парадоксальных явлений в ОЭП, проведенными в работе [5], где был сделан вывод о том, что ОЭП - это никакие не оценки, поскольку оценки не могут быть -полными. Ведь, в [3] прямо говорится о том, что в общем случае только одно лишь перечисление полного множества ПЦ (или ПР) уже есть -полная задача. То есть любой -полный метод не может быть оценочным.
В данной статье приводятся формальные правила, которые позволяют достаточно просто классические оценки Эзари-Прошана перевести из класса -полных в класс интеллектуальных (-класс) оценочных методов.
Об авторах
Александр Геннальевич ЛабутинРоссия
Магистрант Московского технического университета связи и информатики
Борис Петрович Филин
Россия
Доктор технических наук
Список литературы
1. Кривулец В.Г. Об оценке оценок Эзари-Прошана в задачах анализа структурной надежности сетей связи // Труды 55-й Научной сессии, посвященной дню Радио / РНТОРЭС им. А.С.Попова. 2000.1 л.
2. Филин Б.П. О предельном развязывании клаттеров в оценках Полесского границ комбинаторной надёжности случайных бинарных систем // Автоматика и телемеханика. 2005. № 9. С. 149-189.
3. Esary J., Proshan F. Coherent Structures of Non-Identifical Components // Technometrics. 1963. V. 5. № 2. P. 191-209.
4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
5. Лабутин А.Г., Филин Б.П. Об уклонении от NP-полноты в оценках Эзари-Прошана // Автоматика и телемеханика. 2017 (в печати).
6. Гадасин В.А. Триада субстанций в микромире «Корпускула — Случайность — Волна». Сборник статей ВНИИ ПВТИ, 2005.
7. Гадасин В.А. Аксиоматика концепции триад – трёхмерная группа // Труды XV-й международной конференции «Проблема безопасности сложных систем». М.: ИПУ РАН. 2007. С. 64-70.
8. Райншке К., Ушаков И.А. Оценка надежности систем с использованием графов. М.: Радио и связь, 1988.
9. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974.
10. Вентцель Е.С. Теория вероятностей. М.: Наука, 1964.
11. Носов М.В. Метод полного разложения мостиковых соединений в задачах анализа связности структурно-сложных двухполюсных сетей // Надёжность. 2015. № 4. С. 68-74.
12. Филин Б.П. Методы анализа структурной надежности сетей связи. М.: Радио и связь, 1988.
13. Филин Б.П. Метод последовательного старта в определении простых сечений (печ.) / Деп. в ЦИВТИ, 07.07.1977г., № Д 2908 Н.
14. Бураченко В.А., Колесников А.Н., Коржик В.И., Финк Л.М. Общая теория связи. Л.: Военная Краснознамённая Академия связи им. Маршала Советского Союза С.М. Будённого, 1970.
15. Давыденко В.П., Лоскутов Н.Г., Иванов Л.Т. Основы военной кибернетики. Л.: Военная Краснознамённая Академия связи им. Маршала Советского Союза С.М. Будённого, 1971.
16. Богатырев В.А. К расчету надежности сетей связи по совокупности путей // Электросвязь. 1981. № 2. С. 42-44.
17. Филин Б.П. О принципе дуальности в задачах анализа структурной надежности сложных систем // Автоматика и телемеханика. 1989. № 6. С. 158-172.
Для цитирования:
Лабутин А.Г., Филин Б.П. ПЕРЕВОД ОЦЕНОК ЭЗАРИ-ПРОШАНА ИЗ КЛАССА NP-ПОЛНЫХ В ИНТЕЛЛЕКТУАЛЬНЫЙ КЛАСС (IN-КЛАСС). Надежность. 2017;17(3). https://doi.org/10.21683/1729-2646-2017-17-3-
Послать статью по эл. почте 