Дискретная математика



Аннотация

Цель курса — ознакомить студентов с важнейшими разделами дискретной математики и ее применением в математической кибернетике. В процессе обучения прививаются навыки свободного обращения с такими дискретными объектами, как функции алгебры логики, автоматные функции, графы, и вырабатывается представление о проблематике теории кодирования, синтезы упрарляющих систем. Во всех разделах дисциплины большое внимание удаляетсяпостроению алгоритмов для решения задач дискретной математики. Это способствует более глубокому пониманию проблематики теории алгоритмов, ее возможностей и трудностей, помогает строить алгоритмы для решения дискретных задач.

Содержание курса


Введение. Место дискретной математики в системе математического образования. Дискретная математика, математическая кибернетика и компьютерные науки. Соотношение между дискретным и непрерывным подходами к изучению различных явлений.
Логические функции. Алгебра логики. Функции алгебры логики. Реализация функций формулами, эквивалентность формул. Свойства элементарных функций. Принцип двойственности. Разложение функций алгебры логики по переменным. Совершенная дизъюнктивная и конъюнктивная нормальные формы. Полнота и замкнутость, примеры полных систем. Полиномы Жегалкина. Важнейшие замкнутые классы, теорема о полноте. Представление о результатах Поста. Функции к-значной логики и их представление. Существование конечной полной системы во множестве к-значных функций.
Элементы теории графов. Основные понятия теории графов. Типы и способы задания графов. Изоморфизм, связность. Деревья и их свойства. Планарность. Формула Эйлера. Критерий планарности. Теорема о раскраске планарных графов в 5 цветов.
Схемы из функциональных элементов. Реализация функций алгебры логики схемами из функциональных элементов. Двоичный сумматор, вычитатель, умножитель, оценки их сложности. Дешифратор, шифратор, мультиплексор, оценки их сложности. Метод Шеннона для реализации функций алгебры логики схемами из функциональных элементов. Порядок функции Шеннона.
Коды. Проблематика теории кодирования. Алфавитное кодирование. Критерий однозначности декодирования. Неравенство Макмиллана. Существование префиксного кода с заданными длинами кодовых слов. Оптимальные коды, их свойства. Теорема редукции. Помехоустойчивое кодирование. Линейные коды. Коды Хемминга. Коды с исправлением ошибок.
Элементы теории автоматов. Понятие ограниченно-детерминированной функции. Автоматы и автоматные отображения. Представление автоматов диаграммами переходов, каноническими уравнениями, схемами. Теоремы об экспериментах с автоматами.
Вычислимость и неразрешимость. Машины Тьюринга. Вычислимые функции. Примеры вычислимых функций. Неразрешимые проблемы. Примеры неразрешимых проблем.

Литература


  • Яблонский С.В. Введение в дискретную математику: Учеб. пособие. М.: Наука.1986.

  • Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики: Учеб. пособие. М.: Наука. 1992. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов: Учеб. пособие по курсам «Дискретная математика» и «Основы кибернетики». М.: Изд. отдел ф-та ВМиК МГУ. 2000.

  • Алексеев В. Б., Ложкин С.А. Элементы теории графов, схемы и автоматы: Учеб. пособие по курсам «Дискретная математика» и «Основы кибернетики». М.: Изд.отдел ф-та ВМиК МГУ. 2000.



Дополнительная литература

  • Дискретнаяматематика и математические вопросы кибернетики / Под ред. С.В.Яблонского, О.Б.Лупанова. Т.1. М.: Наука. 1974.