|
Это в лекции 3. |
Основы дискретной математики: Информация
Автор: Михаил Дехтярь | Тверской государственный университет
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 37 студентам
Уровень:
Специалист
Длительность:
15:40:00
Студентов:
3183
Выпускников:
268
Качество курса:
4.08 | 3.92
Это начальный курс по дискретным структурам. Лекции курса содержат все необходимые для изучения основного материала предварительные сведения о множествах, комбинаторике и методе математической индукции.
Рассмотрен самый простой и важный класс дискретных функций - булевы функции: их различные представления, связь с логикой высказываний, основные логические тождества ("законы логики"), дизъюнктивные и конъюнктивные нормальные формы и многочлены Жегалкина, полные системы функций (теорема Поста), задача выводимости для Хорновских формул.
Даны краткое введение в логику предикатов и устанавливаются связи между ней и реляционными базами данных, введение в теорию графов, включающее представления графов, граф достижимости, компоненты сильной связности и базы ориентированного графа, деревья, их обходы, связь деревьев и формул (выражений), три классические задачи теории графов: построение минимального остова, обход графа в глубину (задачу о лабиринте) и задачу о кратчайших путях.
Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Специальности: Программист, Математик
ISBN: 978-5-9556-0110-6
Теги: beta, алгоритм Дейкстры, алгоритмы, булева формула, булева функция, законы, замыкание, комбинаторика, компоненты, кортеж, логика, логика предикатов, множество вершин, неориентированный граф, подформула, поиск, процедуры, сложность, тождество, элементы
План занятий
Занятие
Заголовок <<
Дата изучения
Лекция 1
57 минут
Предварительные сведения
Множества и операции над ними.
Как доказывать равенство множеств? Отношения и функции.
Отношения эквивалентности и частичного порядка.
Мощность множеств
Оглавление
-
Лекция 2
48 минут
Индукция и комбинаторика
Метод математической индукции. Индукция по структуре объекта.
Комбинаторика: число размещений, перестановок и сочетаний.
Принцип включения и исключения
Оглавление
-
Лекция 3
1 час 14 минут
Булевы функции и их представления
Класс Pn булевых функций от n переменных. Геометрическое представление
булевых функций. Задание булевых функций с помощью таблиц. Булевы функции от 1-ой
и 2-х переменных. булевы (логические) формулы. Решение задач логики
высказываний с помощью булевых формул и функций
Оглавление
-
Лекция 4
1 час 28 минут
Эквивалентность формул и нормальные формы
Эквивалентность булевых формул.
Основные эквивалентности (законы логики).
Эквивалентные преобразования формул. Принцип замены эквивалентных.
Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Совершенные
ДНФ и КНФ. Сокращенные ДНФ и их построение методом Блейка. Многочлены Жегалкина
и их построение с помощью эквивалентных преобразований формул и методом
неопределенных
коэффициентов по таблицам
Оглавление
-
Лекция 5
1 час
Полные системы функций и теорема Поста
Замкнутые классы функций. Полные системы булевых функций.
Замкнутость классов функций, сохраняющих 0, функций, сохраняющих 1,
самодвойственных функций, монотонных функций и линейных функций.
Критерий полноты системы булевых функций (теорема Поста)
Оглавление
-
Лекция 6
58 минут
Хорновские формулы и задача получения продукции
Хорновские формулы. Задача получения продукции.
Связь между задачей о следствии для Хорновских формул и разрешимостью
задачи о продукции. Эффективные алгоритмы прямого поиска (поиска от данных)
для решения задачи о продукции
Оглавление
-
Лекция 7
1 час 47 минут
Язык логики предикатов
Объекты, их свойства, отношения между объектами и функции.
Утверждения о свойствах объектов и отношениях между ними. Предикаты.
Синтаксис логики предикатов. Семантика логики предикатов: системы,
состояния и значения формул на состояниях
Оглавление
-
Лекция 8
53 минуты
Логика предикатов и базы данных
Реляционные базы данных. Схемы отношений и предикаты. Реляционная алгебра
и представление ее выражений формулами логики предикатов. Язык запросов SQL и
его связь с логикой предикатов. Ограничения целостности: ограничения на ключи,
ограничения на ссылки и ограничения на значения атрибутов
Оглавление
-
Лекция 9
1 час 16 минут
Графы: представления, достижимость и связность
Ориентированные и неориентированные графы. Представление графа с помощью
матрицы смежности, матрицы инцидентности и списов смежности. Граф достижимости (транзитивного
замыкания). Отношение взаимной достижимости, компоненты сильной связности
и базы ориентированного графа
Оглавление
-
Лекция 11
1 час 18 минут
Три алгоритма на графах
Построение минимального остова графа: алгоритм Крускала. Задача о лабиринте и поиск в глубину на неориентированном графе. Нахождение кратчайших путей из одного источника: алгоритм Дейкстры
Оглавление
-
Татьяна Дембелова
|
Почему в вводной лекции курса Основы дискретной математики одним из свойств отношения частичного порядка упоминается антирефлексивность? Посмотрела в других источниках, там -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 |