Отчет по домашнему заданию

по дисциплине

«Интеллектуальные информационные системы»

 

 

Студента          Дворецкого Сергея Владимировича

фамилия, имя, отчество полностью

Курс   5 Группа ПЗ-151

Направление (специальность)  09.03.03

                                                   Прикладная информатика

код, наименование

Руководитель Доцент                      

должность, ученая степень, ученое звание

                     Гегечкори Е.Т.

фамилия, инициалы

Выполнил  _____________________   

дата, подпись студента

 

Омск 2019

Операции над множествами

Множества и подмножества

 

Множеством принято называть собрание объектов любой природы, мыслимых как целое.

Так можно говорить о множестве людей, находящихся в комнате; множестве букв русского (или, скажем, латинского) алфавита; множестве вершин данного многоугольника; множестве натуральных чисел и т.д.

В множестве все элементы должны быть различными, т.е. не должны совпадать.

Как правило, множества будут обозначаться прописными латинскими буквами A, B, …, а объекты – строчными буквами a, b, ….

Если объект а принадлежит множеству A (является элементом множества A), то это записывается так:

a Î A.

Если же a не принадлежит множеству A, мы записываем это так:

a Ï A.

Символ Î называется знаком принадлежности.

Множества бывают конечные и бесконечные. Конечным множеством называется такое множество, число элементов которого конечно, т.е. выражается некоторым натуральным числом. Множество называется бесконечным, если оно не является конечным.

Мы будем рассматривать в дальнейшем главным образом конечные множества.

Множества могут задаваться перечислением и описанием.

В первом случае множество задается просто перечислением его элементов (которые заключаются в фигурные скобки). Так, например, множество, состоящее из элементов a, b, c, обозначается как

{ а, b, c }.

Во втором случае множество задается описанием некоторого характеристического свойства, позволяющего установить, какие объекты принадлежат, а какие объекты не принадлежат задаваемому множеству.

Условимся говорить, что два множества равны, и писать A = В, если A и В состоят из одних и тех же элементов (можно также говорить, что A и В – одинаковые множества или что A и В – одно и то же множество).

Подчеркнем, что порядок элементов в множестве несущественен. Поэтому, в частности, говорить о первом, втором, третьем, … элементе множества можно только тогда, когда предварительно элементы были как-нибудь перенумерованы.

Условимся считать, что существует множество, не содержащее вовсе элементов. Это множество будет называться пустым и обозначаться Æ. Существование понятия "пустое множество"сокращает и упрощает многие формулировки.

Будем называть множество A подмножеством множества В и писать A Í В,если любой элемент множества A принадлежит множеству B (в этом случае В называется надмножеством множества A). Если неверно, что A Í В, то знак Í перечеркивается.

Заметим, что для любого множества М

M Í M и ÆÍ M.

Подмножества M и Æ множества М называются несобственными подмножествами множества М.

Из определения подмножества и равенства множеств непосредственно вытекает, что*

A = В «A Í В Ù B Í A.

Отметим также, что

A Í В Ù B Í C ® A Í C.

Множество A называется истинным подмножеством множества B если A Í В и A ¹ B. В этом случае будем писать A Ì В. Символ Í называется знаком включения, а символ Ì знаком строгого включения.

Операции над множествами

 

Объединением двух множеств A и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств A, В. Объединение множеств  A и В обозначается через A U В.

Таким образом,

x Î A U В «x Î A Ú x Î B.

Пример. Если A = {l,2,3}, a B = {1,3,4}, то A U В = {1,2,3,4}.

Аналогичным образом определяется объединение произвольного числа n множеств A ₁, A ₂, …, A_n. Множество

– это множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств A ₁, A ₂, …, A_n.

Пересечением множеств A и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат A и принадлежат В.  Пересечение множеств A и В обозначается через A   В.

Таким образом,

x Î A   В «x Î A Ù x Î B.

Пример. Если A = {l,2,3}, a B = {1,3,4}, то A   В = {1,3}.

Если A   В = Æ, то говорят, чтомножества A и В не пересекаются.

Пересечением

n, множеств называется множество, состоящее из всех тех и только тех элементов, которые входят в каждое из множеств A ₁, A ₂, …, A_n.

 

 

Следующая операция над множествами, в отличие от операций объединения и пересечения, определяется только для двух множеств,

Разностью множеств A и B называется множество, состоящее из всех тех и только тех элементов, которые принадлежат A и не принадлежат B. Обозначается разность множеств A и B через A \ В.

Таким образом,

