Автор: Михаил Дехтярь | Тверской государственный университет
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Специалист
Длительность:
15:40:00
Студентов:
3170
Выпускников:
266
Качество курса:
4.08 | 3.92
Это начальный курс по дискретным структурам. Лекции курса содержат все необходимые для изучения основного материала предварительные сведения о множествах, комбинаторике и методе математической индукции.
Рассмотрен самый простой и важный класс дискретных функций - булевы функции: их различные представления, связь с логикой высказываний, основные логические тождества ("законы логики"), дизъюнктивные и конъюнктивные нормальные формы и многочлены Жегалкина, полные системы функций (теорема Поста), задача выводимости для Хорновских формул. Даны краткое введение в логику предикатов и устанавливаются связи между ней и реляционными базами данных, введение в теорию графов, включающее представления графов, граф достижимости, компоненты сильной связности и базы ориентированного графа, деревья, их обходы, связь деревьев и формул (выражений), три классические задачи теории графов: построение минимального остова, обход графа в глубину (задачу о лабиринте) и задачу о кратчайших путях. Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Специальности: Программист, Математик
ISBN: 978-5-9556-0110-6
 

План занятий

Занятие
Заголовок <<
Дата изучения
Лекция 1
57 минут
Предварительные сведения
Множества и операции над ними. Как доказывать равенство множеств? Отношения и функции. Отношения эквивалентности и частичного порядка. Мощность множеств
Оглавление
    -
    Лекция 2
    48 минут
    Индукция и комбинаторика
    Метод математической индукции. Индукция по структуре объекта. Комбинаторика: число размещений, перестановок и сочетаний. Принцип включения и исключения
    Оглавление
      -
      Тест 2
      21 минута
      -
      Лекция 3
      1 час 14 минут
      Булевы функции и их представления
      Класс Pn булевых функций от n переменных. Геометрическое представление булевых функций. Задание булевых функций с помощью таблиц. Булевы функции от 1-ой и 2-х переменных. булевы (логические) формулы. Решение задач логики высказываний с помощью булевых формул и функций
      Оглавление
        -
        Лекция 4
        1 час 28 минут
        Эквивалентность формул и нормальные формы
        Эквивалентность булевых формул. Основные эквивалентности (законы логики). Эквивалентные преобразования формул. Принцип замены эквивалентных. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Совершенные ДНФ и КНФ. Сокращенные ДНФ и их построение методом Блейка. Многочлены Жегалкина и их построение с помощью эквивалентных преобразований формул и методом неопределенных коэффициентов по таблицам
        Оглавление
          -
          Полные системы функций и теорема Поста
          Замкнутые классы функций. Полные системы булевых функций. Замкнутость классов функций, сохраняющих 0, функций, сохраняющих 1, самодвойственных функций, монотонных функций и линейных функций. Критерий полноты системы булевых функций (теорема Поста)
          Оглавление
            -
            Лекция 6
            58 минут
            Хорновские формулы и задача получения продукции
            Хорновские формулы. Задача получения продукции. Связь между задачей о следствии для Хорновских формул и разрешимостью задачи о продукции. Эффективные алгоритмы прямого поиска (поиска от данных) для решения задачи о продукции
            Оглавление
              -
              Лекция 7
              1 час 47 минут
              Язык логики предикатов
              Объекты, их свойства, отношения между объектами и функции. Утверждения о свойствах объектов и отношениях между ними. Предикаты. Синтаксис логики предикатов. Семантика логики предикатов: системы, состояния и значения формул на состояниях
              Оглавление
                -
                Лекция 8
                53 минуты
                Логика предикатов и базы данных
                Реляционные базы данных. Схемы отношений и предикаты. Реляционная алгебра и представление ее выражений формулами логики предикатов. Язык запросов SQL и его связь с логикой предикатов. Ограничения целостности: ограничения на ключи, ограничения на ссылки и ограничения на значения атрибутов
                Оглавление
                  -
                  Лекция 9
                  1 час 16 минут
                  Графы: представления, достижимость и связность
                  Ориентированные и неориентированные графы. Представление графа с помощью матрицы смежности, матрицы инцидентности и списов смежности. Граф достижимости (транзитивного замыкания). Отношение взаимной достижимости, компоненты сильной связности и базы ориентированного графа
                  Оглавление
                    -
                    Лекция 10
                    46 минут
                    Деревья
                    Неориентированные и ориентированные деревья. Эквивалентность разных определений деревьев. Деревья и формулы (выражения). Обходы деревьев
                    Оглавление
                      -
                      Лекция 11
                      1 час 18 минут
                      Три алгоритма на графах
                      Построение минимального остова графа: алгоритм Крускала. Задача о лабиринте и поиск в глубину на неориентированном графе. Нахождение кратчайших путей из одного источника: алгоритм Дейкстры
                      Оглавление
                        -
                        1 час 40 минут
                        -
                        Елена Алексеевская
                        Елена Алексеевская

                        Это в лекции 3.

                        Татьяна Дембелова
                        Татьяна Дембелова

                        Почему в вводной лекции курса Основы дискретной математики одним из свойств отношения частичного порядка упоминается антирефлексивность? Посмотрела в других источниках, там -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