Программа курса "Дискретная математика"

Множества. Операции над множествами. Примеры [1,2,3].
Булеан. Свойства операций над подмножествами. Примеры [1,2,3].
Представление множеств и реализация операций над ними в ЭВМ [1,2,3].
Отображения, функции. Представление функций в ЭВМ [1,2,3].
Операции. Примеры [1,2,3].
Отношения и их свойства. Примеры [1,2,3].
Представление отношений в ЭВМ [1,2,3].
Отношения эквивалентности. Примеры [1,2,3].
Отношения порядка. Примеры [1,2,3].
Замыкание отношений. Примеры [1,2,3].
Алгебры, подалгебры, морфизмы. Основные определения и свойства Примеры [1,2,3].
Определение и основные свойства булевых алгебр. Примеры [1,2,3].
Нормированные булевы алгебры [1,2,3].
Алгебра логики. Элементарные булевы функции (функции алгебры логики) [1,2,3,4].
Формулы. Реализация функций формулами. Примеры [1,2,3,4].
Принцип двойственности. Примеры применения принципа [1,2,3,4].
Нормальные формы. Примеры [1,2,3,4].
Представление булевых функций полиномом Жигалкина И.И. Примеры [1,2,3,4].
Замкнутые классы булевых функций. Примеры [1,2,3,4].
Полнота множества булевых функций. Примеры [1,2,3,4].
Минимизация булевых функций. Примеры [1,2,3,4].
Упрощение дизъюнктивной нормальной формы (ДНФ), тупиковые ДНФ. Примеры [1,2,3,4].
Синтез схем из функциональных элементов. Примеры [1,4].
Оптимальный по порядку метод синтеза схем из функциональных элементов (метод К. Шеннона). Пример [1,4].
Асимптотически наилучший метод синтеза схем из функциональных элементов (метод О.Б.Лупанова). Пример [1,4].
Графы. Виды графов. Изоморфизм графов. Примеры [1,3]
Подграфы, маршруты, цепи, циклы. Примеры [1,3]
Представление графов в ЭВМ. Матрицы смежностей, инциденций. Примеры [1,3]
Связность графов. Компоненты связности. Примеры [1,3]
Операции над графами. Примеры [1,3]
Планарные графы. Критерии планарности. Примеры [1,3]
Сети. Потоки в сетях. Теорема Форда и Фалкерсона. Примеры [1,3]
Алгоритм нахождения максимального потока, основанный на теореме Форда и Фалкерсона. Пример [1,3]
Деревья. Ориентированные, упорядоченные и бинарные деревья. Свойства деревьев. Примеры [1,3]
Представления деревьев в ЭВМ. Примеры [1,3]
Нахождение кратчайшего пути в графе. Примеры [1,3]
Фундаментальные циклы и разрезы. Примеры [1,3]
Эйлеровы циклы. Примеры [1,3]
Гамильтоновы циклы. Примеры [1,3]
Алфавитное кодирование. Неравенство Макмиллана. Примеры [1,3,4]
Кодирование с минимальной избыточностью. Примеры [1,3,4]
Помехоустойчивое кодирование. Примеры [1,3,4]
Код Хемминга для исправления одного замещения. Пример [1,3,4]
Сжатие данных. Алгоритм Лемпела-Зива. Примеры [1,3]
Конспект лекций
В.И. Городецкий "Прикладная алгебра и дискретная математика. ч.1 М., 1983 г.
Новиков Ф.А. "Дискретная математика для программистов", СПб, 2000 г.
C.В. Яблонский "Введение в дискретную математику" М., Наука, 1988 г.
2. Графы. Виды графов. Изоморфизм графов. Примеры.

Оцените статью
Добавить комментарий