§1. Основные понятия теории множеств
ИнфоКонсалтинг
Образовательный сервис


Новости сайта

02.10.2017 С наступающим Днём Учителя, дорогие наши учителя!

24.08.2017 Успейте подобрать репетитора на новый учебный год! Это можно сделать на соответствующей странице нашего сайта, притом по любому предмету, в любом городе России и с учётом индивидуальных требований.

Сервис предоставлен Ассоциацией репетиторов.

Найти репетитора

Отправить заявку

24.08.2017 Страницы сайта переиндексированы для системы поиска ИнфоКонсалтинг.

Поиск по нашему сайту

04.10.2016 В разделе "К экзамену" появилось решение задачи 23 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 23 демо-версии 2017 г. по информатике

04.10.2016 В разделе "К экзамену" появилось решение задачи 26 демо-версии КИМ ЕГЭ по информатике от 2017 г.

Задача 26 демо-версии 2017 г. по информатике


§1. Основные понятия теории множеств


Perfect Money

§1. Основные понятия теории множеств

В процессе изучения сути вероятностного подхода к оценке количества информации (см. §28, §29, §30 раздела "Введение в информатику") можно убедиться, что вероятность совершения события и количество получаемой наблюдателем информации при возникновении конкретного события очень зависят от количества самих событий набора. Недаром в §30 раздела "Введение в информатику" расчёту числа событий набора было отведено так много места. Настоящая тема не станет исключением. В ней мы рассмотрим, как количество возможных событий набора связано со способом создания этого набора, формирующегося путём осуществления некоторых операций с другими наборами событий за счёт их сходств и различий.

Основным термином рассматриваемой темы является множество. Сразу заметим, что понятия множество и набор являют собой одно и то же.

    • Математический термин множество переводится на английский язык словом set, — точно так же, как и слово набор.

    • Множество — основное понятие теории множеств. Этим термином объединяются все уникальные отдельные (дискретные) элементы, выбранные согласно некоторому критерию. Количество элементов множества в общем случае далеко не всегда выражается конечным числом.

      Теория множеств — раздел дискретной математики (см. §1 темы "Системы счисления"), в котором рассматриваются множества, их свойства, операции над ними.

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

      Множество не может содержать два полностью совпадающих события (или — две совпадающие точки). Элементы множества должны чем-то различаться и, тем самым, быть уникальными. При наличии двух и более совпадающих элементов считается, что они представляют собой один и тот же элемент.

Возможна ситуация, при которой множество не содержит ни одного элемента. От этого оно не перестаёт считаться множеством, ведь в основе этого понятия — признак общности!

    • Пустое множество (обозначается символом ∅) — множество, в составе которого нет ни одного элемента.

Элементы множества показывают в фигурных скобках: перечислением или записью, из которой видна математическая зависимость принадлежности элементов множеству. Если элемент принадлежит множеству, это демонстрируется записью, аналогичной (1.1):

(1.1)
Принадлежность элемента множеству
(1.1)

