 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Пример решения задачи 7
Задание. Будет ли множество M = [0,1] с операцией x*y = x+y – (9/8) xy полугруппой? Моноидом? Группой?
Решение
1) Проверим, будет ли x*y ÎM при x,y ÎM. Это выполнено если для всех удовлетворяющих неравенствам 0£ x, y £1 чисел x, y будет иметь место 0£ x*y £1. Рассмотрим произвольный 0£ y £1. Функция f(x)= x+y – (9/8)xy при фиксированном y будет линейной по x. На концах интервала [0,1] она принимает значения f(0)=y и f(1) = 1-(1/8)y. Поскольку эти значения лежат в интервале [0,1], то значения этой функции во внутренних точках интервала принадлежат [0,1]. Отсюда для всех x,y Î M значения x*y принадлежат M.
2) Проверим ассоциативность (x*y)*z=x*(y*z). С этой целью раскроем обе части проверяемого равенства:
(x+y-(9/8)xy)+z-(9/8) (x+y-(9/8)xy)z = x+(y+z-(9/8)yz)-(9/8)x(y+z-(9/8)yz)
Поскольку последнее равенство имеет место, то операция * ассоциативна. Стало быть, (M,*) – полугруппа.
3) Проверим, будет ли (M,*) моноидом. Напомним, что моноидом называется полугруппа M, в которой существует элемент e ÎM, удовлетворяющий для всех x ÎM соотношениям x*e = e*x = x.
Этот элемент e ÎM называется нейтральным. Для нахождения нейтрального элемента получаем тождество x+e –(9/8)xe = x, которое должно быть выполнено для всех x ÎM. Легко видеть, что e =0 удовлетворяет этому тождеству. Отсюда вытекает, что (M,*) – моноид.
4) Проверим, будет ли (M,*) группой. Напомним, что моноид (M,*) называется группой, если для каждого x Î M найдется такой y Î M, что x*y = e. Отсюда данный моноид будет группой, если и только если для каждого x Î M существует y ÎM, удовлетворяющий уравнению x+y-(9/8)xy = 0. Находим y = -x/(1-(9/8)x). Отсюда для x=8/9 это уравнение не имеет решений. Стало быть, заданный моноид не является группой.
Ответ: (M,*) является полугруппой, моноидом, но не является группой.
ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ И ЗАДАЧИ
Вопросы
1. Отношения порядка и эквивалентности.
2. Сочетания и размещения.
3. Упорядоченные размещения.
4. Сочетания с повторениями.
5. Число неубывающих функций между конечными линейно упорядоченными множествами.
6. Число неубывающих сюръекций между конечными линейно упорядоченными множествами.
7. Число возрастающих отображений между конечными линейно упорядоченными множествами.
8. Применение теоремы Эйлера к классификации платоновых тел.
9. Сочетания и бином Ньютона.
10. Обобщенные биноминальные коэффициенты.
11. Решение однородных линейных рекурентных соотношений.
12. Разбиения множества и числа Стирлинга второго рода.
13. Применение эйлеровой характеристики для доказательства того, что граф K3,3 неплоский.
14. Применение эйлеровой характеристики для доказательства того, что граф K5 неплоский.
15. Число Белла.
16. Эйлерова характеристика плоских графов.
17. Принцип включения и исключения.
18. Задача о счастливых билетах.
19. Задача о встречах.
20. Производящая функция чисел Фибоначчи.
21. Теорема Эйлера о сумме валентностей вершин графа.
22. Производящая функция последовательности чисел разбиений числа.
23. Теорема о раскраске плоского графа в пять цветов.
Задачи
1. Найти все множества 
, удовлетворяющие условию 
, для некоторых 
и 
.
2. Сколько чисел из множества {1, 2,...., 2000} не делятся ни на 6, ни на 15, ни на 7?
3. Сколько подмножеств множества {1, 2,...., 1000} содержат по крайней мере одно число кратное 6 и ни одного – кратного 15?
4. Найти число подмножеств множества {1, 2, …, 100}, каждое из которых либо состоит из чисел кратных 3, либо состоит из чисел кратных 4. Например {3, 12} и {4, 12} присутствуют среди этих множеств.
5. Сколько подмножеств множества {1, 2,..., 1000} не содержат ни одного нечетного числа, но имеют по крайней мере одно число кратное 7?
6. Из колоды, содержащей 52 карты, вытащили 10 карт. Какова вероятность того, что среди них окажется 2 туза, 2 короля и две дамы?
7.Найти производящую функцию последовательности an = ann, n = 0, 1, 2,..., где a > 0 – действительное число.
8.Сколько ребер в полном графе K 1000?
9.Найти число сюръекций множества {1,2,3,4,5,6,7} на множество {1,2,3}.
10. Граф состоит из двух треугольников, имеющих общую вершину. Найти хроматический многочлен этого графа.
11. Решить рекуррентное соотношение un+2 – 3un+1 + 2un = 0, при начальных условиях u0 = 1, u1 =4.
12. Найти хроматическую функцию циклического графа C5.
13. Простой граф имеет 27 ребер. Две его вершины имеют степени 4, а остальные – степень 3. Сколько вершин имеет данный граф?
14. Сколько разбиений множества {1,2,3,4,5,6,7} имеют в точности 4 блока?
15. Нарисовать дерево, соответствующее коду Прюфера 333221.
16. Найти производящую функцию последовательности an = (n+ 1)(n+ 2),
n = 0,1,2,...
17. Из колоды, содержащей 52 карты, вытащили 10 карт. Какова вероятность того, что среди них окажется 3 туза, 2 короля и одна дама?
18. Сколько существует чисел, состоящих из невозрастающих последовательностей цифр и содержащих все цифры, например 98777665555443221110.
19. Найти производящую функцию для последовательности чисел an = n2.
20. Сколькими способами можно представить число 320 в виде произведения четырех сомножителей? Произведения, отличающиеся перестановкой сомножителей, считать различными.
21. Нарисовать дерево, код Прюфера которого равен 555512321.
22. Найти производящую функцию последовательности an = n(n+1).
23. Найти производящую функцию для последовательности an = exp (an), где a - фиксированное действительное число.
24. Сколькими способами можно представить число 1024 в виде произведения пяти сомножителей?
25. Сколько семизначных чисел, не начинающихся с нуля, не имеют одинаковых цифр?
26. Найти производящую функцию последовательности an = 1/(n+1).
27. Решить линейное рекуррентное уравнение un+2 = 4un+1 –4 un, u 0 = 2, u1=3.
28. Сколько существует позиций на шахматной доске, состоящих из двух белых и двух черных коней, двух белых и двух черных слонов и белого и черного королей?
29. Решить рекуррентное уравнение un+2 = - un+1 + 12 un, u 0 = 2, u1=3.
30. Сколько существует сюръекций {1,2,3,4,5,6,7} ® {1,2,3,4,5}?
31. Сколько перестановок множества {1,2,3,4,5,6} оставляют неподвижным по крайней мере 1 элемент равный 1, 2, или 3?
32. Найти число раскрасок вершин графа «буква A» в 7 цветов. Вершины, имеющие общее ребро, раскрашиваются в различные цвета.
33. Чему равна сумма делителей числа 300?
34. Квадрат разбит на четыре клетки. Сколькими способами можно раскрасить эти клетки, так, что любые две соседние имеют различные цвета?
35. Сколько подмножеств множества {1,2,..., 2000} содержат по крайней мере одно число, делящееся на 6, но не содержат чисел, кратных 15?
36. Сколько существует шашечных позиций, состоящих из 5 белых и 6 черных шашек?
37. 12 человек разбились на 6 групп, по 2 человека в каждой. Сколькими способами это можно сделать?
38. Сколько существует подмножеств множества {1, 2, 3,..., 2000} имеющих по крайней мере одно число, кратное 6 или 15.
39. Чему равна сумма делителей числа 240?
40. Пусть trace(A) обозначает след матрицы A. Доказать, что если A – матрица смежности простого графа G, то число треугольников в этом графе равно trace(A3)/6.
41. Решить рекуррентное уравнение un+2= 2un+1-un, u0=1, u1=2.
42. Пусть A – матрица смежности простого графа (V,E). Найти число путей длины 2 между каждой парой вершин.
43. Нарисовать граф, вершинами которого являются перестановки трех элементов (i1i2i3). Является ли этот граф плоским?
44. Сколько существует чисел, состоящих из 5 различных цифр и не начинающихся с 0?
45. Каждый из тридцати студентов сдал по крайней мере один зачет. Сдали зачет по математике 26 студентов, по физике – 24, по информатике – 28. Студенты, сдавшие два предмета, сдали и третий. Сколько студентов сдали все зачеты?
46. Сколько подмножеств множества {1,2,…,1000} состоят из чисел, кратных 6, но не имеют ни одного числа, кратного 15?
47. Найти сумму всех делителей числа 288.
48. Сколько различных слов можно составить с помощью перестановок слова «литература»?
49. В урне k шаров красного, зеленого и синего цвета. Какова вероятность того, что среди них 3 шара имеют красный и 2 – синий цвет.
50. Решить рекуррентное уравнение un+2= 10un+1-25un, u0=1, u1=2.
ЛИТЕРАТУРА
1 Биркгоф, Г. Современная прикладная алгебра / Г. Биркгоф, Т. Барти. – М.: Мир, 1976. – 400 с.
2 Грин, Д. Математические методы анализа алгоритмов / Д. Грин, Д. Кнут. – М.: Мир, 1987. – 120 с.
3 Евстигнеев, В.А. Теория графов: алгоритмы обработки деревьев / В.А. Евстигнеев, В.Н. Касьянов. – Новосибирск: ВО «Наука», Сибирская издательская фирма, 1994. – 360 с.
4 Ерусалимский, Я.М. Дискретная математика / Я.М. Ерусалимский. – М.: Вузовская книга, 2009. – 288 с.
5 Иванов, Б.Н. Дискретная математика. Алгоритмы и программы / Б.Н. Иванов. – М.: Лаборатория Базовых Знаний, 2003. – 288 с.
6 Канцедал, С.А. Дискретная математика / С.А. Канцедал. – М.: Форум, Инфра-М, 2011. – 224 с.
7 Комбинаторный анализ. Задачи и упражнения / под ред. К.А. Рыбникова. – М.: Наука, 1982. – 368 с.
8 Кук, Д. Компьютерная математика / С.А. Кук, Г. Бейз. – М.: Наука, 1990. – 384 с.
9 Липский, В. Комбинаторика для программистов / В. Липский. – М.: Мир, 1988. – 213 с.
10 Мальцев, И.А. Дискретная математика / И.А. Мальцев. – М.: Лань, 2011. – 304 с.
11 Маркушевич, А.И. Возвратные последовательности / А.И. Маркушевич. – Москва, Ленинград: Гос. изд-во тех.-теор. лит-ры, 1950. – 47 с.
12 Набебин, А.А. Дискретная математика / А.А. Набебин. – М.: Научный мир, 2010. – 512 с.
13 Набебин, А.А. Сборник заданий по дискретной математике / А.А. Набебин. – М.: Научный мир, 2009. – 280 с.
14 Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков. – СПб: Питер, 2006. – 368 с.
15 Риордан, Дж. Введение в комбинаторный анализ / Дж. Риордан. – М.: Изд-во иностр. лит., 1963. – 287 с.
16 Рыбников, К.А. Комбинаторный анализ. Очерки истории / К.А. Рыбников. – М.: Изд-во мех.-мат. ф-та МГУ, 1996. – 125 с.
17 Спирина, М.С. Дискретная математика / М.С. Спирина, П.А. Спирин. – М.: Академия, 2012. – 368 с.
18 Стенли, Р. Перечислительная комбинаторика / Р. Стенли. – М.: Мир, 1990. –
440 с.
19 Хаггарти, Р. Дискретная математика для программистов / Р. Хаггарти. – М.: Техносфера, 2005. – 400 с.
20 Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский. – М.: Высшая школа, 2001. – 384 с.
21 Lovácz, L. Discrete Mathematics / L. Lovácz, K. Vesztergombi – Yale University, 1999. – 139 p.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ …………………………………………………………………………….…..… 3
1. МНОЖЕСТВА И ОТНОШЕНИЯ …………….………………………………….……..... 4
1.1. Способы задания множеств ………..…………………………………….……....... 4
1.2. Операции и их свойства …..……………………………………………..……....… 4
1.3. Решение уравнений с неизвестным множеством ………………...….…………... 6
1.4. Перечисление подмножеств ………………………………………………………. 7
1.5. Отношения и функции ………………………..………………………………….... 8
1.6. Отношения порядка и эквивалентности.. …..……………………………….…. 12
1.7. Математическое моделирование баз данных ………………………………….... 14
1.8. Упражнения ……………………………………………………………………….. 17
2. КОМБИНАТОРИКА ………………….…………………………………………………. 18
2.1. Размещения ……………………………………………..……………………….…..18
2.2. Сочетания ……………………………………………………………….………..….20
2.3. Формула включения и исключения …………………….……………………..…...24
2.4. Разбиения …………………………………………………………………..……..….26
2.5. Упражнения …………………………………………………………………....…….29
3. ПРОИЗВОДЯЩИЕ ФУНКЦИИ…...…………………………………………………...….32
3.1. Свойства производящих функций …………………………………………...……33
3.2. Разбиения чисел …………………………………………………………………......34
3.3. Числа Фибоначчи ……………………………………………………………..….…35
3.4. Рекуррентные уравнения ……………………………...............................................35
3.5. Упражнения ………………………………………………………………..…….….38
4. ТЕОРИЯ ГРАФОВ …...………………………………………...……………………...…..39
4.1. Эйлеровы графы ……………………………………………………….………..…..39
4.2. Простые графы и их свойства ……………………………….………………….…41
4.3. Хроматическое число графа …………………………………………….………....41
4.4. Деревья ………………………………………………………………….…………..43
4.5. Числа Каталана ………………………………………….…………………….……44
4.6. Плоские графы ………………………………………………………….…….…….46
4.7. Упражнения …………………………………………………………….…….…….50
5. КОНЕЧНЫЕ ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВА..……………....…....54
5.1. Диаграмма Хассе частично упорядоченного множества …………………….….54
5.2. Функция Мебиуса ………………………………………………………….….……55
5.3. Формула обращения ……………………………………………………….….……56
5.4. Теорема о произведении …………………………………………………….….….57
5.5. Упражнения ……………………………………………………………….….…….58
РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ …………………………………………..…… 59
КОНТРОЛЬНАЯ РАБОТА..………………………………………………………………. 64
ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ И ЗАДАЧИ …………………………….……..….. 74
ЛИТЕРАТУРА …………….………………………………………………………...…..…...77
Поиск по сайту: