Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней
Это начальный курс по дискретным структурам. Лекции курса содержат все необходимые для изучения основного материала предварительные сведения о множествах, комбинаторике и методе математической индукции.
Рассмотрен самый простой и важный класс дискретных функций - булевы функции: их различные представления, связь с логикой высказываний, основные логические тождества ("законы логики"), дизъюнктивные и конъюнктивные нормальные формы и многочлены Жегалкина, полные системы функций (теорема Поста), задача выводимости для Хорновских формул. Даны краткое введение в логику предикатов и устанавливаются связи между ней и реляционными базами данных, введение в теорию графов, включающее представления графов, граф достижимости, компоненты сильной связности и базы ориентированного графа, деревья, их обходы, связь деревьев и формул (выражений), три классические задачи теории графов: построение минимального остова, обход графа в глубину (задачу о лабиринте) и задачу о кратчайших путях. Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Цель: Обучение студентов методам мышления, характерным для дискретной математики, основным понятиям таких ее дисциплин как комбинаторика, булевы функции, логика предикатов и графы. Еще одна цель - привить студентам навыки алгоритмического мышления на примерах решения задач из рассматриваемых разделов дискретной математики.
Необходимые знания: Изучение курса не требует предварительных знаний, выходящих за рамки школьной программы по математике.

План занятий

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