Полная версия

Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ПЕРЕЧИСЛЕНИЕ ПРОСТЕЙШИХ КОМБИНАТОРНЫХ ОБЪЕКТОВ

ЗАДАНИЕ 1 Множества: представления и операции

Рассматривается машинное представление конечных множеств в виде битовых шкал. Цель задания: практика программирования теоретико-множественных операций и отношений между множествами, заданными битовыми шкалами.

Основные понятия и обозначения

В окружающей действительности существуют как отдельные объекты, так и их совокупности, или множества. Например, имеется отдельная почтовая марка и коллекция марок, произведение А. С. Пушкина «Евгений Онегин» и полное собрание сочинений этого писателя, число 5 и совокупность всех натуральных чисел.

Под множеством X обычно понимается любая совокупность определенных и различимых между собой объектов, мыслимая как единое целое. Эти объекты называются элементами множества X.

Символом е обозначается отношение принадлежности. Запись х е X означает, что элемент х принадлежит множеству X. Если элемент х не принадлежит множеству X, то пишут х & X.

Если множество состоит из конечного числа элементов, то оно называется конечным множеством, а в противном случае - бесконечным. Конечные множества можно описывать, перечисляя их элементы. Элементы, принадлежащие конечному множеству, записывают между двумя фигурными скобками через запятую. Гораздо чаще множества задаются посредством указания характеристического свойства - признака, которому удовлетворяют элементы этого множества, и только они. Для такого задания обычно используются фигурные скобки, внутри которых приводится характеристическое свойство. Так, множество {1, 2, 3, 4, 5} можно определить следующим образом: {х х е Z+ и 1 < х < 5}, где Z+- множество целых неотрицательных чисел.

Отношение включения между множествами А и В обозначается через А ей. Оно означает, что каждый элемент множества А есть элемент множества В. В данном случае говорят, что А - это подмножество множества В. Если в А существует элемент, не принадлежащий В, то А не является подмножеством множества В (А с: В).

Пусть А и В некоторые множества. Множества А к В равны (А = В), если для любого Jt имеем: х е А тогда и только тогда, когда х е В. Другими словами, А= В тогда и только тогда, когда А с В и В с А. Если А а, В и Аф В, то записывают A czB и отмечают, что множество А есть собственное подмножество множества В.

Поскольку множество однозначно задается своими элементами, то порядок их перечисления не играет роли. Кроме того, любой элемент может входить во множество не более одного раза.

Множество, не содержащее элементов, называется пустым и обозначается 0. Пустое множество - подмножество любого множества.

Обычно уже в самом определении конкретного множества явно или неявно ограничивается совокупность допустимых объектов. Например, если речь идет о множестве чисел, делящихся на 3, то ясно, что оно является подмножеством множества целых чисел. Целесообразно совокупность допустимых объектов зафиксировать явным образом и считать, что все рассматриваемые множества являются подмножествами этой совокупности -универсального множества.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>