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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Лекции)
Строка 5: Строка 5:
 
==Объявления==
 
==Объявления==
  
==Вопросы к экзамену==
 
 
# Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
 
# Верхняя оценка биномиального коэффициента. Поведение последовательности биномиальных коэффициентов. Асимптотика суммы биномиальных коэффициентов.
 
# Графы и сети. Оценка числа псевдографов с q ребрами. Оценка числа деревьев с q ребрами. 
 
# Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского.
 
# Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами.
 
# Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.
 
# Полнота в k-значной логике. Теорема о представимости функций k-значной логики в 1-й форме.  Теорема о полноте системы Поста в k-значной логике.
 
# Теорема о представимости функций k-значной логики во 2-й форме. Теорема о полноте системы полиномов.
 
# Теорема о существовании алгоритма распознавания полноты в k-значной логике.
 
# Теорема Кузнецова о функциональной полноте.
 
# Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Критерии их совпадения с Pk.
 
# Существенные функции. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате.
 
# Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. Теорема Слупецкого.
 
# Шефферовы функции. Критерий шефферовости.
 
# Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом.
 
# Конечные автоматы-преобразователи. Отличимость состояний автомата. Теорема Мура о длине эксперимента, отличающего два отличимых состояния конечного автомата.
 
# Полнота для конечных автоматов. Операция суперпозиции. Теорема о несуществовании конечных полных систем в функциональной системе автоматных функций с операцией суперпозиции.
 
# Зависимость с запаздыванием. Операция обратной связи. Теорема о существовании конечных полных систем в функциональной системе автоматных функций с операциями суперпозиции и обратной связи. Несводимость операций суперпозиции и обратной связи друг к другу.
 
#Дизъюнктивные нормальные формы. Импликанта и простая ипликанта функции. Сокращенная ДНФ и способы ее построения.
 
#Тупиковые, минимальные и кратчайшие ДНФ, алгоритм построения всех тупиковых ДНФ.
 
#Ядровая импликанта и ядро функции, ДНФ Квайна. ДНФ "сумма тупиковых". Теорема Журавлева о критерии вхождения простой импликанты функции в ДНФ "сумма тупиковых".
 
#Локальные алгоритмы. Теорема Журавлева о невозможности построения ДНФ "сумма тупиковых" в классе локальных алгоритмов.
 
# Схемы из функциональных элементов (СФЭ). Метод Лупанова построения СФЭ в базисе из элементов конъюнкции, дизъюнкции и отрицания для функций алгебры логики.
 
  
 
==Лекции==
 
==Лекции==
Строка 86: Строка 61:
 
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
 
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
 
# Нигматуллин Р.Г. Сложность булевых функций. Казань: Изд-во Казанского университета, 1983.
 
# Нигматуллин Р.Г. Сложность булевых функций. Казань: Изд-во Казанского университета, 1983.
 +
 +
 +
==Вопросы к экзамену==
 +
 +
# Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
 +
# Верхняя оценка биномиального коэффициента. Поведение последовательности биномиальных коэффициентов. Асимптотика суммы биномиальных коэффициентов.
 +
# Графы и сети. Оценка числа псевдографов с q ребрами. Оценка числа деревьев с q ребрами. 
 +
# Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского.
 +
# Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами.
 +
# Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.
 +
# Полнота в k-значной логике. Теорема о представимости функций k-значной логики в 1-й форме.  Теорема о полноте системы Поста в k-значной логике.
 +
# Теорема о представимости функций k-значной логики во 2-й форме. Теорема о полноте системы полиномов.
 +
# Теорема о существовании алгоритма распознавания полноты в k-значной логике.
 +
# Теорема Кузнецова о функциональной полноте.
 +
# Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Критерии их совпадения с Pk.
 +
# Существенные функции. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате.
 +
# Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. Теорема Слупецкого.
 +
# Шефферовы функции. Критерий шефферовости.
 +
# Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом.
 +
# Конечные автоматы-преобразователи. Отличимость состояний автомата. Теорема Мура о длине эксперимента, отличающего два отличимых состояния конечного автомата.
 +
# Полнота для конечных автоматов. Операция суперпозиции. Теорема о несуществовании конечных полных систем в функциональной системе автоматных функций с операцией суперпозиции.
 +
# Зависимость с запаздыванием. Операция обратной связи. Теорема о существовании конечных полных систем в функциональной системе автоматных функций с операциями суперпозиции и обратной связи. Несводимость операций суперпозиции и обратной связи друг к другу.
 +
#Дизъюнктивные нормальные формы. Импликанта и простая ипликанта функции. Сокращенная ДНФ и способы ее построения.
 +
#Тупиковые, минимальные и кратчайшие ДНФ, алгоритм построения всех тупиковых ДНФ.
 +
#Ядровая импликанта и ядро функции, ДНФ Квайна. ДНФ "сумма тупиковых". Теорема Журавлева о критерии вхождения простой импликанты функции в ДНФ "сумма тупиковых".
 +
#Локальные алгоритмы. Теорема Журавлева о невозможности построения ДНФ "сумма тупиковых" в классе локальных алгоритмов.
 +
# Схемы из функциональных элементов (СФЭ). Метод Лупанова построения СФЭ в базисе из элементов конъюнкции, дизъюнкции и отрицания для функций алгебры логики.
  
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

Версия 17:25, 18 апреля 2017

Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП

Курс читает доцент Селезнева Светлана Николаевна

Объявления

Лекции

Лекция 1. Комбинаторика. Основные комбинаторные числа. Оценки и асимптотики комбинаторных чисел.

Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. Оценки и асимптотики биномиальных коэффициентов. Оценки и асимптотики сумм биномиальных коэффициентов. [1] стр. 171-183, 213-214, Слайды к лекции 1

Лекция 2. Графы. Граф и сеть. Оценки числа графов и сетей различных видов. Планарные графы. Формула Эйлера для планарных графов. Теорема Понтрягина-Куратовского.

Графы и сети. Оценка числа деревьев с q ребрами. Оценка числа псевдографов с q ребрами. Планарные графы. Формула Эйлера для планарных графов. Теорема о наибольшем числе ребер в планарном графе. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского. [1] стр. 222-227, 230-233, [2] стр. 26-38, [3] стр. 126-129, Слайды к лекции 2

Лекция 3. Графы. Экстремальная теория графов. Теорема Турана. Теорема Рамсея.

Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. Числа Рамсея. Оценки чисел Рамсея. [3] стр. 28-31, [4] стр. 301-302, 308-313, Слайды к лекции 3

Лекция 4. Многозначные логики. Способы представления k-значных функций. Полнота. Система Поста.

Функции k-значной логики. Способы представления k-значных функций: 1-я и 2-я формы, полиномы. Полные системы. Теорема о полноте системы Поста в k-значной логике. [1] стр. 43-50, 69-73, Слайды к лекции 4

Лекция 5. Многозначные логики. Алгоритм распознавания полноты конечных систем k-значных функций. Теорема Кузнецова о функциональной полноте.

Теорема о существовании алгоритма распознавания полноты в k-значной логике. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Теорема Кузнецова о функциональной полноте. [1] стр. 50-56, Слайды к лекции 5

Лекция 6. Многозначные логики. Теорема Яблонского. Теорема Слупецкого.

Существенные функции. Три леммы о существенных функциях. Теорема Яблонского. Теорема Слупецкого. [1] стр. 56-65, Слайды к лекции 6

Лекция 7. Многозначные логики. Особенности многозначных логик.

Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом. [1] стр. 67-69, Слайды к лекции 7

Лекция 8. Эксперименты с автоматами. Алгоритмическая неразрешимость проблемы полноты для автоматов.

