Эффективно вычислимые оценки надежности монотонных систем
Диссертация
Проведены численные сравнения оценок надежности монотонных систем (оценок Эзари-Прошана, развязочно-антиблокирующих оценок, разностно-развязочно упаковочных оценок, оценок Оксли-Уэлша). Результаты сравнения свидетельствуют о превосходстве развязочно-антиблокирующих оценок над оценками Эзари-Прошана, разностно-развязочно упаковочных над упаковочными оценками и оценками Оксли-Уэлша. Среди оценок… Читать ещё >
Содержание
- Предмет исследования
- Цель диссертационной работы
Список литературы
- Вероятность и математическая статистика. Большая Русская Энциклопедия. Москва, 1999, стр. 345−346.
- Богатырёв В.А. К расчёту надёжности сети связи по совокупности путей. Электросвязь, 1981, № 2, стр. 42−44.
- Гадасин В.А., Ушаков И. А. Надежность сложных информационно-управляющих систем. М.: Сов. Радио, 1975.
- Гнеденко Б.В., Беляев Ю. К., Соловьев А. Д. Математические методы в теории надежности. М.: Наука, 1965.
- Давыдов Г. Б., Рогинский В. Н., Толчан А. Я. Сети электросвязи. М.: Связь, 1978.
- Дудник Б.Я., Орлов В. К., Филин Б. П., Холин А. В., Шурмин А. В. Надёжность и живучесть систем связи, М.: Радио и связь, 1984.
- Кельманс А.К., Ломоносов М. В., Полесский В. П. О минимальных покрытиях в матроиде. Проблемы передачи информации, 1976, том 29, № 4, стр. 58−66.
- Кельманс А.К., Полесский В. П. Экстремальные множества и задачи покрытия и упаковки в матроидах. В кн.: Исследования по прикладной теории графов, Новосибирск: Наука, Сиб. отд., 1986, стр. 140−188.
- Кривулец В.Г., Полесский В. П. Об оценках надежности монотонной структуры. Проблемы передачи информации, 2001, том 37, № 4, стр. 112−129.
- Кривулец В.Г., Полесский В. П. Квазиупаковочные оценки характеристик надежности сетей. Информационные Процессы, 2001, том 1, N2 2, стр. 126−146.
- Малашенко Ю.Е., Рогожин B.C., Ферапонтов Е. В. Живучесть сетевых систем. Препринт ВЦ АН СССР, М. 1989.
- Мур Э.Ф., Шеннон К. Э. Надежные схемы из ненадежных реле. Киб.Сб. 1960. № 1. Изд-во Иностр. Лит-ры. Москва, стр. 109−148.
- Мизин И.А., Кулешов А. П., Богатырёв В. А. Сети коммутации пакетов. М.: Радио и связь, 1986.
- Надежность и эффективность в технике. Справочник в десяти томах (под ред. Б.В.Гнеденко). М., Машиностроение, 1987, том 2.
- Надежность технических систем: справочник. Под ред. И. А. Ушакова. М.: Радио и связь, 1985. (английский перевод: Handbook of Reliability Engineering. New-York: John Wiley Sons. Inc., 1994.)
- Полесский В.П. Об одном способе построения структурно-надежной сети. В кн.: Дискретные автоматы и сети связи. М.: Наука, 1970, стр. 13−19.
- Полесский В.П. Оценки вероятности связности случайного графа. Проблемы Передачи Информации, 1990, том 26, Я2 1, стр. 90−98.
- Полесский В.П. Достижимые границы вероятности полного ранга случайного подматроида. Проблемы передачи информации, 1995, том 31, № 4, стр. 81−99.
- Полесский В.П. Развязывания клаттеров, корреляционные неравенства и границы комбинаторной надежности. Проблемы передачи информации, 1997, том 33, № 3, стр. 50−70.
- Полесский В.П. Развязывание носителей семейства клаттеров и его роль в теории надежности. Проблемы передачи информации, 2001, •том 37, № 2. стр. 62−76.
- Самойленко С.Н., Давыдов А. А., Золатарев В. В., Третьякова Е. И. Вычислительные сети (адаптивность, помехоустойчивость, надежность). М.: Наука, 1981.
- Райншке К., Ушаков И. А. Оценка надежности систем с использованием графов. М.: Радио и связь, 1988.
- Рогинский В.Н., Богатырёв В. А. К расчёту структурной надёжности связей в сети. Процессы и устройства управления в сетях связи. М.: Наука, 1982.
- Ушаков И.А., Гадасин В. А. Анализ надежности структурно-сложных систем. М.: Знание, 1979.
- Филин Б.П. Методы анализа структурной надёжности сетей связи. М.: Радио и связь, 1988.
- Ball М.О., Provan J.S. Computing k-Terminal Reliability in Time Polynomial in the Number of (s, t)-Quasicuts. Fourth Army Conference on Applied Mathemathics and Computing. Washington: Army Research Office, pp. 901−907.
- Ball M.O., Van Slyke R.M. Backtracking algorithms for network reliability analysis. Annals of Discrete Mathematics, 1977, vol. 1, pp. 49−64.
- Ball M.O., Nemhauser G.L. Matroids and reliability analysis. Math. Operations Res. 1979, vol. 4, no. 2, pp. 132−143.
- Ball M.O. Computing Network Reliability. Operations Research, 1979, vol. 27, no. 4, pp. 823−838.
- Ball M.O., Provsn J.S. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Computing, 1983, vol. 12, pp. 777−788.
- Ball M.O., Colbourn C.J., Provan J.S. Network Reliability. In: Handbooks in OR and MS. Chapter 11. New York: Elsevier, 1995,
- Barlow R.E., Proschan F. Mathematical Theory of Reliability. New York: Wiley, 1965. (русский перевод: Барлоу P., Прошан Ф. Математическая теория надежности. М.: Сов. радио, 1969.)
- Barlow R.E., Proschan F. Statistical Theory of Reliability and Life Testing, to Begin With. Md: Silver Spring. 1981. (русский перевод: Барлоу P., Прошан Ф. Статистическая теория надежности и испытания на безотказность. М.: Наука, 1984.)
- Barlow R.E. Mathematical Theory of Reliability: A Historical Perspective. IEEE Transaction on Reliability, 1984, vol. 33, no. 1, pp. 16−20.
- Beineke L.W. Exploration into graph vulnerability. Technical Report. Dept. of Math. Sciences, Indiana Univ. Purdue Univ. 1990.
- Birnbaum Z.W., Esary J.D., Saunders S.C. Multicomponent Systems and Structures and Their Reliability. Technometrics, 1961, no. 1, pp. 55−77.
- Brecht Т.К., Colbourn C.J. Lower Bounds for Two-Terminal Network Reliability. Discr. Appl. Math, 1988, vol. 21, pp. 185−198.
- Colbourn C.J. The Combinatorics of Network Reliability. Oxford: Oxford Univ. Press, 1987.
- Colbourn С. J. Edge-Packings of Graphs and Network Reliability. Discrete Mathematics, 1988, vol. 72, pp. 49−61.
- Colbourn C.J., Nel L.D. Using and Abusing for Network Reliability. Proc. IEEE Telecommunications Conference Globecom90, IEEE Press, 1990, pp. 663−667.
- Chernyak A.A., Chernyak Zh.A. Note on complexity of Comuting Domination of Binary Systems. Discrete Applied Math, 1997, vol. 73, no. 3, pp. 289−295.
- Dotson W.P., Gobien J.O. A new analysis technique for probabilistic graphs. IEEE Trans. Circuits and Systems, 1979, vol. CAS-26, no. 10, pp. 855−865.
- Edmonds J., Fulkerson D.R. Bottleneck extrema. J. Combinatorial Theory, 1970, vol. 8, pp. 299−306.
- Edmonds J. Submodular Functions, Matroids and Certain Polyhedral. In: Combinatorial Stuctures and Their Applications. New York: Gordon and Breach, 1970, pp. 69−81.
- Edmonds J. Edge-Disjoint Branching. In: Combinatorial Algorithms. Algo-rithmics Press, 1972, pp. 91−96.
- Esary J., Proschan F. Coherent Structures of Non-Identical Components. Technometrics, 1963, vol. 5, no. 2, pp. 191−209.
- Fratta L., Montanari U.G. A Boolean algebra method for computing the terminal reliability in a communication network. IEEE Transactions on Circuit Theory, 1973, vol. CT-20, pp. 203−211.
- Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San-Francisco: W.H.Freeman, 1979. (русский перевод: Гэри M., Джонсон Д. Вычислительные машины и трудноре-шаемые задачи. М.: Мир, 1982.)
- Grimmett G.R. Percolation Theory. Second edition. A Series of Comprehensive Studies in Math. Berlin: Springer, 1999.
- Hansler E., McAuliffe G.K., Wilkov R.S. Exact calculation of computer network reliability. Networks, 19 974, vol. 4, pp. 85−112.
- Huseby A.B. Domination Theory and Crapo b-Invariant. Networks, 1989, vol. 19, pp. 135−149.
- Huseby A.B. On reguality, amenability and optimal factoring strategies for reliability computations. Preprint, Univ. of Oslo.
- Jensen P.A., Bellmore M. An algorithm to determine the reliability of a complex system. IEEE Transactions on Reliability, 1969, vol. R-18, pp. 169−174.
- Karger D.R. A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability Problem. Proceedings of the 37th Annual Symposium on the Foundations of Computer Science, 1996, pp. 113.
- Katona G. A theorem of finite sets. In: Theory of graphs. Budapest: Akademia Kiado, 1966, pp. 187−207.
- Krivoulets V.G., Polesskii V.P. What is the theory of bounds for network reliability? Information Processes, 2001, vol. 1, no. 2, pp. 199−203.
- Krivoulets V.G., Polesskii V.P. Monotone structures. The best possible bounds of their reliability. Information Processes, 2001, vol. 1, no. 2, pp. 188−198.
- Kruskal J.B. The number of simplices in a complex. Mathematical Optimization Techniques, California: University of California Press, 1963, pp. 251— 278.
- McDiarmid C. Clutter Percolation and Random Graphs. Mathematical Programming Study, 1980, vol. 13, pp. 17−25.
- McDiarmid C. General Percolation and Random Graphs. Adv. Appl. Prob, 1981, vol. 13, pp. 40−60.
- Moore E.F., Shannon C.E. Reliable circuits using less reliable relays, J. Franklin Inst., 1956, pp. 262, no. 3, pp. 191−208- no. 4, pp. 281−297.
- Moskowitz F. The analysis of redundancy networks. IEEE Trans. Com-mun. Electron. 1958, vol. 39, pp. 627−632.
- Moran S. An Improvement of an Algorithm for Construction of Edge-Disjoint Branching. Technical Report, Haita, 1984.
- Mine H. Reliability of physical systems. IRE Trans. Circuit Theory, 1959, vol. CT-6, pp. 138−151.
- Nel L.D., Strayer N.J. Two-Terminal Reliability Bounds Based on Edge-Packing by Cutsets. J. Comb. Math. Comb. Comut., 1993, vol. 13, pp. 3−22.
- Nelsen A.C., Baths J.R., Beaadles R.L. A computer program for approximation system reliability. IEEE Transactions on Reliability, 1970, vol. R-19, pp. 61−65.
- Oxley J.G., Welsh D.J.A. On Some Percolation Results of J.M. Hammers-ley. J. Appl. Prob., 1979, vol. 16, pp. 527−540.
- Oxley J.G., Welsh D.J.A. The Tutte Polynomial and Percolation. Graph Theory and Related Topics, 1979, pp. 329−339.
- Polesskii V.P., Krivoulets V.G. Efficiently computable bounds on stochastic monotone binary system reliability. Proceedings of 3d conferences on Mathematical Methods in Reliability. Trondheim, Norway, 2002, to appear.
- Provan J.S., Ball M.O. Computing Networks Reliability in Polynomial Time in the Number of Cuts. Operation Research, 1984, no. 32, pp. 516 526.
- Provan J.S. Polyhedral combinatorics and network reliability. Math. Oper. Res., 1986, vol. 11, no. 3, pp. 36−61.
- Rai S. A cutset approach to reliability evaluation in communication networks. IEEE Transactions on Reliability, 1982, vol. R-31, pp. 428−431.
- Ramanathan A., Colbourn C.J. Bounds of All-Terminal Reliability via Arc-Packing. Ars Combinatorica, 1987, vol. 23A, pp. 91−94.
- Raman V. Finding the Best Edge-Packing for Two-Terminal Reliability is NP-hard. J. Comb. Math. Comb. Comput., 1991, vol. 9, pp. 91−96.
- Reliability of computer and communication networks. Proc. of the DIMACS Workshop on Reliability at Rutgers University, 1989, AMS Publication.
- Resende L.I.P. A program for reliability evaluation of underected networks via polygon-to-chain reductions. IEEE Transactions on Reliability, 1986, vol. R-35, pp. 24−29.
- Resende L.I.P. Implementation of a factoring algorithm for reliability evaluation of undirected networks. Annals of Discrete Mathematics, 1988, vol. 33, pp. 261−273.
- Ross S.M. Introduction to probability models. New York: Academic Press Inc., 1985.
- Satyanarayama A., Prabhaker A. New Topological Formula and Rapid Algorithm for Reliability Analysis of Comlex Networks. IEEE Trans, on Reliability, 1978, vol. 27, pp. 82−100.
- Satyanarayana A., Hagstrom J.N. A new algorithm for the reliability analysis of multi-terminal networks. IEEE Transactions on Reliability, 1982, vol. R-30, pp. 325−334.
- Satyanarayana A., Hagstrom J.N. Combinatorial properties of directed graphs useful in computing reliability. Networks, 1981, no. 11, pp. 357−366.
- Satyanarayana A. A unified formula for analysis of some network reliability problems. IEEE Transactions on Reliability, 1982, vol. R-31, pp. 23−32.
- Satyanarayana A., Chang M.K. Network Reliability and the Factoring Theorem. Networks, 1983, no. 13, pp. 107−20.
- Shier D.R. Network Reliability and Algebraic Structures. Oxford: Claredon Press, 1991.
- Материалы диссертации вошли в отчет по первому этапу НИР.
- Зам. директора ИПИ РАН д.ф.-м.н.1. С.Я. Шоргин
- Научный руководитель НИР гл. научн. сотр., д.ф.-м.н., проф1. А.В. Печинкин1. АКТ
- Центрального научно-исследовательского института связи Министерства связи РФ о внедрении научных результатов Кривульца Виктора Григорьевича
- В данной НИР для оценки устойчивости ВСС РФ были использованы методы анализа устойчивости сетей связи.
- Начальник лаборатории ЦНИИ ^ Н.А.Аверин
- С Н С лаборатории ЦНИИС —Л.И.Борисов