Записи о составе множеств можно увидеть из Примеров 1, 2 и 3.

  • 1

    • Решение задачи Примера 1 из §28 раздела "Введение в информатику" можно интерпретировать следующим образом. Пусть используются следующие обозначения цветов сигналов светофора: К — красный, З — зелёный, М — мигающий зелёный. Для оценки вероятности возможности немедленного перехода в приведённом решении было использовано множество событий A = {К, З, М}. Это множество событий A можно назвать (в "переводе на русский язык" с языка математики) "возможными событиями, заключающимися в реакции на сигнал светофора" (категорически не "возможными сигналами светофора", ведь в задаче спрашивается о реакции пешехода — возможности перехода проезжей части). Естественно, из этой записи следует, что К ∈ A, З ∈ A, М ∈ A.

      Однако было бы правильнее проявить более реалистичный подход и к формулировке задачи, и её решению. Если бы в исходной задаче присутствовало условие, по которому светофор может не работать с некоторой ненулевой вероятностью и этот факт приводил бы к невозможности принятия решения о переходе проезжей части на основе его сигналов, то наше множество возможных событий состояло из следующих элементов: A = {К, З, М, ∅}.

    • Логично определять пустое множество элементом другого множества, ведь оно подразумевает под собой возможное событие, заключающееся в отсутствии действий! Это событие имеет вероятность, отличную от нуля (иначе вообще нет смысла определять его событием множества, как и любое другое, невозможное к осуществлению, т. е. обладающее нулевой вероятностью).

    • Обозначения ∅ и {∅} указывают на совершенно разные ситуации. Пустое множество ∅ есть событие, заключающееся ни в чём. Запись же {∅} означает, что единственным следствием какого-либо действия (выбора набора, обозначенного фигурными скобками) есть ничто (или по-другому: факт совершения события не может привести ни к каким последствиям).

  • 2

    • Игральная кость с нанесёнными на её грани обозначениями чисел от 1 до 6 подбрасывается 5 раз. Множество событий A, состоящих в выпадении всех чисел в результате всех бросаний кости, можно описать одним из двух способов.

      1) Пусть имеет значение, на каком по счёту бросании (из пяти возможных) какое число выпало. Тогда описание множества принимает вид A = {ωω = (a1, …, an), ai ∈ {1, …, 6}, n = 5}, где ω — очередной элемент множества A, содержащий упорядоченный (поскольку в круглых скобках) набор чисел, выпавших при каждом из пяти бросаний кости.

      2) Пусть не имеет никакого значения, на каком по счёту бросании какое число выпало, но важны сами числа (например, для последующего подсчёта общей их суммы как единственного имеющего смысл следствия таких бросаний). Тогда описание множества принимает вид A = {ωω = [a1, …, an], ai ∈ {1, …, 6}, n = 5}, где ω — очередной элемент множества A, содержащий все выпавшие числа без учёта порядка их выпадения — неупорядоченный набор (поскольку в квадратных скобках).

  • 3

    • Игральная кость с нанесёнными на её грани обозначениями чисел от 1 до 6 подбрасывается n раз (n < 6), причём если при очередном бросании выпадает ранее выпавшее число, то бросание считается не реализованным и кость перебрасывается до тех пор, пока не выпадет число, отличное от любого из полученных таким способом ранее. Не имеет никакого значения, на каком именно бросании какое число выпало. Множество событий A, состоящих в выпадении всех чисел по результатам n засчитанных бросаний кости, описывается так:
      A = {ωω = [a1, …, an], ai ∈ {1, …, 6}, ai ≠ ajn < 6}, где ω — очередной элемент множества A, содержащий все выпавшие числа без учёта порядка их выпадения — неупорядоченный набор (поскольку в квадратных скобках), полученный выбором без возвращения (потому что ai ≠ aj).

Множество может содержать, кроме простых элементов, другие множества, являющиеся частью основного. Если одно множество целиком входит в состав другого, это записывают способом (1.2):

(1.2)
Множество является подмножеством другого
(1.2)

Для случая, при котором одно множество является частью другого или полностью совпадает с ним по составу элементов (заметьте — не только по количеству), используется запись (1.3):

(1.3)
Множество является подмножеством другого или совпадает с ним
(1.3)

Записи (1.2) и (1.3) показывают, что множество A является подмножеством B, а все элементы A одновременно являются элементами B.

Если одно множество совпадает с другим как по количеству элементов, так и самими элементами, то эти множества равны: A = B. В этом случае любое из них можно считать подмножеством другого: A ⊆ B и B ⊆ A.

    • Собственное множество — множество, которое является частью другого и не равно ему.

Если A ≠ B и A ⊂ B, то A как раз и является собственным множеством B. Иногда это обстоятельство нужно подчеркнуть, что делается записью наподобие (1.4):

(1.4)
Собственное множество
(1.4)

