Метод включения-исключения.
Информационные системы и технологии.
Теория надежности
Для вычисления размера (числа элементов, кардинального числа) объединения нескольких множеств требуется просуммировать размеры этих множеств по отдельности, затем вычесть размеры всех попарных пересечений этих множеств, прибавить обратно размеры пересечений всевозможных троек множеств, вычесть размеры пересечений четверок и т. д., вплоть до пересечения всех множеств. Результаты оценки надежности… Читать ещё >
Метод включения-исключения. Информационные системы и технологии. Теория надежности (реферат, курсовая, диплом, контрольная)
При решении задач комбинаторного анализа, теории вероятностей и теории надежности в ряде случаев эффективно используется комбинаторный принцип включения-исключения, суть которого заключается в следующем 11, 4).
Для вычисления размера (числа элементов, кардинального числа) объединения нескольких множеств требуется просуммировать размеры этих множеств по отдельности, затем вычесть размеры всех попарных пересечений этих множеств, прибавить обратно размеры пересечений всевозможных троек множеств, вычесть размеры пересечений четверок и т. д., вплоть до пересечения всех множеств.
Таким образом, принцип включения-выключения формулируется следующим образом:
Принцип включения-исключения иллюстрируется с помощью диаграмм Вениа.
Пусть диаграммой Веина на рис. 5.19 представлена пересекаемость трех множеств А, В, С.
Рис. 5.19. Диаграмма Венна пересечения трех множеств Тогда площадь объединения А и В С равна сумме площадей А, В, С, и за вычетом дважды покрытых площадей А п В, А гг С, В п С, но с прибавлением трижды покрытой площади А п В n С:
Приведем формулировку метода включения-исключения, ориентированную на вычисление вероятностей.
Пусть Л, — события, Р (Л;) — их вероятности, тогда вероятность их объединения (т.е. того, что произойдет хотя бы одно из этих событий) равна.
В соответствии с принципом включения-исключения вероятность работоспособности мостиковой схемы на основе учета пересекаемости минимальных путей.
А на основе минимальных сечений.
В случае равной надежности элементов при оценке по принципу включения-исключения на основе минимальных путей имеем.
А на основе сечений.
Результаты оценки надежности мостиковой схемы по методу включения-исключения для путей при X = 10 4 ч-1 представлены на рис. 5.20, а для сечений — на рис. 5.21. На рис. 5.21 кривые 1—4 соответствуют первому, второму, третьему и четвертому приближению (точная оценка). Из графиков видно увеличение точности при увеличении шага приближения.
Рис. 5.20. Оценка надежности Рис. 5.21. Оценка надежности мостиковой схемы, но методу мостиковой схемы, но методу включения-исключения для путей включения-исключения для сечений.