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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Литература)
(Литература)
Строка 27: Строка 27:
 
#Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.
 
#Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.
 
#[[Media:dm-mag-lect1-selezn.pdf|Слайды к лекции 1]]
 
#[[Media:dm-mag-lect1-selezn.pdf|Слайды к лекции 1]]
#[[Media:dm-mag-lect5-selezn-new.pdf|Слайды к лекции 5]]
+
#[[Media:dm-mag-lect5-selezn.pdf|Слайды к лекции 5]]
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

Версия 19:49, 16 марта 2015

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

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

Объявления

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

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

  • Лекция 1: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число и рекуррентные формулы для них. Примеры. Свойства комбинаторных чисел. [1] стр. 171-183, [9]
  • Лекция 2: Функции алгебры логики. Замкнутый класс и полная система. Теорема Поста о функциональной полноте. Базис замкнутого класса. Теорема о максимальном числе функций алгебры логики. Предполный класс. Теорема о предполных классах алгебры логики. Результаты Э. Поста о замкнутых классах алгебры логики. [1] стр. 33-42, [2] стр. 9-23.
  • Лекция 3: Функции k-значной логики. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах и полиномами по модулю k. Полная система. Теорема о полноте системы Поста и следствия из нее. Функция Вебба. [1] стр. 43-50, 69-71, [2] стр. 24-25.
  • Лекция 4: Функции k-значной логики. Алгоритм распознавания полноты конечных систем функций k-значной логики. Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании замкнутых классов многозначных логик без базиса и со счетным базисом. Особенности многозначных логик. [1] стр. 50-53, стр. 65-69.
  • Лекция 5: Графы. Деревья, остовные деревья. Алгоритм построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях графа. Теоремы об оценках числа висячих вершин в остовном дереве графа. [3] стр. 77-80, [4] стр. 48-50, [10]
  • Лекция 6: Графы. Раскраски графов. Хроматическое число графа. Критерий Кёнига двураскрашиваемости графа. Теоремы об оценках хроматического числа графа. [3] стр. 284-285, [4] стр. 152-153, [8].
  • Лекция 7: Графы. Наследственные свойства графов. Экстремальные графы. Теорема о максимальном числе ребер в графе без треугольников. Теорема Турана о максимальном числе ребер в графе без полного графа с n вершинами. Числа Рамсея и их оценки. [3] стр. 270-276, [4] стр. 28-33.

Литература

  1. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
  2. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
  3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
  4. Оре О. Теория графов. М.: Наука, 1980.
  5. Харари Ф. Теория графов. М.: Мир, 1973.
  6. Kleitman D.J., West D.B.
  7. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
  8. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.
  9. Слайды к лекции 1
  10. Слайды к лекции 5