| bovali | Дата: Пятница, 01.10.2010, 10:13 | Сообщение # 1 |
|
Сержант
Группа: Администраторы
Сообщений: 30
Статус: Offline
| ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ
Содержание
1. Дискретная математика. Теория множеств и отношения
1. Множества. Операции над множествами и их свойства. Булева алгебра множеств. Ото-бражения множеств. Композиция отображений. Виды отображений. Критерий обратимости. Де-картово произведение множеств.
2. Бинарные отношения. Отношения эквивалентности, фактор-множества. Отношения частичного порядка. Частично упорядоченные, линейно упорядоченные и вполне упорядочен-ные множества. Решетки.
3. Мощность множества. Сравнение мощностей. Кардинальные числа. Теорема Кантора. Понятие об алгебраических структурах. Группы, кольца, поля.
2. Математическая логика
1. Высказывания. Логические союзы. Формулы. Тавтологии. Законы логики. Булевы функции. Пропозиционные формулы. Многочлены Жегалкина. Полные системы булевых функ-ций. Теоремы о полноте. Базисы. Нормальные формы булевых функций. СДНФ и СКНФ. Теоре-ма Шеннона. Минимизация булевых функций в классе ДНФ. Алгоритм Квайна. Метод карт Карно. Реализации булевых функций. Логические схемы.
2. Предикаты. Кванторы. Формулы исчисления предикатов. Предваренная нормальная форма. Понятие об алгоритмических теориях. Полнота и непротиворечивость. Теоремы Геделя. Понятие о машине Тьюринга.
3. Теория графов
1. Основные определения: графы, мультиграфы, псевдографы, орграфы. Числовые харак-теристики и матрицы графов и орграфов. Изоморфные графы. Маршруты, пути, циклы, цепи. Связные компоненты графа. Расстояние в графах. Радиус, диаметр, центры связного графа. Ал-горитм поиска в ширину.
2. Остовы и деревья. Алгоритмы нахождения остовов минимального веса, пути мини-мальной длины. Циклы и разрезы. Циклический и коциклический ранг графа. Двудольные гра-фы. Критерий двудольности. Задачи о назначениях и о паросочетаниях. Теорема Менгера. Сети. Двудольные сети. Задача о наибольшем потоке. Теорема Форда – Фалкерсона.
3. Планарные графы. Теорема Куратовского-Понтрягина. Раскраски графа. Хроматиче-ское число графа. Эйлеровы графы. Критерий эйлеровости графа. Гамильтоновы графы. Задача коммивояжера. Метод ветвей и границ.
|
| |
| |
