- •1. Основные понятия теории множеств.
- •2. Понятие вектора.
- •3. Понятие соответствия между множествами.
- •4. Понятие отображения множеств.
- •5. Классификация множеств по мощности. Понятие счетного множества. Понятие несчётного множества.
- •6. Понятие отношения. Свойства отношений. Отношение эквивалентности, отношение строгого порядка, отношение нестрогого порядка.
- •7. Понятие операции, ассоциативной операции, дистрибутивной операции. Понятие алгебры, алгебраической системы, модели. Понятие группоида, полугруппы, коммутативной полугруппы.
- •8. Понятие группы. Группа подстановок.
- •9.Понятие кольца. Кольцо вычетов.
- •10. Определение поля
- •11. Перестановки
- •12.Перестановки с повторениями
- •13. Понятие сочетания. Теорема о числе сочетаний из n элементов по k. Свойства сочетаний.
- •Свойства сочетаний
- •14. Понятие сочетания с повторениями. Теорема о числе сочетаний с повторениями.
- •15. Понятие размещения. Теорема о числе размещений.
- •16. Понятие композиции. Теорема о числе композиций n.
- •18. Понятие композиции. Теорема о числе композиций n из k частей при рi0.
- •19. Основные понятия и определения теории графов.
- •20. Способы хранения графов в памяти эвм.
- •21. Алгоритм поиска на графах (поиск в глубину).
- •22. Алгоритм поиска на графах (поиск в ширину).
- •23. Понятие сильной связности. Анализ сильной связности с помощью алгоритмов поиска на графах.
- •25. Сильная связность. Отношение на вершинах графа называется отношением сильной связности. Сильная связность — отношение эквивалентности. Рассмотрим транзитивность:
- •26. Понятие логической функции. Способы задания логических функций.
- •27. Булева алгебра. Основные свойства операций булевой алгебры. Понятие двойственной и самодвойственной логической функции.
- •28. Алгебра Жегалкина. Основные свойства операций алгебры Жегалкина.
- •29. Алгебра Жегалкина. Представление логических функций полиномом Жегалкина.
- •33. Минимизация логических функций методом Квайна.
- •34. Понятие функционально-полной системы логических функций
- •35. 36 Понятие замкнутого класса. Класс монотонных логических функций.Понятие замкнутого класса. Класс линейный логических функций..
- •37. Теорема о функциональной полноте в слабом смысле.
- •38. Понятие замкнутого класса. Класс функций сохраняющих 0. Класс функций сохраняющих 1.
- •39. Понятие замкнутого класса. Класс самодвойственных функций.
- •40. Теорема о функциональной полноте.
16. Понятие композиции. Теорема о числе композиций n.
В математике композиция функций (суперпозиция функций) – это применение одной функции к результату другой. Композиция функций F и G обычно обозначается G ° F.
Определение:
Пусть и две функции. Тогда их композицией называется функция , определённая равенством:
.
Свойства композиции:
Композиция ассоциативна:
.
Если — тождественное отображение на , то есть
,
то
.
Если — тождественное отображение на , то есть
,
то
.
Композиция числа.
В теории чисел композицией, или разложением, натурального числа называется его представление в виде упорядоченной суммы натуральных слагаемых. Слагаемые, входящие в композицию, называют частями, а их количество – длиной композиции.
В отличие от композиции, разбиение числа не учитывает порядок следования частей. Поэтому число разбиений числа никогда не превосходит числа композиций.
Существует 8 композиций числа 4:
4 = 4
4 = 3 + 1
4 = 2 + 2
4 = 2 + 1 + 1
4 = 1 + 3
4 = 1 + 2 + 1
4 = 1 + 1 + 2
4 = 1 + 1 + 1 + 1
В общем случае существует 2n-1 композиций числа n, из которых в точности имеют длину k.
17. Понятие композиции. Теорема о числе композиций n из k частей при рi>0.
Композиции и разбиения. Пусть стоит задача порождения разбиения положительного числа n в последовательность неотрицательных целых чисел {p1,p2,…,pk}, так чтоp1+p2+…+pk=n причем на рi могут накладываться различные ограничения.
Если порядок чисел рi важен, то (p1,p2,…,pk) называется композицией n. Поиск композиций ведется с ограничением рi>0.
Если k фиксировано, то такие композиции называются композициями n из k частей. При их поиске ограничение рi>0 может сниматься, т.е. разрешается рi=0.
Если порядок рi не важен и рi>0, то {p1,p2,…,pk} является мультимножеством и называется разбиением n.
Поясним различие между композициями, композициями из k частей и разбиениями на следующем примере:
n=3,
композиции: (3), (1,2), (2,1), (1,1,1),
композиции из двух частей (рi>0): (1,2), (2,1),
композиции из двух частей (рi³0): (0,3), (1,2), (2,1), (3,0),
разбиения: {3}, {1,2}, {1,1,1}.
Ч исло композиций n из k частей с ограничением рi>0 равно .Доказательство. Представим композицию как на рис 1 Каждая композиция n из k частей (рi>0) соответствует способу выбора (k-1)-элементного подмножества точек из n-1 точек. То есть число таких композиций равно.
18. Понятие композиции. Теорема о числе композиций n из k частей при рi0.
Понятие композиции см. вопрос. 17
Число композиций n из k частей, если pi³0 равно .
Доказательство. Каждой композиции n из k частей при рi³0 взаимно однозначно соответствует двоичный набор, такой, что первое слагаемое равно числу единиц, стоящих перед первым нулем в наборе, второе - числу единиц, стоящих перед первым и вторым нулями, и т.д. Пример такого представления композиции n=4, k=3 приведен в табл.1.
Длина набора равна n+k-1, число нулей равно k-1, следовательно, число наборов (искомых композиций) равно числу способов выбора k-1 мест для нулей из n+k-1 мест ( ) или тоже самое числу способов выбора n мест для единиц из n+k-1 мест ( ).
Таблица 1.
№ |
Композиция |
Двоичный набор |
Сочетание из 6 по 2 |
1 |
0+0+4 |
0 0 1 1 1 1 |
1 2 |
2 |
0+1+З |
0 1 0 1 1 1 |
1 3 |
3 |
0+2+2 |
0 1 1 0 1 1 |
1 4 |
... |
... |
... |
... |
13 |
3+0+1 |
1 1 1 0 0 1 |
4 5 |
14 |
3+1+0 |
1 1 1 0 1 0 |
4 6 |
15 |
4+0+0 |
1 1 1 1 0 0 |
5 6 |