Дискретные модели — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Лекции)
(Лекции)
Строка 7: Строка 7:
 
==Вопросы к экзамену==
 
==Вопросы к экзамену==
  
== Лекции ==
+
==Программа курса==
*'''Лекция 1''': Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число и рекуррентные формулы для них. Примеры. Свойства комбинаторных чисел. [[Media:dm-mag-lect1-selezn.pdf|Лекция 1]]
+
 
*'''Лекция 2''': Производящие функции, подсчет комбинаторных сумм и доказательство комбинаторных тождеств. Принцип включений-исключений. [[Media:dm-mag-lect2-selezn.pdf|Лекция 2]]
+
*'''Лекция 1''': Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число и рекуррентные формулы для них. Примеры. Свойства комбинаторных чисел.  
*'''Лекция 3''': Рекуррентные уравнения. Линейные однородные и неоднородные рекуррентные уравнения (ЛОРУ и ЛНРУ). Общие решения ЛОРУ и ЛНРУ. Примеры. [[Media:dm-mag-lect3-selezn.pdf|Лекция 3]]
+
*'''Лекция 2''': Функции алгебры логики. Замкнутый класс и полная система. Теорема Поста о функциональной полноте. Базис замкнутого класса. Теорема о максимальном числе функций алгебры логики. Предполный класс. Теорема о предполных классах алгебры логики. Результаты Э. Поста о замкнутых классах алгебры логики.
 +
*'''Лекция 3''': Функции k-значной логики. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах и полиномами по модулю k. Полная система. Теорема о полноте системы Поста и следствия из нее. Функция Вебба.
 +
*'''Лекция 4''': Алгоритм распознавания полноты конечных систем функций k-значной логики. Теоремы Янова и Мучника о существовании замкнутых классов многозначных логик без базиса и со счетным базисом. Особенности многозначных логик.
 +
*'''Лекция 5''': Графы. Деревья, остовные деревья. Алгоритм построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях графа. Теоремы об оценках числа висячих вершин в остовном дереве графа.
 +
*'''Лекция 6''': Графы. Раскраски графов. Хроматическое число графа. Критерий Кёнига двураскрашиваемости графа. Теоремы об оценках хроматического числа графа.
 +
*'''Лекция 7''': Графы. Наследственные свойства графов. Экстремальные графы. Теорема о максимальном числе ребер в графе без треугольников. Теорема Турана о максимальном числе ребер в графе без полного графа с n вершинами. Числа Рамсея и их оценки.
  
 
== Литература ==
 
== Литература ==

Версия 12:53, 16 февраля 2015

Программа обязательного курса для студентов магистратуры, 1-й курс, 2-й семестр.

Лектор - доцент Селезнева Светлана Николаевна.

Объявления

Вопросы к экзамену

Программа курса

  • Лекция 1: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число и рекуррентные формулы для них. Примеры. Свойства комбинаторных чисел.
  • Лекция 2: Функции алгебры логики. Замкнутый класс и полная система. Теорема Поста о функциональной полноте. Базис замкнутого класса. Теорема о максимальном числе функций алгебры логики. Предполный класс. Теорема о предполных классах алгебры логики. Результаты Э. Поста о замкнутых классах алгебры логики.
  • Лекция 3: Функции k-значной логики. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах и полиномами по модулю k. Полная система. Теорема о полноте системы Поста и следствия из нее. Функция Вебба.
  • Лекция 4: Алгоритм распознавания полноты конечных систем функций k-значной логики. Теоремы Янова и Мучника о существовании замкнутых классов многозначных логик без базиса и со счетным базисом. Особенности многозначных логик.
  • Лекция 5: Графы. Деревья, остовные деревья. Алгоритм построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях графа. Теоремы об оценках числа висячих вершин в остовном дереве графа.
  • Лекция 6: Графы. Раскраски графов. Хроматическое число графа. Критерий Кёнига двураскрашиваемости графа. Теоремы об оценках хроматического числа графа.
  • Лекция 7: Графы. Наследственные свойства графов. Экстремальные графы. Теорема о максимальном числе ребер в графе без треугольников. Теорема Турана о максимальном числе ребер в графе без полного графа с n вершинами. Числа Рамсея и их оценки.

Литература

  1. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
  2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
  3. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
  4. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.