Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Топ:
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Интересное:
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Дисциплины:
2017-11-27 | 640 |
5.00
из
|
Заказать работу |
Пусть дано n -множество элементов S и N- множество свойств p 1,…, pN. Элементы множества S могут как обладать, так и не обладать любым из свойств pi. Количество элементов, обладающих теми или иными свойствами и их комбинациями, известно.
Требуется найти число элементов, не обладающих ни одним из свойств.
Обозначим:
1) через некоторую i -ю выборку свойств, а через – число элементов, каждый из которых обладает всеми этими r выбранными свойствами.
2) через – отсутствие у элемента свойства pi. Тогда, например, – число элементов, обладающих свойствами p 1 и p3 и не обладающих свойствами p2 и p4.
Рассмотрим два частных случая.
1. Имеется лишь одно свойство p. Тогда очевидно, что число элементов, не обладающих свойством p, равно общему числу элементов минус число элементов, обладающих свойством p. .
2. Имеется конечное множество свойств p 1,…, pN, но они не совместимы (т.е. ни один из элементов не может обладать более чем одним свойством). Тогда число элементов, не обладающих ни одним из свойств, равно общему числу элементов минус число элементов, обладающих свойством p 1, минус число элементов, обладающих свойством p 2 и т.д.
.
Общий случай – элементы могут обладать комбинацией совместимых свойств.
Теорема. Если даны n -множество элементов S и N свойств pi , то число элементов, не обладающих ни одним из свойств, равно (формула решета):
n n (p 1) n (p2) n (p3) |
Рассмотрим доказательство при N =3.
Обозначим кругами подмножества элементов, обладающих хотя бы свойством p 1, хотя бы свойством p 2 и хотя бы свойством p 3. Тогда пересечения двух кругов будут давать подмножество элементов, обладающих хотя бы двумя свойствами одновременно, а пересечение всех трех кругов дает подмножество элементов, обладающих всеми тремя свойствами. Прямоугольник, в котором расположены круги, обозначает все множество S, содержащее n элементов. Нужно найти количество элементов, не обладающие ни одним из трёх свойств (за пределами кругов).
Чтобы найти это число, нужно из n -множества исключить элементы, обладающие свойством p 1, затем обладающие свойством p2, затем – p3, т.е. вычесть . Однако при этом элементы, обладающие двумя свойствами (например, p 1 и p2), окажутся исключёнными дважды (сначала как элементы, обладающие свойством p 1, затем как обладающие p2). Следовательно, нужно возвратить по одному разу элементы, исключённые дважды, т.е. добавить . Но при этом элементы, обладающие сразу тремя свойствами (p 1, p2, p3), сначала были трижды исключены как элементы, обладающие по отдельности свойствами p 1, p2 или p3, а затем трижды включены как обладающие парами свойств. Поэтому их нужно один раз исключить, т.е. вычесть . Рассуждая подобным образом, получаем алгоритм, который состоит в попеременном включении и отбрасывании подмножеств, дающий приведенную выше формулу решета.
Следствие. Характер доказательства таков, что его можно применять к любой комбинации свойств. Например,
.
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!