экзамен-диск-мат2012
.docВопросы к экзамену по дискретной математике 2011—2012 уч.г.
I часть
1. Множества. Свойства операций над ними.
2. Декартово произведение множеств. Булеан.
3. Соответствия. Типы соответствий.
4. Суперпозиции соответствий. Обратные соответствия. Функции.
5. Специальные бинарные отношения.
6. Частично упорядоченные множества. Минимальные и наименьшие элементы.
7. Отношения эквивалентности. Классы эквивалентных элементов.
8. Эквивалентность множеств и ее свойства.
9. Счетные множества. Подмножества счетного множества.
10. Т. об объединении счетных множеств. Счетность мн-ва рациональных чисел.
11. Т. о декартовом произведении счетных множеств.
12. Счетные подмножества бесконечных множеств.
13. Счетные подмножества несчетных множеств.
14.Т. Кантора о несчетности отрезка. Трансцендентные числа.
15.Эквивалентность отрезков, интервалов и прямой.
16.Т. Кантора-Бернштейна.
17. Определение неравенства мощностей. Четыре случая сравнения мощностей.
18.Свойства счетных множеств на языке мощностей.
19. Множество всех подмножеств счетного множества.
20.Т. Кантора о бесконечности шкалы мощностей.
II часть
21. Сочетания, подмножества.
22. Бином Ньютона, треугольник Паскаля.
23. Т. о включениях-исключениях.
24. Т. об объединении подмножеств.
25. Задача о беспорядках.
26. Задача разбиения множества на подмножества. Полиномиальные коэффициенты.
27. Разбиение числа в сумму неотрицательных слагаемых.
28. Разбиение числа в сумму положительных слагаемых.
29. О методе производящих функций.
30. Обобщения: перестановки с повторениями, сочетания с повторениям.
31. Графы. Разметки графов. Изоморфизм.
32. Степени вершин. Количество помеченных графов на n вершинах.
33. Лемма о рукопожатиях. Следствие о числе вершин нечетной степени.
34. Критерии простого цикла и простой цепи.
35. Теорема об остовном дереве связного графа.
36. Перестановки и подстановки. Произведения подстановок. Разложения подстановок в независимые циклы.
37. Перестановочные матрицы и их основные свойства.
38. Матрица смежности. Матрицы смежности изоморфных графов.
39. Связность. Компоненты связности. Дополнительные графы и связность. Следствие о числе ребер связного графа.
40. Метрика на графах. Диаметр и радиус. Связь диаметров взаимно дополнительных графов.
41. Диаметр и ранг графа.
42. Матрица инцидентности и ее ранг.
43. Матрица Кирхгофа, ее связь с матрицей инцидентности. Матрицы Кирхгофа изоморфных графов.
44. Свойство алгебраических дополнений к элементам матрицы Кирхгофа.
45. Теорема об определении дерева.
46. Следствия определения дерева.
47. Дополнение ациклического подграфа до остовного дерева.
48. Перестроение остовных деревьев.
49. Лемма об (n+1,n) – графах.
50. Формула Бинэ-Коши. Теорема Кирхгофа.
51. Теорема Кэли. Следствие о числе помеченных деревьев. Ранг матрицы Кирхгофа.
52. Построение регулярных графов.
Л И Т Е Р А Т У Р А
1 Яблонский С.В.
Введение в дискретную математику.
2 Александров П.С.
Введение в теорию множеств и функций.
3 Клини С.К.
Математическая логика.
4 Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для
инженера.
5 Гаврилов, Сапоженко Сборник задач по дискретной математике
6 Лавров И.А., Максимова Л.Л. Задачи по математической логике,
теории алгоритмов и теории множеств.
7. Элементы теории множеств и математической логики. Теория и задачи
Учебное пособие, 2005 сост. Башкин В.А., Белова Л.Ю., Белов Ю.А.