Дискретная математика. Поток КН-2. 2017

Последнее изменение: 05/08/2020 10:30:51

Список вопросов к экзамену

Часть 1. Множества.

Лекция 1: Множества, соответствия, отображения.
Лекция 2: Бинарные отношения.
Лекция 3: Отношения порядка.
Лекция 4: Мощности множеств.
Лекция 5: Система аксиом Цермело-Френкеля.
Лекция 6: Ординалы.

Часть 2. Комбинаторика.

Лекция 1: Основные формулы.
Лекция 2: Биномиальные коэффициенты и числа Каталана
Лекция 3: Принцип включения-исключения.
Лекция 4: Рекуррентные соотношения.
Лекция 5: О-символика и формула Стирлинга.

Часть 3. Графы.

Лекция 1: Основные понятия.
Лекция 2: Мосты и точки сочленения. Эйлеровы и гамильтоновы циклы. Деревья.
Лекция 3: Двудольные графы.
Лекция 4: Планарные графы и раскраски.
Лекция 5: Ориентированные графы.

Часть 4. Булевы функции

Лекция 1: Нормальные формы.
Лекция 2: Замкнутые классы и теорема Поста.

Часть 5: Общая алгебра

Лекция 1: Полугруппы.

Список литературы

Теория множеств

  1. Важенин Ю.М. Множества, логика, алгоритмы
  2. Н.К.Верещагин, Н.Шень Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств
  3. Яблонский С.В. Введение в дискретную математику.
  4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров.
  5. Новиков Ф.А. Дискретная математика для программистов.
  6. Кнут Д. Искусство программирования
  7. И.В.Ященко Парадоксы теории множеств
  8. Н.Я.Виленкин Рассказы о множествах

Комбинаторика

  1. Виленкин Н.Я. Комбинаторика
  2. Виленкин Н.Я. Популярная комбинаторика
  3. Успенский В.А. Треугольник Паскаля
  4. Спивак А. Числа Каталана
  5. Левина А. Что такое комбинаторика
  6. Грэхем Р., Кнут Д., Паташник О. Конкретная математика

Графы

  1. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: Графы, матроиды, алгоритмы
  2. Замятин В.П. Графы и сети.
  3. Верников Б.М. Элементы теории графов.

Булевы функции

  1. Баранский В.А., Кабанов В.В. Общая алгебра и ее приложения: учеб. пособие
  2. Замятин В.П. Математическая логика.

Общая алгебра

  1. Баранский В.А., Кабанов В.В. Общая алгебра и ее приложения: учеб. пособие
  2. Фрид Э. Элементарное введение в абстрактную алгебру
  3. Лаллеман Ж. Полугруппы и комбинаторные приложения