x Î A \ В «x Î A Ú x Ï B.

Пример. Если A = {l,2,3}, a B = {1,3,4}, то A \ B = {2} и B \ A = {4}.

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

 

Множество (set) — это структура данных, представляющая собой не организованный набор уникальных элементов одного типа. Данная структура очень тесно связано с математическим понятием теории множеств. В наиболее упрощенном понимании, множество — это набор уникальных однотипных данных, рассматриваемых как единое целое. Рассмотрим пример реализации множества и основных операций выполняемых с множествами на языке C#.

На рисунке ниже схематически представлены два множества A и B, а также основные операции: объединение, пересечение, разность.

 

Давайте подробнее рассмотрим все наиболее часто встречающиеся операции над множествами:

1. Add — добавление элемента. Если такой элемент уже присутствует, то он не будет добавлен.

2. Remove — удаление элемента из множества.

3. Union — объединение множеств. Создается новое множество, включающее в себя все элементы из множества А и множества В. Если элемент содержится в обоих множествах, он будет добавлен однократно.

4. Difference — разность множеств. Создается новое множество, включающее в себя все элементы множества А, которые не входят в множество В.

5. Intersection — пересечение множеств. Создается новое множество, включающее в себя все элементы входящие одновременно и в множество А, и в множество В.

6. Subset — проверка на подмножество. Чтобы быть подмножеством, все элементы множества А должны содержаться в множестве В. Тогда множество А является подмножеством множества В.

 

Приступим к реализации данного класса. Будем использовать обобщенный класс и реализовывать интерфейс IEnumerable для произвольного доступа к элементам множества. Для хранения данных воспользуемся списком. Данная реализация является весьма примитивной и не оптимальной, но возможность разобраться в алгоритмах работы основных операций над множествами.

 

Реализация класса Set.cs

Для начала объявим класс и его свойства

 

 

Реализуем операции добавления и удаления элементов множества

 

 

Реализуем операцию объединения множеств

 

 

Реализуем операцию пересечения множеств

 

 

Реализуем операцию разности множеств

 

 

Делаем проверку на подмножество и реализуем интерфейс IEnumerable

 

Проверим работу нашего класса

 

 

 

В результате получаем следующий вывод на экран

 

 

На платформе.NET все операции над множествами уже оптимально реализованы в рамках LINQ запросов, поэтому реализовывать самостоятельно нет необходимости. Я не претендую на правильность, оптимальность и красоту реализации. Единственная цель, которую я преследую, поделиться полезной информацией о программировании, которая может кому-то пригодиться.

 

Код множество

 

1 using System;

2 using System.Collections;

3 using System.Collections.Generic;

4 using System.Linq;

5 

6 namespace Set

