|
Это в лекции 3. |
Опубликован: 21.08.2007 | Уровень: специалист | Доступ: свободно | ВУЗ: Тверской государственный университет
Это начальный курс по дискретным структурам. Лекции курса содержат все необходимые для изучения основного материала предварительные сведения о множествах, комбинаторике и методе математической индукции.
Рассмотрен самый простой и важный класс дискретных функций - булевы функции: их различные представления, связь с логикой высказываний, основные логические тождества ("законы логики"), дизъюнктивные и конъюнктивные нормальные формы и многочлены Жегалкина, полные системы функций (теорема Поста), задача выводимости для Хорновских формул.
Даны краткое введение в логику предикатов и устанавливаются связи между ней и реляционными базами данных, введение в теорию графов, включающее представления графов, граф достижимости, компоненты сильной связности и базы ориентированного графа, деревья, их обходы, связь деревьев и формул (выражений), три классические задачи теории графов: построение минимального остова, обход графа в глубину (задачу о лабиринте) и задачу о кратчайших путях.
Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Цель: Обучение студентов методам мышления, характерным для дискретной математики, основным понятиям таких ее дисциплин как комбинаторика, булевы функции, логика предикатов и графы. Еще одна цель - привить студентам навыки алгоритмического мышления на примерах решения задач из рассматриваемых разделов дискретной математики.
Необходимые знания: Изучение курса не требует предварительных знаний, выходящих за рамки школьной программы по математике.
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Лекция 157 минут | Предварительные сведения
Множества и операции над ними.
Как доказывать равенство множеств? Отношения и функции.
Отношения эквивалентности и частичного порядка.
Мощность множеств
Оглавление | - |
Тест 118 минут | - | |
Лекция 248 минут | Индукция и комбинаторика
Метод математической индукции. Индукция по структуре объекта.
Комбинаторика: число размещений, перестановок и сочетаний.
Принцип включения и исключения
Оглавление | - |
Тест 221 минута | - | |
Лекция 31 час 14 минут | Булевы функции и их представления
Класс Pn булевых функций от n переменных. Геометрическое представление
булевых функций. Задание булевых функций с помощью таблиц. Булевы функции от 1-ой
и 2-х переменных. булевы (логические) формулы. Решение задач логики
высказываний с помощью булевых формул и функций
Оглавление | - |
Тест 318 минут | - | |
Лекция 41 час 28 минут | Эквивалентность формул и нормальные формы
Эквивалентность булевых формул.
Основные эквивалентности (законы логики).
Эквивалентные преобразования формул. Принцип замены эквивалентных.
Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Совершенные
ДНФ и КНФ. Сокращенные ДНФ и их построение методом Блейка. Многочлены Жегалкина
и их построение с помощью эквивалентных преобразований формул и методом
неопределенных
коэффициентов по таблицам
Оглавление | - |
Тест 418 минут | - | |
Лекция 51 час | Полные системы функций и теорема Поста
Замкнутые классы функций. Полные системы булевых функций.
Замкнутость классов функций, сохраняющих 0, функций, сохраняющих 1,
самодвойственных функций, монотонных функций и линейных функций.
Критерий полноты системы булевых функций (теорема Поста)
Оглавление | - |
Тест 518 минут | - | |
Лекция 658 минут | Хорновские формулы и задача получения продукции
Хорновские формулы. Задача получения продукции.
Связь между задачей о следствии для Хорновских формул и разрешимостью
задачи о продукции. Эффективные алгоритмы прямого поиска (поиска от данных)
для решения задачи о продукции
Оглавление | - |
Тест 612 минут | - | |
Лекция 71 час 47 минут | Язык логики предикатов
Объекты, их свойства, отношения между объектами и функции.
Утверждения о свойствах объектов и отношениях между ними. Предикаты.
Синтаксис логики предикатов. Семантика логики предикатов: системы,
состояния и значения формул на состояниях
Оглавление | - |
Тест 718 минут | - | |
Лекция 853 минуты | Логика предикатов и базы данных
Реляционные базы данных. Схемы отношений и предикаты. Реляционная алгебра
и представление ее выражений формулами логики предикатов. Язык запросов SQL и
его связь с логикой предикатов. Ограничения целостности: ограничения на ключи,
ограничения на ссылки и ограничения на значения атрибутов
Оглавление | - |
Тест 818 минут | - | |
Лекция 91 час 16 минут | Графы: представления, достижимость и связность
Ориентированные и неориентированные графы. Представление графа с помощью
матрицы смежности, матрицы инцидентности и списов смежности. Граф достижимости (транзитивного
замыкания). Отношение взаимной достижимости, компоненты сильной связности
и базы ориентированного графа
Оглавление | - |
Тест 918 минут | - | |
Лекция 1046 минут | Деревья
Неориентированные и ориентированные деревья.
Эквивалентность разных определений деревьев.
Деревья и формулы (выражения). Обходы деревьев
Оглавление | - |
Тест 1018 минут | - | |
Лекция 111 час 18 минут | Три алгоритма на графах
Построение минимального остова графа: алгоритм Крускала. Задача о лабиринте и поиск в глубину на неориентированном графе. Нахождение кратчайших путей из одного источника: алгоритм Дейкстры
Оглавление | - |
Тест 1118 минут | - | |
5 часов | - |
Татьяна Дембелова
|
Почему в вводной лекции курса Основы дискретной математики одним из свойств отношения частичного порядка упоминается антирефлексивность? Посмотрела в других источниках, там -0 рефлексивность... http://ru.wikipedia.org/wiki/%D0%9E%D1%82%D0%BD%D0%BE%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B0 |