Конечные автоматы-преобразователи. Отличимость состояний автомата. Теорема Мура о длине эксперимента, отличающего два отличимых состояния конечного автомата. Проблема полноты для конечных автоматов. Теорема о существовании конечных полных систем автоматов. Теорема о несводимости операций суперпозиции и обратной связи друг к другу. Теорема об алгоритмической неразрешимости распознавания полноты систем автоматов. [2] стр. 83-86, [1] стр. 86-113

Лекция 9. Проблема минимизации ДНФ. Локальные алгоритмы. Построение ДНФ сумма тупиковых в классе локальных алгоритмов. Невозможность построения ДНФ сумма минимальных в классе локальных алгоритмов. [3] стр. 12-21

Лекция 10. Асимптотически наилучший метод синтеза СФЭ. Инвариантные классы и их свойства. Синтез СФЭ для функций из некоторых инвариантных классов. [4] стр. 65-69, , [3] стр. 5-10

Лекция 11. Нижние оценки сложности реализации функций алгебры логики π-схемами и формулами.

Лекция 12. Эквивалентные преобразования формул двузначной логики. Пример Линдона.

Лекция 13. Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.

Лекция 14. Конечные поля и их основные свойства. Коды Боуза-Чоудхури-Хоквингема.

Литература

  1. Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
  2. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
  3. Харари Ф. Теория графов. М.: Мир, 1973.
  4. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
  5. Сапоженко А.А. Некоторые вопросы сложности алгоритмов. М.: Издательский отдел ф-та ВМК МГУ им. М.В. Ломоносова, 2001.
  6. Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
  7. Нигматуллин Р.Г. Сложность булевых функций. Казань: Изд-во Казанского университета, 1983.


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

  1. Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
  2. Верхняя оценка биномиального коэффициента. Поведение последовательности биномиальных коэффициентов. Асимптотика суммы биномиальных коэффициентов.
  3. Графы и сети. Оценка числа псевдографов с q ребрами. Оценка числа деревьев с q ребрами.
  4. Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского.
  5. Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами.
  6. Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.
  7. Полнота в k-значной логике. Теорема о представимости функций k-значной логики в 1-й форме. Теорема о полноте системы Поста в k-значной логике.
  8. Теорема о представимости функций k-значной логики во 2-й форме. Теорема о полноте системы полиномов.
  9. Теорема о существовании алгоритма распознавания полноты в k-значной логике.
  10. Теорема Кузнецова о функциональной полноте.
  11. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Критерии их совпадения с Pk.
  12. Существенные функции. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате.
  13. Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. Теорема Слупецкого.
  14. Шефферовы функции. Критерий шефферовости.
  15. Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом.
  16. Конечные автоматы-преобразователи. Отличимость состояний автомата. Теорема Мура о длине эксперимента, отличающего два отличимых состояния конечного автомата.
  17. Полнота для конечных автоматов. Операция суперпозиции. Теорема о несуществовании конечных полных систем в функциональной системе автоматных функций с операцией суперпозиции.
  18. Зависимость с запаздыванием. Операция обратной связи. Теорема о существовании конечных полных систем в функциональной системе автоматных функций с операциями суперпозиции и обратной связи. Несводимость операций суперпозиции и обратной связи друг к другу.
  19. Дизъюнктивные нормальные формы. Импликанта и простая ипликанта функции. Сокращенная ДНФ и способы ее построения.
  20. Тупиковые, минимальные и кратчайшие ДНФ, алгоритм построения всех тупиковых ДНФ.
  21. Ядровая импликанта и ядро функции, ДНФ Квайна. ДНФ "сумма тупиковых". Теорема Журавлева о критерии вхождения простой импликанты функции в ДНФ "сумма тупиковых".
  22. Локальные алгоритмы. Теорема Журавлева о невозможности построения ДНФ "сумма тупиковых" в классе локальных алгоритмов.
  23. Схемы из функциональных элементов (СФЭ). Метод Лупанова построения СФЭ в базисе из элементов конъюнкции, дизъюнкции и отрицания для функций алгебры логики.