7 {

8 /// <summary>

9 /// Множество.

10 /// </summary>

11 /// <typeparam name="T"> Тип данных, хранимых во множестве. </typeparam>

12 public class Set<T>: IEnumerable<T>

13 {

14    /// <summary>

15    /// Коллекция хранимых данных.

16    /// </summary>

17    private List<T> _items = new List<T>();

18

19    /// <summary>

20    /// Количество элементов.

21    /// </summary>

22    public int Count => _items.Count;

23

24    /// <summary>

00000000000000000000000000000000000000000000000000000000000000000000000000000025    /// Добавить данные во множество.

26    /// </summary>

27    /// <param name="item"> Добавляемые данные. </param>

28    public void Add(T item)

29    {

30        // Проверяем входные данные на пустоту.

31        if (item == null)

32        {

33            throw new ArgumentNullException(nameof(item));

34        }

35

36        // Множество может содержать только уникальные элементы,

37        // поэтому если множество уже содержит такой элемент данных, то не добавляем его.

38        if (!_items.Contains(item))

39        {

40            _items.Add(item);

41        }

42    }

43

44    /// <summary>

45    /// Удалить элемент из множества.

46    /// </summary>

47    /// <param name="item"> Удаляемый элемент данных. </param>

48    public void Remove(T item)

49    {

50        // Проверяем входные данные на пустоту.

51        if (item == null)

52        {

53            throw new ArgumentNullException(nameof(item));

54        }

55

56        // Если коллекция не содержит данный элемент, то мы не можем его удалить.

57        if (!_items.Contains(item))

58        {

59            throw new KeyNotFoundException($"Элемент {item} не найден в множестве.");

60        }

61

62        // Удаляем элемент из коллекции.

63        _items.Remove(item);

64    }

65

66    /// <summary>

67    /// Объединение множеств.

68    /// </summary>

69    /// <param name="set1"> Первое множество. </param>

70    /// <param name="set2"> Второе множество. </param>

71    /// <returns> Новое множество, содержащее все уникальные элементы полученных множеств. </returns>

72    public static Set<T> Union(Set<T> set1, Set<T> set2)

73    {

74        // Проверяем входные данные на пустоту.

75        if (set1 == null)

76        {

77            throw new ArgumentNullException(nameof(set1));

78        }

79

80        if (set2 == null)

81        {

82            throw new ArgumentNullException(nameof(set2));

83        }

84

85        // Результирующее множество.

86        var resultSet = new Set<T>();

87

88        // Элементы данных результирующего множества.

89        var items = new List<T>();

90

91        // Если первое входное множество содержит элементы данных,

92        // то добавляем их в результирующее множество.

93        if (set1._items!= null && set1._items.Count > 0)

94        {

95            // т.к. список является ссылочным типом,

96            // то необходимо не просто передавать данные, а создавать их дубликаты.

97            items.AddRange(new List<T>(set1._items));

98        }

99

100       // Если второе входное множество содержит элементы данных,

101       // то добавляем из в результирующее множество.

102       if (set2._items!= null && set2._items.Count > 0)

103       {

104           // т.к. список является ссылочным типом,

105           // то необходимо не просто передавать данные, а создавать их дубликаты.

106           items.AddRange(new List<T>(set2._items));

107       }

108

109       // Удаляем все дубликаты из результирующего множества элементов данных.

110       resultSet._items = items.Distinct().ToList();

111

112       // Возвращаем результирующее множество.

113       return resultSet;

114   }

115

116   /// <summary>

117   /// Пересечение множеств.

118   /// </summary>

119   /// <param name="set1"> Первое множество. </param>

120   /// <param name="set2"> Второе множество. </param>

121   /// <returns> Новое множество, содержащее совпадающие элементы данных из полученных множеств. </returns>

122   public static Set<T> Intersection(Set<T> set1, Set<T> set2)

123   {

124       // Проверяем входные данные на пустоту.

125       if (set1 == null)

126       {

127           throw new ArgumentNullException(nameof(set1));

128       }

129

130       if (set2 == null)

131       {

132           throw new ArgumentNullException(nameof(set2));

133       }

134

135       // Результирующее множество.

136       var resultSet = new Set<T>();

137

138       // Выбираем множество содержащее наименьшее количество элементов.

139       if (set1.Count < set2.Count)

140       {

141           // Первое множество меньше.

142           // Проверяем все элементы выбранного множества.

143           foreach (var item in set1._items)

144           {

145               // Если элемент из первого множества содержится во втором множестве,

146               // то добавляем его в результирующее множество.

147               if (set2._items.Contains(item))

148               {

149                   resultSet.Add(item);

150               }

151           }

152       }

153       else

154       {

155           // Второе множество меньше или множества равны.

156           // Проверяем все элементы выбранного множества.

157           foreach (var item in set2._items)

158           {

159               // Если элемент из второго множества содержится в первом множестве,

160               // то добавляем его в результирующее множество.

161               if (set1._items.Contains(item))

162               {

163                   resultSet.Add(item);

164               }

165           }

166       }

167

168       // Возвращаем результирующее множество.

169       return resultSet;

170   }

171

172   /// <summary>

173   /// Разность множеств.

174   /// </summary>

175   /// <param name="set1"> Первое множество. </param>

176   /// <param name="set2"> Второе множество. </param>

177   /// <returns> Новое множество, содержащее не совпадающие элементы данных между полученными множествами. </returns>

178   public static Set<T> Difference(Set<T> set1, Set<T> set2)

179   {

180       // Проверяем входные данные на пустоту.

181       if (set1 == null)

182       {

183           throw new ArgumentNullException(nameof(set1));

184       }

185

186       if (set2 == null)

187       {

188           throw new ArgumentNullException(nameof(set2));

189       }

190

191       // Результирующее множество.

192       var resultSet = new Set<T>();

193

194       // Проходим по всем элементам первого множества.

195       foreach (var item in set1._items)

196       {

197           // Если элемент из первого множества не содержится во втором множестве,

198           // то добавляем его в результирующее множество.

199           if (!set2._items.Contains(item))

200           {

201               resultSet.Add(item);

202           }

203        }

204

205       // Проходим по всем элементам второго множества.

206       foreach (var item in set2._items)

207       {

208           // Если элемент из второго множества не содержится в первом множестве,

209           // то добавляем его в результирующее множество.

210           if (!set1._items.Contains(item))

211           {

212               resultSet.Add(item);

213           }

214       }

215

216       // Удаляем все дубликаты из результирующего множества элементов данных.

217       resultSet._items = resultSet._items.Distinct().ToList();

218

219       // Возвращаем результирующее множество.

220       return resultSet;

221   }

222

223   /// <summary>

224      /// Подмножество.

225   /// </summary>

226   /// <param name="set1"> Множество, проверяемое на вхождение в другое множество. </param>

227   /// <param name="set2"> Множество в которое проверяется вхождение другого множества. </param>

228   /// <returns> Является ли первое множество подмножеством второго. true - является, false - не является. </returns>

229   public static bool Subset(Set<T> set1, Set<T> set2)

230   {

231       // Проверяем входные данные на пустоту.

232       if (set1 == null)

233       {

234           throw new ArgumentNullException(nameof(set1));

235       }

236

237       if (set2 == null)

238       {

239           throw new ArgumentNullException(nameof(set2));

240            }

241

242       // Перебираем элементы первого множества.

243       // Если все элементы первого множества содержатся во втором,

244       // то это подмножество. Возвращаем истину, иначе ложь.

245       var result = set1._items.All(s => set2._items.Contains(s));

246       return result;

247   }

248

249   /// <summary>

250   /// Вернуть перечислитель, выполняющий перебор всех элементов множества.

251   /// </summary>

252   /// <returns> Перечислитель, который можно использовать для итерации по коллекции. </returns>

253   public IEnumerator<T> GetEnumerator()

254   {

255       // Используем перечислитель списка элементов данных множества.

256       return _items.GetEnumerator();

257   }

258

259   /// <summary>

260   /// Вернуть перечислитель, который осуществляет итерационный переход по множеству.

261   /// </summary>

262   /// <returns> Объект IEnumerator, который используется для прохода по коллекции. </returns>

263   IEnumerator IEnumerable.GetEnumerator()

264   {

265       // Используем перечислитель списка элементов данных множества.

266       return _items.GetEnumerator();

267   }

268 }

269}

 

