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