Information
Created: 20.08.2007 | Level: specialist | Access: paid | University: Тверской государственный университет
Это начальный курс по дискретным структурам. Лекции курса содержат все необходимые для изучения основного материала предварительные сведения о множествах, комбинаторике и методе математической индукции.
Рассмотрен самый простой и важный класс дискретных функций - булевы функции: их различные представления, связь с логикой высказываний, основные логические тождества ("законы логики"), дизъюнктивные и конъюнктивные нормальные формы и многочлены Жегалкина, полные системы функций (теорема Поста), задача выводимости для Хорновских формул.
Даны краткое введение в логику предикатов и устанавливаются связи между ней и реляционными базами данных, введение в теорию графов, включающее представления графов, граф достижимости, компоненты сильной связности и базы ориентированного графа, деревья, их обходы, связь деревьев и формул (выражений), три классические задачи теории графов: построение минимального остова, обход графа в глубину (задачу о лабиринте) и задачу о кратчайших путях.
Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Goal: Обучение студентов методам мышления, характерным для дискретной математики, основным понятиям таких ее дисциплин как комбинаторика, булевы функции, логика предикатов и графы. Еще одна цель - привить студентам навыки алгоритмического мышления на примерах решения задач из рассматриваемых разделов дискретной математики.
Prerequisites: Изучение курса не требует предварительных знаний, выходящих за рамки школьной программы по математике.
План занятий
| Lesson | Title << | Date |
|---|---|---|
| - | ||
Lecture 157 minutes | Предварительные сведения
Множества и операции над ними.
Как доказывать равенство множеств? Отношения и функции.
Отношения эквивалентности и частичного порядка.
Мощность множеств
Contents | - |
Тест 118 minutes | - | |
Lecture 248 minutes | Индукция и комбинаторика
Метод математической индукции. Индукция по структуре объекта.
Комбинаторика: число размещений, перестановок и сочетаний.
Принцип включения и исключения
Contents | - |
Тест 221 minute | - | |
Lecture 31 hour 14 minutes | Булевы функции и их представления
Класс Pn булевых функций от n переменных. Геометрическое представление
булевых функций. Задание булевых функций с помощью таблиц. Булевы функции от 1-ой
и 2-х переменных. булевы (логические) формулы. Решение задач логики
высказываний с помощью булевых формул и функций
Contents | - |
Тест 318 minutes | - | |
Lecture 41 hour 28 minutes | Эквивалентность формул и нормальные формы
Эквивалентность булевых формул.
Основные эквивалентности (законы логики).
Эквивалентные преобразования формул. Принцип замены эквивалентных.
Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Совершенные
ДНФ и КНФ. Сокращенные ДНФ и их построение методом Блейка. Многочлены Жегалкина
и их построение с помощью эквивалентных преобразований формул и методом
неопределенных
коэффициентов по таблицам
Contents | - |
Тест 418 minutes | - | |
Lecture 51 hour | Полные системы функций и теорема Поста
Замкнутые классы функций. Полные системы булевых функций.
Замкнутость классов функций, сохраняющих 0, функций, сохраняющих 1,
самодвойственных функций, монотонных функций и линейных функций.
Критерий полноты системы булевых функций (теорема Поста)
Contents | - |
Тест 518 minutes | - | |
Lecture 658 minutes | Хорновские формулы и задача получения продукции
Хорновские формулы. Задача получения продукции.
Связь между задачей о следствии для Хорновских формул и разрешимостью
задачи о продукции. Эффективные алгоритмы прямого поиска (поиска от данных)
для решения задачи о продукции
Contents | - |
Тест 612 minutes | - | |
Lecture 71 hour 47 minutes | Язык логики предикатов
Объекты, их свойства, отношения между объектами и функции.
Утверждения о свойствах объектов и отношениях между ними. Предикаты.
Синтаксис логики предикатов. Семантика логики предикатов: системы,
состояния и значения формул на состояниях
Contents | - |
Тест 718 minutes | - | |
Lecture 853 minutes | Логика предикатов и базы данных
Реляционные базы данных. Схемы отношений и предикаты. Реляционная алгебра
и представление ее выражений формулами логики предикатов. Язык запросов SQL и
его связь с логикой предикатов. Ограничения целостности: ограничения на ключи,
ограничения на ссылки и ограничения на значения атрибутов
Contents | - |
Тест 818 minutes | - | |
Lecture 91 hour 16 minutes | Графы: представления, достижимость и связность
Ориентированные и неориентированные графы. Представление графа с помощью
матрицы смежности, матрицы инцидентности и списов смежности. Граф достижимости (транзитивного
замыкания). Отношение взаимной достижимости, компоненты сильной связности
и базы ориентированного графа
Contents | - |
Тест 918 minutes | - | |
Lecture 1046 minutes | Деревья
Неориентированные и ориентированные деревья.
Эквивалентность разных определений деревьев.
Деревья и формулы (выражения). Обходы деревьев
Contents | - |
Тест 1018 minutes | - | |
Lecture 111 hour 18 minutes | Три алгоритма на графах
Построение минимального остова графа: алгоритм Крускала. Задача о лабиринте и поиск в глубину на неориентированном графе. Нахождение кратчайших путей из одного источника: алгоритм Дейкстры
Contents | - |
Тест 1118 minutes | - | |
5 hours | - |