Вывод результата

 

1 using System;

2

3 namespace Set

4 {

5 class Program

6 {

7    static void Main(string[] args)

8    {

9        // Создаем множества.

10       var set1 = new Set<int>()

11       {

12           1, 2, 3, 4, 5, 6

13       };

14

15       var set2 = new Set<int>()

16       {

17           4, 5, 6, 7, 8, 9

18       };

19

20       var set3 = new Set<int>()

21       {

22           2, 3, 4

23       };

24

25       // Выполняем операции со множествами.

26       var union = Set<int>.Union(set1, set2);

27       var difference = Set<int>.Difference(set1, set2);

28       var intersection = Set<int>.Intersection(set1, set2);

29       var subset1 = Set<int>.Subset(set3, set1);

30       var subset2 = Set<int>.Subset(set3, set2);

31

32       // Выводим исходные множества на консоль.

33       PrintSet(set1, "Первое множество: ");

34       PrintSet(set2, "Второе множество: ");

35       PrintSet(set3, "Третье множество: ");

36

37       // Выводим результирующие множества на консоль.

38       PrintSet(union, "Объединение первого и второго множества: ");

39       PrintSet(difference, "Разность первого и второго множества: ");

40       PrintSet(intersection, "Пересечение первого и второго множества: ");

41           

42       // Выводим результаты проверки на подмножества.

43       if(subset1)

44       {

45           Console.WriteLine("Третье множество является подмножеством первого.");

46       }

47       else

48       {

49           Console.WriteLine("Третье множество не является подмножеством первого.");

50       }

51

52       if (subset2)

53       {

54           Console.WriteLine("Третье множество является подмножеством второго.");

55       }

56       else

57       {

58           Console.WriteLine("Третье множество не является подмножеством второго.");

59       }

60

61       Console.ReadLine();

62     }

63

64   /// <summary>

65   /// Вывод множества на консоль.

66   /// </summary>

67   /// <param name="set"> Множество. </param>

68   /// <param name="title"> Заголовок перед выводом множества. </param>

69   private static void PrintSet(Set<int> set, string title)

70   {

71       Console.Write(title);

72       foreach (var item in set)

73       {

74           Console.Write($"{item} ");

75       }

76       Console.WriteLine();

77   }

78 }

79}

* Здесь и далее мы пользуемся логическими, связками, определенными в алгебре логики.