Дискретные модели управляющих систем — различия между версиями
(→Вопросы к экзамену) |
|||
| Строка 9: | Строка 9: | ||
==Вопросы к экзамену== | ==Вопросы к экзамену== | ||
| − | # Размещения, перестановки, размещения с повторениями, сочетания, их число рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. | + | # Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. |
| − | + | ||
# Верхняя оценка биномиального коэффициента. Поведение последовательности биномиальных коэффициентов. Асимптотика суммы биномиальных коэффициентов. | # Верхняя оценка биномиального коэффициента. Поведение последовательности биномиальных коэффициентов. Асимптотика суммы биномиальных коэффициентов. | ||
| − | |||
# Графы и сети. Оценка числа деревьев с h ребрами. Оценка числа псевдографов с h ребрами. Оценка числа п-сетей с h ребрами. | # Графы и сети. Оценка числа деревьев с h ребрами. Оценка числа псевдографов с h ребрами. Оценка числа п-сетей с h ребрами. | ||
| − | |||
# Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского. | # Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского. | ||
| − | |||
# Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. | # Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. | ||
| − | |||
# Числа Рамсея. Оценки чисел Рамсея. | # Числа Рамсея. Оценки чисел Рамсея. | ||
| − | |||
# Полнота в k-значной логике. Теоремы о представимости функций k-значной логики в 1-й и во 2-й формах. Теорема о полноте системы Поста в k-значной логике. Теорема о полноте системы полиномов. | # Полнота в k-значной логике. Теоремы о представимости функций k-значной логики в 1-й и во 2-й формах. Теорема о полноте системы Поста в k-значной логике. Теорема о полноте системы полиномов. | ||
| − | |||
# Теорема о существовании алгоритма распознавания полноты в k-значной логике. | # Теорема о существовании алгоритма распознавания полноты в k-значной логике. | ||
| − | |||
# Существенные функции. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате. | # Существенные функции. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате. | ||
| − | |||
# Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. | # Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. | ||
| − | |||
# Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом. | # Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом. | ||
| − | |||
# Конечные автоматы-преобразователи. Отличимость состояний автомата. Теорема Мура о длине эксперимента, отличающего два отличимых состояния конечного автомата. Проблема полноты для конечных автоматов. | # Конечные автоматы-преобразователи. Отличимость состояний автомата. Теорема Мура о длине эксперимента, отличающего два отличимых состояния конечного автомата. Проблема полноты для конечных автоматов. | ||
| − | |||
# Проблема полноты для конечных автоматов. Операция суперпозиции. Теорема о несуществовании конечных полных систем в функциональной системе автоматных функций с операцией суперпозиции. | # Проблема полноты для конечных автоматов. Операция суперпозиции. Теорема о несуществовании конечных полных систем в функциональной системе автоматных функций с операцией суперпозиции. | ||
| − | |||
# Зависимость с запаздыванием. Операция обратной связи. Теорема о существовании конечных полных систем в функциональной системе автоматных функций с операциями суперпозиции и обратной связи. Несводимость операций суперпозиции и обратной связи друг к другу. | # Зависимость с запаздыванием. Операция обратной связи. Теорема о существовании конечных полных систем в функциональной системе автоматных функций с операциями суперпозиции и обратной связи. Несводимость операций суперпозиции и обратной связи друг к другу. | ||
| − | + | # Схемы из функциональных элементов (СФЭ). Метод Лупанова построения СФЭ в базисе из элементов конъюнкции, дизъюнкции и отрицания для функций алгебры логики. | |
| − | # Схемы из функциональных элементов (СФЭ). Метод Лупанова построения СФЭ в базисе из элементов конъюнкции, дизъюнкции и отрицания для функций алгебры логики. | + | |
==Лекции== | ==Лекции== | ||
Версия 18:44, 24 мая 2015
Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП
Курс читает доцент Селезнева Светлана Николаевна
Объявления
Экзамен по "Дискретным моделям управляющих систем"
Вопросы к экзамену
- Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
- Верхняя оценка биномиального коэффициента. Поведение последовательности биномиальных коэффициентов. Асимптотика суммы биномиальных коэффициентов.
- Графы и сети. Оценка числа деревьев с h ребрами. Оценка числа псевдографов с h ребрами. Оценка числа п-сетей с h ребрами.
- Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского.
- Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами.
- Числа Рамсея. Оценки чисел Рамсея.
- Полнота в k-значной логике. Теоремы о представимости функций k-значной логики в 1-й и во 2-й формах. Теорема о полноте системы Поста в k-значной логике. Теорема о полноте системы полиномов.
- Теорема о существовании алгоритма распознавания полноты в k-значной логике.
- Существенные функции. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате.
- Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений.
- Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом.
- Конечные автоматы-преобразователи. Отличимость состояний автомата. Теорема Мура о длине эксперимента, отличающего два отличимых состояния конечного автомата. Проблема полноты для конечных автоматов.
- Проблема полноты для конечных автоматов. Операция суперпозиции. Теорема о несуществовании конечных полных систем в функциональной системе автоматных функций с операцией суперпозиции.
- Зависимость с запаздыванием. Операция обратной связи. Теорема о существовании конечных полных систем в функциональной системе автоматных функций с операциями суперпозиции и обратной связи. Несводимость операций суперпозиции и обратной связи друг к другу.
- Схемы из функциональных элементов (СФЭ). Метод Лупанова построения СФЭ в базисе из элементов конъюнкции, дизъюнкции и отрицания для функций алгебры логики.
Лекции
Лекция 1. Основные комбинаторные числа. Оценки и асимптотики комбинаторных чисел.
Размещения, перестановки, размещения с повторениями, сочетания, их число рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. Оценки и асимптотики биномиальных коэффициентов. Оценки и асимптотики сумм биномиальных коэффициентов. [1] стр. 171-183, 213-214, [6]
Лекция 2. Графы и сети. Оценки графов и сетей различных типов. Планарные графы. Формула Эйлера для планарных графов. Теорема Понтрягина-Куратовского.
Графы и сети. Оценка числа деревьев с h ребрами. Оценка числа псевдографов с h ребрами. Оценка числа п-сетей с h ребрами. Планарные графы. Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского. [1] стр. 222-227, [2] стр. 33-37
Лекция 3. Экстремальная теория графов. Теорема Турана. Теорема Рамсея.
Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. Числа Рамсея. Оценки чисел Рамсея. [5] стр. 28-31
Лекция 4. Проблема полноты. Теорема о полноте систем функций двузначной логики. Алгоритм распознавания полноты систем функций k-значной логики.
Полные системы. Теорема Поста о полноте систем функций двузначной логики. Теорема о полноте системы Поста в k-значной логике. Теорема о существовании алгоритма распознавания полноты в k-значной логике. [1] стр. 43-53
Лекция 5. Теорема Слупецкого. Особенности k-значных логик.
Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. Теорема Слупецкого. Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом. [1] стр. 56-71.
Лекция 6. Эксперименты с автоматами. Алгоритмическая неразрешимость проблемы полноты для автоматов.
Конечные автоматы-преобразователи. Отличимость состояний автомата. Теорема Мура о длине эксперимента, отличающего два отличимых состояния конечного автомата. Проблема полноты для конечных автоматов. Теорема о существовании конечных полных систем автоматов. Теорема о несводимости операций суперпозиции и обратной связи друг к другу. Теорема об алгоритмической неразрешимости распознавания полноты систем автоматов. [2] стр. 83-86, [1] стр. 86-113
Лекция 7. Проблема минимизации ДНФ. Локальные алгоритмы. Построение ДНФ сумма тупиковых в классе локальных алгоритмов. Невозможность построения ДНФ сумма минимальных в классе локальных алгоритмов. [3] стр. 12-21
Лекция 8. Асимптотически наилучший метод синтеза СФЭ. Инвариантные классы и их свойства. Синтез СФЭ для функций из некоторых инвариантных классов. [4] стр. 65-69, , [3] стр. 5-10
Лекция 9. Нижние оценки сложности реализации функций алгебры логики π-схемами и формулами.
Лекция 10. Эквивалентные преобразования формул двузначной логики. Пример Линдона.
Лекция 11. Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.
Лекция 12. Конечные поля и их основные свойства. Коды Боуза-Чоудхури-Хоквингема.
Литература
- Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
- Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
- Сапоженко А.А. Некоторые вопросы сложности алгоритмов. М.: Издательский отдел ф-та ВМК МГУ им. М.В. Ломоносова, 2001.
- Нигматуллин Р.Г. Сложность булевых функций. Казань: Изд-во Казанского университета, 1983.
- Харари Ф. Теория графов. М.: Мир, 1973.
- Слайды к лекции 1
- Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
Вопросы к экзамену
(весенний семестр 2014/2015 учебного года, аспиранты 1 г/о кафедр ИО, МК, ММП, лектор — доцент С.Н. Селезнева)