Организацию множеств, при которой одно является подмножеством другого, можно наблюдать в Примере 4. До его изучения полезно узнать, что такое достоверное и невозможное события.

    • Достоверное событие — набор событий, который является либо единственным, либо выбранным.

      Невозможное событие — набор событий, не являющийся выбранным.

    • Из §28 раздела "Введение в информатику" видно, что для реализации конкретного события сначала выбирается содержащий его набор (который, впрочем, тоже является событием — подмножеством множества всех наборов). Если этот набор выбран из нескольких или он единственный (тогда он выбран априори), то единственным следствием его реализации является совершение какого-нибудь события, относящегося именно к этому набору (выбор элемента именно данного подмножества). Реализуемое в будущем событие принадлежит конкретному набору, поэтому он и называется достоверным событием. Понятие невозможного события обратно по смыслу понятию достоверного.

  • 4

    • Развивая мысль, изложенную в Примере 1, заметим, что события К, З и М составляют отдельное множество, именуемое "набором возможных событий, заключающихся в реакции на сигнал светофора". Напомним, что в условии (и решении) задачи Примера 1 из §28 раздела "Введение в информатику", которое мы обсуждаем, ничего не сказано о ситуации невозможности принятия решения о переходе проезжей части, поэтому будем считать событие Ω = {К, З, М} достоверным (подойдя к переходу, пешеход видит какой-то сигнал светофора и потому может принять решение о немедленном начале движения через проезжую часть), а ∅ — невозможным. Тогда множество A событий, заключающихся в реакции на сигнал светофора (если таковой имеется) может быть представлено в виде A = {Ω, ∅} или A = {{К, З, М}, ∅} (что есть то же самое). Естественно, что Ω ⊆ A.

      Согласно приведённой организации множеств, получение пешеходом информации в случае работающего светофора состоит из двух этапов: 1) 1 бит о том, что светофор работает, и 2) некоторое количество бит о текущем сигнале (количество информации зависит от конкретного сигнала, устанавливается применением алгоритма Хаффмана — см. §26 раздела "Введение в информатику").

    • Множество, состоящее из достоверного и невозможного событий (см. Пример 4), называется тривиальной алгеброй. Если к упомянутым подмножествам тривиальной алгебры добавить другие множества, то можно получить новую алгебру. Напрашивается вывод: под словом "алгебра" понимается не только раздел математики, в котором рассматриваются основные операции с элементами множеств вообще, но и само множество, объединяющее некоторое количество подмножеств, заключающих в себе определённый смысл. Можно также сказать, что алгебра — это математическая модель рассмотрения набора объектов в целом, взаимодействий этих объектов и нескольких наборов объектов, свойств каждого объекта в отдельности.

    • В частности, математическую модель, описывающую все результаты всех действий разрабатываемой системы управления, можно назвать алгеброй; в ней объектами являются события системы управления. На этой алгебре строится алгебраическая система — множество, включающее конкретные объекты системы управления (исполнители) и связи между ними (каналы связи). Алгебраическая система позволяет выполнить проектирование каждого исполнителя и всех каналов связи, подчинив протокол связи алгебре.

      При разработке системы управления созданная алгебра является основой алгебраической системы, сама же алгебраическая система представляет собой логическую структуру проекта (о системах управления см. §18 раздела "Введение в информатику").

Как было сказано выше, повторяющиеся элементы множества представляют собой один элемент. Однако изменение представления состава множества путём удаления повторений элемента требует изменения вероятности его выбора как неповторяющегося: события, составляющие множество, уже не будут равновозможными. Покажем множества, в которых есть повторяющиеся элементы (в том числе повторяющиеся подмножества), и выполним представления их составов как имеющие математический смысл, а также подсчитаем вероятности выбора таких элементов (см. Пример 5).

  • 5

    • Предположим, что множество X содержит следующие числа:
      X = {2, 5, 10, 2, 1, 7, 10, 1}.

      В этом множестве имеется 8 чисел, некоторые из них совпадают. Если бы все числа были разные, то вероятность выбора любого составляла бы 0,125 при условии, что выбор каждого равновероятен. Из записи, однако, видно, что числа 1, 2 и 10 повторяются, поэтому правильным представлением состава множества будет такое:
      X = {2, 5, 10, 1, 7}.

      Каждое из повторяющихся чисел упоминается во множестве по 2 раза, следовательно, вероятности их выбора нужно удвоить относительно вероятности, вычисленной ранее для восьми чисел, если бы они были разными: p1 = p2 = p10 = 0,25.

      Представим множество Y, которое имеет более сложный состав:
      Y = {{2, 10}, {2}, {1}, {7, 2}, {10, 2}, {1, 1}}.

      Пусть вероятности выбора каждого подмножества (если считать их отличающимися) совпадают. Тогда вероятность выбора любого из них составляет pi = 1/6. Однако видно, что подмножества {2, 10} повторяются (порядок упоминания элементов не играет никакой роли, способы представления упорядоченных и неупорядоченных наборов см. в Примерах 2, 3 и 5). Подмножества {1} и {1, 1} тоже считаются повторяющимися, ведь {1} = {1, 1}. Тогда верное представление множества Y выглядит так:
      Y = {{2, 10}, {2}, {1}, {7, 2}}.

      Подмножества {2, 10} и {1} повторяются по 2 раза, значит, вероятности их выбора следует удвоить относительно вероятности, вычисленной для шести разных подмножеств: p{2, 10} = p{1} =1/3.



Поддержите нас!


Обращаем Ваше внимание:

Ваш браузер недостаточно эффективен. Установите достойный браузер здесь.

Все анонсы? / ?



Индекс цитирования
CY, Page Rank
Яндекс.Метрика