Мультимножество: различия между версиями
[непроверенная версия] | [отпатрулированная версия] |
Нет описания правки |
→Литература: источники |
||
(не показано 28 промежуточных версий 17 участников) | |||
Строка 1: | Строка 1: | ||
{{Перенаправление|Комплект|Набор|других значений «комплекта» как набора}} |
|||
'''Мультимножество''' — в математике, обобщение понятия [[Множество|множества]], допускающее включение одного и того же элемента по нескольку раз. |
|||
⚫ | |||
{{Якорь|Комплект}}Идея мультимножества неявно используется со времён древности ([[Кнут, Дональд Эрвин|Кнут]] приводит в пример [[Бхаскара II|Бхаскару II]] из XII века, изучавшего перестановки мультимножеств), но введение понятия и фиксацию термина относят к [[Де Брёйн, Николас|де Брёйну]] (1970-е годы)<ref>{{книга |
|||
⚫ | |||
|автор = [[Дональд Кнут]] |
|||
|заглавие = Искусство программирования, том 2. Получисленные алгоритмы |
|||
|оригинал = The Art of Computer Programming, vol.2. Seminumerical Algorithms |
|||
|издание = 3-е изд |
|||
|место = М. |
|||
|издательство = Вильямс |
|||
|год = 2007 |
|||
|страницы = 832 |
|||
|isbn = 0-201-89684-2 |
|||
}}</ref>. Используется в основном в приложениях ([[Информатика|информатике]], [[Искусственный интеллект|искусственном интеллекте]], [[Теория принятия решений|теории принятия решений]]), в применении к теории [[Сеть Петри|сетей Петри]] мультимножество называется '''''комплектом'''''<ref>{{книга |
|||
|автор = Джеймс Питерсон |
|||
|часть = Обзор теории комплектов |
|||
|заглавие = Теория сетей Петри и моделирование систем |
|||
|оригинал = Petri Net Theory and The Modelling of Systems |
|||
|ссылка = |
|||
|место = М. |
|||
|издательство = [[Мир (издательство)|Мир]] |
|||
|год = 1984 |
|||
|страницы = 231—235 |
|||
|страниц = 264 |
|||
|isbn = |
|||
|тираж = 8400 |
|||
}}</ref>. В различных приложениях используют разную нотацию. |
|||
⚫ | Формально, мультимножество на множестве <math>A</math> определяется как [[упорядоченная пара]] <math>(A, m)</math>, где <math>m \colon A \to \mathbb{N}</math> — это [[Функция (математика)|функция]], сопоставляющая каждому элементу множества <math>A</math> некоторое [[натуральное число]], называемое кратностью этого элемента. |
||
== Формальное определение == |
|||
⚫ | |||
⚫ | |||
== Примеры == |
|||
⚫ | |||
: <math>120 = 2^3 3^1 5^1\,,</math> |
|||
поэтому его мультимножество простых делителей — <math>\{2, 2, 2, 3, 5\}</math>. |
|||
Другой пример — мультимножество корней [[Алгебраическое уравнение|алгебраического уравнения]]. Например, уравнение <math>x^3 - 5x^2 + 8x - 4 = 0</math> имеет корни <math>\{1, 2, 2\}</math>. |
Другой пример — мультимножество корней [[Алгебраическое уравнение|алгебраического уравнения]]. Например, уравнение <math>x^3 - 5x^2 + 8x - 4 = 0</math> имеет корни <math>\{1, 2, 2\}</math>. |
||
== Число мультимножеств == |
|||
Число различных мультимножеств мощности <math>k</math>, состоящих из элементов, выбранных из множества мощности <math>n</math>, может быть вычислено по следующей формуле, как [[биномиальный коэффициент]]: |
Число различных мультимножеств мощности <math>k</math>, состоящих из элементов, выбранных из множества мощности <math>n</math>, может быть вычислено по следующей формуле, как [[биномиальный коэффициент]]: |
||
: <math>{n+k-1 \choose k}</math> |
: <math>{n+k-1 \choose k}</math>. |
||
== Примечания == |
|||
{{Примечания}} |
|||
== Литература == |
== Литература == |
||
* {{книга |
|||
* Петровский А.Б. Пространства множеств и мультимножеств. – М.: Едиториал УРСС, 2003. – 248 с. |
|||
| автор = А. Б. Петровский |
|||
| заглавие = Пространства множеств и мультимножеств |
|||
| ссылка = http://www.raai.org/about/persons/petrovsky/pages/Petrovsky_2003.pdf |
|||
| место = М. |
|||
| издательство = Едиториал УРСС |
|||
| год = 2003 |
|||
| страницы = 248 |
|||
| isbn = 5-7262-0633-9 |
|||
}} |
|||
{{ВС}} |
|||
{{rq|refless|recat}} |
|||
[[Категория:Теория множеств]] |
[[Категория:Теория множеств]] |
||
[[ca:Multiconjunt]] |
|||
[[cs:Multimnožina]] |
|||
[[de:Multimenge]] |
|||
[[en:Multiset]] |
|||
[[eo:Multaro]] |
|||
[[es:Multiconjunto]] |
|||
[[fr:Multiensemble]] |
|||
[[it:Multiinsieme]] |
|||
[[ja:多重集合]] |
|||
[[ko:중복집합]] |
|||
[[nl:Multiset]] |
|||
[[pl:Multizbiór]] |
|||
[[pt:Multiconjunto]] |
|||
[[ro:Multimulțime]] |
|||
[[simple:Multiset]] |
|||
[[sl:Večkratna množica]] |
|||
[[sv:Multimängd]] |
|||
[[uk:Мультимножина]] |
|||
[[zh:多重集]] |
Текущая версия от 17:40, 5 февраля 2024
Мультимножество — модификация понятия множества, допускающая включение одного и того же элемента в совокупность по нескольку раз. Число элементов в мультимножестве, с учётом повторяющихся элементов, называется его размером или мощностью.
Идея мультимножества неявно используется со времён древности (Кнут приводит в пример Бхаскару II из XII века, изучавшего перестановки мультимножеств), но введение понятия и фиксацию термина относят к де Брёйну (1970-е годы)[1]. Используется в основном в приложениях (информатике, искусственном интеллекте, теории принятия решений), в применении к теории сетей Петри мультимножество называется комплектом[2]. В различных приложениях используют разную нотацию.
Формально, мультимножество на множестве определяется как упорядоченная пара , где — это функция, сопоставляющая каждому элементу множества некоторое натуральное число, называемое кратностью этого элемента.
Один из самых простых примеров — мультимножество простых множителей целого числа. Так, например, разложение числа 120 на простые множители имеет вид: , поэтому его мультимножество простых делителей — .
Другой пример — мультимножество корней алгебраического уравнения. Например, уравнение имеет корни .
Число различных мультимножеств мощности , состоящих из элементов, выбранных из множества мощности , может быть вычислено по следующей формуле, как биномиальный коэффициент:
- .
Примечания
[править | править код]- ↑ Дональд Кнут. Искусство программирования, том 2. Получисленные алгоритмы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: Вильямс, 2007. — С. 832. — ISBN 0-201-89684-2.
- ↑ Джеймс Питерсон. Обзор теории комплектов // Теория сетей Петри и моделирование систем = Petri Net Theory and The Modelling of Systems. — М.: Мир, 1984. — С. 231—235. — 264 с. — 8400 экз.
Литература
[править | править код]- А. Б. Петровский. Пространства множеств и мультимножеств. — М.: Едиториал УРСС, 2003. — С. 248. — ISBN 5-7262-0633-9.
Для улучшения этой статьи желательно: |