1) *Понятие множества и его элементов. Способы задания множеств. Подмножества.
2) *Операции над множествами (объединение, пересечение, …), их графическое представление.
3) *Способы представления множеств в ЭВМ.
4) *Алгоритм типа слияния для различных операций над множествами.
5) *Разбиения и покрытия.
6) *Свойства операций над множествами (коммутативность, ассоциативность, …).
7) *Отношения на множествах. Способы задания отношений.
8) *Специальные отношения (обратное, универсальное, тождественное). Композиция отношений.
9) *Свойства отношений (рефлексивность, симметричность, транзитивность, …), теорема 1.1 о свойствах отношений.
10) *Теорема 1.2 о проверке свойств отношений.
11) *Представление отношений в ЭВМ и проверка свойств отношений с помощью матриц.
12) *Отношение эквивалентности и разбиения.
13) *Отношение порядка и его свойства. Частично упорядоченные множества, наибольший и наименьший, максимальный и минимальный элементы, точная верхняя и нижняя грани. Понятие замкнутости множеств.
14) *Понятие функции. Классификация функций (биекция, сюръекция, …). Некоторые специальные функции (перестановка, характеристическая функция,…)
15) *Принцип математической индукции (индуктивное определение, индуктивное доказательство).
16) *Комбинаторные задачи. Основные комбинаторные принципы (сложения и умножения).
17) *Перестановка и функция подстановки. Способ задания, операции (произведение подстановок, обратная подстановка).
18) *Понятие выборки. Способы классификации выборок.
19) *Размещения и сочетания без повторений – определение, формулы для расчета числа вариантов.
20) *Размещения и сочетания с повторениями – определение, формулы для расчета числа вариантов.
21) *Биномиальные коэффициенты. Теорема о свойствах биномиальных коэффициентов (Теорема 2.4). Треугольник Паскаля.
22) *Бином Ньютона и следствия. Тождество Коши.
23) *Перестановки с повторениями.
24) *Разбиения и числа Стирлинга. Упорядоченные и неупорядоченные разбиения. Полиномиальная теорема.
25) *Комбинаторный принцип сложения для пересекающихся множеств. Принцип включения и исключения. Подсчет числа предметов, обладающих ровно r свойствами.
26) *Рекуррентные уравнения, общий вид и примеры. Возвратная последовательность порядка k.
27) *Возвратное уравнение и характеристический многочлен. Поиск решения возвратного уравнения (Теорема о корнях характеристического многочлена).
28) *Графы – основные понятия, способы представления.
29) *Виды графов (орграф, псевдограф, …) и их связь с бинарными отношениями.
30) *Изоморфизм графов и его свойства.
31) *Степени вершин. Лемма о рукопожатиях.
32) *Маршруты, цепи, циклы. Расстояние между вершинами, диаметр графа.
33) *Связность, компоненты связности. Сильная и слабая связность. Выделение компонент сильной связности в орграфе.
34) *Подграфы. Минимальный остов и алгоритм его построения.
35) *Виды графов – пустой, полный, двудольный, сети.
36) Операции над графами. Удаление и добавление вершин, ребер, стягивание вершин и подграфа, соединение, объединение и произведение графов.
37) *Деревья. Ориентированные деревья.
38) *Способы представления графов в ЭВМ.
39) *Понятие обхода графа. Поиск в глубину и в ширину.
40) *Алгоритмы поиска кратчайших путей в графе. Алгоритм Дейкстры.
41) *Алгоритмы поиска кратчайших путей в графе. Алгоритм Флойда-Уоршалла.
42) *Эйлеровы и гамильтоновы графы, понятия эйлеровой цепи, цикла, гамильтонова цикла. Алгоритм поиска эйлеровой цепи.
43) *Высказывания алгебры логики, операции над ними. Таблицы истинности основных операций.
44) *Построение формул, их синтаксис и семантика. Приоритет операций. Расстановка скобок. Равносильность формул.
45) *Функции алгебры логики и формулы. Функции частичные и полностью определенные, переменные существенные и фиктивные.
46) *Теорема о подстановке формул. Правила подстановки и замены.
47) *Булевы функции и булева алгебра. Аксиомы булевой алгебры. Их применение.
48) *Нормальные формы. Теорема о разложении булевой функции по k переменным.
49) *Совершенные нормальные формы и способы их построения.
50) *Карты Карно: построение, определения, использование для нахождения упрощенного представления функции.
51) *Контактные схемы и булевы функции. Применение булевой алгебры для упрощения контактных схем.
52) *Понятие импликанты и простой импликанты. Минимальная и сокращенная ДНФ.
53) *Нахождение минимальной ДНФ – метод Квайна-Мак-Класки. Основные этапы метода. Подробно – построение сокращенной ДНФ.
54) *Нахождение минимальной ДНФ – метод Квайна-Мак-Класки. Основные этапы метода. Подробно – построение импликантной таблицы и ее упрощение.
55) *Минимизация частично определенных функций с помощью карт Карно и метода Квайна-Мак-Класки.
56) Функциональная полнота. Примеры базисов, формулы перехода к базису Буля.
57) Классы булевых функций, примеры.
58) Алгебра Жегалкина. Переход от алгебры Жегалкина к алгебре Буля. Многочлен Жегалкина.
59) Теорема Поста (формулировка, применение, примеры)
Вопросы к экзамену по курсу "Дискретная математика"
Страница: 1
Сообщений 1 страница 1 из 1
Поделиться12010-05-30 19:34:16
Страница: 1