Конспект лекций Дискретная математика
Конспект лекций по дисциплине “Дискретная математика”
Студента: Лавренова Дмитрия
Факультета: KТиУ
Специальность: БИТ
Группа: 1133
2012
Содержание
- Конспект лекций по дисциплине “Дискретная математика”
- Санкт Петербург Содержание.
- Раздел I. Множества, функции, отношения. Лекция № 1. Множества и операции над ними.
- 1. Основные понятия теории множеств.
- 2. Операции над множествами и их свойства.
- 3. Векторы и прямые произведения.
- Лекция № 2. Соответствия и функции.
- Соответствия.
- Отображения и функции.
- Лекция № 3. Отношения и их свойства.
- Основные понятия и определения.
- Свойства отношений.
- Лекция № 4. Основные виды отношений.
- Отношения эквивалентности.
- Отношения порядка.
- Лекция № 4. Пересчёт.
- Раздел II. Введение в общую алгебру. Лекция № 6. Элементы общей алгебры.
- 1. Свойства бинарных алгебраических операций.
- 2. Алгебраические структуры.
- Гомоморфизм и изоморфизм.
- Лекция № 7. Различные виды алгебраических структур.
- Полугруппы.
- Группы.
- Поля и кольца.
- Раздел III. Введение в логику. Лекция № 8. Элементы математической логики.
- Булевы функции.
- Лекция № 9. Логические функции.
- Функции алгебры логики.
- Примеры логических функций.
- Суперпозиции и формулы.
- Лекция № 10. Булевы алгебры.
- Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.
- Булева алгебра функций.
- Эквивалентные преобразования.
- Лекция № 11. Булевы алгебры и теория множеств.
- Двойственность.
- Булева алгебра и теория множеств.
- Днф, интервалы и покрытия.
- Лекция № 12. Полнота и замкнутость.
- Функционально полные системы.
- Алгебра Жегалкина и линейные функции.
- Замкнутые классы. Монотонные функции.
- Теоремы о функциональной полноте.
- Лекция № 13. Язык логики предикатов.
- Предикаты.
- Кванторы.
- Истинные формулы и эквивалентные соотношения.
- Доказательства в логике предикатов.
- Лекция № 14. Комбинаторика.
- Правила суммы и произведения.
- Размещения.
- Перестановки.
- Сочетания. Бином Ньютона.
- Раздел IV. Теория графов. Лекция № 15. Графы: основные понятия и операции.
- Графы, их вершины, рёбра и дуги. Изображение графов.
- Матрица инцидентности и список рёбер. Матрица смежности графа.
- Идентификация графов, заданных своими представлениями.
- Лекция № 16. Маршруты, цепи и циклы.
- Основные определения.
- Связные компоненты графов.
- Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- Эйлеровы графы.
- Лекция № 17. Некоторые классы графов и их частей.
- Деревья.
- Ориентированные графы.
- Графы с помеченными вершинами и рёбрами.
- Лекция № 18. Теория алгоритмов Понятие алгоритма
- 1.2.1. Основные требования к алгоритмам
- 1.2.2. Машина Тьюринга
- Универсальная машина Тьюринга
- 1.2.3. Тезис Тьюринга
- 1.3. Граф машина
- 1.3.1. Модель данных
- 1.3.2. Построение моделей алгоритмов в системе graph
- 2. Сложность алгоритмов
- 2.1.Временная и пространственная сложность алгоритма. Классы dtime и dspace
- 2.2. Классы сложности
- 2.2.1. Полиномиальность и эффективность
- 2.2.2. Алгоритмическая сводимость задач
- 3. Алгоритмы и их сложность
- 3.1. Представление абстрактных объектов (последовательностей)
- 3.1.1. Смежное представление последовательностей
- 3.1.2. Связанное представление последовательностей
- Список вопросов для подготовки к экзамену по дисциплине "дискретная математика"